Lücke das Lemma: erfüllbare Theorie impliziert widerspruchsfreie Theorie

Question

Lücke das Lemma: erfüllbare Theorie impliziert widerspruchsfreie Theorie

Logik
Mathematik
Modelltheorie

temo

Ich habe eine Frage zu einer Lücke im Lemma. Zuerst, wie die Dinge in dem Kurs, den ich besuche, definiert wurden (es tut mir leid, dass ich die Leser dazu zwingen muss, diese Liste von Definitionen durchzugehen, aber ich weiß nicht, wie ich sie kürzer machen soll):

Lassen $\sigma$ eine Unterschrift sein und $T$ A $\sigma$ -Theorie. Wir haben diese Theorie als erfüllbar definiert, wenn es ein Modell gibt $M$ so dass für jeden Satz der Theorie $M$ erfüllt die Sätze. Wir haben Sätze als beweisbar definiert, wenn sie zu der kleinsten Menge gehören, die eine Liste von Eigenschaften und universelles if für jedes Modell erfüllt $M$ Sie sind zufrieden. Weiter haben wir die Theorie als widerspruchsfrei definiert, wenn es keine Sätze gibt $\alpha_1,\ldots,\alpha_n \in T$ so dass $\neg ( \alpha_1 \wedge \ldots \wedge \alpha_n)$ ist nachweisbar.

Dann haben wir bewiesen, dass jeder beweisbare Satz universell ist, und dann wurde (ohne vollständigen Beweis) erwähnt, dass nach dem vorherigen Satz jede erfüllbare Theorie widerspruchsfrei ist. Meine Frage ist: Wie kann die Aussage, dass jeder beweisbare Satz universell ist, verwendet werden, um dies zu beweisen?

Arturo Magidin

Wenn

T

$T$ nicht widerspruchsfrei ist, dann hat man Sätze

α_{1}, \dots, α_{n} \in T

$\alpha_1,\ldots,\alpha_n\in T$ so dass

\neg (α_{1} \land \dots \land α_{n})

$\neg(\alpha_1\land\cdots\land\alpha_n)$ ist nachweisbar. Aber seit

T

$T$ erfüllbar ist, hat es ein Modell

M

$M$ ; seit

M

$M$ ist ein Modell,

α_{1}, \dots, α_{n}

$\alpha_1,\ldots,\alpha_n$ sind darin zufrieden

M

$M$ . Seit

\neg (α_{1} \land \dots \land α_{n})

$\neg(\alpha_1\land\cdots\land\alpha_n)$ ist beweisbar, es ist allgemein, also ist es erfüllt in

M

$M$ . So

M

$M$ erfüllt jeden

α_{i}

$\alpha_i$ , und erfüllt mindestens auf

\neg α_{j}

$\neg\alpha_j$ , was unmöglich ist (

M

$M$ ist ein Modell).

Antworten (2)

Lücke das Lemma: erfüllbare Theorie impliziert widerspruchsfreie Theorie

Wenn $T$ nicht widerspruchsfrei ist, dann hat man Sätze $\alpha_1,\ldots,\alpha_n\in T$ so dass $\neg(\alpha_1\land\cdots\land\alpha_n)$ ist nachweisbar. Aber seit $T$ erfüllbar ist, hat es ein Modell $M$ ; seit $M$ ist ein Modell, $\alpha_1,\ldots,\alpha_n$ sind darin zufrieden $M$ . Seit $\neg(\alpha_1\land\cdots\land\alpha_n)$ ist beweisbar, es ist allgemein, also ist es erfüllt in $M$ . So $M$ erfüllt jeden $\alpha_i$ , und erfüllt mindestens auf $\neg\alpha_j$ , was unmöglich ist ( $M$ ist ein Modell).

Yuval Filmus · Answer 1

Vermuten $T$ ist eine erfüllbare Theorie. Wählen Sie ein Modell aus $M$ dafür. Wenn $C$ ist ein Widerspruch beweisbar in $T$ , dann durch Ihren Vorschlag $C$ halten muss $M$ . Jedoch, $C$ ist logisch nicht gültig, und insbesondere die rekursive Definition der Gültigkeit zeigt, dass sie nicht gelten kann. So $C$ darf nicht nachweisbar gewesen sein $T$ schließlich.

Mit anderen Worten, $M$ ist ein Beweis dafür $T$ ist eine "vernünftige" Theorie. Es zeugt von der Konsistenz $T$ - in der Tat, es ist ein Beispiel dafür! - und zeigt das auch $T$ kann keine "inhärenten" Widersprüche enthalten.

Karl Mummert · Answer 2

Eine andere Art, dasselbe auszudrücken: let $T$ Seien Sie Ihre Theorie und lassen Sie $M$ ein Modell sein von $T$ . Lassen $S$ sei die Menge aller Sätze, die in wahr sind $M$ (symbolisch, $S = \{ \phi : M \vDash \phi\}$ ). Dann:

$S$ erweitert $T$ , Weil $M \vDash T$ .
$S$ ist unter Beweisbarkeit geschlossen: if $\psi_1, \ldots, \psi_k \in S$ Und $\psi_1, \ldots, \psi_k \vdash \phi$ Dann $\phi \in S$ . Dies folgt aus der Solidität des Beweissystems.
$S$ ist konsequent: für keinen Satz $\phi$ tut $S$ enthalten $\phi \land \lnot \phi$ . Dies folgt aus der Definition des $\vDash$ Beziehung.

Diese drei Kugeln zusammen implizieren $T$ ist konsistent.

Als Prämie $S$ ist auch komplett: für alle $\phi$ , entweder $\phi \in S$ oder $\lnot \phi \in S$ , wieder wegen der Definition der $\vDash$ Beziehung. Die Existenz eines Modells ist also in gewisser Weise ein sehr starker Beweis dafür, dass die Theorie konsistent ist: Es beweist nicht nur die Konsistenz von $T$ , es bietet auch eine konsistente Vervollständigung von $T$ .

Lücke das Lemma: erfüllbare Theorie impliziert widerspruchsfreie Theorie

temo

Arturo Magidin

Antworten (2)

Yuval Filmus

Karl Mummert

Ist die Theorie regulärer formaler Sprachen endlich axiomatisierbar?

Finden eines geeigneten Universums für eine gegebene Struktur

Prinicpal 1-Typen scheinbares Paradoxon

Wie wird die vollständige Semantik von SOL und HOL spezifiziert?

Endlich viele abzählbare Modelle implizieren Entscheidbarkeit

Jedes ZFC-Modell hat ein Element, das ein ZFC-Modell ist

Modelle der Nachfolgearithmetik

Ein Modell, das nur ein undefinierbares Element über einer Sprache mit nur einer endlichen Anzahl von Symbolen hat

Warum haben Modelle von ZF, die keine ωω\omega-Modelle sind, nicht standardisierte Formeln, deren Länge "unendlich große natürliche Zahlen" sind?

Nicht-Axiomatisierbarkeit und Ultraprodukte