Mixing
How to show that $mathbb{Q}$ and $mathbb{Q}^2$ are elementarily equivalent?
$begingroup$
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 $qinmathbb{Q}$ I initially though about choosing $(q,q)inmathbb{Q}^2$
But as soon as $(q,q')inmathbb{Q}^2$ with $qneq q'$ is chosen, I lose.
Also the given $(q_1,q_2)$ the function I apply on both of them to get $qin 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?
first-order-logic rational-numbers
asked Jan 21 at 8:50
LumonLumon
357
$endgroup$
add a comment |
$begingroup$
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 $qinmathbb{Q}$ I initially though about choosing $(q,q)inmathbb{Q}^2$
But as soon as $(q,q')inmathbb{Q}^2$ with $qneq q'$ is chosen, I lose.
Also the given $(q_1,q_2)$ the function I apply on both of them to get $qin 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?
first-order-logic rational-numbers
asked Jan 21 at 8:50
LumonLumon
357
$endgroup$
1
$begingroup$
I'm not familiar with Ehrenfeucht–Fraïssé games, so maybe I'm missing something, but Wikipedia says they are for structures with no functions symbols. Isn't "+" a function symbol?
$endgroup$
– Paul Sinclair
Jan 21 at 16:10
1
$begingroup$
Both share the same relation P, it uses + inside it, but + itself is not part of the structures. I guess you can imagine P as a black box taking 3 elements and returning either true or false regardless of how it is done.
$endgroup$
– Lumon
Jan 21 at 16:16
1
$begingroup$
Thanks. I should have realized that only $P$ was part of the structure.
$endgroup$
– Paul Sinclair
Jan 21 at 16:23
$begingroup$
Why can't you choose $(q,0)$ and $q+q'$?
$endgroup$
– Paul Sinclair
Jan 21 at 16:24
1
$begingroup$
Say he chooses $1$, then I choose $(1,0)$, then he chooses $(5,3)$ so I choose $8$ then he chooses $9$ and I choose $(9,0$), then I lose. Also if he chooses $(1,2)$ and then $(2,1)$ I won't be able to choose $3$ twice, so that is also a problem
$endgroup$
– Lumon
Jan 21 at 16:27
add a comment |
$begingroup$
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 $qinmathbb{Q}$ I initially though about choosing $(q,q)inmathbb{Q}^2$
But as soon as $(q,q')inmathbb{Q}^2$ with $qneq q'$ is chosen, I lose.
Also the given $(q_1,q_2)$ the function I apply on both of them to get $qin 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?
first-order-logic rational-numbers
asked Jan 21 at 8:50
LumonLumon
357
$endgroup$
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 $qinmathbb{Q}$ I initially though about choosing $(q,q)inmathbb{Q}^2$
But as soon as $(q,q')inmathbb{Q}^2$ with $qneq q'$ is chosen, I lose.
Also the given $(q_1,q_2)$ the function I apply on both of them to get $qin 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?
first-order-logic rational-numbers
first-order-logic rational-numbers
asked Jan 21 at 8:50
LumonLumon
357
asked Jan 21 at 8:50
LumonLumon
357
edited Jan 21 at 18:53
Lumon
asked Jan 21 at 8:50
LumonLumon
357
asked Jan 21 at 8:50
LumonLumon
357
asked Jan 21 at 8:50
LumonLumon
357
357
1
$begingroup$
I'm not familiar with Ehrenfeucht–Fraïssé games, so maybe I'm missing something, but Wikipedia says they are for structures with no functions symbols. Isn't "+" a function symbol?
$endgroup$
– Paul Sinclair
Jan 21 at 16:10
1
$begingroup$
Both share the same relation P, it uses + inside it, but + itself is not part of the structures. I guess you can imagine P as a black box taking 3 elements and returning either true or false regardless of how it is done.
$endgroup$
– Lumon
Jan 21 at 16:16
1
$begingroup$
Thanks. I should have realized that only $P$ was part of the structure.
$endgroup$
– Paul Sinclair
Jan 21 at 16:23
$begingroup$
Why can't you choose $(q,0)$ and $q+q'$?
$endgroup$
– Paul Sinclair
Jan 21 at 16:24
1
$begingroup$
Say he chooses $1$, then I choose $(1,0)$, then he chooses $(5,3)$ so I choose $8$ then he chooses $9$ and I choose $(9,0$), then I lose. Also if he chooses $(1,2)$ and then $(2,1)$ I won't be able to choose $3$ twice, so that is also a problem
$endgroup$
– Lumon
Jan 21 at 16:27
add a comment |
1
$begingroup$
I'm not familiar with Ehrenfeucht–Fraïssé games, so maybe I'm missing something, but Wikipedia says they are for structures with no functions symbols. Isn't "+" a function symbol?
$endgroup$
– Paul Sinclair
Jan 21 at 16:10
1
$begingroup$
Both share the same relation P, it uses + inside it, but + itself is not part of the structures. I guess you can imagine P as a black box taking 3 elements and returning either true or false regardless of how it is done.
$endgroup$
– Lumon
Jan 21 at 16:16
1
$begingroup$
Thanks. I should have realized that only $P$ was part of the structure.
$endgroup$
– Paul Sinclair
Jan 21 at 16:23
$begingroup$
Why can't you choose $(q,0)$ and $q+q'$?
$endgroup$
– Paul Sinclair
Jan 21 at 16:24
1
$begingroup$
Say he chooses $1$, then I choose $(1,0)$, then he chooses $(5,3)$ so I choose $8$ then he chooses $9$ and I choose $(9,0$), then I lose. Also if he chooses $(1,2)$ and then $(2,1)$ I won't be able to choose $3$ twice, so that is also a problem
$endgroup$
– Lumon
Jan 21 at 16:27
1
1
$begingroup$
I'm not familiar with Ehrenfeucht–Fraïssé games, so maybe I'm missing something, but Wikipedia says they are for structures with no functions symbols. Isn't "+" a function symbol?
$endgroup$
– Paul Sinclair
Jan 21 at 16:10
$begingroup$
I'm not familiar with Ehrenfeucht–Fraïssé games, so maybe I'm missing something, but Wikipedia says they are for structures with no functions symbols. Isn't "+" a function symbol?
$endgroup$
– Paul Sinclair
Jan 21 at 16:10
1
1
$begingroup$
Both share the same relation P, it uses + inside it, but + itself is not part of the structures. I guess you can imagine P as a black box taking 3 elements and returning either true or false regardless of how it is done.
$endgroup$
– Lumon
Jan 21 at 16:16
$begingroup$
Both share the same relation P, it uses + inside it, but + itself is not part of the structures. I guess you can imagine P as a black box taking 3 elements and returning either true or false regardless of how it is done.
$endgroup$
– Lumon
Jan 21 at 16:16
1
1
$begingroup$
Thanks. I should have realized that only $P$ was part of the structure.
$endgroup$
– Paul Sinclair
Jan 21 at 16:23
$begingroup$
Thanks. I should have realized that only $P$ was part of the structure.
$endgroup$
– Paul Sinclair
Jan 21 at 16:23
$begingroup$
Why can't you choose $(q,0)$ and $q+q'$?
$endgroup$
– Paul Sinclair
Jan 21 at 16:24
$begingroup$
Why can't you choose $(q,0)$ and $q+q'$?
$endgroup$
– Paul Sinclair
Jan 21 at 16:24
1
1
$begingroup$
Say he chooses $1$, then I choose $(1,0)$, then he chooses $(5,3)$ so I choose $8$ then he chooses $9$ and I choose $(9,0$), then I lose. Also if he chooses $(1,2)$ and then $(2,1)$ I won't be able to choose $3$ twice, so that is also a problem
$endgroup$
– Lumon
Jan 21 at 16:27
$begingroup$
Say he chooses $1$, then I choose $(1,0)$, then he chooses $(5,3)$ so I choose $8$ then he chooses $9$ and I choose $(9,0$), then I lose. Also if he chooses $(1,2)$ and then $(2,1)$ I won't be able to choose $3$ twice, so that is also a problem
$endgroup$
– Lumon
Jan 21 at 16:27
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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,bneq 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/2mid a,bin 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 $ileqslant k$, for already chosen $a_1,ldots,a_{i-1}inmathbb Q$ and corresponding $f(a_1),ldots,f(a_{i-1})inmathbb Q^2$, and by Spoiler given $a_iinmathbb Q$ (or $b_iinmathbb 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).
answered Jan 22 at 12:54
SMMSMM
2,513510
$endgroup$
$begingroup$
Thanks a lot for the detailed answer, unfortunately this is way more advanced than my level, I don't know what a lifting is (with wikipedia) or what this method is, I only need to find an explicit strategy (get $a$ give $(q,q')$ get $(a,b)$ give $q$) but I appreciate the help a lot!
$endgroup$
– Lumon
Jan 22 at 13:13
1
$begingroup$
@Lumon Maybe I overcomplicated things. At the first step, for a given $a$ you can basically choose any $f(a)$ (or vice versa). Now there is the obvious way how to expand $f$ to $O_{k-1}(a)$ to $O_{k-1}(f(a))$. E.g. $2a$ maps to $2f(a)$, $a/2$ maps to $f(a)/2$, then $2a+a/2$ maps to $2f(a)+2f(a)/2$, etc. In the second step, for a given $a'$ (or $b'$), if $a'in O_{k-1}(a)$ then you already know what $f(a')$ is. If $a'notin O_{k-1}(a)$ then we choose $f(a')$ in such a way that $O_{k-2}(a,a')$ and $O_{k-2}(f(a),f(a'))$ are "isomorphic". Thing is to check that this can be done, and then proceed.
$endgroup$
– SMM
Jan 22 at 13:32
1
$begingroup$
@Lumon I don't think that there is an "easy" way to construct the winning strategy. Also, it is important to note that the strategy must depend on $k$, because the strategy for the game with $omega$ steps is impossible.
$endgroup$
– SMM
Jan 22 at 13:37
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3081645%2fhow-to-show-that-mathbbq-and-mathbbq2-are-elementarily-equivalent%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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,bneq 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/2mid a,bin 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 $ileqslant k$, for already chosen $a_1,ldots,a_{i-1}inmathbb Q$ and corresponding $f(a_1),ldots,f(a_{i-1})inmathbb Q^2$, and by Spoiler given $a_iinmathbb Q$ (or $b_iinmathbb 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).
answered Jan 22 at 12:54
SMMSMM
2,513510
$endgroup$
$begingroup$
Thanks a lot for the detailed answer, unfortunately this is way more advanced than my level, I don't know what a lifting is (with wikipedia) or what this method is, I only need to find an explicit strategy (get $a$ give $(q,q')$ get $(a,b)$ give $q$) but I appreciate the help a lot!
$endgroup$
– Lumon
Jan 22 at 13:13
1
$begingroup$
@Lumon Maybe I overcomplicated things. At the first step, for a given $a$ you can basically choose any $f(a)$ (or vice versa). Now there is the obvious way how to expand $f$ to $O_{k-1}(a)$ to $O_{k-1}(f(a))$. E.g. $2a$ maps to $2f(a)$, $a/2$ maps to $f(a)/2$, then $2a+a/2$ maps to $2f(a)+2f(a)/2$, etc. In the second step, for a given $a'$ (or $b'$), if $a'in O_{k-1}(a)$ then you already know what $f(a')$ is. If $a'notin O_{k-1}(a)$ then we choose $f(a')$ in such a way that $O_{k-2}(a,a')$ and $O_{k-2}(f(a),f(a'))$ are "isomorphic". Thing is to check that this can be done, and then proceed.
$endgroup$
– SMM
Jan 22 at 13:32
1
$begingroup$
@Lumon I don't think that there is an "easy" way to construct the winning strategy. Also, it is important to note that the strategy must depend on $k$, because the strategy for the game with $omega$ steps is impossible.
$endgroup$
– SMM
Jan 22 at 13:37
add a comment |
$begingroup$
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,bneq 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/2mid a,bin 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 $ileqslant k$, for already chosen $a_1,ldots,a_{i-1}inmathbb Q$ and corresponding $f(a_1),ldots,f(a_{i-1})inmathbb Q^2$, and by Spoiler given $a_iinmathbb Q$ (or $b_iinmathbb 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).
answered Jan 22 at 12:54
SMMSMM
2,513510
$endgroup$
$begingroup$
Thanks a lot for the detailed answer, unfortunately this is way more advanced than my level, I don't know what a lifting is (with wikipedia) or what this method is, I only need to find an explicit strategy (get $a$ give $(q,q')$ get $(a,b)$ give $q$) but I appreciate the help a lot!
$endgroup$
– Lumon
Jan 22 at 13:13
1
$begingroup$
@Lumon Maybe I overcomplicated things. At the first step, for a given $a$ you can basically choose any $f(a)$ (or vice versa). Now there is the obvious way how to expand $f$ to $O_{k-1}(a)$ to $O_{k-1}(f(a))$. E.g. $2a$ maps to $2f(a)$, $a/2$ maps to $f(a)/2$, then $2a+a/2$ maps to $2f(a)+2f(a)/2$, etc. In the second step, for a given $a'$ (or $b'$), if $a'in O_{k-1}(a)$ then you already know what $f(a')$ is. If $a'notin O_{k-1}(a)$ then we choose $f(a')$ in such a way that $O_{k-2}(a,a')$ and $O_{k-2}(f(a),f(a'))$ are "isomorphic". Thing is to check that this can be done, and then proceed.
$endgroup$
– SMM
Jan 22 at 13:32
1
$begingroup$
@Lumon I don't think that there is an "easy" way to construct the winning strategy. Also, it is important to note that the strategy must depend on $k$, because the strategy for the game with $omega$ steps is impossible.
$endgroup$
– SMM
Jan 22 at 13:37
add a comment |
$begingroup$
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,bneq 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/2mid a,bin 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 $ileqslant k$, for already chosen $a_1,ldots,a_{i-1}inmathbb Q$ and corresponding $f(a_1),ldots,f(a_{i-1})inmathbb Q^2$, and by Spoiler given $a_iinmathbb Q$ (or $b_iinmathbb 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).
answered Jan 22 at 12:54
SMMSMM
2,513510
$endgroup$
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,bneq 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/2mid a,bin 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 $ileqslant k$, for already chosen $a_1,ldots,a_{i-1}inmathbb Q$ and corresponding $f(a_1),ldots,f(a_{i-1})inmathbb Q^2$, and by Spoiler given $a_iinmathbb Q$ (or $b_iinmathbb 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).
answered Jan 22 at 12:54
SMMSMM
2,513510
answered Jan 22 at 12:54
SMMSMM
2,513510
answered Jan 22 at 12:54
SMMSMM
2,513510
answered Jan 22 at 12:54
SMMSMM
2,513510
2,513510
$begingroup$
Thanks a lot for the detailed answer, unfortunately this is way more advanced than my level, I don't know what a lifting is (with wikipedia) or what this method is, I only need to find an explicit strategy (get $a$ give $(q,q')$ get $(a,b)$ give $q$) but I appreciate the help a lot!
$endgroup$
– Lumon
Jan 22 at 13:13
1
$begingroup$
@Lumon Maybe I overcomplicated things. At the first step, for a given $a$ you can basically choose any $f(a)$ (or vice versa). Now there is the obvious way how to expand $f$ to $O_{k-1}(a)$ to $O_{k-1}(f(a))$. E.g. $2a$ maps to $2f(a)$, $a/2$ maps to $f(a)/2$, then $2a+a/2$ maps to $2f(a)+2f(a)/2$, etc. In the second step, for a given $a'$ (or $b'$), if $a'in O_{k-1}(a)$ then you already know what $f(a')$ is. If $a'notin O_{k-1}(a)$ then we choose $f(a')$ in such a way that $O_{k-2}(a,a')$ and $O_{k-2}(f(a),f(a'))$ are "isomorphic". Thing is to check that this can be done, and then proceed.
$endgroup$
– SMM
Jan 22 at 13:32
1
$begingroup$
@Lumon I don't think that there is an "easy" way to construct the winning strategy. Also, it is important to note that the strategy must depend on $k$, because the strategy for the game with $omega$ steps is impossible.
$endgroup$
– SMM
Jan 22 at 13:37
add a comment |
$begingroup$
Thanks a lot for the detailed answer, unfortunately this is way more advanced than my level, I don't know what a lifting is (with wikipedia) or what this method is, I only need to find an explicit strategy (get $a$ give $(q,q')$ get $(a,b)$ give $q$) but I appreciate the help a lot!
$endgroup$
– Lumon
Jan 22 at 13:13
1
$begingroup$
@Lumon Maybe I overcomplicated things. At the first step, for a given $a$ you can basically choose any $f(a)$ (or vice versa). Now there is the obvious way how to expand $f$ to $O_{k-1}(a)$ to $O_{k-1}(f(a))$. E.g. $2a$ maps to $2f(a)$, $a/2$ maps to $f(a)/2$, then $2a+a/2$ maps to $2f(a)+2f(a)/2$, etc. In the second step, for a given $a'$ (or $b'$), if $a'in O_{k-1}(a)$ then you already know what $f(a')$ is. If $a'notin O_{k-1}(a)$ then we choose $f(a')$ in such a way that $O_{k-2}(a,a')$ and $O_{k-2}(f(a),f(a'))$ are "isomorphic". Thing is to check that this can be done, and then proceed.
$endgroup$
– SMM
Jan 22 at 13:32
1
$begingroup$
@Lumon I don't think that there is an "easy" way to construct the winning strategy. Also, it is important to note that the strategy must depend on $k$, because the strategy for the game with $omega$ steps is impossible.
$endgroup$
– SMM
Jan 22 at 13:37
$begingroup$
Thanks a lot for the detailed answer, unfortunately this is way more advanced than my level, I don't know what a lifting is (with wikipedia) or what this method is, I only need to find an explicit strategy (get $a$ give $(q,q')$ get $(a,b)$ give $q$) but I appreciate the help a lot!
$endgroup$
– Lumon
Jan 22 at 13:13
$begingroup$
Thanks a lot for the detailed answer, unfortunately this is way more advanced than my level, I don't know what a lifting is (with wikipedia) or what this method is, I only need to find an explicit strategy (get $a$ give $(q,q')$ get $(a,b)$ give $q$) but I appreciate the help a lot!
$endgroup$
– Lumon
Jan 22 at 13:13
1
1
$begingroup$
@Lumon Maybe I overcomplicated things. At the first step, for a given $a$ you can basically choose any $f(a)$ (or vice versa). Now there is the obvious way how to expand $f$ to $O_{k-1}(a)$ to $O_{k-1}(f(a))$. E.g. $2a$ maps to $2f(a)$, $a/2$ maps to $f(a)/2$, then $2a+a/2$ maps to $2f(a)+2f(a)/2$, etc. In the second step, for a given $a'$ (or $b'$), if $a'in O_{k-1}(a)$ then you already know what $f(a')$ is. If $a'notin O_{k-1}(a)$ then we choose $f(a')$ in such a way that $O_{k-2}(a,a')$ and $O_{k-2}(f(a),f(a'))$ are "isomorphic". Thing is to check that this can be done, and then proceed.
$endgroup$
– SMM
Jan 22 at 13:32
$begingroup$
@Lumon Maybe I overcomplicated things. At the first step, for a given $a$ you can basically choose any $f(a)$ (or vice versa). Now there is the obvious way how to expand $f$ to $O_{k-1}(a)$ to $O_{k-1}(f(a))$. E.g. $2a$ maps to $2f(a)$, $a/2$ maps to $f(a)/2$, then $2a+a/2$ maps to $2f(a)+2f(a)/2$, etc. In the second step, for a given $a'$ (or $b'$), if $a'in O_{k-1}(a)$ then you already know what $f(a')$ is. If $a'notin O_{k-1}(a)$ then we choose $f(a')$ in such a way that $O_{k-2}(a,a')$ and $O_{k-2}(f(a),f(a'))$ are "isomorphic". Thing is to check that this can be done, and then proceed.
$endgroup$
– SMM
Jan 22 at 13:32
1
1
$begingroup$
@Lumon I don't think that there is an "easy" way to construct the winning strategy. Also, it is important to note that the strategy must depend on $k$, because the strategy for the game with $omega$ steps is impossible.
$endgroup$
– SMM
Jan 22 at 13:37
$begingroup$
@Lumon I don't think that there is an "easy" way to construct the winning strategy. Also, it is important to note that the strategy must depend on $k$, because the strategy for the game with $omega$ steps is impossible.
$endgroup$
– SMM
Jan 22 at 13:37
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3081645%2fhow-to-show-that-mathbbq-and-mathbbq2-are-elementarily-equivalent%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I'm not familiar with Ehrenfeucht–Fraïssé games, so maybe I'm missing something, but Wikipedia says they are for structures with no functions symbols. Isn't "+" a function symbol?
$endgroup$
– Paul Sinclair
Jan 21 at 16:10
1
$begingroup$
Both share the same relation P, it uses + inside it, but + itself is not part of the structures. I guess you can imagine P as a black box taking 3 elements and returning either true or false regardless of how it is done.
$endgroup$
– Lumon
Jan 21 at 16:16
1
$begingroup$
Thanks. I should have realized that only $P$ was part of the structure.
$endgroup$
– Paul Sinclair
Jan 21 at 16:23
$begingroup$
Why can't you choose $(q,0)$ and $q+q'$?
$endgroup$
– Paul Sinclair
Jan 21 at 16:24
1
$begingroup$
Say he chooses $1$, then I choose $(1,0)$, then he chooses $(5,3)$ so I choose $8$ then he chooses $9$ and I choose $(9,0$), then I lose. Also if he chooses $(1,2)$ and then $(2,1)$ I won't be able to choose $3$ twice, so that is also a problem
$endgroup$
– Lumon
Jan 21 at 16:27