Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to prove the equivalence of the following assertions (Exercise 2.5.12 from Marker "Model Theory: An Introduction").

  1. There is a universal formula $\psi(\bar v)$ such that $T \models \forall \bar v (\phi(\bar v) \leftrightarrow \psi(\bar v))$.
  2. If $\cal M$ and $\cal N$ are models of $T$ with $\cal M \subset N$, $\bar a \in M$ and ${\cal N} \models \phi(\bar a)$, then ${\cal M} \models \phi(\bar a)$.

It is straightforward to show that 1 implies 2. For the converse I tried to work out some examples. Let $$\begin{array} {rl} T = \{ & \forall x (\exists y R(x, y) \leftrightarrow P(x)) \lor \forall x (\exists y R(x, y) \leftrightarrow \lnot P(x)), \\ & \exists x, y R(x, y)\} \end {array}$$ and $\phi$ be $\exists y R(x, y)$. Assume that $\cal M$ and $\cal N$ are models of $T$ with $\cal M \subset N$. Then $${\cal M} \models \forall x(\exists y R(x, y) \leftrightarrow P(x)) \lor \forall x (\exists y R(x, y) \leftrightarrow \lnot P(x)).$$ Without lose of generality assume that $${\cal M} \models \forall x(\exists y R(x, y) \leftrightarrow P(x)).$$ For some $b, c \in M$ we must also have ${\cal M} \models R(b, c)$ and hence ${\cal M} \models P(b)$. It follows that ${\cal N} \models \exists y R(b, y) \land P(b)$. Hence ${\cal N} \not \models \forall x (\exists y R(x, y) \leftrightarrow \lnot P(x))$. And so $${\cal N} \models \forall x (\exists y R(x, y) \leftrightarrow P(x)).$$ But now if ${\cal N} \models \exists y R(a, y)$ for some $a \in M$, then ${\cal N} \models P(a)$ hence ${\cal M} \models P(a)$ and hence ${\cal M} \models \exists y R(a, y)$. Thus the second property holds and so $$T \models \forall x(\exists y R(x, y) \leftrightarrow \psi(x))$$ for some universal formula $\psi$. But I can't find such a formula. Is there such a $\psi$ or have I an error in my deductions?

Edit

I have found the universal formula. $$T \models \forall x \Bigg(\exists y R(x, y) \leftrightarrow \forall u, v \bigg(\Big(\big(R(u,v) \to p(u)\big) \land p(x) \Big) \lor \Big(\big(R(u,v) \to \lnot p(u) \big) \land \lnot p(x)\Big)\bigg)\Bigg)$$

share|improve this question
    
What exactly is a "universal formula"? A series of universal quantifications applied to a quantifier-free formula? –  Henning Makholm Sep 13 '12 at 14:15
    
@HenningMakholm Exactly –  Levon Haykazyan Sep 13 '12 at 14:20
    
the part starting with $\forall u, v$ is the formula I was looking for. –  Levon Haykazyan Sep 14 '12 at 17:44

1 Answer 1

up vote 3 down vote accepted

Here are a couple of hints:

(1) Prove this first for sentences $\chi$ instead of formulas.

(2) When working with sentences, do not explicitly construct the universal sentence $\chi^*$. Instead, consider the family $S_{\chi}$ of all universal sentences $\theta$ such that $T,\chi \vdash \theta$. Show that if $T \cup S_{\chi} \cup \{\neg \chi\}$ is inconsistent, then you can produce the universal sentence you need. The idea here is that you can recover $\chi$ from some of these universal sentences if $T \cup S_{\chi}$ is strong enough to prove $\chi$ in $T$. Since $S_{\chi}$ were all $T$-provable implications of $\chi$, you should be able to get equivalence in $T$.

(3) Now, actually prove that $T \cup S_{\chi} \cup \{\neg \chi\}$ is inconsistent. Try supposing there is a countable model $A$ of this theory, and show that it cannot exist.

(4) To pass to the case of formulas, expand the signature with new constants to represent the variables, and so change your formula into a sentence by replacing the variables with the constants. Repeat the argument above to obtain a universal sentence, and then justify the claim that replacing the constants with variables again will preserve the equivalence in $T$.


I apologize for not providing more details at the present moment. The proof I am thinking of is a little long. If you want me to flesh out the details please indicate so and I will do so later today.

share|improve this answer
    
Thank you for hints. At the moment I am not looking for the complete solution (I want to find it myself). Instead finding the universal formula for my particular case I think would help me to get a clue. –  Levon Haykazyan Sep 13 '12 at 17:52
    
I don't think finding the universal formula in your case will help you solve the general case. The proof is not constructive. –  Isaac Solomon Sep 13 '12 at 18:51
1  
I have found the formula I was looking for. I have accepted your answer as it helped me to solve the problem. –  Levon Haykazyan Sep 14 '12 at 12:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.