Is the union of a chain of elementary embeddings elementary?Elementary Embeddings and Relative ConstructibilityElementary extensions and type spacesOn Joyal's completeness theorem for first order logicFrom elementary equivalence to isomorphismIf two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?How many elementary embeddings can there be?When is a direct limit of nice models of set theory is again a model of set theory?Amalgamation via elementary embeddingsQuantifier elimination in uncountable elementary “Fraïssé classes”

Is the union of a chain of elementary embeddings elementary?


Elementary Embeddings and Relative ConstructibilityElementary extensions and type spacesOn Joyal's completeness theorem for first order logicFrom elementary equivalence to isomorphismIf two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?How many elementary embeddings can there be?When is a direct limit of nice models of set theory is again a model of set theory?Amalgamation via elementary embeddingsQuantifier elimination in uncountable elementary “Fraïssé classes”













12












$begingroup$


I am a little confused about what I think must be either a standard theorem or a standard counterexample in model theory, and I am hoping that the MathOverflow model theorists can help sort me out about which way it goes.



My situation is that I have a chain of submodels, which is not necessarily an elementary chain,



$$M_0subseteq M_1subseteq M_2subseteqcdots$$



and I have elementary embeddings $j_n:M_nto M_n$, which cohere in the sense that $j_n=j_n+1upharpoonright M_n$. So there is a natural limit model $M=bigcup_n M_n$ and limit embedding $j:Mto M$, where $j(x)$ is the eventual common value of $j_n(x)$.



Question. Is the limit map $j:Mto M$ necessarily elementary?



A natural generalization would be a coherent system of elementary embeddings $j_n:M_nto N_n$, with possibly different models on each side. The question is whether the limit embedding $j:Mto N$ is elementary, where $M=bigcup_n M_n$, $N=bigcup_n N_n$ and $j=bigcup_n j_n$. And of course one could generalize to arbitrary chains or indeed, arbitrary directed systems of coherent elementary embeddings, instead of just $omega$-chains.



I thought either there should be an easy counterexample or an easy proof, perhaps via Ehrenfeucht-Fraïssé games?










share|cite|improve this question











$endgroup$









  • 3




    $begingroup$
    The generalization is not true: For example, you could take $M_n = (mathbbN,<)$ for all $n$, and $N_n = (mathbbNsqcup frac1nmathbbZ,<)$. Then $M_n preceq N_n$ for all $n$, but $bigcup_n M_n notpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter contains a copy of $mathbbQ$, hence isn't discrete. I think there should be a counterexample to the original question as well, but I haven't come up with one yet. Of course, requiring $M_n = N_n$ means that any funny business in the union of the codomains happens in the union of the domains as well...
    $endgroup$
    – Alex Kruckman
    7 hours ago











  • $begingroup$
    Can't you do some form of skolemnization of a target sentence wiith respect to some M_n, show j acts nicely on individuals witnessing the skolemnization by showing it acts nicely on a large enough submodel, to get the sentence to be preserved by j? (Seeing Alex's comment now suggests "No".) Gerhard "Or Are Elementary Chains Needed?" Paseman
    $endgroup$
    – Gerhard Paseman
    7 hours ago











  • $begingroup$
    Alex, very nice example! (I guess you intend that the Z copy is on top.) Why not post the example as an answer?
    $endgroup$
    – Joel David Hamkins
    6 hours ago







  • 1




    $begingroup$
    @JoelDavidHamkins Thanks. Yes, the copies of $mathbbZ$ come after the copies of $mathbbN$ in the order. I was waiting to post an answer until I came up with a counterexample to the main question - but if I don't manage to do that, I'll convert my comment into an answer.
    $endgroup$
    – Alex Kruckman
    6 hours ago















12












$begingroup$


I am a little confused about what I think must be either a standard theorem or a standard counterexample in model theory, and I am hoping that the MathOverflow model theorists can help sort me out about which way it goes.



My situation is that I have a chain of submodels, which is not necessarily an elementary chain,



$$M_0subseteq M_1subseteq M_2subseteqcdots$$



and I have elementary embeddings $j_n:M_nto M_n$, which cohere in the sense that $j_n=j_n+1upharpoonright M_n$. So there is a natural limit model $M=bigcup_n M_n$ and limit embedding $j:Mto M$, where $j(x)$ is the eventual common value of $j_n(x)$.



Question. Is the limit map $j:Mto M$ necessarily elementary?



A natural generalization would be a coherent system of elementary embeddings $j_n:M_nto N_n$, with possibly different models on each side. The question is whether the limit embedding $j:Mto N$ is elementary, where $M=bigcup_n M_n$, $N=bigcup_n N_n$ and $j=bigcup_n j_n$. And of course one could generalize to arbitrary chains or indeed, arbitrary directed systems of coherent elementary embeddings, instead of just $omega$-chains.



I thought either there should be an easy counterexample or an easy proof, perhaps via Ehrenfeucht-Fraïssé games?










share|cite|improve this question











