How to show that $\mathbb{Q}$ and $\mathbb{Q}^2$ are elementarily equivalent?

141 Views Asked by At

I try to prove that $(\mathbb{Q},P)$ and $(\mathbb{Q}^2,P)$ are elementarily equivalent using Ehrenfeucht–Fraïssé games

$P(a,b,c)=True$ when $a+b=c$

$+$ on $\mathbb{Q}^2$ is defined as $(x,x')+(y,y')=(x+y,x'+y')$

$=$ on $\mathbb{Q}^2$ is defined as $(x,x')=(y,y')\iff x=y,x'=y' $

So, if I get a $q\in\mathbb{Q}$ I initially thought about choosing $(q,q)\in\mathbb{Q}^2$.

But as soon as $(q,q')\in\mathbb{Q}^2$ with $q\neq q'$ is chosen, I lose.

Also the given $(q_1,q_2)$ the function I apply on both of them to get $q\in \mathbb{Q}$ cannot be symmetric, otherwise I won't have an answer for $(q_2,q_1)$.

But there are so many possibilities and nothing I tried is a winning strategy, can you please give me a hint (not a full proof I probably miss some property or function)?

Can this be further generalized for every set of numbers $A$ and $A^2$ or every field at least?

1

There are 1 best solutions below

3
On

First, let us notice that an infinite lasting game cannot have a winning strategy for Duplicator. It is a fact that if Duplicator has a winning strategy in an infinite lasting game between two countable structures, then they are isomorphic. We can easily see that these structures are not isomorphic, e.g. because the operation $+$ is definable in the language (its graph itself is in the language), and $(\mathbb Q,+)$ and $(\mathbb Q^2,+)$ are not isomorphic because they don't have equal dimensions as vector spaces over $\mathbb Q$ (this is also a fact: an additive homomorphism between vector spaces over $\mathbb Q$ is $\mathbb Q$-linear).

But let us see this directly, because it gives a hint. Assume that Duplicator has a winning strategy in an infinite lasting game. Assume that Spoiler chooses $(1,0)$ in the first step, and Duplicator responds by $a$. Then Spoiler chooses $(0,1)$ in the second step, and Duplicator responds by $b$. Clearly $a,b\neq 0$, so we can write $a/b=m/n$, i.e. $na=mb$, for some integers $m,n$, and let us assume that $m,n>0$ (if not, one can make some obvious adjustments in the argument). In the next $n-1$ steps Spoiler chooses $2a,3a,\ldots,na$ respectively, and we see that in each of them Duplicator is forced to respond by $(2,0),(3,0),\ldots,(n,0)$. In the following $m-1$ steps Spoiler chooses $2b,3b,\ldots,mb$, and as before Duplicator is forced to respond by $(0,2),(0,3),\ldots,(0,m)$. But at this point Duplicator looses because he mapped $na=mb$ to two different elements $(n,0)$ and $(0,m)$. Thus Duplicator cannot have a winning strategy in an infinite lasting game.

But in order to prove elementary equivalence, Duplicator must have a winning strategy in $k$-steps games for every $k<\omega$. As the previous argument shows, the duration of the game, $k$, must play a role in Duplicator's strategy. E.g. in the previous argument if the game has less than $m+n+2$ steps, then we don't obtain the above contradiction (maybe we can obtain some other), so one part of Duplicator's strategy at the begging of the previous game should be to choose $b$ such that at least $m+n+2>k$ (but this is not the only part, of course).

The hint for the general solution would be the following. For a subset $A$ (of either $\mathbb Q$ or $\mathbb Q^2$), denote by $O_n(A)$ by recursively by: $$O_0(A)=\{0\}\cup A,\ \ \ \ \ O_{n+1}(A)=\{a+b,a-b,a/2\mid a,b\in O_n(A)\}.$$ (Here $0$ denotes the zero in the structure we are talking about, as well as the operations $+$,$-$, and $-/2$.) Basically, $O_n(A)$ is the set of elements which we can define by using $P$ in $n$ steps starting from $A$ (and formulae that make sense are $P(a,b,x)$, $P(b,x,a)$, $P(x,x,a)$). So, note that if we start with a finite set $A$, then $O_n(A)$ are also finite.

Assume that we are playing the $k$-steps game. Essentially, Duplicator's strategy is the following: at each step $i\leqslant k$, for already chosen $a_1,\ldots,a_{i-1}\in\mathbb Q$ and corresponding $f(a_1),\ldots,f(a_{i-1})\in\mathbb Q^2$, and by Spoiler given $a_i\in\mathbb Q$ (or $b_i\in\mathbb Q^2$, it doesn't really matter), Duplicator extends the mapping such that it has a unique lifting to an elementary bijection between $O_{k-i}(a_1,\ldots,a_i)$ and $O_{k-i}(f(a_1),\ldots,f(a_i))$.

Now try to prove that this is always possible (I hope it is true, I think that I see how to proceed, but I didn't write everything; finiteness of these sets is a key property).