Teilmengen unendlicher rekursiver Mengen

11

Eine aktuelle Prüfungsfrage lautete wie folgt:

  1. ist eine unendliche rekursiv aufzählbare Menge. Beweisen Sie, dass A eine unendliche rekursive Teilmenge hat.AA
  2. Lassen eine unendliche rekursive Untergruppe von seiner A . Muss C eine Teilmenge haben, die nicht rekursiv aufzählbar ist?CAC

Ich habe schon 1. geantwortet. In Bezug auf 2. antwortete ich bejahend und argumentierte wie folgt.

Angenommen, alle Teilmengen von wären rekursiv aufzählbar. Da C unendlich ist, ist die Potenzmenge von C unzählbar, so dass unter der Annahme unzählige rekursiv aufzählbare Mengen vorhanden wären. Die rekursiv aufzählbaren Mengen stehen jedoch in Eins-zu-Eins-Entsprechung mit den Turing-Maschinen, die sie erkennen, und Turing-Maschinen sind aufzählbar. Widerspruch. So C muss eine Teilmenge hat , die nicht rekursiv durchlaufen werden kann.CCCC

Ist das richtig?

computability check-my-proof user1435
quelle
2
Es ist am Ende nicht ganz richtig, weil jeder Satz von unendlich vielen Turing-Maschinen aufgezählt wird, nicht nur von einer. Sie können dies jedoch umgehen.
Carl Mummert
@ Carl: Ah, richtig, danke - dummer Fehler. Aber alles was ich brauche ist eine Injektion in die TMs, keine Bijektion, oder? Und bei der Definition von Turing-berechenbar, mit der meine Klasse gearbeitet hat, ist jedes TM einer und nur einer Funktion zugeordnet. Also verschiedene Mengen -> verschiedene Erkennungsfunktionen -> verschiedene TMs, die sie berechnen.
user1435
1
! user1435: Sie kehren die Dinge im letzten Satz um. Jede Turingmaschine berechnet eine einzelne Funktion, aber jede berechenbare Funktion wird von unendlich vielen Turingmaschinen erhalten.
Carl Mummert
Aber wenn meine Funktion f {Erkennungsfunktionen r} über f (r) = eine der unendlich vielen TMs, die sie berechnen, auf {TMs} abbildet, habe ich eine Injektion, oder? Oder ich nehme an, ich könnte {TMs} einfach durch eine Äquivalenzbeziehung ~ partitionieren, die die Unendlichkeit von TMs identifiziert, die dieselbe Funktion berechnen, und dann r der entsprechenden Äquivalenzklasse zuordnen.
user1435
Carl hat recht, sie stehen nicht in einer Eins-zu-Eins-Korrespondenz, jeder ce-Satz entspricht unendlich vielen TMs. Wenn Sie andere Objektgruppen berücksichtigen, wie Sie es in Ihrem Kommentar tun, ändert sich nichts, es handelt sich nicht um die Gruppe von TMs.
Kaveh

Antworten:

11

Es ist richtig.

Jede unendliche Menge hat eine unentscheidbare Teilmenge. Sie können das Kardinalitätsargument verwenden: ℵ0≤C⟹ℵ0<2C

C

D={i∈C∣i∉Wi}WiiD⊆CDCK={i∣i∉Wi}CD

Kaveh
quelle
"Jede unendliche Menge hat eine unentscheidbare Teilmenge." Dies ist schwächer als die Behauptung, die ich zu beweisen versuchte. Ich habe versucht zu beweisen, dass C eine Nicht-RE-Teilmenge haben muss, keine nicht entscheidbare Teilmenge. Ist meine Behauptung noch richtig?
user1435
Ja. Der Begriff "unentscheidbar" ist etwas überladen (Wikipedia hat eine gute Diskussion ). Diese Antwort bedeutet also wahrscheinlich, was Sie zu beweisen versuchen.
David Lewis
@ user1435, ja, das gleiche Argument funktioniert für jede zählbare Klasse von Sprachen. Ich habe die Frage aktualisiert, um es klar zu machen.
Kaveh