Ich versuche, Notationen für große abzählbare Ordnungszahlen auf "natürliche Weise" zu erstellen. Mit "natürlich" meine ich, dass bei einem induktiven Datentyp X diese Gleichheit die übliche rekursive Gleichheit sein sollte (die gleiche, die deriving Eqin Haskell erzeugt würde) und die Reihenfolge die übliche rekursive lexikographische Reihenfolge sein sollte (die gleiche, die deriving Ordin Haskell erzeugt würde) ), und es gibt ein entscheidbares Prädikat, das bestimmt, ob ein Element von X eine gültige Ordnungszahl ist oder nicht.
Zum Beispiel können Ordnungszahlen kleiner als & egr; 0 durch erblich endliche sortierte Listen dargestellt werden und erfüllen diese Anforderungen. Definiere X als μα. μβ. 1 + α × β, auch bekannt als erblich begrenzte Listen. Stellen Sie sicher isValid, dass X sortiert ist und alle Mitglieder von X sind isValid. Die gültigen Mitglieder von X sind alle Ordnungszahlen kleiner als ε 0 in der üblichen lexikographischen Reihenfolge.
Ich vermute , dass μα 0 . ... μα n . 1 + α 0 ×… × α n kann auf ähnliche Weise verwendet werden, um Ordinalzahlen zu definieren, die kleiner als φ n + 1 (0) sind, wobei φ die Veblen-Funktion ist.
Wie Sie sehen können, sind bei φ ω (0) keine μ-Quantifizierer mehr vorhanden . Kann ich größere Ordnungszahlen erstellen, die meinen Anforderungen entsprechen? Ich hatte gehofft, bis Γ 0 zu kommen . Kann ich größere Ordnungszahlen erhalten, wenn ich meine Entscheidbarkeitsanforderung auf mein Gültigkeitsprädikat fallen lasse?
quelle
comparein coq.inria.fr/pylons/contribs/files/Cantor/v8.3/… In derselben Datei befindet sich ein Lemma,nf_introdas die Gültigkeit charakterisieren könnte.Inductive lt : T2 -> T2 -> Propsieht für mich nicht nach lexikografischer Reihenfolge aus.Antworten:
Hermann Ruge Jervel hat ein schönes System, das bis zum Bachmann-Howard-Ordinal reicht, das auf beschrifteten Bäumen basiert. Siehe: http://folk.uio.no/herman/logsem.pdf
Ich mag auch sein Buch über die Beweistheorie, das dieses System behandelt: http://folk.uio.no/herman/bevisteori.ps
quelle