Mdthbs

According to the Wikipedia Page on amorphous sets, no amorphous set can be totally ordered. If I am correct, this states that every infinite totally ordered set has two disjoint infinite subsets, but I am not sure how to go about proving it in ZF (if it is even provable in ZF), although here's my attempt:

Every infinite totally ordered set $S$ has either an infinitely decreasing or infinitely increasing subset, so I tried considering such a subset $A$. Without loss of generality, suppose $A$ is increasing. Then, letting $a_{1}$ be an element in $A$, the set $A_{1}:={ain Amid a>a_{1}}$ is infinite and thus non-empty. Now, let $a_{2}$ be an element of ${ain A|a>a_{1}}$. Since $a_{2}in A$, the set $A_{2}:={ain Amid a>a_{2}}$ is nonempty, and we can continue in this way to generate a sequence ${a_{1},a_{2},dots}$.

My problem is that I rather suspect I just used the axiom of countable choice if not something stronger. Is there a way of proving this in ZF alone?

Your proof attempt does indeed depend not only on countable choice, but on dependent choice.

Here's an argument that doesn't:

Suppose $S$ is infinite and totally ordered. If we can find even one element that has both infinitely many predecessors and infinitely many successors, then $S$ is surely not amorphous.¹

Thus the elements of $S$ fall into two classes, namely those with only finitely many predecessors and those with only finitely many successors. At least one of those classes must be infinite; without loss of generality let's suppose that there are infinitely many elements that have finitely many predecessors.

However, in a total order there can be at most one element that has, for example, exactly 42 predecessors. So counting predecessors gives us an injection from an infinite subset of $S$ into $mathbb N$, which means that this subset is countable and $S$ is therefore not amorphous.

¹: Note that this apparently unassuming first step is in fact critical to the argument; without it everything unravels. It is consistent with ZF that there may be an infinite totally ordered set that has no countably infinite subset. (Cohen showed a model in which $mathbb R$, definitely totally orderable, has a subset with this property.)

Yes, this is provable in ZF. Let $S$ be an infinite linearly ordered set; I'll try to produce two disjoint, infinite subsets of $S$. First, for any $sin S$, consider the set $A_s$ of elements above $s$ in the linear ordering and the set $B_s$ of elements below $s$. If, for some $s$, both $A_s$ and $B_s$ are infinite, we're done, because they're certainly disjoint.

So from now on, we can assume that, for each $s$, one of $A_s$ and $B_s$ is finite (and the other must then be infinite because $S$ is infinite). Without loss of generality, assume there are infinitely many $s$ with $B_s$ finite. (If that's not the case, then, as $S$ is infinite, there will be infinitely many $s$ with $A_s$ finite, and the following argument will apply to the reversed linear ordering.)

For each of the infinitely many $s$ with $B_s$ finite, $|B_s|$ is a natural number, and these natural numbers are different for different $s$. So we have a one-to-one map $f:smapsto |B_s|$ of an infinite subset of $S$ into $mathbb N$. But the image of that map (which in fact is all of $mathbb N$ but I don't need that) can be split into two infinite pieces by taking alternating elements of it. The inverse images of those pieces under $f$ are two disjoint infinite subsets of $S$, as required.