Modelle der Nachfolgearithmetik

Question

Modelle der Nachfolgearithmetik

Logik
Mathematik
Modelltheorie
Peano-Axiome

Nagase

Betrachten Sie die Theorie $\text{Th}(\mathbb{N}, S, 0)$ , von der wir wissen, dass sie durch die folgenden Axiome axiomatisiert wird:

$\forall x (S(x) \neq 0)$
$\forall x \forall y (S(x) = S(y) \rightarrow x=y)$
$\forall x (x \neq 0 \rightarrow \exists y (x=S(y))$

plus das Axiomschema:

$\forall x (S^n(x) \neq x)$ für jede $n \in \mathbb{N}$ (Wo $S^n(x)$ ist die Anwendung von $S$ $n$ mal zu $x$ ).

Nun ist bekannt, dass Modelle dieser Theorie genau diejenigen sind, die die Form haben $\mathbb{N} + \lambda \cdot \mathbb{Z}$ , Wo $\lambda$ ist eine endliche oder unendliche Kardinalzahl. Meine Frage ist, wie man das beweist. Es ist nicht schwer zu zeigen, dass jede Struktur dieser Form ein Modell für die Theorie ist, aber was ist umgekehrt, dh dass jedes Modell der Theorie diese Form hat?

Nun ist klar, dass jedes Modell dieser Theorie aus einem Anfangssegment bestehen wird, das eine Kopie davon ist $\mathbb{N}$ . Mein Gedanke war dann, eine Äquivalenzrelation zu definieren $x \equiv y$ wenn es das gibt $n$ so dass $S^n(x)=y$ , und zeigen Sie dann, dass die Äquivalenzklassen alle die Form haben $\mathbb{N}$ oder $\mathbb{Z}$ . Geht das in die richtige Richtung?

Auch als Randnotiz, nur zur Kontrolle, aber das $1$ -Typen dieser Theorie sind alle entweder durch eine Formel der Form isoliert $S^n(0)=x$ , oder sonst der eindeutige nicht isolierte Typ $\{S^n(0) \neq x \; | \; n \in \mathbb{N}\}$ , richtig?

Noah Schweber

Ihre vorgeschlagene Äquivalenzbeziehung hat die richtige Idee, funktioniert aber nicht wirklich: Sie ist nicht symmetrisch. Sobald Sie das jedoch behoben haben, haben Sie die richtige Idee.

Nagase

@NoahSchweber - Stimmt natürlich! Du meinst, ich sollte auf der rechten Seite "da ist

n

$n$ so dass entweder

S^{n} (x) = y

$S^n(x) = y$ oder

S^{n} (y) = x

$S^n(y) = x$ , Rechts? Kannst du deinen Kommentar als Antwort posten?

Prima Petri

Du sagst: Modelle dieser Theorie sind genau die, die die Form ℕ+𝜆⋅ℤ haben. Was ist mit Modellen der Form ℕ+ℚ⋅ℤ ?

Nagase

@PrimoPetri - Seit

| Q | = ℵ_{0}

$|\mathbb{Q}|=\aleph_0$ , sie sind vom Typ

N + ℵ_{0} \cdot Z

$\mathbb{N} + \aleph_0 \cdot \mathbb{Z}$ . Ich glaube nicht, dass die Nachfolgearithmetik zwischen der Auftragsart der Kopien unterscheiden kann

Z

$\mathbb{Z}$ (das heißt, die Art und Weise, wie die

Z

$\mathbb{Z}$ s sind untereinander geordnet).

Dan Christensen

Ist (4) nicht überflüssig? Ist dieses "Rückschleifen" nicht durch (1) und (2) verboten?

Nagase

@DanChristensen - Nein, sie sind nicht überflüssig. Betrachten Sie ein Modell

M

$\mathcal{M}$ bestehend aus

N

$\mathbb{N}$ und ein einzelnes Element, sagen wir

a

$a$ , nicht in

N

$\mathbb{N}$ . Definieren

S

$S$ als Nachfolger wie gewohnt vorbei

N

$\mathbb{N}$ und einstellen

S (a) = a

$S(a)=a$ . Dann

M

$\mathcal{M}$ erfüllt 1-3, erfüllt aber 4 nicht für

n = 1

$n=1$ .

Dan Christensen

Danke. Warum dann nicht einfach das natürlichere Induktionsprinzip verwenden und die Konstruktion vermeiden

S^{n} (x)

$S^n(x)$ Funktion?

Nagase

@DanChristensen - Sie können ein Induktionsschema verwenden, ähnlich dem, das Sie mit PA erster Ordnung haben (aber natürlich auf Formeln beschränkt, die nur die Nachfolgerfunktion enthalten). Dies wird einen weiteren unendlichen Satz von Axiomen für die Theorie ergeben. Aber ich finde es einfacher, die Modelle der Theorie mit diesem speziellen Schema zu analysieren.

Dan Christensen

Ich denke, Sie bräuchten eine Induktion, um die Existenz von zu beweisen

S^{n} (x)

$S^n(x)$ Funktion. Nur zur Klarstellung, ist das so

S^{0} (x) = x, S^{1} (x) = S (x), S^{2} (x) = S (S (x))

$S^0(x)=x, ~S^1(x) = S(x), ~S^2(x)=S(S(x))$ , usw? Dann

S^{n} (x) = x + n

$S^n(x)=x+n$ .

Nagase

@DanChristensen - Es gibt kein "

S^{n}

$S^n$ Funktion. Die Amtssprache enthält nur

S

$S$ . Ich benutze nur

S^{n}

$S^n$ als Abkürzung für die Anwendung der Funktion

n

$n$ Mal zu einem Begriff. A1

_{1}

$_1$ Ist

\forall x (S (x) \neq x)

$\forall x (S(x) \neq x)$ , A2

_{2}

$_2$ Ist

\forall x (S (S (x)) \neq x)

$\forall x (S(S(x)) \neq x)$ , usw., sodass keines der Axiome tatsächlich enthält

S^{n}

$S^n$ .

Dan Christensen

In PA 2. Ordnung (in der Sprache der Mengenlehre) kann man die Existenz einer solchen Funktion ausgehend von Peanos Axiomen formal beweisen. Ich verstehe, dass Sie das in 1st Order PA nicht tun können.

Antworten (1)

Modelle der Nachfolgearithmetik

Ihre vorgeschlagene Äquivalenzbeziehung hat die richtige Idee, funktioniert aber nicht wirklich: Sie ist nicht symmetrisch. Sobald Sie das jedoch behoben haben, haben Sie die richtige Idee.
@NoahSchweber - Stimmt natürlich! Du meinst, ich sollte auf der rechten Seite "da ist $n$ so dass entweder $S^n(x) = y$ oder $S^n(y) = x$ , Rechts? Kannst du deinen Kommentar als Antwort posten?
Du sagst: Modelle dieser Theorie sind genau die, die die Form ℕ+𝜆⋅ℤ haben. Was ist mit Modellen der Form ℕ+ℚ⋅ℤ ?
@PrimoPetri - Seit $|\mathbb{Q}|=\aleph_0$ , sie sind vom Typ $\mathbb{N} + \aleph_0 \cdot \mathbb{Z}$ . Ich glaube nicht, dass die Nachfolgearithmetik zwischen der Auftragsart der Kopien unterscheiden kann $\mathbb{Z}$ (das heißt, die Art und Weise, wie die $\mathbb{Z}$ s sind untereinander geordnet).
Ist (4) nicht überflüssig? Ist dieses "Rückschleifen" nicht durch (1) und (2) verboten?
@DanChristensen - Nein, sie sind nicht überflüssig. Betrachten Sie ein Modell $\mathcal{M}$ bestehend aus $\mathbb{N}$ und ein einzelnes Element, sagen wir $a$ , nicht in $\mathbb{N}$ . Definieren $S$ als Nachfolger wie gewohnt vorbei $\mathbb{N}$ und einstellen $S(a)=a$ . Dann $\mathcal{M}$ erfüllt 1-3, erfüllt aber 4 nicht für $n=1$ .
Danke. Warum dann nicht einfach das natürlichere Induktionsprinzip verwenden und die Konstruktion vermeiden $S^n(x)$ Funktion?
@DanChristensen - Sie können ein Induktionsschema verwenden, ähnlich dem, das Sie mit PA erster Ordnung haben (aber natürlich auf Formeln beschränkt, die nur die Nachfolgerfunktion enthalten). Dies wird einen weiteren unendlichen Satz von Axiomen für die Theorie ergeben. Aber ich finde es einfacher, die Modelle der Theorie mit diesem speziellen Schema zu analysieren.
Ich denke, Sie bräuchten eine Induktion, um die Existenz von zu beweisen $S^n(x)$ Funktion. Nur zur Klarstellung, ist das so $S^0(x)=x, ~S^1(x) = S(x), ~S^2(x)=S(S(x))$ , usw? Dann $S^n(x)=x+n$ .
@DanChristensen - Es gibt kein " $S^n$ Funktion. Die Amtssprache enthält nur $S$ . Ich benutze nur $S^n$ als Abkürzung für die Anwendung der Funktion $n$ Mal zu einem Begriff. A1 $_1$ Ist $\forall x (S(x) \neq x)$ , A2 $_2$ Ist $\forall x (S(S(x)) \neq x)$ , usw., sodass keines der Axiome tatsächlich enthält $S^n$ .
In PA 2. Ordnung (in der Sprache der Mengenlehre) kann man die Existenz einer solchen Funktion ausgehend von Peanos Axiomen formal beweisen. Ich verstehe, dass Sie das in 1st Order PA nicht tun können.

Noah Schweber · Answer 1

Sie haben die richtige Idee, aber sie muss optimiert werden: Die Beziehung "endliche Entfernung" ist das, was Sie wollen, aber es ist nicht das, was Sie geschrieben haben (was Sie geschrieben haben, ist nicht symmetrisch). Satz $x\sim y$ wenn es etwas Endliches gibt $n$ so dass $S^n(x)=y$ oder es gibt etwas Endliches $n$ so dass $S^n(y)=x$ (Beachten Sie, dass dies nur die übliche "Grafikmetrik" ist).

Die wichtigsten Beobachtungen sind nun, dass es in jedem Modell der Nachfolgerarithmetik genau ein Element ohne Vorgänger gibt und die Nachfolgerfunktion injektiv ist. Diese beiden Tatsachen implizieren schnell, dass jedes Modell der Nachfolgearithmetik aus genau einem besteht $\sim$ -Klasse von "Typ $\mathbb{N}$ „und alle anderen $\sim$ -Klassen (falls vorhanden) haben "type $\mathbb{Z}$ ."

(Es kann hilfreich sein, darüber nachzudenken, was die Nachfolgearithmetik über die Beziehung "Distanz Eins" beweist $x=S(y)\vee y=S(x)$ ; Meiner Erfahrung nach ist dies etwas einfacher zu konzeptualisieren, obwohl ich nicht sicher bin, warum.)

Modelle der Nachfolgearithmetik

Nagase

Noah Schweber

Nagase

Prima Petri

Nagase

Dan Christensen

Nagase

Dan Christensen

Nagase

Dan Christensen

Nagase

Dan Christensen

Antworten (1)

Noah Schweber

Gibt es ein Nichtstandardmodell der Peanoschen Arithmetik, bei dem jedes Element nur endlich viele Primteiler hat?

Sind alle Modelle der Peano-Arithmetik mit der Logik erster Ordnung nicht standardisiert?

Eine Frage zum Satz von Tennebaum?

Gibt es ein natürliches Modell der Peano-Arithmetik, bei dem der Satz von Goodstein versagt?

Sind die natürlichen Standardzahlen ein herausragendes Modell der PA?

Kann die Tatsache, dass NBG ohne Wahl eine konservative Erweiterung von ZF ist, in der Peano-Arithmetik bewiesen werden?

Nachfolgerarithmetik ist nicht endlich axiomatisierbar

Wie viel Arithmetik finden wir definierbar in den Surrealen?

Können zwei verschiedene Modelle der Arithmetik nicht vergleichbare Ansichten der Peano-Arithmetik haben?

Ist die Theorie regulärer formaler Sprachen endlich axiomatisierbar?