# Partition of non-well-orderable sets

Call a non-well-orderable set "simple'' if whenever it is partitioned into two pieces, one of them is well-orderable.

Does ZF prove that every non-well-orderable set has a simple non-well-orderable subset?

• I don't know for sure, but it seems easy to construct this with the axiom of choice, however can we do the converse (prove axiom of choice from this proposition)? I would say probably, but the construction should be tricky! (+1) My guess: You need ZFC Commented Aug 31, 2023 at 23:32
• It is consistent with $\mathsf{ZF}$ that $\mathbb R$ is not well-orderable and that the continuum hypothesis holds in the sense that any subset of $\mathbb R$ is either countable or has the same size as $\mathbb R$. Commented Aug 31, 2023 at 23:39
• @AndrésE.Caicedo Can you explain why $\mathbb{R}$ can be partitioned into two non-well-orderable sets in this case? Commented Sep 1, 2023 at 5:04
• @user123 $\mathbb R=(-\infty,0)\cup[0,\infty)$. Both sets have size $|\mathbb R|$ and are therefore non-well-orderable, since $\mathbb R$ itself cannot be well-ordered (in the setting I described). If $A$ is an uncountable subset of $\mathbb R$, then $|A|=|\mathbb R|$ (again, in the setting I described), and a bijection between $A$ and $\mathbb R$ allows us to transfer the suggested partition of $\mathbb R$ into a partition of $A$ into two pieces of size $|\mathbb R|$ and therefore non-well-orderable. Commented Sep 1, 2023 at 5:57

Let me add another example, namely Cohen's first model. In that model we have a subset of $$\Bbb R$$ which is an infinite Dedekind-finite set, $$A$$. I claim that this $$A$$, and indeed any infinite Dedekind-finite subset of $$\Bbb R$$, is not well-orderable, and it is not simple.

To see that, first note that $$A$$ is not amorphous. Recall that a set is called amorphous if every partition into two parts has one of those be finite. But amorphous sets cannot be linearly ordered, so $$A$$ is not amorphous. Next, since $$A$$ is Dedekind-finite, every well-orderable subset is finite.

So, if a Dedekind-finite is not amorphous, it is not simple. Moreover, any subset of a Dedekind-finite set is Dedekind-finite. And so, once it can be linearly ordered, it is immediately hereditarily "not simple". And that is indeed the case in Cohen's model.

• Any thoughts on whether the statement that every non-well-orderable set has a simple non-well-orderable subset is consistent with $\mathsf{ZF}$? Commented Sep 1, 2023 at 20:24
• Yeah, it did cross my mind. Very unclear! Commented Sep 1, 2023 at 21:44
• @AndrésE.Caicedo This is at least consistent with ZFA. In the basic Fraenkel model, it should be true that any set is either wellorderable or contains an amorphous subset. And an amorphous set is of course simple. There is a good chance that this can be transferred to a ZF model, but Im not an expert on these things... Commented Sep 5, 2023 at 13:02
• @Andreas: It's not entirely clear, since at some point you're going to have to contend with non-well orderable sets of ordinals, which are themselves linearly orderable, so amorphous sets are not necessarily going to work. This would require a much more delicate transfer approach. Commented Sep 5, 2023 at 15:19
• @AsafKaragila I see, youre right! In fact it holds that ZF proves: If "any nonwellorderable set contains an amorphous set" then AC holds. So indeed this approach cannot work at all for ZF. Commented Sep 6, 2023 at 12:36

As Andrés mentions in the comments, $$\mathbb R$$ is consistently a counterexample.

Consider a model (e.g. Solovay's) where every set of reals has the perfect set property, which means that it either is countable or has a perfect subset. Since all perfect sets have cardinality $$2^{\aleph_0},$$ this means all sets of reals have cardinality at most $$\aleph_0$$, or $$2^{\aleph_0}.$$

Every set of reals having the perfect set property also implies that the reals are not well-orderable, since, for instance, a well-ordering of the reals allows one to construct a Bernstein set, which doesn't have any nice regularity properties.

Putting it together, in this model, 'uncountable' and 'not-well-orderable' and 'size $$2^{\aleph_0}$$' are synonymous for sets of reals. So with that in mind, since $$\mathbb R$$ can be easily partitioned into two uncountable sets, so too can any uncountable subset of $$\mathbb R,$$ and thus the conjecture is false in this model.

• $\mathbb R=(-\infty,0)\cup[0,\infty)$. And any uncountable subset of $\mathbb R$ has the same size as $\mathbb R$. Commented Sep 1, 2023 at 5:59
• @AndrésE.Caicedo Thank you, now I had to expand to justify my answer's existence. Commented Sep 1, 2023 at 6:22