$endgroup$









  • 3




    $begingroup$
    The generalization is not true: For example, you could take $M_n = (mathbbN,<)$ for all $n$, and $N_n = (mathbbNsqcup frac1nmathbbZ,<)$. Then $M_n preceq N_n$ for all $n$, but $bigcup_n M_n notpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter contains a copy of $mathbbQ$, hence isn't discrete. I think there should be a counterexample to the original question as well, but I haven't come up with one yet. Of course, requiring $M_n = N_n$ means that any funny business in the union of the codomains happens in the union of the domains as well...
    $endgroup$
    – Alex Kruckman
    7 hours ago











  • $begingroup$
    Can't you do some form of skolemnization of a target sentence wiith respect to some M_n, show j acts nicely on individuals witnessing the skolemnization by showing it acts nicely on a large enough submodel, to get the sentence to be preserved by j? (Seeing Alex's comment now suggests "No".) Gerhard "Or Are Elementary Chains Needed?" Paseman
    $endgroup$
    – Gerhard Paseman
    7 hours ago











  • $begingroup$
    Alex, very nice example! (I guess you intend that the Z copy is on top.) Why not post the example as an answer?
    $endgroup$
    – Joel David Hamkins
    6 hours ago







  • 1




    $begingroup$
    @JoelDavidHamkins Thanks. Yes, the copies of $mathbbZ$ come after the copies of $mathbbN$ in the order. I was waiting to post an answer until I came up with a counterexample to the main question - but if I don't manage to do that, I'll convert my comment into an answer.
    $endgroup$
    – Alex Kruckman
    6 hours ago













12












12








12


1



$begingroup$


I am a little confused about what I think must be either a standard theorem or a standard counterexample in model theory, and I am hoping that the MathOverflow model theorists can help sort me out about which way it goes.



My situation is that I have a chain of submodels, which is not necessarily an elementary chain,



$$M_0subseteq M_1subseteq M_2subseteqcdots$$



and I have elementary embeddings $j_n:M_nto M_n$, which cohere in the sense that $j_n=j_n+1upharpoonright M_n$. So there is a natural limit model $M=bigcup_n M_n$ and limit embedding $j:Mto M$, where $j(x)$ is the eventual common value of $j_n(x)$.



Question. Is the limit map $j:Mto M$ necessarily elementary?



A natural generalization would be a coherent system of elementary embeddings $j_n:M_nto N_n$, with possibly different models on each side. The question is whether the limit embedding $j:Mto N$ is elementary, where $M=bigcup_n M_n$, $N=bigcup_n N_n$ and $j=bigcup_n j_n$. And of course one could generalize to arbitrary chains or indeed, arbitrary directed systems of coherent elementary embeddings, instead of just $omega$-chains.



I thought either there should be an easy counterexample or an easy proof, perhaps via Ehrenfeucht-Fraïssé games?










share|cite|improve this question











$endgroup$




I am a little confused about what I think must be either a standard theorem or a standard counterexample in model theory, and I am hoping that the MathOverflow model theorists can help sort me out about which way it goes.



My situation is that I have a chain of submodels, which is not necessarily an elementary chain,



$$M_0subseteq M_1subseteq M_2subseteqcdots$$



and I have elementary embeddings $j_n:M_nto M_n$, which cohere in the sense that $j_n=j_n+1upharpoonright M_n$. So there is a natural limit model $M=bigcup_n M_n$ and limit embedding $j:Mto M$, where $j(x)$ is the eventual common value of $j_n(x)$.



Question. Is the limit map $j:Mto M$ necessarily elementary?



A natural generalization would be a coherent system of elementary embeddings $j_n:M_nto N_n$, with possibly different models on each side. The question is whether the limit embedding $j:Mto N$ is elementary, where $M=bigcup_n M_n$, $N=bigcup_n N_n$ and $j=bigcup_n j_n$. And of course one could generalize to arbitrary chains or indeed, arbitrary directed systems of coherent elementary embeddings, instead of just $omega$-chains.



I thought either there should be an easy counterexample or an easy proof, perhaps via Ehrenfeucht-Fraïssé games?







lo.logic model-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 11 hours ago







Joel David Hamkins

















asked 12 hours ago









Joel David HamkinsJoel David Hamkins

168k27 gold badges518 silver badges903 bronze badges




