Let $L = {<}$ prove there is no $L$-theory that has precisely the well ordered sets as models












3












$begingroup$


This is the literal question: let $L$ be the language that only contains the two place relation symbol $<$. Prove there is no $L$-theory that has precisely the well ordered sets as models.



I assume the $L$-structure must be well ordered with respect to the relation $a^M leq b^M iff (a^M <^M b^M) vee (a^M = b^M)$ where the superscript $M$ denotes it's the interpretation in the $L$-structure $M$.



Here's my work so far:



Suppose such a $L$-theory $T$ does exist. Add the constants $c_1, c_2, ...$ to $L$ giving a new language $L'$. Define the $L'$-theory $T'$ by adding $B := {c_{n + 1} < c_{n} | n in mathbb{N}}$ to $T$.



Now $T'$ cannot be consistent, because then there exists an $L'$-structure $M$ such that $M models T'$, so $M models T$, so $M$ is a well ordered set, but also $c_1^M > c_2^M > ...$, which is a contradiction. By the contraposition of the compactness theorem, there must exist a finite subset $A$ of $T'$ that is inconsistent as well. This $A$ must contain a finite number of elements from $B$. I'm stuck here.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Yes, thank you.
    $endgroup$
    – Pel de Pinda
    Dec 11 '18 at 10:58






  • 2




    $begingroup$
    I think you're on the right track. Now you want to get a contradiction by showing that $T'$ is consistent. In other words you want to show thst the theory $T_n$, obtained by adding $c_1gt c_2gtcdotsgt c_n$ has a model. Hmm. I gess you can prove something a little stringer, namely, that any theory whose models include arbitrarily large finite ordered sets, also contains a non-well-ordered set.
    $endgroup$
    – bof
    Dec 11 '18 at 11:05






  • 1




    $begingroup$
    A fancier argument: an elementary class which is closed under passage to substructures is (for reasons I forget) axiomatizable by a set of universal sentences, so it is also closed under unions of chains. Since a subset of a well-ordered set is well-ordered, while the union of a chain of well-ordered sets is not necessarily well-ordered, the class of all well-ordered sets can't be elementary.
    $endgroup$
    – bof
    Dec 11 '18 at 11:14










  • $begingroup$
    @bof Thank you, I think I understand now. Is this correct? For any model $M$ of $T$, we can add the variables $c_i^M$ for those $i$'s that $(c_{i + 1} < c_i)$ is in $T'$ giving $M'$. Then $M' models c_{i + 1} < c_i$ for those $i$ such that $(c_{i + 1} < c_i)$ is in $T'$. It is impossible that $M'$ is not a well order since it contains only finitely many constants, so also $M' models T$. So $M models T'$ and it is consistent, contradiction.
    $endgroup$
    – Pel de Pinda
    Dec 11 '18 at 11:40








  • 1




    $begingroup$
    @PeldePinda "It is impossible that $M'$ is not a well order since it contains only finitely many constants." No, the number of constants interpreted in $M'$ has nothing to do with whether it's a well-order. $M'$ might have infinitely many elements that aren't the interpretations of any of the $c_i$. The reason $M'$ is a well order is that $M'models T$, and every model of $T$ is a well order by hypothesis.
    $endgroup$
    – Alex Kruckman
    Dec 11 '18 at 15:01
















3












$begingroup$


This is the literal question: let $L$ be the language that only contains the two place relation symbol $<$. Prove there is no $L$-theory that has precisely the well ordered sets as models.



I assume the $L$-structure must be well ordered with respect to the relation $a^M leq b^M iff (a^M <^M b^M) vee (a^M = b^M)$ where the superscript $M$ denotes it's the interpretation in the $L$-structure $M$.



Here's my work so far:



Suppose such a $L$-theory $T$ does exist. Add the constants $c_1, c_2, ...$ to $L$ giving a new language $L'$. Define the $L'$-theory $T'$ by adding $B := {c_{n + 1} < c_{n} | n in mathbb{N}}$ to $T$.



