Direkt zum Inhalt

Lexikon der Mathematik: rekursiv aufzählbar

Eigenschaft einer Teilmenge der natürlichen Zahlen, weitestgehend synonym zum Begriff „aufzählbar“.

Eine Menge \(A\subseteq {{\mathbb{N}}}_{0}\) ist rekursiv aufzählbar, falls \(A=\varnothing \) oder falls es eine total berechenbare Funktion \(f:{{\mathbb{N}}}_{0}\to {{\mathbb{N}}}_{0}\) gibt, so daß A die Wertemenge von f ist, also \begin{eqnarray}A=\{f(0),f(1),f(2),\ldots\}.\end{eqnarray} Man sagt dann, f zählt die Menge A auf.

Der Begriff „rekursiv aufzählbar“ unterscheidet sich von „abzählbar“ dadurch, daß die Berechenbarkeit der Funktion f verlangt wird. Insbesondere braucht eine Teilmenge einer rekursiv aufzählbaren Menge nicht notwendig selbst rekursiv aufzählbar zu sein.

Es gilt der Satz, daß eine Menge genau dann rekursiv aufzählbar ist, wenn sie semi-entscheidbar ist. Hieraus ergibt sich weiterhin, daß eine Menge genau dann entscheidbar ist (Entscheidbarkeit), wenn die Menge und ihre Komplementmenge rekursiv aufzählbar sind.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos