Begrenzte Vollständigkeit und eingeschränkte Quantifizierer

Die Aussage ist falsch. Lassen$Q_1$Sei$v_1=v_1$und ähnlich für$Q_2$. Betrachten Sie eine Struktur$A$Wo$R(x, y)$manchmal hält und manchmal scheitert, und lassen$T$sei die Menge aller Aussagen, die wahr sind in$A$.

Ich glaube, die Aussage, die Sie wollen, ist falsch.

Lassen$L=\{R\}$. Einen Satz gegeben$\varphi$von L, lassen$\varphi{'}$sei der Satz, der durch Ersetzen jedes Vorkommens von erhalten wird$R$In$\varphi$von$=$. Lassen$\psi_{\varphi}:=\varphi \iff \varphi{'}$.

Nun lass$T_{0}$= Die Theorie der Gleichheit$\cup$Es gibt genau zwei Elemente$\cup \{\psi_{\varphi}:=\varphi \iff \varphi{'}: \varphi \text{ is an L sentence with R in it}\}$. Lassen$M\models{T_{0}}$. Lassen$T=Th(M)$. Lassen$Q^{1}:=v_{1}=v_{1}$,$Q^{2}:=v_{2}=v_{2}$. Jetzt ist klar, dass die von Ihnen gewünschte Schlussfolgerung nicht stimmt.

Nun lass$P^{1}$sei eine Formel mit just$v_{1}$frei. Ich bin mir ziemlich sicher, dass wir es beweisen können$\forall{v_{1}}(Q^{1}\implies{P^{1}})\in{T}$oder$\forall{v_{1}}(Q^{1}\implies{\neg P^{1}})\in{T}$. durch eine Induktion über die Komplexität von$P^{1}$: Es ist jedoch komplizierter als ich gehofft hatte.

Die Antwort ist nein. Ich werde das Gegenbeispiel unten geben.

Betrachten Sie die Sprache erster Ordnung$L=\{\equiv\}$die nur das binäre Beziehungssymbol hat$\equiv$. Lassen$M:=\{0,1\}$. Wir definieren eine Interpretation$\Phi$von$L$In$M$folgendermaßen:

Lassen$Var$bezeichnen die Menge der Variablen in unserem Alphabet.

Claim1: Für jede Formel$P$In$L$und jede Deutung$\Gamma:Var\rightarrow M$, wir haben$|P|_{\Phi}(\Gamma)=|P|_{\Phi}(f\Gamma)$

Beweis: Induktive Länge der Formel$P$. Lassen$\Gamma$sei unsere Interpretationsfunktion der variablen Symbole. Base:$P$ist atomar. Fall 1:$P$Ist "$\equiv(x_1x_2)$" Und$x_1,x_2$sind zwei Variablensymbole (evtl$x_1$ist das Symbol als$x_2$). Seit$f$ist also eine Bijektion$\Gamma(x_1)=\Gamma(x_2)$iff$f\Gamma(x_1)=f\Gamma(x_2)$. Somit,$(\Gamma(x_1),\Gamma(x_2))\in \Phi(\equiv)$iff$(f\Gamma(x_1),f\Gamma(x_2))\in \Phi(\equiv)$. Daher,$|P|_{\Phi}(\Gamma)=|P|_{\Phi}(f\Gamma).$Der Beweis des Induktionsschritts ist trivial und folgt unmittelbar aus der rekursiven Definition von$|P|_{\Phi}(\Gamma)$.$\square$

Nun lass$T$die Teilmenge der Formeln von sein$L$das ist definiert durch$T:=\{P|\text{For every interpretation of the variable symbols $\Gamma$, we have $|P|_{\Phi}(\Gamma)=1$}\}$. Es ist ein Theorem, dass die Menge wahrer Aussagen über eine Struktur eine Godelsche Menge bildet. Somit,$T$ist Godelian.

Verwenden Sie jetzt Ideen aus den beiden anderen Antworten.

Jetzt einstellen$Q^1,Q^2$sein$v_1=v_1,v_2=v_2$. Indem wir unsere Interpretation betrachten$\Phi$, das können wir deutlich sehen$\exists v_1(Q^1),\exists v_2(Q^2)\in T$.

Anspruch 2: Für jede Formel$P^1$Das$v_1$als einzige freie Variable Entweder$\forall v_1[ P^1]\in T$oder$\forall v_1[\lnot P^1]\in T$

Beweis: Angenommen, die erste Option gilt nicht, daher gibt es eine variable Interpretation$\Gamma$so dass$| P^1|_{\Phi}(\Gamma)=0$. Somit,$| \not P^1|_{\Phi}(\Gamma)=1$. Unter Verwendung von Anspruch 1 erhalten wir$| \lnot P^1|_{\Phi}(f\Gamma)=1$sowie. Jetzt für jede variable Interpretation$\Theta$, entweder$\Theta(v_1)=\Gamma(v_1)$oder$\Theta(v_1)=f\Gamma(v_1)$(Denn die Größe unseres Modells beträgt zwei und$f$hat keine Fixpunkte). Seit$v_1$ist die einzige freie Variable von$P^1$. Also auch nicht$| \lnot P^1|_{\Phi}(\Theta)=| \lnot P^1|_{\Phi}(\Gamma)=1$oder$| \lnot P^1|_{\Phi}(\Theta)=| \lnot P^1|_{\Phi}(f\Gamma)=1$. Somit,$| \lnot P^1|_{\Phi}(\Theta)$ist immer$1$für jede variable Interpretation$\Theta$. Daher,$|\forall v_1( \lnot P^1)|_{\Phi}(\Theta)=1$für jeden$\Theta$. Daher,$\forall v_1( \lnot P^1) \in T$.$\square$

Seit,$\forall v_1(Q^1)\in T$man verwendet Anspruch 2, um zu zeigen, dass:

Allerdings, wenn man sich das Modell ansieht$M$und die Deutung$\Phi$das können wir deutlich erkennen:

Jetzt können wir ein bestimmtes interessantes Konzept in dem obigen Beweis isolieren und die folgende Definition machen:

Lassen$L$sei eine Sprache erster Ordnung mit nur Beziehungssymbolen. Lassen$\Phi$eine Interpretation sein von$L$In$M$. Wir sagen das eine Bijektion$f:M\rightarrow M$ist ein Modellautomorphismus gdw für jedes Beziehungssymbol$R$In$L$mit arität$r$, wir haben folgendes:

Für jeden$m_1,m_2,...,m_r\in M$:

Offensichtlich ist die Menge der Modellautomorphismen von$M$bildet eine Gruppe unter Funktionszusammensetzung. Ich werde zurückkommen und diesen Beitrag ergänzen, wenn ich Zeit habe.