Now $T'$ cannot be consistent, because then there exists an $L'$-structure $M$ such that $M models T'$, so $M models T$, so $M$ is a well ordered set, but also $c_1^M > c_2^M > ...$, which is a contradiction. By the contraposition of the compactness theorem, there must exist a finite subset $A$ of $T'$ that is inconsistent as well. This $A$ must contain a finite number of elements from $B$. I'm stuck here.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Yes, thank you.
    $endgroup$
    – Pel de Pinda
    Dec 11 '18 at 10:58






  • 2




    $begingroup$
    I think you're on the right track. Now you want to get a contradiction by showing that $T'$ is consistent. In other words you want to show thst the theory $T_n$, obtained by adding $c_1gt c_2gtcdotsgt c_n$ has a model. Hmm. I gess you can prove something a little stringer, namely, that any theory whose models include arbitrarily large finite ordered sets, also contains a non-well-ordered set.
    $endgroup$
    – bof
    Dec 11 '18 at 11:05






  • 1




    $begingroup$
    A fancier argument: an elementary class which is closed under passage to substructures is (for reasons I forget) axiomatizable by a set of universal sentences, so it is also closed under unions of chains. Since a subset of a well-ordered set is well-ordered, while the union of a chain of well-ordered sets is not necessarily well-ordered, the class of all well-ordered sets can't be elementary.
    $endgroup$
    – bof
    Dec 11 '18 at 11:14










  • $begingroup$
    @bof Thank you, I think I understand now. Is this correct? For any model $M$ of $T$, we can add the variables $c_i^M$ for those $i$'s that $(c_{i + 1} < c_i)$ is in $T'$ giving $M'$. Then $M' models c_{i + 1} < c_i$ for those $i$ such that $(c_{i + 1} < c_i)$ is in $T'$. It is impossible that $M'$ is not a well order since it contains only finitely many constants, so also $M' models T$. So $M models T'$ and it is consistent, contradiction.
    $endgroup$
    – Pel de Pinda
    Dec 11 '18 at 11:40








  • 1




    $begingroup$
    @PeldePinda "It is impossible that $M'$ is not a well order since it contains only finitely many constants." No, the number of constants interpreted in $M'$ has nothing to do with whether it's a well-order. $M'$ might have infinitely many elements that aren't the interpretations of any of the $c_i$. The reason $M'$ is a well order is that $M'models T$, and every model of $T$ is a well order by hypothesis.
    $endgroup$
    – Alex Kruckman
    Dec 11 '18 at 15:01














3












3








3


3



$begingroup$


This is the literal question: let $L$ be the language that only contains the two place relation symbol $<$. Prove there is no $L$-theory that has precisely the well ordered sets as models.



I assume the $L$-structure must be well ordered with respect to the relation $a^M leq b^M iff (a^M <^M b^M) vee (a^M = b^M)$ where the superscript $M$ denotes it's the interpretation in the $L$-structure $M$.



Here's my work so far:



Suppose such a $L$-theory $T$ does exist. Add the constants $c_1, c_2, ...$ to $L$ giving a new language $L'$. Define the $L'$-theory $T'$ by adding $B := {c_{n + 1} < c_{n} | n in mathbb{N}}$ to $T$.



Now $T'$ cannot be consistent, because then there exists an $L'$-structure $M$ such that $M models T'$, so $M models T$, so $M$ is a well ordered set, but also $c_1^M > c_2^M > ...$, which is a contradiction. By the contraposition of the compactness theorem, there must exist a finite subset $A$ of $T'$ that is inconsistent as well. This $A$ must contain a finite number of elements from $B$. I'm stuck here.










share|cite|improve this question











$endgroup$




This is the literal question: let $L$ be the language that only contains the two place relation symbol $<$. Prove there is no $L$-theory that has precisely the well ordered sets as models.



I assume the $L$-structure must be well ordered with respect to the relation $a^M leq b^M iff (a^M <^M b^M) vee (a^M = b^M)$ where the superscript $M$ denotes it's the interpretation in the $L$-structure $M$.



Here's my work so far:



Suppose such a $L$-theory $T$ does exist. Add the constants $c_1, c_2, ...$ to $L$ giving a new language $L'$. Define the $L'$-theory $T'$ by adding $B := {c_{n + 1} < c_{n} | n in mathbb{N}}$ to $T$.



Now $T'$ cannot be consistent, because then there exists an $L'$-structure $M$ such that $M models T'$, so $M models T$, so $M$ is a well ordered set, but also $c_1^M > c_2^M > ...$, which is a contradiction. By the contraposition of the compactness theorem, there must exist a finite subset $A$ of $T'$ that is inconsistent as well. This $A$ must contain a finite number of elements from $B$. I'm stuck here.







logic model-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 11 '18 at 18:14







Pel de Pinda

















asked Dec 11 '18 at 10:34









Pel de PindaPel de Pinda

