Arithmetische Hierarchie Die ist ein Konzept der mathematischen Logik Sie klassifiziert Mengen von natürlichen Zahlen di

Arithmetische Hierarchie

Die Arithmetische Hierarchie ist ein Konzept der mathematischen Logik. Sie klassifiziert Mengen von natürlichen Zahlen, die in der Sprache der Peano-Arithmetik definierbar sind, nach der Komplexität ihrer Definitionen. Die arithmetisch definierbaren Mengen werden auch als arithmetisch bezeichnet. Die arithmetische Hierarchie spielt eine wichtige Rolle in der Berechenbarkeitstheorie. Die hyperarithmetische Hierarchie und die analytische Hierarchie erweitern die arithmetische Hierarchie nach oben.

Definition Bearbeiten

Klassifikation von Formeln Bearbeiten

Die arithmetische Hierarchie klassifiziert Formeln in der Sprache der Peano-Arithmetik in Klassen namens , und für natürliche Zahlen n.

Die niedrigste Stufe bilden Formeln, die eine entscheidbare Relation definieren. Diese bilden die Klasse . Die weiteren Klassen werden für jede Zahl n induktiv wie folgt definiert:

Wenn äquivalent zu einer Formel ist, wobei in liegt, dann liegt in .
Wenn äquivalent zu einer Formel ist, wobei in liegt, dann liegt in .
(für alle n)

Jede arithmetische Formel ist äquivalent zu einer Formel in Pränexnormalform, die abwechselnd einen All- und einen Existenzquantor hat. Bei einer -Formel steht zuerst ein Existenzquantor; bei einer -Formel ein Allquantor. Jede -Formel ist äquivalent zur Negation einer -Formel.

Da zu jeder Formel redundante Quantoren, die keine vorkommende Variable binden, hinzugefügt werden können, liegen alle Formeln in oder auch in und für alle m > n.

Alternativ kann die niedrigste Klasse so definiert werden, dass sie nur Formeln enthält, die zu einer Formel äquivalent sind, die nur beschränkte Quantoren hat. In diesem Fall enthält die niedrigste Klasse weniger Relationen; alle weiteren Klassen bleiben gleich.

Klassifikation von Mengen und Relationen Bearbeiten

Eine Menge X von natürlichen Zahlen wird durch eine Formel in der Sprache der Peano-Arithmetik definiert, wenn X genau die Zahlen enthält, die erfüllen, d. h.:

wobei der Term in der Sprache der Arithmetik ist, der die Zahl repräsentiert. Eine Menge heißt arithmetisch, wenn sie durch eine Formel der Peano-Arithmetik definiert wird. Eine Menge X von natürlichen Zahlen ist , , oder , wenn sie durch eine Formel in der entsprechenden Klasse definiert wird. Ebenso lassen sich auch Relationen bzw. Mengen von k-Tupeln natürlicher Zahlen klassifizieren, wenn man Formeln mit k freien Variablen betrachtet.

Bezug zu Berechenbarkeit Bearbeiten

Die entscheidbaren Mengen sind genau die -Mengen. Die rekursiv aufzählbaren Mengen sind die -Mengen. Auch darüber hinaus gibt es eine enge Beziehung zwischen der arithmetischen Hierarchie und den Turinggraden. Nach dem Satz von Post gilt für alle :

(der -te Turing-Jump der leeren Menge) ist many-one vollständig für .
Die Mengen in sind genau die Mengen, die rekursiv aufzählbar in sind.
ist vollständig unter Turing-Reduktion für .

Literatur Bearbeiten

Hartley Rogers: Theory of recursive functions and effective computability. McGraw-Hill, 1967.

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele

Veröffentlichungsdatum: Dezember 02, 2023, 22:02 pm