168k27 gold badges518 silver badges903 bronze badges










  • 3




    $begingroup$
    The generalization is not true: For example, you could take $M_n = (mathbbN,<)$ for all $n$, and $N_n = (mathbbNsqcup frac1nmathbbZ,<)$. Then $M_n preceq N_n$ for all $n$, but $bigcup_n M_n notpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter contains a copy of $mathbbQ$, hence isn't discrete. I think there should be a counterexample to the original question as well, but I haven't come up with one yet. Of course, requiring $M_n = N_n$ means that any funny business in the union of the codomains happens in the union of the domains as well...
    $endgroup$
    – Alex Kruckman
    7 hours ago











  • $begingroup$
    Can't you do some form of skolemnization of a target sentence wiith respect to some M_n, show j acts nicely on individuals witnessing the skolemnization by showing it acts nicely on a large enough submodel, to get the sentence to be preserved by j? (Seeing Alex's comment now suggests "No".) Gerhard "Or Are Elementary Chains Needed?" Paseman
    $endgroup$
    – Gerhard Paseman
    7 hours ago











  • $begingroup$
    Alex, very nice example! (I guess you intend that the Z copy is on top.) Why not post the example as an answer?
    $endgroup$
    – Joel David Hamkins
    6 hours ago







  • 1




    $begingroup$
    @JoelDavidHamkins Thanks. Yes, the copies of $mathbbZ$ come after the copies of $mathbbN$ in the order. I was waiting to post an answer until I came up with a counterexample to the main question - but if I don't manage to do that, I'll convert my comment into an answer.
    $endgroup$
    – Alex Kruckman
    6 hours ago












  • 3




    $begingroup$
    The generalization is not true: For example, you could take $M_n = (mathbbN,<)$ for all $n$, and $N_n = (mathbbNsqcup frac1nmathbbZ,<)$. Then $M_n preceq N_n$ for all $n$, but $bigcup_n M_n notpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter contains a copy of $mathbbQ$, hence isn't discrete. I think there should be a counterexample to the original question as well, but I haven't come up with one yet. Of course, requiring $M_n = N_n$ means that any funny business in the union of the codomains happens in the union of the domains as well...
    $endgroup$
    – Alex Kruckman
    7 hours ago











  • $begingroup$
    Can't you do some form of skolemnization of a target sentence wiith respect to some M_n, show j acts nicely on individuals witnessing the skolemnization by showing it acts nicely on a large enough submodel, to get the sentence to be preserved by j? (Seeing Alex's comment now suggests "No".) Gerhard "Or Are Elementary Chains Needed?" Paseman
    $endgroup$
    – Gerhard Paseman
    7 hours ago











  • $begingroup$
    Alex, very nice example! (I guess you intend that the Z copy is on top.) Why not post the example as an answer?
    $endgroup$
    – Joel David Hamkins
    6 hours ago







  • 1




    $begingroup$
    @JoelDavidHamkins Thanks. Yes, the copies of $mathbbZ$ come after the copies of $mathbbN$ in the order. I was waiting to post an answer until I came up with a counterexample to the main question - but if I don't manage to do that, I'll convert my comment into an answer.
    $endgroup$
    – Alex Kruckman
    6 hours ago







3




3




$begingroup$
The generalization is not true: For example, you could take $M_n = (mathbbN,<)$ for all $n$, and $N_n = (mathbbNsqcup frac1nmathbbZ,<)$. Then $M_n preceq N_n$ for all $n$, but $bigcup_n M_n notpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter contains a copy of $mathbbQ$, hence isn't discrete. I think there should be a counterexample to the original question as well, but I haven't come up with one yet. Of course, requiring $M_n = N_n$ means that any funny business in the union of the codomains happens in the union of the domains as well...
$endgroup$
– Alex Kruckman
7 hours ago





$begingroup$
The generalization is not true: For example, you could take $M_n = (mathbbN,<)$ for all $n$, and $N_n = (mathbbNsqcup frac1nmathbbZ,<)$. Then $M_n preceq N_n$ for all $n$, but $bigcup_n M_n notpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter contains a copy of $mathbbQ$, hence isn't discrete. I think there should be a counterexample to the original question as well, but I haven't come up with one yet. Of course, requiring $M_n = N_n$ means that any funny business in the union of the codomains happens in the union of the domains as well...
$endgroup$
– Alex Kruckman
7 hours ago













$begingroup$
Can't you do some form of skolemnization of a target sentence wiith respect to some M_n, show j acts nicely on individuals witnessing the skolemnization by showing it acts nicely on a large enough submodel, to get the sentence to be preserved by j? (Seeing Alex's comment now suggests "No".) Gerhard "Or Are Elementary Chains Needed?" Paseman
$endgroup$
– Gerhard Paseman
7 hours ago





$begingroup$
Can't you do some form of skolemnization of a target sentence wiith respect to some M_n, show j acts nicely on individuals witnessing the skolemnization by showing it acts nicely on a large enough submodel, to get the sentence to be preserved by j? (Seeing Alex's comment now suggests "No".) Gerhard "Or Are Elementary Chains Needed?" Paseman
$endgroup$
– Gerhard Paseman
7 hours ago













$begingroup$
Alex, very nice example! (I guess you intend that the Z copy is on top.) Why not post the example as an answer?
$endgroup$
– Joel David Hamkins
6 hours ago





$begingroup$
Alex, very nice example! (I guess you intend that the Z copy is on top.) Why not post the example as an answer?
$endgroup$
– Joel David Hamkins
6 hours ago





1




1




