# Choosing elements of linear orders

Is it consistent with ZF that there can be a countable family of linear orders, each isomorphic to $\mathbb Z$ (that is, every element has a unique predecessor and successor, and any two elements have finitely many elements between them), such that one cannot choose an element from each of them?

(Random musing inspired by this question.)

• Let $\{P_n: n \geq 1\}$ be a countable family of pairs of socks - So there is no set that contains exactly one sock from each $P_n$. Then $\{P_n \times Z: n \geq 1\}$ should work. – hot_queen Jun 29 '14 at 16:52
• @hot_queen: So then what are the orderings? – Nate Eldredge Jun 29 '14 at 17:05
• @hot_queen: But you can't choose the ordering for these sets. If you could, you can choose from $P_n$ the element for which $(a,0)$ was smaller than $(b,0)$. – Asaf Karagila Jun 29 '14 at 17:58
• You guys are right. What I wrote is nonsense. – hot_queen Jun 29 '14 at 17:59
• Is your statement equivalent to Countable Choice? – Forever Mozart Jun 30 '14 at 1:41

Yes, it is consistent. Let me sketch an argument using atoms, then the Jech-Sochor transfer theorem can do its magic (since it's a bounded statement).

Start with a countable set of atoms which is the disjoint union of $A_n$'s each countably infinite. Fix $\leq_n$ on $A_n$ which is a linear order of type $\omega^*+\omega$ (or $\Bbb Z$, in other words).

The automorphism group is $\mathscr G$, of permutations of the atoms which preserve both the partition into the $A_n$'s and their linear orders. In other words, we take a sequence of automorphisms of $\leq_n$ (which are finite shifts), and they each act on the relevant $A_n$. Let us denote a permutation by $\pi$ and $\pi_n$ is the permutation on the $n$-th coordinate.

We define a filter of subgroups in the following way. Given $H$ a subgroup of $\mathscr G$, $H$ is in the filter if and only if there exists a finite $E\subseteq\omega$, such that whenever $\pi\in\mathscr G$ for which $\forall n\in E$, $\pi_n=\operatorname{id}$, then $\pi\in H$. (For example taking $E=\varnothing$ we have that $\{\pi\in\mathscr G\mid\forall n\in\varnothing(\pi_n=\operatorname{id})\}=\mathscr G$ itself.)

Some easy propositions:

1. Each $A_n$ is symmetric, and each $\leq_n$ is symmetric.
2. The enumerated partition $\{A_n\mid n\in\omega\}$ is symmetric, and the enumeration of the orders is also symmetric.

And the important point: There is no choice function from the $A_n$'s.

Sketch for a proof: If $f$ was such a choice function, it would have a finite support $E$ as above, now taking any $k\notin E$ we can apply any $\pi$ which fixes $f$ but $\pi_k\neq\operatorname{id}$ to get a contradiction.

(This is the usual argument.)

Now we can use the Jech-Sochor theorem. Or we could have used forcing to begin with, it would just make things harder to write down properly in this case.

• I'm afraid you lost me at "The filter of subgroups ..." Are you sure that sentence says what you meant it to? As written it looks like every subgroup $H$ meets the condition because we can take $E=\varnothing$ and then "for all $n\in E$" is vacuously true. (And where is $\pi$ quantified in this definition?) – Henning Makholm Jun 30 '14 at 1:17
• Also, did I miss a definition of "symmetric", which you seem to apply to a lot of different things in the subsequent text? – Henning Makholm Jun 30 '14 at 1:17
• @Henning: I sort of skipped the most of it; I'd thought that you know a bit more about the topic. In any case, here are two different threads with the definitions. As for the empty case, note that if $E=\varnothing$ then it is necessarily the case that $H=\mathscr G$. – Asaf Karagila Jun 30 '14 at 1:23
• x @Asaf: Really? Take any odd $H$. Then there exists $E$ (namely $\varnothing$) such that $E$ is a finite subset of $\omega$ (yes, $\varnothing$ is a finite subset of $\omega$), and such that $\forall n\in E$ such-and-such holds (trivially because $E$ is empty). – Henning Makholm Jun 30 '14 at 1:27
• Henning, I do not appreciate the tone of your text. I'm trying to answer and be helpful. And since we require that ALL the permutations $\pi$ such that $\pi_n=\operatorname{id}$, for all $n\in E$ this is necessarily means that EVERY $\pi\in\mathscr G$ satisfies this condition. So all in all, $H=\mathscr G$ (yes, double inclusion and whatnot). – Asaf Karagila Jun 30 '14 at 1:29