817314




817314












  • $begingroup$
    Yes, thank you.
    $endgroup$
    – Pel de Pinda
    Dec 11 '18 at 10:58






  • 2




    $begingroup$
    I think you're on the right track. Now you want to get a contradiction by showing that $T'$ is consistent. In other words you want to show thst the theory $T_n$, obtained by adding $c_1gt c_2gtcdotsgt c_n$ has a model. Hmm. I gess you can prove something a little stringer, namely, that any theory whose models include arbitrarily large finite ordered sets, also contains a non-well-ordered set.
    $endgroup$
    – bof
    Dec 11 '18 at 11:05






  • 1




    $begingroup$
    A fancier argument: an elementary class which is closed under passage to substructures is (for reasons I forget) axiomatizable by a set of universal sentences, so it is also closed under unions of chains. Since a subset of a well-ordered set is well-ordered, while the union of a chain of well-ordered sets is not necessarily well-ordered, the class of all well-ordered sets can't be elementary.
    $endgroup$
    – bof
    Dec 11 '18 at 11:14










  • $begingroup$
    @bof Thank you, I think I understand now. Is this correct? For any model $M$ of $T$, we can add the variables $c_i^M$ for those $i$'s that $(c_{i + 1} < c_i)$ is in $T'$ giving $M'$. Then $M' models c_{i + 1} < c_i$ for those $i$ such that $(c_{i + 1} < c_i)$ is in $T'$. It is impossible that $M'$ is not a well order since it contains only finitely many constants, so also $M' models T$. So $M models T'$ and it is consistent, contradiction.
    $endgroup$
    – Pel de Pinda
    Dec 11 '18 at 11:40








  • 1




    $begingroup$
    @PeldePinda "It is impossible that $M'$ is not a well order since it contains only finitely many constants." No, the number of constants interpreted in $M'$ has nothing to do with whether it's a well-order. $M'$ might have infinitely many elements that aren't the interpretations of any of the $c_i$. The reason $M'$ is a well order is that $M'models T$, and every model of $T$ is a well order by hypothesis.
    $endgroup$
    – Alex Kruckman
    Dec 11 '18 at 15:01


















  • $begingroup$
    Yes, thank you.
    $endgroup$
    – Pel de Pinda
    Dec 11 '18 at 10:58






  • 2




    $begingroup$
    I think you're on the right track. Now you want to get a contradiction by showing that $T'$ is consistent. In other words you want to show thst the theory $T_n$, obtained by adding $c_1gt c_2gtcdotsgt c_n$ has a model. Hmm. I gess you can prove something a little stringer, namely, that any theory whose models include arbitrarily large finite ordered sets, also contains a non-well-ordered set.
    $endgroup$
    – bof
    Dec 11 '18 at 11:05






  • 1




    $begingroup$
    A fancier argument: an elementary class which is closed under passage to substructures is (for reasons I forget) axiomatizable by a set of universal sentences, so it is also closed under unions of chains. Since a subset of a well-ordered set is well-ordered, while the union of a chain of well-ordered sets is not necessarily well-ordered, the class of all well-ordered sets can't be elementary.
    $endgroup$
    – bof
    Dec 11 '18 at 11:14










  • $begingroup$
    @bof Thank you, I think I understand now. Is this correct? For any model $M$ of $T$, we can add the variables $c_i^M$ for those $i$'s that $(c_{i + 1} < c_i)$ is in $T'$ giving $M'$. Then $M' models c_{i + 1} < c_i$ for those $i$ such that $(c_{i + 1} < c_i)$ is in $T'$. It is impossible that $M'$ is not a well order since it contains only finitely many constants, so also $M' models T$. So $M models T'$ and it is consistent, contradiction.
    $endgroup$
    – Pel de Pinda
    Dec 11 '18 at 11:40








  • 1




    $begingroup$
    @PeldePinda "It is impossible that $M'$ is not a well order since it contains only finitely many constants." No, the number of constants interpreted in $M'$ has nothing to do with whether it's a well-order. $M'$ might have infinitely many elements that aren't the interpretations of any of the $c_i$. The reason $M'$ is a well order is that $M'models T$, and every model of $T$ is a well order by hypothesis.
    $endgroup$
    – Alex Kruckman
    Dec 11 '18 at 15:01
















$begingroup$
Yes, thank you.
$endgroup$
– Pel de Pinda
Dec 11 '18 at 10:58