Die Arithmetische Hierarchie ist ein Konzept der mathematischen Logik Sie klassifiziert Mengen von naturlichen Zahlen die in der Sprache der Peano Arithmetik definierbar sind nach der Komplexitat ihrer Definitionen Die arithmetisch definierbaren Mengen werden auch als arithmetisch bezeichnet Die arithmetische Hierarchie spielt eine wichtige Rolle in der Berechenbarkeitstheorie Die hyperarithmetische Hierarchie und die analytische Hierarchie erweitern die arithmetische Hierarchie nach oben Inhaltsverzeichnis 1 Definition 1 1 Klassifikation von Formeln 1 2 Klassifikation von Mengen und Relationen 2 Bezug zu Berechenbarkeit 3 LiteraturDefinition BearbeitenKlassifikation von Formeln Bearbeiten Die arithmetische Hierarchie klassifiziert Formeln in der Sprache der Peano Arithmetik in Klassen namens S n 0 displaystyle Sigma n 0 nbsp P n 0 displaystyle Pi n 0 nbsp und D n 0 displaystyle Delta n 0 nbsp fur naturliche Zahlen n Die niedrigste Stufe bilden Formeln die eine entscheidbare Relation definieren Diese bilden die Klasse D 0 0 P 0 0 S 0 0 displaystyle Delta 0 0 Pi 0 0 Sigma 0 0 nbsp Die weiteren Klassen werden fur jede Zahl n induktiv wie folgt definiert Wenn f displaystyle varphi nbsp aquivalent zu einer Formel x 1 x 2 x k ps displaystyle exists x 1 exists x 2 cdots exists x k psi nbsp ist wobei ps displaystyle psi nbsp in P n 0 displaystyle Pi n 0 nbsp liegt dann liegt f displaystyle varphi nbsp in S n 1 0 displaystyle Sigma n 1 0 nbsp Wenn f displaystyle varphi nbsp aquivalent zu einer Formel x 1 x 2 x k ps displaystyle forall x 1 forall x 2 cdots forall x k psi nbsp ist wobei ps displaystyle psi nbsp in S n 0 displaystyle Sigma n 0 nbsp liegt dann liegt f displaystyle varphi nbsp in P n 1 0 displaystyle Pi n 1 0 nbsp D n 0 S n 0 P n 0 displaystyle Delta n 0 Sigma n 0 cap Pi n 0 nbsp fur alle n Jede arithmetische Formel ist aquivalent zu einer Formel in Pranexnormalform die abwechselnd einen All und einen Existenzquantor hat Bei einer S n 0 displaystyle Sigma n 0 nbsp Formel steht zuerst ein Existenzquantor bei einer P n 0 displaystyle Pi n 0 nbsp Formel ein Allquantor Jede P n 0 displaystyle Pi n 0 nbsp Formel ist aquivalent zur Negation einer S n 0 displaystyle Sigma n 0 nbsp Formel Da zu jeder Formel redundante Quantoren die keine vorkommende Variable binden hinzugefugt werden konnen liegen alle Formeln in S n 0 displaystyle Sigma n 0 nbsp oder P n 0 displaystyle Pi n 0 nbsp auch in S m 0 displaystyle Sigma m 0 nbsp und P m 0 displaystyle Pi m 0 nbsp fur alle m gt n Alternativ kann die niedrigste Klasse D 0 0 P 0 0 S 0 0 displaystyle Delta 0 0 Pi 0 0 Sigma 0 0 nbsp so definiert werden dass sie nur Formeln enthalt die zu einer Formel aquivalent sind die nur beschrankte Quantoren hat In diesem Fall enthalt die niedrigste Klasse weniger Relationen alle weiteren Klassen bleiben gleich Klassifikation von Mengen und Relationen Bearbeiten Eine Menge X von naturlichen Zahlen wird durch eine Formel f x displaystyle varphi x nbsp in der Sprache der Peano Arithmetik definiert wenn X genau die Zahlen enthalt die f x displaystyle varphi x nbsp erfullen d h n X N f n displaystyle n in X Leftrightarrow mathbb N models varphi underline n nbsp wobei n displaystyle underline n nbsp der Term in der Sprache der Arithmetik ist der die Zahl n displaystyle n nbsp reprasentiert Eine Menge heisst arithmetisch wenn sie durch eine Formel der Peano Arithmetik definiert wird Eine Menge X von naturlichen Zahlen ist S n 0 displaystyle Sigma n 0 nbsp P n 0 displaystyle Pi n 0 nbsp oder D n 0 displaystyle Delta n 0 nbsp wenn sie durch eine Formel in der entsprechenden Klasse definiert wird Ebenso lassen sich auch Relationen bzw Mengen von k Tupeln naturlicher Zahlen klassifizieren wenn man Formeln mit k freien Variablen betrachtet Bezug zu Berechenbarkeit BearbeitenDie entscheidbaren Mengen sind genau die D 1 0 displaystyle Delta 1 0 nbsp Mengen Die rekursiv aufzahlbaren Mengen sind die S 1 0 displaystyle Sigma 1 0 nbsp Mengen Auch daruber hinaus gibt es eine enge Beziehung zwischen der arithmetischen Hierarchie und den Turinggraden Nach dem Satz von Post gilt fur alle n 1 displaystyle n geq 1 nbsp n displaystyle emptyset n nbsp der n displaystyle n nbsp te Turing Jump der leeren Menge ist many one vollstandig fur S n 0 displaystyle Sigma n 0 nbsp Die Mengen in S n 1 0 displaystyle Sigma n 1 0 nbsp sind genau die Mengen die rekursiv aufzahlbar in n displaystyle emptyset n nbsp sind n 1 displaystyle emptyset n 1 nbsp ist vollstandig unter Turing Reduktion fur D n 0 displaystyle Delta n 0 nbsp Literatur BearbeitenHartley Rogers Theory of recursive functions and effective computability McGraw Hill 1967 Abgerufen von https de wikipedia org w index php title Arithmetische Hierarchie amp oldid 180598012