$begingroup$
@JoelDavidHamkins Thanks. Yes, the copies of $mathbbZ$ come after the copies of $mathbbN$ in the order. I was waiting to post an answer until I came up with a counterexample to the main question - but if I don't manage to do that, I'll convert my comment into an answer.
$endgroup$
– Alex Kruckman
6 hours ago




$begingroup$
@JoelDavidHamkins Thanks. Yes, the copies of $mathbbZ$ come after the copies of $mathbbN$ in the order. I was waiting to post an answer until I came up with a counterexample to the main question - but if I don't manage to do that, I'll convert my comment into an answer.
$endgroup$
– Alex Kruckman
6 hours ago










2 Answers
2






active

oldest

votes


















4














$begingroup$

Here is a counterexample to your "natural generalization":
Let $A$ and $B$ be (countably) infinite sets, with $Asubseteq B$, $Bsetminus A$ infinite.



Let $M_0= (omegatimes A,<)$ be the structure where $(n,a)<(m,b)$ iff $n<m $ and $a=b$ -- countably many $omega$ columns next to each other. Similarly let $N_0:= (omegatimes B, <)$, and let $j_0$ be the inclusion map.



Let $M_k= M_0$, and $N_k = (omega times A )cup (omega cup -1,ldots, -ktimes (Bsetminus A))$, again with the obvious order. So the columns with "indices" in $Bsetminus A$ become longer, but the map $j_k=j_0$ is still elementary since it does not "see" those columns.



But the limit structures $M$ and $N$ different theories: in $N$ there are elements which have no minimal element below them.






share|cite|improve this answer









$endgroup$














  • $begingroup$
    I see that Alex Kruckman came up with a similar counterexample a few minutes before me.
    $endgroup$
    – Goldstern
    7 hours ago











  • $begingroup$
    Very nice! I had been trying to make such a counterexample to the generalization, with all the first models the same, just as you had done, but I hadn't yet managed. I was working with DLOs and discrete order combinations, but your method of separate columns is very clear.
    $endgroup$
    – Joel David Hamkins
    7 hours ago


















4














$begingroup$

First I'll give a counterexample to the natural generalization, adapted from my earlier comment:



Let $M_n = (mathbbN,<)$ for all $n$, and let $N_n = (mathbbNsqcup frac1n!mathbbZ,<)$, where all elements of $frac1n!mathbbZ$ are greater than all elements of $mathbbN$ in the order. Note that each $N_n$ is isomorphic to $(mathbbNsqcupmathbbZ,<)$, and there is a natural inclusion $N_nsubseteq N_n+1$ for all $n$, since $frac1n!mathbbZ subseteq frac1(n+1)!mathbbZ$ as subsets of $mathbbQ$.



Now $M_npreceq N_n$ for all $n$, but $bigcup_n M_nnotpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter is $(mathbbNsqcupmathbbQ,<)$, which is not discrete.




Now I'll explain how to turn any counterexample to the natural generalization into a counterexample to the original question.



Suppose we have a coherent system of elementary embeddings $j_ncolon M_n to N_n$ such that the limit map $jcolon Mto N$ is not elementary. Let $L$ be the language of this counterexample, which we assume to be relational, and let $L' = Lcup E$, where $E$ is a new binary relation.



For each $n$, we construct a structure $M^*_n$ as follows: $E$ is an equivalence relation with countably many classes, which we denote by $(C_i)_iin mathbbZ$. We interpret the relations from $L$ on each class $C_i$ so that $C_i$ is a copy of $M_n$ when $ileq 0$ and a copy of $N_n$ when $i > 0$. There are no relations between the classes.



There is a natural inclusion $M_n^*subseteq M_n+1^*$ for all $n$, in which each class $C_i$ in $M_n^*$ is included in to the class $C_i$ in $M_n+1^*$ according to the inclusions $M_nsubseteq M_n+1$ and $N_nsubseteq N_n+1$.



Let $j_n^*colon M^*_nto M^*_n$ map $C_i$ to $C_i+1$ as the identity on $M_n$ for all $i<0$, as the identity on $N_n$ for all $i>0$, and as $j_n colon M_nto N_n$ for $i = 0$. Then $j_n^*$ is an elementary embedding, and $j_n = j_n+1restriction M_n^*$.



In the limit, $M^* = bigcup_n M_n^*$ has equivalence classes such that $C_i$ is a copy of $M$ when $ileq 0$ and a copy of $N$ when $i>0$. And the limit map $j^*colon M^*to M^*$ maps $C_i$ to $C_i+1$ as the identity on $M$ for all $i<0$, as the identity on $N$ for all $i>0$, and as $jcolon Mto N$ for $i=0$. This $j^*$ is not elementary, since an $L$-formula whose truth is not preserved by $j$ can be relativized to the equivalence class $C_0$ to give an $L'$-formula whose truth is not preserved by $j^*$.






share|cite|improve this answer