$begingroup$
Yes, thank you.
$endgroup$
– Pel de Pinda
Dec 11 '18 at 10:58




2




2




$begingroup$
I think you're on the right track. Now you want to get a contradiction by showing that $T'$ is consistent. In other words you want to show thst the theory $T_n$, obtained by adding $c_1gt c_2gtcdotsgt c_n$ has a model. Hmm. I gess you can prove something a little stringer, namely, that any theory whose models include arbitrarily large finite ordered sets, also contains a non-well-ordered set.
$endgroup$
– bof
Dec 11 '18 at 11:05




$begingroup$
I think you're on the right track. Now you want to get a contradiction by showing that $T'$ is consistent. In other words you want to show thst the theory $T_n$, obtained by adding $c_1gt c_2gtcdotsgt c_n$ has a model. Hmm. I gess you can prove something a little stringer, namely, that any theory whose models include arbitrarily large finite ordered sets, also contains a non-well-ordered set.
$endgroup$
– bof
Dec 11 '18 at 11:05




1




1




$begingroup$
A fancier argument: an elementary class which is closed under passage to substructures is (for reasons I forget) axiomatizable by a set of universal sentences, so it is also closed under unions of chains. Since a subset of a well-ordered set is well-ordered, while the union of a chain of well-ordered sets is not necessarily well-ordered, the class of all well-ordered sets can't be elementary.
$endgroup$
– bof
Dec 11 '18 at 11:14




$begingroup$
A fancier argument: an elementary class which is closed under passage to substructures is (for reasons I forget) axiomatizable by a set of universal sentences, so it is also closed under unions of chains. Since a subset of a well-ordered set is well-ordered, while the union of a chain of well-ordered sets is not necessarily well-ordered, the class of all well-ordered sets can't be elementary.
$endgroup$
– bof
Dec 11 '18 at 11:14












$begingroup$
@bof Thank you, I think I understand now. Is this correct? For any model $M$ of $T$, we can add the variables $c_i^M$ for those $i$'s that $(c_{i + 1} < c_i)$ is in $T'$ giving $M'$. Then $M' models c_{i + 1} < c_i$ for those $i$ such that $(c_{i + 1} < c_i)$ is in $T'$. It is impossible that $M'$ is not a well order since it contains only finitely many constants, so also $M' models T$. So $M models T'$ and it is consistent, contradiction.
$endgroup$
– Pel de Pinda
Dec 11 '18 at 11:40






$begingroup$
@bof Thank you, I think I understand now. Is this correct? For any model $M$ of $T$, we can add the variables $c_i^M$ for those $i$'s that $(c_{i + 1} < c_i)$ is in $T'$ giving $M'$. Then $M' models c_{i + 1} < c_i$ for those $i$ such that $(c_{i + 1} < c_i)$ is in $T'$. It is impossible that $M'$ is not a well order since it contains only finitely many constants, so also $M' models T$. So $M models T'$ and it is consistent, contradiction.
$endgroup$
– Pel de Pinda
Dec 11 '18 at 11:40






1




1




$begingroup$
@PeldePinda "It is impossible that $M'$ is not a well order since it contains only finitely many constants." No, the number of constants interpreted in $M'$ has nothing to do with whether it's a well-order. $M'$ might have infinitely many elements that aren't the interpretations of any of the $c_i$. The reason $M'$ is a well order is that $M'models T$, and every model of $T$ is a well order by hypothesis.
$endgroup$
– Alex Kruckman
Dec 11 '18 at 15:01




$begingroup$
@PeldePinda "It is impossible that $M'$ is not a well order since it contains only finitely many constants." No, the number of constants interpreted in $M'$ has nothing to do with whether it's a well-order. $M'$ might have infinitely many elements that aren't the interpretations of any of the $c_i$. The reason $M'$ is a well order is that $M'models T$, and every model of $T$ is a well order by hypothesis.
$endgroup$
– Alex Kruckman
Dec 11 '18 at 15:01










1 Answer
1






active

oldest

votes


















2












$begingroup$

I thought it would be better to give an answer rather than carry on with the comments. Your argument contains the key ideas but doesn't quite fit together. To fix it, argue like this:



