Ist der Schnittpunkt unendlich vieler rekursiver Mengen rekursiv?

Ist der Schnittpunkt von unendlich vielen rekursiven Mengen $\bigcap_{i}U_{i}$(wo jeder Satz anders ist) rekursiv? Rekursiv aufzählbar? Ich weiß, dass die Vereinigung nicht rekursiv sein muss, weil sie entscheidet, ob ein Element in der Menge enthalten ist$U_i$ ist dasselbe wie die Entscheidung über das Halteproblem, da Sie für jedes Element entscheiden müssen, ob die Funktion, die if berechnet $x \in U_i$ für einige $i$ wird beendet.

Da Sie bereits über Gewerkschaften Bescheid wissen, können Sie dies herausfinden, indem Sie sich an die Gesetze von de Morgan erinnern: Das Komplement einer Gewerkschaft ist das Komplement der Überschneidung von Komplementen. In diesem Sinne: lassen$U_i$sei die Menge von (Indizes von) Turing-Maschinen, die nicht innerhalb anhalten$i$Ausführungsschritte. Also die Ergänzung$\mathbb{N} \setminus U_i$ ist die Menge von (Indizes) jener Maschinen, die innerhalb der ersten anhalten $i$ Schritte.

Jetzt haben wir:

Übrigens geben Sie an, dass "Sie entscheiden, ob sich ein Element in der Menge befindet $U_i$ ist das gleiche wie die Entscheidung über das Halteproblem ... ", was nicht unbedingt wahr ist. Zum Beispiel, wenn ich setze $U_i = \{42\}$ für alle $i$, dann alle $U_i$sind entscheidbar. Sie müssen darauf achten, was Ihre$U_i$sind.

Für jedes $i\in \mathbb{N}$, nehmen $S_i = \mathbb{N}\setminus \{i\}$. Sie können jetzt jedes gewünschte Set als erstellen$X = \bigcap_{i\notin X}S_i$.

Ebenso ist es einfacher zu lassen, dass eine Vereinigung rekursiver Mengen überhaupt etwas sein kann $T_i=\{i\}$ und jetzt ein beliebiger Satz $X$ ist $X = \bigcup_{i\in X}T_i$.