Einfache und immune Mengen

(Weitergeleitet von Einfache Menge)

Einfache und immune Mengen sind Klassen von Teilmengen der natürlichen Zahlen und liefern wichtige Gegenbeispiele in der Berechenbarkeitstheorie. Sie sind eng mit dem Begriff der rekursiven Aufzählbarkeit (RE) verbunden: Während immune Mengen genau die abzählbar unendlichen Mengen natürlicher Zahlen sind, die keine unendliche rekursiv aufzählbare Teilmenge besitzen, sind die einfachen Mengen die rekursiv aufzählbaren Komplemente immuner Mengen. Die Definitionen lassen sich weiter verstärken und führen so auf den Begriff der hyper- oder gar hyperhypereinfachen Mengen.

Emil Post vermutete bereits in den 1940er-Jahren die Existenz einfacher Mengen, doch erst 1956 bzw. 1957 konnte dies (unabhängig voneinander) von Richard Friedberg und Albert Muchnik auch bewiesen werden.

Definition

Bearbeiten

Es sei   eine effektive Nummerierung aller rekursiv aufzählbarer Mengen.

Eine Menge   natürlicher Zahlen heiße immun, falls gilt  .

(d. h.   ist abzählbar unendlich, besitzt aber keine unendliche rekursiv aufzählbare Teilmenge). Hier bezeichne   die Kardinalität einer Menge.

Eine Menge   heiße nun einfach, falls sie selbst rekursiv aufzählbar und ihr Komplement   immun ist.

Geschichte

Bearbeiten

Als Post 1944 begann, Probleme nach ihrer Entscheidbarkeit zu vergleichen[1], stellte sich schnell die Frage, ob jede rekursiv aufzählbare Menge, die nicht mehr entscheidbar ist, automatisch schon vollständig für die aufzählbaren Mengen ist. Nun besitzen Komplemente RE-vollständiger Mengen (genauer alle produktiven Mengen) eine unendliche aufzählbare Teilmenge. Das heißt, die Existenz von einfachen Mengen ist bereits hinreichend für die negative Beantwortung der obigen Frage. Post selbst vermutete diese Existenz, konnte sie allerdings noch nicht beweisen. Erst als Friedberg[2] und Muchnik[3] 1956/57 das (allgemeinere) Postsche Problem lösten, konstruierten sie en passant die erste einfache Menge. Dies war außerdem der erste Beweis in der Geschichte der Berechenbarkeitstheorie, der mit Hilfe der Prioritätsmethode geführt wurde. Heute sind dagegen deutlich simplere Konstruktionen einfacher Mengen bekannt.

Beispiel

Bearbeiten

Nach Voraussetzung gibt es eine Turing-Maschine   (oder einen Algorithmus in einem alternativen Berechenbarkeitsmodell), die bei Eingabe   die Menge   aufzählt. Sei nun   diejenige partielle Zahlfunktion, bei der   stets das erste von   gefundene Element   ist, für das   gilt, falls ein solches existiert. Dann ist offenbar   (partiell) berechenbar und ihr Wertebereich   ist einfach.

Analog lassen sich so auch weitere einfache Mengen konstruieren.[4]

Eigenschaften

Bearbeiten
  • Immune Mengen sind nicht rekursiv aufzählbar, andernfalls würden sie ja sich selbst als unendliche aufzählbare Teilmenge enthalten.
  • Eine unendliche Menge ist genau dann immun, wenn sie keine unendliche entscheidbare Teilmenge enthält.
  • Einfache Mengen sind daher nicht entscheidbar.
  • Immune Mengen sind per Konstruktion nicht produktiv und einfache Mengen daher auch nicht kreativ.
  • Nach dem Satz von Myhill sind einfache Mengen also nicht RE-vollständig.
  • Es gibt ein Paar   einfacher Mengen, das die natürlichen Zahlen ausschöpft  .[5]

Hypereinfache und hyperimmune Mengen

Bearbeiten

Man sagt, eine geordnete Menge   natürlicher Zahlen werde durch eine Zahlenfunktion   majorisiert, falls   gilt, der Funktionswert   also stets mindestens so groß ist wie der  -kleinste Wert von  .

Eine Menge   heiße hyperimmun (h.i.), falls sie von keiner total berechenbaren Funktion   majorisiert wird.
Eine Menge   heiße dann hypereinfach (h.s.; von engl. hypersimple), falls sie rekursiv aufzählbar und ihr Komplement h.i. ist.
  • Hypereinfache Mengen sind notwendig unendlich.
  • Hyperimmune Mengen sind stets immun und hypereinfache Mengen daher immer auch einfach.
  • Es gibt einfache Mengen, die nicht hypereinfach sind.[6]
  • Der Schnitt zweier hypereinfacher Mengen ist wieder hypereinfach.
  • Die Vereinigung einer hyperimmunen mit einer immunen Menge ist wieder hyperimmun.

Hyperhypereinfache und hyperhyperimmune Mengen

Bearbeiten

Es gibt eine Charakterisierung von h.i. Mengen, die gelegentlich auch als alternative Definition verwendet wird:

Es sei dafür   eine effektive Nummerierung aller endlichen Teilmengen von   (bspw.   für  ).

Eine unendliche Menge   ist nun genau dann hyperimmun, wenn es keine total berechenbare Funktion   gibt, so dass   gilt.

Mit anderen Worten ist eine unendliche Menge   also h.i., wenn es keine – in kanonischen Indizes – berechenbare Liste von paarweise disjunkten endlichen Mengen gibt, die alle   schneiden.

Wenn man nun von den kanonischen  -Indizes zu den oben eingeführten allgemeineren  -Indizes übergeht, ergibt sich die Definition von hyperhyperimmunen Mengen. Es stellte sich heraus, dass diese sogar echt stärker ist.

Eine unendliche Menge   heiße hyperhyperimmun (h.h.i.), falls es keine total berechenbare Funktion   gibt, so dass für jedes   die Menge   endlich ist und   gilt.

Eine Menge ist h.h.i. falls sie unendlich ist und es keine – in  -Indizes – berechenbare Liste von paarweise disjunkten endlichen Mengen gibt, die diese Menge alle schneiden.

Eine Menge Menge   heiße dann hyperhypereinfach (h.h.s.), falls sie rekursiv aufzählbar und ihr Komplement h.h.i. ist.
  • Hyperhyperimmune Mengen sind stets hyperimmun, da sich  -Indizes berechenbar in  -Indizes umwandeln lassen.
  • Es gibt hyperimmune Mengen, die nicht hyperhyperimmun sind.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. E. Post: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, Ausg. 50 (1944), No. 5, S. 284–316 (online, PDF-Datei; 4,0 MB).
  2. R. Friedberg: Two recursively enumerable sets of incomparable degree of unsolvability (solution of Post's problem 1944). In: Proceedings of the National Academy of Sciences. Band 43, S. 236–238 (pnas.org [PDF]).
  3. A. Muchnik: Über die Unlösbarkeit des Problems der Reduzierbarkeit in der Theorie der Algorithmen. (russisch). In: Doklady Akademii Nauk SSSR (N.S.). Band 108, 1956, S. 194–197.
  4. Setze   mit   analog zu  , allerdings mit  .
  5. Setze dazu   und  , mit   aus dem obigen Beispiel.
  6. Nehme dazu die Menge   aus dem obigen Beispiel, sie ist einfach, aber ihr Komplement wird durch   majorisiert.