4
$\begingroup$

Let $\mathscr L$ be the first-order language having a binary function, denoted by $+$, as signature.

We consider the two $\mathscr L$-structures $(\Bbb R, +)$ and $(\Bbb Q, +)$, where $+$ denotes the usual addition. Are they elementary equivalent?

Clearly they are not isomorphic as $\mathscr L$-structures. I know a similar example (with a binary relation $≤$) : $(\Bbb R, ≤)$ and $(\Bbb Q, ≤)$ are elementary equivalent. I believe that the answer to my main question is "yes", but I don't know how to prove it.

Any hint is welcome. Thanks!


Edit: Let $\mathscr L'$ be the first-order language having two binary functions as signature. Then the two $\mathscr L'$-structures $(\Bbb R, +,\cdot)$ and $(\Bbb Q, +,\cdot)$ (where $+$ denotes the usual addition and $\cdot$ denotes the usual multiplication) are not elementary equivalent. The formula $\newcommand{\_}{\;\;}$ $$\exists t \_ [\exists x \_ (x+x=x \_\wedge\_ \exists y \_ y \cdot y = y \_\wedge\_ \neg(x=y)) \_\wedge\_ t \cdot t = y+y]$$ is satisfied in $(\Bbb R, +,\cdot)$ by picking $t=\sqrt 2,x=0,y=1$, but not in $(\Bbb Q, +,\cdot)$.

$\endgroup$
  • 4
    $\begingroup$ This might be not completely clarifying, but the theory $Th(\mathbb{Q},+)$ is a well-known complete theory: is the theory of infinite abelian divisible groups. As the name suggest, $(\mathbb{R},+)$ satisfies the same theory. I guess a good way to prove the elementary equivalence is using a back & forth argument, or using the Tarski-Vaught test for the structures $(\mathbb{Q},+)\subseteq (\mathbb{R},+)$. $\endgroup$ – Darío G Aug 21 '16 at 9:22
  • 1
    $\begingroup$ An off-topic remark. Should we say "elementarily equivalent" (as my instructor from way back insisted), or is "elementary equivalent" more common nowadays? $\endgroup$ – GEdgar Aug 21 '16 at 17:05
  • 1
    $\begingroup$ @GEdgar: I have no idea. However "elementarily equivalent" seems to be more used than "elementary equivalent" (see for instance math.stackexchange.com/search?q=%22elementarily+equivalent%22). $\endgroup$ – Watson Aug 21 '16 at 17:50
7
$\begingroup$

As @Wore pointed out not quite correctly in a comment, both of these structures are models of the same well-known complete theory: the theory of torsion-free divisible Abelian groups. That theory has the following axioms:

  • $+$ forms an Abelian group
  • (axiom scheme where $n$ varies over positive integers) $\forall x : \exists y : \sum_{k=1}^n y = x $
  • (axiom scheme where $n$ varies over positive integers) $\forall x: \sum_{k=1}^n x = 0 \rightarrow x = 0$
  • $\exists x : x \neq 0$

(Note that I've added $0$ as a constant symbol to make the axioms easier to state correctly, but it doesn't matter. You can rewrite "$t = 0$" as "$t + t = t$" whenever it occurs, for any term $t$.)

All you need to do is show that the above axiomatizes a complete theory; it is clear that both $(\mathbb{R}, +)$ and $(\mathbb{Q},+)$ are models.

There are two main approaches to showing that the above axiomatizes a complete theory. The first approach is to show that two uncountable models of the same cardinality are isomorphic; Vaught's test then implies completeness. The second approach is to use your favorite technique to show that the theory has quantifier elimination; you can then observe that the theory is complete for quantifier-free sentences (because you can't say anything interesting without quantifiers in this theory), and therefore complete.

Hint for the Vaught's test approach: you can think of any model of this theory as a vector space over $\mathbb{Q}$, and vice versa. Two vector spaces are isomorphic if they have the same dimension (which is possibly an infinite cardinal), and the dimension of an uncountable vector space over $\mathbb{Q}$ is just its cardinality.

The quantifier elimination approach doesn't really need a further hint. Read about any standard technique for showing quantifier elimination, and then use it directly to show QE for this theory as an exercise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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