Models of set theory where not every set can be linearly ordered Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Proving “every set can be totally ordered” without using Axiom of ChoiceCan all sets be totally ordered (not well-ordered) in ZF?How can there be genuine models of set theory?Reverse Mathematics of Well-OrderingsHow to exhibit models of set theoryZorn's lemma and maximal linearly ordered subsetsCounterexample to the Hausdorff Maximal PrincipleCan every non-empty set satisfying the axioms of $sfZF$ be totally ordered?Can Well Ordering Theorem Be Proved Without the Axiom of Power Set?the power set of every well-ordered set is well-ordered implies well orderingEvery countable linearly ordered set is similar to one of its subsetsLinearly ordering the power set of a well ordered set with ZF (without AC)
How many morphisms from 1 to 1+1 can there be?
Should a wizard buy fine inks every time he want to copy spells into his spellbook?
Karn the great creator - 'card from outside the game' in sealed
The Nth Gryphon Number
How much damage would a cupful of neutron star matter do to the Earth?
What is the difference between a "ranged attack" and a "ranged weapon attack"?
If the probability of a dog barking one or more times in a given hour is 84%, then what is the probability of a dog barking in 30 minutes?
Can the Flaming Sphere spell be rammed into multiple Tiny creatures that are in the same 5-foot square?
Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?
Is there hard evidence that the grant peer review system performs significantly better than random?
How could we fake a moon landing now?
preposition before coffee
Do wooden building fires get hotter than 600°C?
What does this say in Elvish?
What does 丫 mean? 丫是什么意思?
An adverb for when you're not exaggerating
Sum letters are not two different
Why can't I install Tomboy in Ubuntu Mate 19.04?
Dynamic filling of a region of a polar plot
What's the difference between the capability remove_users and delete_users?
Tannaka duality for semisimple groups
If Windows 7 doesn't support WSL, then what is "Subsystem for UNIX-based Applications"?
A term for a woman complaining about things/begging in a cute/childish way
Time evolution of a Gaussian wave packet, why convert to k-space?
Models of set theory where not every set can be linearly ordered
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Proving “every set can be totally ordered” without using Axiom of ChoiceCan all sets be totally ordered (not well-ordered) in ZF?How can there be genuine models of set theory?Reverse Mathematics of Well-OrderingsHow to exhibit models of set theoryZorn's lemma and maximal linearly ordered subsetsCounterexample to the Hausdorff Maximal PrincipleCan every non-empty set satisfying the axioms of $sfZF$ be totally ordered?Can Well Ordering Theorem Be Proved Without the Axiom of Power Set?the power set of every well-ordered set is well-ordered implies well orderingEvery countable linearly ordered set is similar to one of its subsetsLinearly ordering the power set of a well ordered set with ZF (without AC)
$begingroup$
Can anybody point me towards a model of set theory where not every set can be linearly ordered, and a corresponding proof. I have seen it claimed that in Fraenkels second permutation model that there is a set that cannot be linearly ordered, but cannot find a proof.
Essentially, I am asking for a proof that without choice sometimes the linear ordering principle fails.
set-theory axiom-of-choice
New contributor
$endgroup$
add a comment |
$begingroup$
Can anybody point me towards a model of set theory where not every set can be linearly ordered, and a corresponding proof. I have seen it claimed that in Fraenkels second permutation model that there is a set that cannot be linearly ordered, but cannot find a proof.
Essentially, I am asking for a proof that without choice sometimes the linear ordering principle fails.
set-theory axiom-of-choice
New contributor
$endgroup$
1
$begingroup$
In the case of the Fraenkel model, would this just come down to saying that any linear ordering would have a finite support, and then we just consider a permutation of two atoms outside of said support?
$endgroup$
– LGar
Apr 15 at 19:23
1
$begingroup$
Yes, by the way, a direct argument in both the models of Fraenkel is that any linear order would have a finite support and we can find a permutation that moves some things in an incongruous way.
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:35
1
$begingroup$
Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
$endgroup$
– YuiTo Cheng
Apr 15 at 23:04
$begingroup$
This question is not as far as I can tell a duplicate - that question is asking for a proof of the linear ordering principle without choice, while I was asking for a proof that the linear ordering principle can sometimes fail in the abscence of choice.
$endgroup$
– LGar
Apr 16 at 0:21
$begingroup$
What about Is every set linearly ordered in ZF
$endgroup$
– YuiTo Cheng
Apr 16 at 0:57
add a comment |
$begingroup$
Can anybody point me towards a model of set theory where not every set can be linearly ordered, and a corresponding proof. I have seen it claimed that in Fraenkels second permutation model that there is a set that cannot be linearly ordered, but cannot find a proof.
Essentially, I am asking for a proof that without choice sometimes the linear ordering principle fails.
set-theory axiom-of-choice
New contributor
$endgroup$
Can anybody point me towards a model of set theory where not every set can be linearly ordered, and a corresponding proof. I have seen it claimed that in Fraenkels second permutation model that there is a set that cannot be linearly ordered, but cannot find a proof.
Essentially, I am asking for a proof that without choice sometimes the linear ordering principle fails.
set-theory axiom-of-choice
set-theory axiom-of-choice
New contributor
New contributor
edited Apr 16 at 0:22
LGar
New contributor
asked Apr 15 at 19:21
LGarLGar
506
506
New contributor
New contributor
1
$begingroup$
In the case of the Fraenkel model, would this just come down to saying that any linear ordering would have a finite support, and then we just consider a permutation of two atoms outside of said support?
$endgroup$
– LGar
Apr 15 at 19:23
1
$begingroup$
Yes, by the way, a direct argument in both the models of Fraenkel is that any linear order would have a finite support and we can find a permutation that moves some things in an incongruous way.
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:35
1
$begingroup$
Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
$endgroup$
– YuiTo Cheng
Apr 15 at 23:04
$begingroup$
This question is not as far as I can tell a duplicate - that question is asking for a proof of the linear ordering principle without choice, while I was asking for a proof that the linear ordering principle can sometimes fail in the abscence of choice.
$endgroup$
– LGar
Apr 16 at 0:21
$begingroup$
What about Is every set linearly ordered in ZF
$endgroup$
– YuiTo Cheng
Apr 16 at 0:57
add a comment |
1
$begingroup$
In the case of the Fraenkel model, would this just come down to saying that any linear ordering would have a finite support, and then we just consider a permutation of two atoms outside of said support?
$endgroup$
– LGar
Apr 15 at 19:23
1
$begingroup$
Yes, by the way, a direct argument in both the models of Fraenkel is that any linear order would have a finite support and we can find a permutation that moves some things in an incongruous way.
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:35
1
$begingroup$
Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
$endgroup$
– YuiTo Cheng
Apr 15 at 23:04
$begingroup$
This question is not as far as I can tell a duplicate - that question is asking for a proof of the linear ordering principle without choice, while I was asking for a proof that the linear ordering principle can sometimes fail in the abscence of choice.
$endgroup$
– LGar
Apr 16 at 0:21
$begingroup$
What about Is every set linearly ordered in ZF
$endgroup$
– YuiTo Cheng
Apr 16 at 0:57
1
1
$begingroup$
In the case of the Fraenkel model, would this just come down to saying that any linear ordering would have a finite support, and then we just consider a permutation of two atoms outside of said support?
$endgroup$
– LGar
Apr 15 at 19:23
$begingroup$
In the case of the Fraenkel model, would this just come down to saying that any linear ordering would have a finite support, and then we just consider a permutation of two atoms outside of said support?
$endgroup$
– LGar
Apr 15 at 19:23
1
1
$begingroup$
Yes, by the way, a direct argument in both the models of Fraenkel is that any linear order would have a finite support and we can find a permutation that moves some things in an incongruous way.
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:35
$begingroup$
Yes, by the way, a direct argument in both the models of Fraenkel is that any linear order would have a finite support and we can find a permutation that moves some things in an incongruous way.
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:35
1
1
$begingroup$
Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
$endgroup$
– YuiTo Cheng
Apr 15 at 23:04
$begingroup$
Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
$endgroup$
– YuiTo Cheng
Apr 15 at 23:04
$begingroup$
This question is not as far as I can tell a duplicate - that question is asking for a proof of the linear ordering principle without choice, while I was asking for a proof that the linear ordering principle can sometimes fail in the abscence of choice.
$endgroup$
– LGar
Apr 16 at 0:21
$begingroup$
This question is not as far as I can tell a duplicate - that question is asking for a proof of the linear ordering principle without choice, while I was asking for a proof that the linear ordering principle can sometimes fail in the abscence of choice.
$endgroup$
– LGar
Apr 16 at 0:21
$begingroup$
What about Is every set linearly ordered in ZF
$endgroup$
– YuiTo Cheng
Apr 16 at 0:57
$begingroup$
What about Is every set linearly ordered in ZF
$endgroup$
– YuiTo Cheng
Apr 16 at 0:57
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Yes, both of Fraenkel's models are examples of such models. To see why note that:
In the first model, the atoms are an amorphous set. Namely, there cannot be split into two infinite sets. An amorphous set cannot be linearly ordered. To see why, note that $ain Amid atext defines a finite initial segment$ is either finite or co-finite. Assume it's co-finite, otherwise take the reverse order, then by removing finitely many elements we have a linear ordering where every proper initial segment is finite. This defines a bijection with $omega$, of course. So the set can be split into two infinite sets after all.
In the second model, the atoms can be written as a countable union of pairs which do not have a choice function. If the atoms were linearly orderable in that model, then we could have defined a choice function from the pairs: take the smallest one.
For models of $sf ZF$ one can imitate Fraenkel's construction using sets-of-sets-of Cohen reals as your atoms. This can be found in Jech's "Axiom of Choice" book in Chapter 5, as Cohen's second model.
$endgroup$
add a comment |
$begingroup$
An interesting example of a different kind is any model where all sets of reals have the Baire property. In any such set the quotient of $mathbb R$ by the Vitali equivalence relation is not linearly orderable. See here for a sketch.
Examples of such models are Solovay's model where all sets of reals are Lebesgue measurable, or natural models of the axiom of determinacy, or Shelah's model from section 7 of
MR0768264 (86g:03082a). Shelah, Saharon. Can you take Solovay's inaccessible away? Israel J. Math. 48 (1984), no. 1, 1–47.
$endgroup$
1
$begingroup$
Good examples, albeit significantly more complicated! :-)
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:33
add a comment |
Your Answer
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
);
);
LGar is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3189095%2fmodels-of-set-theory-where-not-every-set-can-be-linearly-ordered%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
$begingroup$
Yes, both of Fraenkel's models are examples of such models. To see why note that:
In the first model, the atoms are an amorphous set. Namely, there cannot be split into two infinite sets. An amorphous set cannot be linearly ordered. To see why, note that $ain Amid atext defines a finite initial segment$ is either finite or co-finite. Assume it's co-finite, otherwise take the reverse order, then by removing finitely many elements we have a linear ordering where every proper initial segment is finite. This defines a bijection with $omega$, of course. So the set can be split into two infinite sets after all.
In the second model, the atoms can be written as a countable union of pairs which do not have a choice function. If the atoms were linearly orderable in that model, then we could have defined a choice function from the pairs: take the smallest one.
For models of $sf ZF$ one can imitate Fraenkel's construction using sets-of-sets-of Cohen reals as your atoms. This can be found in Jech's "Axiom of Choice" book in Chapter 5, as Cohen's second model.
$endgroup$
add a comment |
$begingroup$
Yes, both of Fraenkel's models are examples of such models. To see why note that:
In the first model, the atoms are an amorphous set. Namely, there cannot be split into two infinite sets. An amorphous set cannot be linearly ordered. To see why, note that $ain Amid atext defines a finite initial segment$ is either finite or co-finite. Assume it's co-finite, otherwise take the reverse order, then by removing finitely many elements we have a linear ordering where every proper initial segment is finite. This defines a bijection with $omega$, of course. So the set can be split into two infinite sets after all.
In the second model, the atoms can be written as a countable union of pairs which do not have a choice function. If the atoms were linearly orderable in that model, then we could have defined a choice function from the pairs: take the smallest one.
For models of $sf ZF$ one can imitate Fraenkel's construction using sets-of-sets-of Cohen reals as your atoms. This can be found in Jech's "Axiom of Choice" book in Chapter 5, as Cohen's second model.
$endgroup$
add a comment |
$begingroup$
Yes, both of Fraenkel's models are examples of such models. To see why note that:
In the first model, the atoms are an amorphous set. Namely, there cannot be split into two infinite sets. An amorphous set cannot be linearly ordered. To see why, note that $ain Amid atext defines a finite initial segment$ is either finite or co-finite. Assume it's co-finite, otherwise take the reverse order, then by removing finitely many elements we have a linear ordering where every proper initial segment is finite. This defines a bijection with $omega$, of course. So the set can be split into two infinite sets after all.
In the second model, the atoms can be written as a countable union of pairs which do not have a choice function. If the atoms were linearly orderable in that model, then we could have defined a choice function from the pairs: take the smallest one.
For models of $sf ZF$ one can imitate Fraenkel's construction using sets-of-sets-of Cohen reals as your atoms. This can be found in Jech's "Axiom of Choice" book in Chapter 5, as Cohen's second model.
$endgroup$
Yes, both of Fraenkel's models are examples of such models. To see why note that:
In the first model, the atoms are an amorphous set. Namely, there cannot be split into two infinite sets. An amorphous set cannot be linearly ordered. To see why, note that $ain Amid atext defines a finite initial segment$ is either finite or co-finite. Assume it's co-finite, otherwise take the reverse order, then by removing finitely many elements we have a linear ordering where every proper initial segment is finite. This defines a bijection with $omega$, of course. So the set can be split into two infinite sets after all.
In the second model, the atoms can be written as a countable union of pairs which do not have a choice function. If the atoms were linearly orderable in that model, then we could have defined a choice function from the pairs: take the smallest one.
For models of $sf ZF$ one can imitate Fraenkel's construction using sets-of-sets-of Cohen reals as your atoms. This can be found in Jech's "Axiom of Choice" book in Chapter 5, as Cohen's second model.
answered Apr 15 at 19:30
Asaf Karagila♦Asaf Karagila
309k33441775
309k33441775
add a comment |
add a comment |
$begingroup$
An interesting example of a different kind is any model where all sets of reals have the Baire property. In any such set the quotient of $mathbb R$ by the Vitali equivalence relation is not linearly orderable. See here for a sketch.
Examples of such models are Solovay's model where all sets of reals are Lebesgue measurable, or natural models of the axiom of determinacy, or Shelah's model from section 7 of
MR0768264 (86g:03082a). Shelah, Saharon. Can you take Solovay's inaccessible away? Israel J. Math. 48 (1984), no. 1, 1–47.
$endgroup$
1
$begingroup$
Good examples, albeit significantly more complicated! :-)
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:33
add a comment |
$begingroup$
An interesting example of a different kind is any model where all sets of reals have the Baire property. In any such set the quotient of $mathbb R$ by the Vitali equivalence relation is not linearly orderable. See here for a sketch.
Examples of such models are Solovay's model where all sets of reals are Lebesgue measurable, or natural models of the axiom of determinacy, or Shelah's model from section 7 of
MR0768264 (86g:03082a). Shelah, Saharon. Can you take Solovay's inaccessible away? Israel J. Math. 48 (1984), no. 1, 1–47.
$endgroup$
1
$begingroup$
Good examples, albeit significantly more complicated! :-)
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:33
add a comment |
$begingroup$
An interesting example of a different kind is any model where all sets of reals have the Baire property. In any such set the quotient of $mathbb R$ by the Vitali equivalence relation is not linearly orderable. See here for a sketch.
Examples of such models are Solovay's model where all sets of reals are Lebesgue measurable, or natural models of the axiom of determinacy, or Shelah's model from section 7 of
MR0768264 (86g:03082a). Shelah, Saharon. Can you take Solovay's inaccessible away? Israel J. Math. 48 (1984), no. 1, 1–47.
$endgroup$
An interesting example of a different kind is any model where all sets of reals have the Baire property. In any such set the quotient of $mathbb R$ by the Vitali equivalence relation is not linearly orderable. See here for a sketch.
Examples of such models are Solovay's model where all sets of reals are Lebesgue measurable, or natural models of the axiom of determinacy, or Shelah's model from section 7 of
MR0768264 (86g:03082a). Shelah, Saharon. Can you take Solovay's inaccessible away? Israel J. Math. 48 (1984), no. 1, 1–47.
answered Apr 15 at 19:39
Andrés E. CaicedoAndrés E. Caicedo
66.1k8160252
66.1k8160252
1
$begingroup$
Good examples, albeit significantly more complicated! :-)
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:33
add a comment |
1
$begingroup$
Good examples, albeit significantly more complicated! :-)
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:33
1
1
$begingroup$
Good examples, albeit significantly more complicated! :-)
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:33
$begingroup$
Good examples, albeit significantly more complicated! :-)
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:33
add a comment |
LGar is a new contributor. Be nice, and check out our Code of Conduct.
LGar is a new contributor. Be nice, and check out our Code of Conduct.
LGar is a new contributor. Be nice, and check out our Code of Conduct.
LGar is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3189095%2fmodels-of-set-theory-where-not-every-set-can-be-linearly-ordered%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$
In the case of the Fraenkel model, would this just come down to saying that any linear ordering would have a finite support, and then we just consider a permutation of two atoms outside of said support?
$endgroup$
– LGar
Apr 15 at 19:23
1
$begingroup$
Yes, by the way, a direct argument in both the models of Fraenkel is that any linear order would have a finite support and we can find a permutation that moves some things in an incongruous way.
$endgroup$
– Asaf Karagila♦
Apr 15 at 21:35
1
$begingroup$
Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
$endgroup$
– YuiTo Cheng
Apr 15 at 23:04
$begingroup$
This question is not as far as I can tell a duplicate - that question is asking for a proof of the linear ordering principle without choice, while I was asking for a proof that the linear ordering principle can sometimes fail in the abscence of choice.
$endgroup$
– LGar
Apr 16 at 0:21
$begingroup$
What about Is every set linearly ordered in ZF
$endgroup$
– YuiTo Cheng
Apr 16 at 0:57