Specker-Folge

Datei:SuiteSpecker.svg

Eine Specker-Folge. Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -te Ziffer von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{n+k}} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4,} wenn die Berechnung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left\{n\right\}(n)} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Schritten anhält; sonst Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3.}

In der Berechenbarkeitstheorie ist die Specker-Folge eine berechenbare, monoton wachsende, beschränkte Folge von rationalen Zahlen, deren Supremum keine berechenbare reelle Zahl ist. Das erste Beispiel einer solchen Folge wurde 1949 von Ernst Specker konstruiert.

Die Existenz von Specker-Folgen hat Konsequenzen für die berechenbare Analysis. Die Tatsache, dass es solche Folgen gibt, bedeutet, dass die Klasse der berechenbaren reellen Zahlen nicht die aus der reellen Analysis bekannte Supremumseigenschaft aufweist, selbst dann, wenn man sich dabei auf berechenbare Folgen beschränkt. Ein üblicher Weg, dieses Problem zu lösen, ist, nur berechenbare Folgen versehen mit einem berechenbaren Konvergenzmodul zu betrachten. Keine Specker-Folge hat einen berechenbaren Konvergenzmodul, das bedeutet: Jeder Konvergenzmodul einer Specker-Folge wächst schneller als jede berechenbare Funktion, sonst ließe sich auf berechenbare Weise abschätzen, nach wie vielen Folgengliedern die ersten $n$ Stellen feststehen, und damit wäre das Supremum eine berechenbare reelle Zahl.

Die Supremumseigenschaft wurde auch im Bereich der reversen Mathematik untersucht, wo ihre genaue Stärke bestimmt wurde. In der Sprache der Disziplin ausgedrückt ist die Supremumseigenschaft äquivalent zu ACA₀ über RCA₀.

Verletzung der Supremumseigenschaft

Da jede rationale Zahl berechenbar ist und die Vervollständigung der rationalen Zahlen bekanntlich genau die Menge der reellen Zahlen ist, die berechenbaren reellen Zahlen als abzählbare Menge aber eine echte Teilmenge der reellen Zahlen bilden, können die berechenbaren reellen Zahlen nicht vollständig sein. Da besagte Supremumseigenschaft in metrischen, separablen, geordneten Räumen und somit jedem Unterraum der reellen Zahlen äquivalent zur Ordnungsvollständigkeit und somit zur Vollständigkeit ist, können die berechenbaren reellen Zahlen nicht die Supremumseigenschaft erfüllen. Naheliegend wäre nun, sich auf berechenbare Folgen berechenbarer Zahlen zu beschränken.

Konstruktion

Die Existenz einer Specker-Folge besagt darüber hinaus, dass die Supremumseigenschaft bereits verletzt ist, wenn man sich auf berechenbare Folgen beschränkt. Die folgende Konstruktion wurde von Kushner beschrieben. Sei $A$ eine rekursiv aufzählbare, aber nicht entscheidbare Menge natürlicher Zahlen, und sei ($a_{i}$) eine berechenbare Aufzählung von $A$ ohne Wiederholung. Eine Folge $\left(q_{n}\right)$ von rationalen Zahlen sei durch

$q_{n}:=\sum _{i=0}^{n}2^{-a_{i}-1}$

definiert. Offensichtlich ist jedes $q_{n}$ nichtnegativ und rational, und die Folge $\left(q_{n}\right)$ wächst monoton. Außerdem ist es möglich, jedes $q_{n}$ durch die Reihe

$\sum _{i=0}^{\infty }2^{-i-1}=1$

nach oben abzuschätzen, da $(a_{i})$ keine Wiederholung enthält. Daher ist die Folge $\left(q_{n}\right)$ durch $1$ beschränkt. Klassischerweise bedeutet dies, dass $(q_{n})$ ein Supremum $x$ besitzt.

Es wurde gezeigt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} keine berechenbare reelle Zahl ist. Der Beweis verwendet ein bestimmte Eigenschaft berechenbarer reeller Zahlen: Wäre Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} berechenbar, dann gäbe es eine berechenbare Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(n)} so, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left|q_j-q_i\right|<\tfrac{1}{n}} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i,j>r(n)} . Um Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} zu berechnen, vergleiche man die Binärexpansion von $x$ mit der Binärexpansion von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_i} für immer größere Werte von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} . Die Definition von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_i} führt dazu, dass jedes Mal, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} um Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} größer wird, eine binäre Ziffer von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} zu $1$ wechselt. Also gibt es ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} so, dass ein hinreichend großes Anfangsstück von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_n} dergestalt festgelegt ist, dass keine weitere Binärziffer in diesem Stück auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} wechseln kann, was zu einer Abschätzung der Distanz zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_j} für $i,j>n$ führt.

Wenn irgendeine solche Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} berechenbar wäre, würde dies auf folgende Weise zu einem Entscheidungsverfahren für $A$ führen. Zu einer Eingabe $k$ berechne man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(2^{k+1})} . Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} in der Folge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(a_i\right)} vorkäme, würde dies eine Erhöhung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_i} um Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{-k-1}} verursachen. Das kann aber nicht passieren, sobald alle Elemente von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(q_i\right)} nicht weiter als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{-k-1}} voneinander entfernt sind. Wenn also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} in einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i} aufgezählt wird, muss es um den Wert von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} kleiner sein als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(2^{k+1})} . Es bleibt eine endliche Zahl von möglichen Orten, wo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} aufgezählt werden könnte. Um das Entscheidungsverfahren zu vervollständigen, prüfe man diese endlich vielen Stellen in berechenbarer Weise und gebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} aus, je nachdem, ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} gefunden wird oder nicht.

Literatur

• Douglas Bridges, Fred Richman: Varieties of Constructive Mathematics. Oxford 1987.
• Jakob G. Simonsen: Specker sequences revisited. In: Mathematical Logic Quarterly. 2005, Band 51, S. 532–540. doi:10.1002/malq.200410048
• S. Simpson: Subsystems of second-order arithmetic. Springer, 1999.
• E. Specker: Nicht konstruktiv beweisbare Sätze der Analysis. In: Journal of Symbolic Logic. 1949, Band 14, S. 145–158.