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.

My query is regarding following question:-

Let $\mathcal Q$ denote the additive group of rational numbers, i.e. the structure $\langle Q ; +; 0\rangle$. Let $\mathcal L$ be the language of $\mathcal Q$ and let $\mathcal T$ be the complete theory of $\mathcal Q$.

(i) By considering automophisms of $\mathcal Q$ prove that every formula in $F_1(\mathcal L)$ is $E_1(\mathcal T)$-equivalent to exactly one of the four formulas $v_1\bumpeq v_1; v_1\bumpeq 0; \neg v_1\bumpeq 0; \neg v_1\bumpeq v_1$:

(ii) Deduce that there are exactly two 1-types (over T), both of which are principal.

(iii) Show that there exists a 2-type (over T) which is not realised in $\mathcal Q$ and deduce that T is not $\aleph_0$-categorical.

$F_n(\mathcal L)$ denotes the set of all $\mathcal L$-formulas $\phi$ with FrVar($\phi$)$ \subseteq \{v_1,...,v_n\}$

$E_n(\mathcal T)$ denotes the binary relation on $F_n(\mathcal L)$ defined by

($\psi\space,\phi)\in E_n(\mathcal T)\iff\mathcal T\models\forall v_1,...,v_n (\phi(v_1,...,v_n)\iff\psi(v_1,...,v_n))$

I am wondering if someone could help me understand and solve this question.

(i) The automorphism is $\pi :\mathcal Q \rightarrow \mathcal Q $ such that for $r\in Q $ we have $\pi(r)=r\space\pi(1)$. I just don't know how automorphism is used to deduce that "every formula in $F_1(\mathcal L)$ is $E_1(\mathcal T)$-equivalent to exactly one of the four formulas $v_1\bumpeq v_1; v_1\bumpeq 0; \neg v_1\bumpeq 0; \neg v_1\bumpeq v_1$".

Similar question is solved in course notes without description. Only automorphism is given and then without explanation lecturer says, " From this automorphism we get four formulas...." Can someone please explain the role of automorphism here?

(ii) I deduced that $v_1\bumpeq 0$ and $\neg v_1\bumpeq 0$ are two principal formulas that generates two principal 1-type $\{v_1\bumpeq 0,v_1\bumpeq v_1\}$ and $\{\neg v_1\bumpeq 0,\neg v_1\bumpeq v_1\}$.

I deduced so because $\mathcal T\models\forall v_1( v_1\bumpeq 0\implies v_1\bumpeq v_1)$ , $\mathcal T\models\forall v_1( v_1\bumpeq 0\implies v_1\bumpeq 0)$ and $\mathcal T\models\forall v_1(\neg v_1\bumpeq 0\implies \neg v_1\bumpeq v_1)$ ,$\mathcal T\models\forall v_1( \neg v_1\bumpeq 0\implies \neg v_1\bumpeq 0)$

Am I right?

(iii) I am confused how to solve this last part. I am thinking along this way. Please let me know if I am thinking along the right line. If I give example that show there are infinitely many $E_2(\mathcal T)$-equivalence classes in $F_2(\mathcal L)$ then I deduce there exists a non-principal 2-type say $p$ (by theorem in notes).Then by 'Omitting types theorem' I can deduce that there exists a countably infinite model of $\mathcal T$ that omits $p$. By another theorem in notes I know that there exists countably infinite model that realizes $p$. Clearly both these models are not isomorphic otherwise they would be realising same 2-types. So $\mathcal T$ is not $\aleph_0- categorical$.

Please ask me if you need any further information.

share|improve this question
    
Re (iii): It might help to think about this backwards. $T$ is the theory of torsion-free divisible abelian groups, and so has (for example) $\mathbb{Q}^2$ as another countable model. Can you think of a 2-type that is realized in $\mathbb{Q}^2$ but omitted in $\mathbb{Q}$? –  Chris Eagle Apr 30 '12 at 9:40

1 Answer 1

up vote 1 down vote accepted

(i) One of the key ideas of model theory is that one should think about logical objects semantically as well as syntactically. So when you see a formula, you should think about both its syntactic structure and what elements it picks out in a model.

Given an $\mathcal{L}$-structure $M$, formulas in one free variable (in $F_1(\mathcal{L})$) correspond to definable subsets of $M$, formulas in two free variables correspond to definable subsets of $M\times M$, etc. The key fact is that two formulas are equivalent ($E_1(\mathcal{T})$-equivalent) if and only if they define the same subset of some (every) model of $\mathcal{T}$.

The formulas you refer to, $v_1 = v_1$, $v_1 = 0$, $\lnot v_1 = 0$, and $\lnot v_1 = v_1$ define the subsets $Q$, $\{0\}$, $Q\setminus \{0\}$, and $\emptyset$, respectively. To see that every formula is equivalent to one of these, we need to see that these are the only definable subsets. So suppose there is some formula $\phi(v_1)$ which is not equivalent to one of these four. Then there is some nonzero $a$ with $Q\models \phi(a)$ (otherwise $\phi$ would be equivalent to $\lnot v_1 = v_1$ or $v_1 = 0$) and also there is some nonzero $b$ with $Q\models \lnot\phi(b)$ (otherwise $\lnot\phi$ would be equivalent to $\lnot v_1 = v_1$ or $v_1 = 0$ and $\phi$ would be equivalent to $v_1 = v_1$ or $\lnot v_1 = 0$).

But since $a$ and $b$ are nonzero, there is an automorphism moving $a$ to $b$ (multiplication by $b/a$). Since automorphisms preserve satisfaction of formulas, $Q\models \phi(b)$, which is a contradiction.

(ii) Your reasoning is correct, although technically the complete types contain not just those formulas, but also all formulas which are equivalent to them (of which there are infinitely many).

(iii) You're on the right track. To show that there are infinitely many non-equivalent formulas in two variables, just start thinking... what are the possible formulas in two variables?

Once you find infinitely many non-equivalent formulas, I encourage you to try to explicitly find the type which is not realized in $Q$. It's not complicated to write down.

share|improve this answer
    
Thank you so much for such a nice and clear explanation. I have much better understanding of question. Can you please also confirm if I have come up with correct set of non-equivalent formulas in two variables . $\phi_n(v_1,v_2):= v_1\bumpeq(v_2\dot+(v_2\dot+...\dot+v_2)...)$. So if $n\neq m$ then $\phi^\mathcal Q_n \neq \phi^\mathcal Q_m$ and so we have countably infinite number of non-equivalent formulas. Am I right? –  moona Apr 30 '12 at 16:28
    
Yes, this is an infinite set of non-equivalent formulas. $\phi_n$ expresses $v_1 = n\cdot v_2$. To get the type which is not realized in $Q$, see if you can express $v_1 = \frac{n}{m}\cdot v_2$. –  Alex Kruckman Apr 30 '12 at 21:21
    
I think $\phi_{n/m} := \underbrace{v_1 \dot + v_1 \dot +...\dot + v_1}_\text{m times} \bumpeq \underbrace{v_2\dot + v_2 \dot +...\dot + v_2}_\text{n times} $ expresses $v_1=\frac{n}{m} \cdotp v_2$ –  moona Apr 30 '12 at 22:20

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.