Mdthbs

I am not a queen, who am I?

What makes black pepper strong or mild?

WAN encapsulation

What do you call a plan that's an alternative plan in case your initial plan fails?

Doubts about chords

When -s is used with third person singular. What's its use in this context?

How to draw this diagram using TikZ package?

Can Pao de Queijo, and similar foods, be kosher for Passover?

Disable hyphenation for an entire paragraph

Do I really need recursive chmod to restrict access to a folder?

How do I keep my slimes from escaping their pens?

Should gear shift center itself while in neutral?

How to recreate this effect in Photoshop?

Is there a documented rationale why the House Ways and Means chairman can demand tax info?

ListPlot join points by nearest neighbor rather than order

Why was the term "discrete" used in discrete logarithm?

What are the motives behind Cersei's orders given to Bronn?

How can I make names more distinctive without making them longer?

Letter Boxed validator

How do I stop a creek from eroding my steep embankment?

Is a manifold-with-boundary with given interior and non-empty boundary essentially unique?

3 doors, three guards, one stone

Output the ŋarâþ crîþ alphabet song without using (m)any letters

Is there a Spanish version of "dot your i's and cross your t's" that includes the letter 'ñ'?

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

3

$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 45 mins ago

LGar

asked 5 hours ago

LGarLGar

406

New contributor

LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  5 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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♦
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
  $endgroup$
  – YuiTo Cheng
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  46 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What about Is every set linearly ordered in ZF
  $endgroup$
  – YuiTo Cheng
  11 mins ago
  
  
  

  
  
  
  

add a comment | 

3

$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 45 mins ago

LGar

asked 5 hours ago

LGarLGar

406

New contributor

LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  5 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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♦
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Possible duplicate of Proving "every set can be totally ordered" without using Axiom of Choice
  $endgroup$
  – YuiTo Cheng
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  46 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What about Is every set linearly ordered in ZF
  $endgroup$
  – YuiTo Cheng
  11 mins ago
  
  
  

  
  
  
  

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 45 mins ago

LGar

asked 5 hours ago

LGarLGar

406

New contributor

LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

edited 45 mins ago

LGar

asked 5 hours ago

LGarLGar

406

New contributor

LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

edited 45 mins ago

LGar

asked 5 hours ago

LGarLGar

406

New contributor

LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 5 hours ago

LGarLGar

406

New contributor

LGar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 5 hours ago

LGarLGar

406

2 Answers
2

active

oldest

votes

5

$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 5 hours ago

Asaf Karagila♦Asaf Karagila

308k33441775

$endgroup$

add a comment | 

5

$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 5 hours ago

Andrés E. CaicedoAndrés E. Caicedo

66.1k8160252

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Good examples, albeit significantly more complicated! :-)
  $endgroup$
  – Asaf Karagila♦
  3 hours ago
  

  
  
  
  

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.

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

5

$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 5 hours ago

Asaf Karagila♦Asaf Karagila

308k33441775

$endgroup$

add a comment | 

5

$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 5 hours ago

Asaf Karagila♦Asaf Karagila

308k33441775

$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 5 hours ago

Asaf Karagila♦Asaf Karagila

308k33441775

$endgroup$

share|cite|improve this answer

answered 5 hours ago

Asaf Karagila♦Asaf Karagila

308k33441775

answered 5 hours ago

Asaf Karagila♦Asaf Karagila

308k33441775

answered 5 hours ago

Asaf Karagila♦Asaf Karagila

308k33441775

5

$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 5 hours ago

Andrés E. CaicedoAndrés E. Caicedo

66.1k8160252

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Good examples, albeit significantly more complicated! :-)
  $endgroup$
  – Asaf Karagila♦
  3 hours ago
  

  
  
  
  

add a comment | 

5

$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 5 hours ago

Andrés E. CaicedoAndrés E. Caicedo

66.1k8160252

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Good examples, albeit significantly more complicated! :-)
  $endgroup$
  – Asaf Karagila♦
  3 hours ago
  

  
  
  
  

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 5 hours ago

Andrés E. CaicedoAndrés E. Caicedo

66.1k8160252

$endgroup$

share|cite|improve this answer

answered 5 hours ago

Andrés E. CaicedoAndrés E. Caicedo

66.1k8160252

answered 5 hours ago

Andrés E. CaicedoAndrés E. Caicedo

66.1k8160252

answered 5 hours ago

Andrés E. CaicedoAndrés E. Caicedo

66.1k8160252