Let $T$ be any $L$-theory that has every well-founded set as a model. As you suggest, we can extend $L'$ by adding constants $c_n$ and consider the set of sentences $B = { c_n > c_{n+1} mid n in Bbb{N} }$. Then any finite subset of $T cup B$ is consistent, since it has a model in the well-founded ordered set $Bbb{N}$. By the compactness theorem, $T cup B$ has a model. $M$ say. Since every sentence in $B$ holds in $M$, the $c_n$ form an infinite descending chain in $M$, so $M$ is not well-ordered. Thus any $L$-theory that has every well-founded set as a model also has models that are not well-founded. Hence there is no $L$-theory whose models are precisely the well-founded sets.






share|cite|improve this answer









$endgroup$













    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
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3035155%2flet-l-prove-there-is-no-l-theory-that-has-precisely-the-well-ordered%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









    2












    $begingroup$

    I thought it would be better to give an answer rather than carry on with the comments. Your argument contains the key ideas but doesn't quite fit together. To fix it, argue like this:



    Let $T$ be any $L$-theory that has every well-founded set as a model. As you suggest, we can extend $L'$ by adding constants $c_n$ and consider the set of sentences $B = { c_n > c_{n+1} mid n in Bbb{N} }$. Then any finite subset of $T cup B$ is consistent, since it has a model in the well-founded ordered set $Bbb{N}$. By the compactness theorem, $T cup B$ has a model. $M$ say. Since every sentence in $B$ holds in $M$, the $c_n$ form an infinite descending chain in $M$, so $M$ is not well-ordered. Thus any $L$-theory that has every well-founded set as a model also has models that are not well-founded. Hence there is no $L$-theory whose models are precisely the well-founded sets.






    share|cite|improve this answer









    $endgroup$


















      2












      $begingroup$

      I thought it would be better to give an answer rather than carry on with the comments. Your argument contains the key ideas but doesn't quite fit together. To fix it, argue like this:



      Let $T$ be any $L$-theory that has every well-founded set as a model. As you suggest, we can extend $L'$ by adding constants $c_n$ and consider the set of sentences $B = { c_n > c_{n+1} mid n in Bbb{N} }$. Then any finite subset of $T cup B$ is consistent, since it has a model in the well-founded ordered set $Bbb{N}$. By the compactness theorem, $T cup B$ has a model. $M$ say. Since every sentence in $B$ holds in $M$, the $c_n$ form an infinite descending chain in $M$, so $M$ is not well-ordered. Thus any $L$-theory that has every well-founded set as a model also has models that are not well-founded. Hence there is no $L$-theory whose models are precisely the well-founded sets.






      share|cite|improve this answer









      $endgroup$
















        2












        2








        2





        $begingroup$

        I thought it would be better to give an answer rather than carry on with the comments. Your argument contains the key ideas but doesn't quite fit together. To fix it, argue like this:



        Let $T$ be any $L$-theory that has every well-founded set as a model. As you suggest, we can extend $L'$ by adding constants $c_n$ and consider the set of sentences $B = { c_n > c_{n+1} mid n in Bbb{N} }$. Then any finite subset of $T cup B$ is consistent, since it has a model in the well-founded ordered set $Bbb{N}$. By the compactness theorem, $T cup B$ has a model. $M$ say. Since every sentence in $B$ holds in $M$, the $c_n$ form an infinite descending chain in $M$, so $M$ is not well-ordered. Thus any $L$-theory that has every well-founded set as a model also has models that are not well-founded. Hence there is no $L$-theory whose models are precisely the well-founded sets.






        share|cite|improve this answer









        $endgroup$



        I thought it would be better to give an answer rather than carry on with the comments. Your argument contains the key ideas but doesn't quite fit together. To fix it, argue like this:



        Let $T$ be any $L$-theory that has every well-founded set as a model. As you suggest, we can extend $L'$ by adding constants $c_n$ and consider the set of sentences $B = { c_n > c_{n+1} mid n in Bbb{N} }$. Then any finite subset of $T cup B$ is consistent, since it has a model in the well-founded ordered set $Bbb{N}$. By the compactness theorem, $T cup B$ has a model. $M$ say. Since every sentence in $B$ holds in $M$, the $c_n$ form an infinite descending chain in $M$, so $M$ is not well-ordered. Thus any $L$-theory that has every well-founded set as a model also has models that are not well-founded. Hence there is no $L$-theory whose models are precisely the well-founded sets.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 11 '18 at 21:16









        Rob ArthanRob Arthan

        29.3k42966




        29.3k42966






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3035155%2flet-l-prove-there-is-no-l-theory-that-has-precisely-the-well-ordered%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

            Plaza Victoria

            Puebla de Zaragoza

            Musa