# Limited completeness and restricted quantifiers

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.

• Is the question unclear or uninteresting ? – Amr Apr 12 '14 at 19:46
• It needs a better title for one. – Memming Apr 12 '14 at 20:41
• @Memming Yes, but I can't think of a better title – Amr Apr 12 '14 at 20:53
• I've attempted to give a more incisive title. I don't know the answer, but my intuition is that it is false and that a model can be used to prove it so. – hardmath Apr 15 '14 at 15:04
• @hardmath Why is your intuition that it is false, I have the intuition that it is true. I will still try the ideas given in the answers below – Amr Apr 15 '14 at 15:28

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$.

• Hi Dr. Wafik ! $Q_1$ defined to be $v_1=v_1$ does not satisfy: 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$$, does it ? – Amr Apr 13 '14 at 23:15
• In my question, $(1),(2),(3)$ are givens and $(4)$ is what is required to prove. – Amr Apr 13 '14 at 23:20
• You're right. I was sloppy. The construction of the structure needs the following: R forms a cycle, and all other relations always hold. Now every element satisfy the same formulas with one free variable. – Wafik Apr 14 '14 at 6:18
• What does $R$ cyclic mean ? Does it mean that $A\models {\{\forall x\forall y [R(xy)\rightarrow R(yx)]\}}$ – Amr Apr 14 '14 at 6:24

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.

• Thanks for your help. 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 first order logic. This definition is used in Manin's book and I thought it was standard. – Amr Apr 13 '14 at 11:26
• Ah, I see. I'll edit my answer but I think that this still gives you what you are looking for, or is it something different? – UserB1234 Apr 13 '14 at 14:24
• I will read you ranswer, thank you. – Amr Apr 13 '14 at 19:14
• I do not agree when you say: "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}$." – Amr Apr 13 '14 at 19:22
• Informally, if we only know that $c_1=c_1$ for some some constant in our model, we may not be able to determine everything about $c_1$ I really think counterexamples are easy to find – Amr Apr 13 '14 at 19:25

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.

• @DanulG I proved the part of your solution which you did not give a proof for. It is related to what I would call model "automorphisms" – Amr Apr 15 '14 at 18:55
• @hardmath The answer is no. I have a complete proof now. – Amr Apr 15 '14 at 18:56
• Thanks for the other answers – Amr Apr 15 '14 at 19:12