Limited completeness and restricted quantifiers

Question

Let $L$ be a first order language with no constant or operation symbols. $L$ also has a relation symbol $R$ of arity $2$. Let $T$ be a Godelian set of formulas. Let $Q^1,Q^2$ be two formulas. The only free variable of $Q^1$ is $v_1$ and the only free variable of $Q^2$ is $v_2$. $v_1$ does not occur inside $Q^2$ and $v_2$ does not occur inside $Q^1$. It is given that: $$\exists v_1(Q^1),\exists v_2(Q^2)\in T...(1)$$ It is also given that for every formula $P^1$ with only $v_1$ as its free variable, the following holds: $$\forall v_1 (Q^1\rightarrow P^1)\in T \,\,\text{or}\,\,\forall v_1(Q^1\rightarrow (\lnot P^1))\in T...(2)$$

Informally, this means that if there is an object satisfies $Q^1$, then we know everything about it.

Similarly, for every formula $P^2$ with only $v_2$ as its free variable, the following holds: $$\forall v_2 (Q^2\rightarrow P^2)\in T \,\,\text{or}\,\,\forall v_2(Q^2\rightarrow (\lnot P^2))\in T...(3)$$

I really think that the following must be true but I am unable to prove it: $$\forall v_1\forall v_2 [(Q^1\land Q^2)\rightarrow R(v_1v_2)]\in T \,\,\text{or}\,\,\forall v_1\forall v_2 [(Q^1\land Q^2)\rightarrow \big(\lnot R(v_1v_2)\big)]\in T...(4)$$

I would like to see a proof for the above statement.

Thank you

---

A Godelian set is a maximally consistent set of formulas that contains all logical axioms, tautologies, and is closed under modus ponens, and the generalization rule of $\forall$. This definition is used in Manin's book and I thought it was standard.

Answer 1

The answer is no. I will give the counterexample below.

Consider the first-order language $L=\{\equiv\}$ that only has the binary relation symbol $\equiv$. Let $M:=\{0,1\}$. We define an interpretation $\Phi$ of $L$ in $M$ as follows: $$\Phi(\equiv):=\{(a,a)|a\in M\}$$ Since $L$ does not have any constant or operation symbols, the above line completely determines our interpretation $\Phi$. Now consider $f:M\rightarrow M$ that sends $0$ to $1$ and $1$ to $0$. Clearly, $f$ is a bijection.

Let $Var$ denote the set of variables in our alphabet.

Claim1: For every formula $P$ in $L$ and every interpretation $\Gamma:Var\rightarrow M$, we have $|P|_{\Phi}(\Gamma)=|P|_{\Phi}(f\Gamma)$

Proof: Induct on the length of the formula $P$. Let $\Gamma$ be our interpretation function of the variable symbols. Base: $P$ is atomic. Case 1: $P$ is "$\equiv(x_1x_2)$" and $x_1,x_2$ are two variable symbols (possibly $x_1$ is the symbol as $x_2$). Since $f$ is a bijection, therefore $\Gamma(x_1)=\Gamma(x_2)$ iff $f\Gamma(x_1)=f\Gamma(x_2)$. Hence, $(\Gamma(x_1),\Gamma(x_2))\in \Phi(\equiv)$ iff $(f\Gamma(x_1),f\Gamma(x_2))\in \Phi(\equiv)$. Thus, $|P|_{\Phi}(\Gamma)=|P|_{\Phi}(f\Gamma).$ The proof of the induction step is trivial and follows immediately from the recursive definition of $|P|_{\Phi}(\Gamma)$. $\square$

Now let $T$ be the subset of the formulas of $L$ that is deined by $T:=\{P|\text{For every interpretation of the variable symbols $\Gamma$, we have $|P|_{\Phi}(\Gamma)=1$}\}$. It is a theorem that the set of true statements about a structure form a Godelian set. Hence, $T$ is Godelian.

Now using ideas from the other two answers.

Now set $Q^1,Q^2$ to be $v_1=v_1,v_2=v_2$. By looking at our interpretation $\Phi$, we can see clearly that $\exists v_1(Q^1),\exists v_2(Q^2)\in T$.

Claim 2: For every formula $P^1$ that $v_1$ as its only free variable, Either $\forall v_1[ P^1]\in T$ or $\forall v_1[\lnot P^1]\in T$