$endgroup$

















    Your Answer








    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "504"
    ;
    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/4.0/"u003ecc by-sa 4.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
    );



    );














    draft saved

    draft discarded
















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f340275%2fis-the-union-of-a-chain-of-elementary-embeddings-elementary%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    4














    $begingroup$

    Here is a counterexample to your "natural generalization":
    Let $A$ and $B$ be (countably) infinite sets, with $Asubseteq B$, $Bsetminus A$ infinite.



    Let $M_0= (omegatimes A,<)$ be the structure where $(n,a)<(m,b)$ iff $n<m $ and $a=b$ -- countably many $omega$ columns next to each other. Similarly let $N_0:= (omegatimes B, <)$, and let $j_0$ be the inclusion map.



    Let $M_k= M_0$, and $N_k = (omega times A )cup (omega cup -1,ldots, -ktimes (Bsetminus A))$, again with the obvious order. So the columns with "indices" in $Bsetminus A$ become longer, but the map $j_k=j_0$ is still elementary since it does not "see" those columns.



    But the limit structures $M$ and $N$ different theories: in $N$ there are elements which have no minimal element below them.






    share|cite|improve this answer









    $endgroup$














    • $begingroup$
      I see that Alex Kruckman came up with a similar counterexample a few minutes before me.
      $endgroup$
      – Goldstern
      7 hours ago











    • $begingroup$
      Very nice! I had been trying to make such a counterexample to the generalization, with all the first models the same, just as you had done, but I hadn't yet managed. I was working with DLOs and discrete order combinations, but your method of separate columns is very clear.
      $endgroup$
      – Joel David Hamkins
      7 hours ago















    4














    $begingroup$

    Here is a counterexample to your "natural generalization":
    Let $A$ and $B$ be (countably) infinite sets, with $Asubseteq B$, $Bsetminus A$ infinite.



    Let $M_0= (omegatimes A,<)$ be the structure where $(n,a)<(m,b)$ iff $n<m $ and $a=b$ -- countably many $omega$ columns next to each other. Similarly let $N_0:= (omegatimes B, <)$, and let $j_0$ be the inclusion map.



    Let $M_k= M_0$, and $N_k = (omega times A )cup (omega cup -1,ldots, -ktimes (Bsetminus A))$, again with the obvious order. So the columns with "indices" in $Bsetminus A$ become longer, but the map $j_k=j_0$ is still elementary since it does not "see" those columns.



    But the limit structures $M$ and $N$ different theories: in $N$ there are elements which have no minimal element below them.






    share|cite|improve this answer









    $endgroup$














    • $begingroup$
      I see that Alex Kruckman came up with a similar counterexample a few minutes before me.
      $endgroup$
      – Goldstern
      7 hours ago











    • $begingroup$
      Very nice! I had been trying to make such a counterexample to the generalization, with all the first models the same, just as you had done, but I hadn't yet managed. I was working with DLOs and discrete order combinations, but your method of separate columns is very clear.
      $endgroup$
      – Joel David Hamkins
      7 hours ago













    4














    4










    4







    $begingroup$

    Here is a counterexample to your "natural generalization":
    Let $A$ and $B$ be (countably) infinite sets, with $Asubseteq B$, $Bsetminus A$ infinite.



    Let $M_0= (omegatimes A,<)$ be the structure where $(n,a)<(m,b)$ iff $n<m $ and $a=b$ -- countably many $omega$ columns next to each other. Similarly let $N_0:= (omegatimes B, <)$, and let $j_0$ be the inclusion map.



    Let $M_k= M_0$, and $N_k = (omega times A )cup (omega cup -1,ldots, -ktimes (Bsetminus A))$, again with the obvious order. So the columns with "indices" in $Bsetminus A$ become longer, but the map $j_k=j_0$ is still elementary since it does not "see" those columns.



    But the limit structures $M$ and $N$ different theories: in $N$ there are elements which have no minimal element below them.






    share|cite|improve this answer









    $endgroup$



    Here is a counterexample to your "natural generalization":
    Let $A$ and $B$ be (countably) infinite sets, with $Asubseteq B$, $Bsetminus A$ infinite.



    Let $M_0= (omegatimes A,<)$ be the structure where $(n,a)<(m,b)$ iff $n<m $ and $a=b$ -- countably many $omega$ columns next to each other. Similarly let $N_0:= (omegatimes B, <)$, and let $j_0$ be the inclusion map.



    Let $M_k= M_0$, and $N_k = (omega times A )cup (omega cup -1,ldots, -ktimes (Bsetminus A))$, again with the obvious order. So the columns with "indices" in $Bsetminus A$ become longer, but the map $j_k=j_0$ is still elementary since it does not "see" those columns.



    But the limit structures $M$ and $N$ different theories: in $N$ there are elements which have no minimal element below them.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 7 hours ago









    GoldsternGoldstern

    11.8k1 gold badge36 silver badges62 bronze badges




    11.8k1 gold badge36 silver badges62 bronze badges














    • $begingroup$
      I see that Alex Kruckman came up with a similar counterexample a few minutes before me.
      $endgroup$
      – Goldstern
      7 hours ago











    • $begingroup$
      Very nice! I had been trying to make such a counterexample to the generalization, with all the first models the same, just as you had done, but I hadn't yet managed. I was working with DLOs and discrete order combinations, but your method of separate columns is very clear.
      $endgroup$
      – Joel David Hamkins
      7 hours ago
















    • $begingroup$
      I see that Alex Kruckman came up with a similar counterexample a few minutes before me.
      $endgroup$
      – Goldstern
      7 hours ago











    • $begingroup$
      Very nice! I had been trying to make such a counterexample to the generalization, with all the first models the same, just as you had done, but I hadn't yet managed. I was working with DLOs and discrete order combinations, but your method of separate columns is very clear.
      $endgroup$
      – Joel David Hamkins
      7 hours ago















    $begingroup$
    I see that Alex Kruckman came up with a similar counterexample a few minutes before me.
    $endgroup$
    – Goldstern
    7 hours ago





    $begingroup$
    I see that Alex Kruckman came up with a similar counterexample a few minutes before me.
    $endgroup$
    – Goldstern
    7 hours ago













    $begingroup$
    Very nice! I had been trying to make such a counterexample to the generalization, with all the first models the same, just as you had done, but I hadn't yet managed. I was working with DLOs and discrete order combinations, but your method of separate columns is very clear.
    $endgroup$
    – Joel David Hamkins
    7 hours ago




    $begingroup$
    Very nice! I had been trying to make such a counterexample to the generalization, with all the first models the same, just as you had done, but I hadn't yet managed. I was working with DLOs and discrete order combinations, but your method of separate columns is very clear.
    $endgroup$
    – Joel David Hamkins
    7 hours ago











    4














    $begingroup$

    First I'll give a counterexample to the natural generalization, adapted from my earlier comment:



    Let $M_n = (mathbbN,<)$ for all $n$, and let $N_n = (mathbbNsqcup frac1n!mathbbZ,<)$, where all elements of $frac1n!mathbbZ$ are greater than all elements of $mathbbN$ in the order. Note that each $N_n$ is isomorphic to $(mathbbNsqcupmathbbZ,<)$, and there is a natural inclusion $N_nsubseteq N_n+1$ for all $n$, since $frac1n!mathbbZ subseteq frac1(n+1)!mathbbZ$ as subsets of $mathbbQ$.



    Now $M_npreceq N_n$ for all $n$, but $bigcup_n M_nnotpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter is $(mathbbNsqcupmathbbQ,<)$, which is not discrete.




    Now I'll explain how to turn any counterexample to the natural generalization into a counterexample to the original question.



    Suppose we have a coherent system of elementary embeddings $j_ncolon M_n to N_n$ such that the limit map $jcolon Mto N$ is not elementary. Let $L$ be the language of this counterexample, which we assume to be relational, and let $L' = Lcup E$, where $E$ is a new binary relation.



    For each $n$, we construct a structure $M^*_n$ as follows: $E$ is an equivalence relation with countably many classes, which we denote by $(C_i)_iin mathbbZ$. We interpret the relations from $L$ on each class $C_i$ so that $C_i$ is a copy of $M_n$ when $ileq 0$ and a copy of $N_n$ when $i > 0$. There are no relations between the classes.



    There is a natural inclusion $M_n^*subseteq M_n+1^*$ for all $n$, in which each class $C_i$ in $M_n^*$ is included in to the class $C_i$ in $M_n+1^*$ according to the inclusions $M_nsubseteq M_n+1$ and $N_nsubseteq N_n+1$.



    Let $j_n^*colon M^*_nto M^*_n$ map $C_i$ to $C_i+1$ as the identity on $M_n$ for all $i<0$, as the identity on $N_n$ for all $i>0$, and as $j_n colon M_nto N_n$ for $i = 0$. Then $j_n^*$ is an elementary embedding, and $j_n = j_n+1restriction M_n^*$.



    In the limit, $M^* = bigcup_n M_n^*$ has equivalence classes such that $C_i$ is a copy of $M$ when $ileq 0$ and a copy of $N$ when $i>0$. And the limit map $j^*colon M^*to M^*$ maps $C_i$ to $C_i+1$ as the identity on $M$ for all $i<0$, as the identity on $N$ for all $i>0$, and as $jcolon Mto N$ for $i=0$. This $j^*$ is not elementary, since an $L$-formula whose truth is not preserved by $j$ can be relativized to the equivalence class $C_0$ to give an $L'$-formula whose truth is not preserved by $j^*$.






    share|cite|improve this answer











    $endgroup$



















      4














      $begingroup$

      First I'll give a counterexample to the natural generalization, adapted from my earlier comment:



      Let $M_n = (mathbbN,<)$ for all $n$, and let $N_n = (mathbbNsqcup frac1n!mathbbZ,<)$, where all elements of $frac1n!mathbbZ$ are greater than all elements of $mathbbN$ in the order. Note that each $N_n$ is isomorphic to $(mathbbNsqcupmathbbZ,<)$, and there is a natural inclusion $N_nsubseteq N_n+1$ for all $n$, since $frac1n!mathbbZ subseteq frac1(n+1)!mathbbZ$ as subsets of $mathbbQ$.



      Now $M_npreceq N_n$ for all $n$, but $bigcup_n M_nnotpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter is $(mathbbNsqcupmathbbQ,<)$, which is not discrete.




      Now I'll explain how to turn any counterexample to the natural generalization into a counterexample to the original question.



      Suppose we have a coherent system of elementary embeddings $j_ncolon M_n to N_n$ such that the limit map $jcolon Mto N$ is not elementary. Let $L$ be the language of this counterexample, which we assume to be relational, and let $L' = Lcup E$, where $E$ is a new binary relation.



      For each $n$, we construct a structure $M^*_n$ as follows: $E$ is an equivalence relation with countably many classes, which we denote by $(C_i)_iin mathbbZ$. We interpret the relations from $L$ on each class $C_i$ so that $C_i$ is a copy of $M_n$ when $ileq 0$ and a copy of $N_n$ when $i > 0$. There are no relations between the classes.



      There is a natural inclusion $M_n^*subseteq M_n+1^*$ for all $n$, in which each class $C_i$ in $M_n^*$ is included in to the class $C_i$ in $M_n+1^*$ according to the inclusions $M_nsubseteq M_n+1$ and $N_nsubseteq N_n+1$.



      Let $j_n^*colon M^*_nto M^*_n$ map $C_i$ to $C_i+1$ as the identity on $M_n$ for all $i<0$, as the identity on $N_n$ for all $i>0$, and as $j_n colon M_nto N_n$ for $i = 0$. Then $j_n^*$ is an elementary embedding, and $j_n = j_n+1restriction M_n^*$.



      In the limit, $M^* = bigcup_n M_n^*$ has equivalence classes such that $C_i$ is a copy of $M$ when $ileq 0$ and a copy of $N$ when $i>0$. And the limit map $j^*colon M^*to M^*$ maps $C_i$ to $C_i+1$ as the identity on $M$ for all $i<0$, as the identity on $N$ for all $i>0$, and as $jcolon Mto N$ for $i=0$. This $j^*$ is not elementary, since an $L$-formula whose truth is not preserved by $j$ can be relativized to the equivalence class $C_0$ to give an $L'$-formula whose truth is not preserved by $j^*$.






      share|cite|improve this answer











      $endgroup$

















        4














        4










        4







        $begingroup$

        First I'll give a counterexample to the natural generalization, adapted from my earlier comment:



        Let $M_n = (mathbbN,<)$ for all $n$, and let $N_n = (mathbbNsqcup frac1n!mathbbZ,<)$, where all elements of $frac1n!mathbbZ$ are greater than all elements of $mathbbN$ in the order. Note that each $N_n$ is isomorphic to $(mathbbNsqcupmathbbZ,<)$, and there is a natural inclusion $N_nsubseteq N_n+1$ for all $n$, since $frac1n!mathbbZ subseteq frac1(n+1)!mathbbZ$ as subsets of $mathbbQ$.



        Now $M_npreceq N_n$ for all $n$, but $bigcup_n M_nnotpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter is $(mathbbNsqcupmathbbQ,<)$, which is not discrete.




        Now I'll explain how to turn any counterexample to the natural generalization into a counterexample to the original question.



        Suppose we have a coherent system of elementary embeddings $j_ncolon M_n to N_n$ such that the limit map $jcolon Mto N$ is not elementary. Let $L$ be the language of this counterexample, which we assume to be relational, and let $L' = Lcup E$, where $E$ is a new binary relation.



        For each $n$, we construct a structure $M^*_n$ as follows: $E$ is an equivalence relation with countably many classes, which we denote by $(C_i)_iin mathbbZ$. We interpret the relations from $L$ on each class $C_i$ so that $C_i$ is a copy of $M_n$ when $ileq 0$ and a copy of $N_n$ when $i > 0$. There are no relations between the classes.



        There is a natural inclusion $M_n^*subseteq M_n+1^*$ for all $n$, in which each class $C_i$ in $M_n^*$ is included in to the class $C_i$ in $M_n+1^*$ according to the inclusions $M_nsubseteq M_n+1$ and $N_nsubseteq N_n+1$.



        Let $j_n^*colon M^*_nto M^*_n$ map $C_i$ to $C_i+1$ as the identity on $M_n$ for all $i<0$, as the identity on $N_n$ for all $i>0$, and as $j_n colon M_nto N_n$ for $i = 0$. Then $j_n^*$ is an elementary embedding, and $j_n = j_n+1restriction M_n^*$.



        In the limit, $M^* = bigcup_n M_n^*$ has equivalence classes such that $C_i$ is a copy of $M$ when $ileq 0$ and a copy of $N$ when $i>0$. And the limit map $j^*colon M^*to M^*$ maps $C_i$ to $C_i+1$ as the identity on $M$ for all $i<0$, as the identity on $N$ for all $i>0$, and as $jcolon Mto N$ for $i=0$. This $j^*$ is not elementary, since an $L$-formula whose truth is not preserved by $j$ can be relativized to the equivalence class $C_0$ to give an $L'$-formula whose truth is not preserved by $j^*$.






        share|cite|improve this answer











        $endgroup$



        First I'll give a counterexample to the natural generalization, adapted from my earlier comment:



        Let $M_n = (mathbbN,<)$ for all $n$, and let $N_n = (mathbbNsqcup frac1n!mathbbZ,<)$, where all elements of $frac1n!mathbbZ$ are greater than all elements of $mathbbN$ in the order. Note that each $N_n$ is isomorphic to $(mathbbNsqcupmathbbZ,<)$, and there is a natural inclusion $N_nsubseteq N_n+1$ for all $n$, since $frac1n!mathbbZ subseteq frac1(n+1)!mathbbZ$ as subsets of $mathbbQ$.



        Now $M_npreceq N_n$ for all $n$, but $bigcup_n M_nnotpreceq bigcup_n N_n$, since the former is $(mathbbN,<)$ and the latter is $(mathbbNsqcupmathbbQ,<)$, which is not discrete.




        Now I'll explain how to turn any counterexample to the natural generalization into a counterexample to the original question.



        Suppose we have a coherent system of elementary embeddings $j_ncolon M_n to N_n$ such that the limit map $jcolon Mto N$ is not elementary. Let $L$ be the language of this counterexample, which we assume to be relational, and let $L' = Lcup E$, where $E$ is a new binary relation.



        For each $n$, we construct a structure $M^*_n$ as follows: $E$ is an equivalence relation with countably many classes, which we denote by $(C_i)_iin mathbbZ$. We interpret the relations from $L$ on each class $C_i$ so that $C_i$ is a copy of $M_n$ when $ileq 0$ and a copy of $N_n$ when $i > 0$. There are no relations between the classes.



        There is a natural inclusion $M_n^*subseteq M_n+1^*$ for all $n$, in which each class $C_i$ in $M_n^*$ is included in to the class $C_i$ in $M_n+1^*$ according to the inclusions $M_nsubseteq M_n+1$ and $N_nsubseteq N_n+1$.



        Let $j_n^*colon M^*_nto M^*_n$ map $C_i$ to $C_i+1$ as the identity on $M_n$ for all $i<0$, as the identity on $N_n$ for all $i>0$, and as $j_n colon M_nto N_n$ for $i = 0$. Then $j_n^*$ is an elementary embedding, and $j_n = j_n+1restriction M_n^*$.



        In the limit, $M^* = bigcup_n M_n^*$ has equivalence classes such that $C_i$ is a copy of $M$ when $ileq 0$ and a copy of $N$ when $i>0$. And the limit map $j^*colon M^*to M^*$ maps $C_i$ to $C_i+1$ as the identity on $M$ for all $i<0$, as the identity on $N$ for all $i>0$, and as $jcolon Mto N$ for $i=0$. This $j^*$ is not elementary, since an $L$-formula whose truth is not preserved by $j$ can be relativized to the equivalence class $C_0$ to give an $L'$-formula whose truth is not preserved by $j^*$.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited 5 hours ago

























        answered 5 hours ago









        Alex KruckmanAlex Kruckman

        2,2541 gold badge12 silver badges18 bronze badges




        2,2541 gold badge12 silver badges18 bronze badges































            draft saved

            draft discarded















































            Thanks for contributing an answer to MathOverflow!


            • 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.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f340275%2fis-the-union-of-a-chain-of-elementary-embeddings-elementary%23new-answer', 'question_page');

            );

            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







            Popular posts from this blog

            Canceling a color specificationRandomly assigning color to Graphics3D objects?Default color for Filling in Mathematica 9Coloring specific elements of sets with a prime modified order in an array plotHow to pick a color differing significantly from the colors already in a given color list?Detection of the text colorColor numbers based on their valueCan color schemes for use with ColorData include opacity specification?My dynamic color schemes

            Invision Community Contents History See also References External links Navigation menuProprietaryinvisioncommunity.comIPS Community ForumsIPS Community Forumsthis blog entry"License Changes, IP.Board 3.4, and the Future""Interview -- Matt Mecham of Ibforums""CEO Invision Power Board, Matt Mecham Is a Liar, Thief!"IPB License Explanation 1.3, 1.3.1, 2.0, and 2.1ArchivedSecurity Fixes, Updates And Enhancements For IPB 1.3.1Archived"New Demo Accounts - Invision Power Services"the original"New Default Skin"the original"Invision Power Board 3.0.0 and Applications Released"the original"Archived copy"the original"Perpetual licenses being done away with""Release Notes - Invision Power Services""Introducing: IPS Community Suite 4!"Invision Community Release Notes

            199年 目錄 大件事 到箇年出世嗰人 到箇年死嗰人 節慶、風俗習慣 導覽選單