Bsrgvty

1, 2, 4, 8, 16, ... 33?

How to make interviewee comfortable interviewing in lounge chairs

To what extent is it worthwhile to report check fraud / refund scams?

Guitar tuning (EADGBE), "perfect" fourths?

How use custom order in folder on Windows 7 and 10

2000s Animated TV show where teenagers could physically go into a virtual world

Writing a letter of recommendation for a mediocre student

How to deal with my team leader who keeps calling me about project updates even though I am on leave for personal reasons?

Piece de Resistance - Ten Quotas. Nine Passed. Your Turn

Is it more effective to add yeast before or after kneading?

What is the meaning of "heutig" in this sentence?

Resolving moral conflict

Why does this image of Jupiter look so strange?

What's the story to "WotC gave up on fixing Polymorph"?

Painting a 4x6 grid with 2 colours

I reverse the source code, you negate the input!

Type_traits *_v variable template utility order fails to compile

Can Northern Ireland's border issue be solved by repartition?

Is it right to extend flaps only in the white arc?

What do you do if you have developments on your paper during the long peer review process?

Could Apollo astronauts see city lights from the moon?

Social leper versus social leopard

When is it acceptable to write a bad letter of recommendation?

Does Fires of Invention allow adventure instant and sorceries to be played for free?

Models of set theory where not every set can be linearly ordered

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?How 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?Linearly ordering the power set of a well ordered set with ZF (without AC)In ZF set theory, can every countably infinite set be linearly ordered?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

5

1

$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

share|cite|improve this question

edited Apr 16 at 0:22

LGar

asked Apr 15 at 19:21

LGarLGar

5566 bronze badges

$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
 | 

5

1

$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

share|cite|improve this question

edited Apr 16 at 0:22

LGar

asked Apr 15 at 19:21

LGarLGar

5566 bronze badges

$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

share|cite|improve this question

edited Apr 16 at 0:22

LGar

asked Apr 15 at 19:21

LGarLGar

5566 bronze badges

$endgroup$

share|cite|improve this question

edited Apr 16 at 0:22

LGar

asked Apr 15 at 19:21

LGarLGar

5566 bronze badges

share|cite|improve this question

edited Apr 16 at 0:22

LGar

asked Apr 15 at 19:21

LGarLGar

5566 bronze badges

asked Apr 15 at 19:21

LGarLGar

5566 bronze badges

asked Apr 15 at 19:21

LGarLGar

5566 bronze badges

2 Answers
2

active

oldest

votes

9

$begingroup$

Yes, both of Fraenkel's models are examples of such models. To see why note that:

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




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

share|cite|improve this answer

answered Apr 15 at 19:30

Asaf Karagila♦Asaf Karagila

316k3535 gold badges454454 silver badges793793 bronze badges

$endgroup$

add a comment
 | 

7

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

share|cite|improve this answer

answered Apr 15 at 19:39

Andrés E. CaicedoAndrés E. Caicedo

67.1k88 gold badges170170 silver badges263263 bronze badges

$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/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

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

Name

Email

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

Name

Email

Required, but never shown

9

$begingroup$

Yes, both of Fraenkel's models are examples of such models. To see why note that:

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




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

share|cite|improve this answer

answered Apr 15 at 19:30

Asaf Karagila♦Asaf Karagila

316k3535 gold badges454454 silver badges793793 bronze badges

$endgroup$

add a comment
 | 

9

$begingroup$

Yes, both of Fraenkel's models are examples of such models. To see why note that:

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




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

share|cite|improve this answer

answered Apr 15 at 19:30

Asaf Karagila♦Asaf Karagila

316k3535 gold badges454454 silver badges793793 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

Yes, both of Fraenkel's models are examples of such models. To see why note that:

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




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

share|cite|improve this answer

answered Apr 15 at 19:30

Asaf Karagila♦Asaf Karagila

316k3535 gold badges454454 silver badges793793 bronze badges

$endgroup$

share|cite|improve this answer

answered Apr 15 at 19:30

Asaf Karagila♦Asaf Karagila

316k3535 gold badges454454 silver badges793793 bronze badges

answered Apr 15 at 19:30

Asaf Karagila♦Asaf Karagila

316k3535 gold badges454454 silver badges793793 bronze badges

answered Apr 15 at 19:30

Asaf Karagila♦Asaf Karagila

316k3535 gold badges454454 silver badges793793 bronze badges

7

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

share|cite|improve this answer

answered Apr 15 at 19:39

Andrés E. CaicedoAndrés E. Caicedo

67.1k88 gold badges170170 silver badges263263 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Good examples, albeit significantly more complicated! :-)
  $endgroup$
  – Asaf Karagila♦
  Apr 15 at 21:33
  

  
  
  
  

add a comment
 | 

7

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

share|cite|improve this answer

answered Apr 15 at 19:39

Andrés E. CaicedoAndrés E. Caicedo

67.1k88 gold badges170170 silver badges263263 bronze badges

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

share|cite|improve this answer

answered Apr 15 at 19:39

Andrés E. CaicedoAndrés E. Caicedo

67.1k88 gold badges170170 silver badges263263 bronze badges

$endgroup$

share|cite|improve this answer

answered Apr 15 at 19:39

Andrés E. CaicedoAndrés E. Caicedo

67.1k88 gold badges170170 silver badges263263 bronze badges

answered Apr 15 at 19:39

Andrés E. CaicedoAndrés E. Caicedo

67.1k88 gold badges170170 silver badges263263 bronze badges

answered Apr 15 at 19:39

Andrés E. CaicedoAndrés E. Caicedo

67.1k88 gold badges170170 silver badges263263 bronze badges