Proof: Suppose the first option does not hold, therefore there is some variable interpretation $\Gamma$ such that $| P^1|_{\Phi}(\Gamma)=0$. Hence, $| \not P^1|_{\Phi}(\Gamma)=1$. Using Claim 1, we get $| \lnot P^1|_{\Phi}(f\Gamma)=1$ as well. Now for any variable interpretation $\Theta$, either $\Theta(v_1)=\Gamma(v_1)$ or $\Theta(v_1)=f\Gamma(v_1)$ (because the size of our model is two and $f$ does not have any fixed points). Since $v_1$ is the only free variable of $P^1$. Thus, either $| \lnot P^1|_{\Phi}(\Theta)=| \lnot P^1|_{\Phi}(\Gamma)=1$ or $| \lnot P^1|_{\Phi}(\Theta)=| \lnot P^1|_{\Phi}(f\Gamma)=1$. Hence, $| \lnot P^1|_{\Phi}(\Theta)$ is always $1$ for any variable interpretation $\Theta$. Thus, $|\forall v_1( \lnot P^1)|_{\Phi}(\Theta)=1$ for every $\Theta$. Thus, $\forall v_1( \lnot P^1) \in T$. $\square$

Since, $\forall v_1(Q^1)\in T$ one use claim 2 to show that:

$$\forall v_1 (Q^1\rightarrow P^1)\in T \,\,\text{or}\,\,\forall v_1(Q^1\rightarrow (\lnot P^1))\in T$$ Similarly, one can also show that:

$$\forall v_2 (Q^2\rightarrow P^2)\in T \,\,\text{or}\,\,\forall v_2(Q^2\rightarrow (\lnot P^2))\in T$$

However, by looking at the model $M$ and the interpretation $\Phi$ we can clearly see that:

$$\forall v_1\forall v_2 [(Q^1\land Q^2)\rightarrow \equiv(v_1v_2)]\not\in T \,\,\text{and}\,\,\forall v_1\forall v_2 [(Q^1\land Q^2)\rightarrow \big(\lnot \equiv(v_1v_2)\big)]\not\in T$$

---

Now we can isolate a certain interesting concept in the above proof and make the following definition:

Let $L$ be a first order language with relation symbols only. Let $\Phi$ be an interpretation of $L$ in $M$. We say that a bijection $f:M\rightarrow M$ is a model automorphism iff for every relation symbol $R$ in $L$ with arity $r$, we have the following:

For every $m_1,m_2,...,m_r\in M$: $$(m_1,m_2,...,m_r)\in \Phi(R) \,\,\, \text{iff} \,\,\,(f(m_1),f(m_2),...,f(m_r))\in \Phi(R)$$

Clearly, the set of model automorphisms of $M$ forms a group under function composition. I will come back and add to this post when I have time.

Answer 2

I believe the statement you want is false.

Let $L=\{R\}$. Given a sentence $\varphi$ of L, let $\varphi{'}$ be the sentence obtained by replacing each occurrence of $R$ in $\varphi$ by $=$. Let $\psi_{\varphi}:=\varphi \iff \varphi{'}$.

Now let $T_{0}$ = The theory of equality $\cup$ there are exactly two elements $\cup \{\psi_{\varphi}:=\varphi \iff \varphi{'}: \varphi \text{ is an L sentence with R in it}\}$. Let $M\models{T_{0}}$. Let $T=Th(M)$. Let $Q^{1}:=v_{1}=v_{1}$, $Q^{2}:=v_{2}=v_{2}$. Now it is clear that the conclusion you want isn't true.

Now let $P^{1}$ be a formula with just $v_{1}$ free. I'm pretty sure that we can prove $\forall{v_{1}}(Q^{1}\implies{P^{1}})\in{T}$ or $\forall{v_{1}}(Q^{1}\implies{\neg P^{1}})\in{T}$. by an induction on the complexity of $P^{1}$: However it is more complicated than I was hoping it would be.

Answer 3

The statement is false. Let $Q_1$ be $v_1=v_1$ and similarly for $Q_2$. Consider a structure $A$ where $R(x, y)$ sometimes holds and sometimes fails, and let $T$ be the set of all statements true in $A$.