Effektive deskriptive Mengenlehre - Effective descriptive set theory

Effektive deskriptive Mengenlehre ist der Zweig der deskriptiven Mengenlehre, der sich mit Mengen von Realen mit Lightface- Definitionen befasst. das heißt, Definitionen, die keinen beliebigen reellen Parameter erfordern (Moschovakis 1980). Somit kombiniert eine effektive deskriptive Mengenlehre die deskriptive Mengenlehre mit der Rekursionstheorie .

Konstruktionen

Effektiver polnischer Raum

Ein effektiver polnischer Raum ist ein vollständig trennbarer metrischer Raum mit einer berechenbaren Darstellung . Solche Räume werden sowohl in der effektiven deskriptiven Mengenlehre als auch in der konstruktiven Analyse untersucht . Insbesondere Standardbeispiele für polnische Räume wie die reale Linie , das Cantor-Set und der Baire-Raum sind effektive polnische Räume.

Arithmetische Hierarchie

Die arithmetische Hierarchie , die arithmetische Hierarchie oder die Kleene-Mostowski-Hierarchie klassifizieren bestimmte Mengen basierend auf der Komplexität der Formeln, die sie definieren. Jede Menge, die eine Klassifizierung erhält, wird als "arithmetisch" bezeichnet.

Formaler ordnet die arithmetische Hierarchie den Formeln Klassifikationen in der Sprache der Arithmetik erster Ordnung zu . Die Klassifikationen sind bezeichnet und für natürliche Zahlen n (einschließlich 0). Die griechischen Buchstaben hier sind Lightface- Symbole, was darauf hinweist, dass die Formeln keine festgelegten Parameter enthalten. ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$

Wenn eine Formel mit nur einer Formel logisch äquivalent ist begrenzt quantifiers dann wird die Klassifizierungen zugeordnet und . ${\ displaystyle \ phi}$ ${\ displaystyle \ phi}$ ${\ displaystyle \ Sigma _ {0} ^ {0}}$ ${\ displaystyle \ Pi _ {0} ^ {0}}$

Die Klassifikationen und werden für jede natürliche Zahl n induktiv nach folgenden Regeln definiert: ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$

Wenn logisch äquivalent zu einer Formel der Form , wo sie dann die Klassifikation zugewiesen ist . ${\ displaystyle \ phi}$ ${\ displaystyle \ existiert n_ {1} \ existiert n_ {2} \ cdots \ existiert n_ {k} \ psi}$ ${\ displaystyle \ psi}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$ ${\ displaystyle \ phi}$ ${\ displaystyle \ Sigma _ {n + 1} ^ {0}}$
Wenn logisch äquivalent zu einer Formel der Form , wo sie dann die Klassifikation zugewiesen ist . ${\ displaystyle \ phi}$ ${\ displaystyle \ forall n_ {1} \ forall n_ {2} \ cdots \ forall n_ {k} \ psi}$ ${\ displaystyle \ psi}$ ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle \ phi}$ ${\ displaystyle \ Pi _ {n + 1} ^ {0}}$