Return to Answer

Here is one way to view the so-called ordering principle as a selection principle.

Theorem. The following are equivalent over ZF set theory:

1. Every set admits a linear order.
2. For every set $X$, there is a choice function choosing for each linear order of a proper subset of $X$ a proper extension of that order to a linear order of a subset of $X$.

In 2, the proper extension can add just one or a lot of new points, as it likes.

Proof. For the implication $(1\to 2)$, suppose that we have a set $X$. We may fix a linear order $\leq$ of $X$. Now, given a linear order $\preceq$ of a proper subset $Y\subseteq X$, we can simply extend $\preceq$ by placing all the other elements of $X-Y$ on top and in the order induced by $\leq\upharpoonright(X-Y)$.

For the implication $(2\to 1)$, suppose that we have a function $F$ that chooses larger linear orders for any given linear order of a proper subset of $X$. Define $\langle X_\alpha,\leq_\alpha\rangle$ by recursively applying the function, starting with the empty order $X_0=\emptyset$, applying $F$ at successor stages, and taking unions at limits. Since the set of all linearly ordered subsets of $X$ is a set in ZF, it has a Hartog number, and so this recursion cannot go forever through the ordinals. But the only way it stops is if $X_\alpha=X$ for some $\alpha$. And thus $X$ is linearly orderable as desired. $\Box$

(We can formulate statement 2 as a selection principle, by considering families of sets of pairs $\langle \preceq,\leq\rangle$, where these are linear orders of subsets of $X$ and the first extends properly to the second, and where in each set in family, the first order $\preceq$ is the same. So the desired choice function is selecting such a pair, which in effect is selecting a particular extension $\leq$ of $\preceq$.)

Here is one way to view the so-called ordering principle as a selection principle.

Theorem. The following are equivalent over ZF set theory:

1. Every set admits a linear order.
2. For every set $X$, there is a choice function choosing for each linear order of a proper subset of $X$ a proper extension of that order to a linear order of a subset of $X$.

In 2, the proper extension can add just one or a lot of new points, as it likes.

Proof. For the implication $(1\to 2)$, suppose that we have a set $X$. We may fix a linear order $\leq$ of $X$. Now, given a linear order $\preceq$ of a proper subset $Y\subseteq X$, we can simply extend $\preceq$ by placing all the other elements of $X-Y$ on top and in the order induced by $\leq\upharpoonright(X-Y)$.

For the implication $(2\to 1)$, suppose that we have a function $F$ that chooses larger linear orders for any given linear order of a proper subset of $X$. Define $\langle X_\alpha,\leq_\alpha\rangle$ by recursively applying the function, starting with the empty order $X_0=\emptyset$, applying $F$ at successor stages, and taking unions at limits. Since the set of all linearly ordered subsets of $X$ is a set in ZF, it has a Hartog number, and so this recursion cannot go forever through the ordinals. But the only way it stops is if $X_\alpha=X$ for some $\alpha$. And thus $X$ is linearly orderable as desired. $\Box$

(We can formulate statement 2 as a selection principle, by considering families of sets of pairs $\langle \preceq,\leq\rangle$, where these are linear orders of subsets of $X$ and the first extends properly to the second, and where in each set in family, the first order $\preceq$ is the same. So the desired choice function is selecting such a pair, which in effect is selecting a particular extension $\leq$ of $\preceq$.)

If the choice function in statement 2 always adding just one more point, then this would provide a well-ordering of $X$. So in the cases where AC fails and $X$ is not well-orderable, then the choice function will generally be placing a lot of new points into the chosen larger order.

Here is one way to view the so-called ordering principle as a selection principle.

Theorem. The following are equivalent over ZF set theory:

1. Every set admits a linear order.
2. For every set $X$, there is a choice function choosing for each linear order of a proper subset of $X$ a proper extension of that order to a linear order of a subset of $X$.

Proof. For the implication $(1\to 2)$, suppose that we have a set $X$. We may fix a linear order $\leq$ of $X$. Now, given a linear order $\preceq$ of a proper subset $Y\subseteq X$, we can simply extend $\preceq$ by placing all the other elements of $X-Y$ on top and in the order induced by $\leq\upharpoonright(X-Y)$.

For the implication $(2\to 1)$, suppose that we have a function $F$ that chooses larger linear orders for any given linear order of a proper subset of $X$. Define $\langle X_\alpha,\leq_\alpha\rangle$ by recursively applying the function, starting with the empty order $X_0=\emptyset$, applying $F$ at successor stages, and taking unions at limits. Since the set of all linearly ordered subsets of $X$ is a set in ZF, it has a Hartog number, and so this recursion cannot go forever through the ordinals. But the only way it stops is if $X_\alpha=X$ for some $\alpha$. And thus $X$ is linearly orderable as desired. $\Box$

(We can formulate statement 2 as a selection principle, by considering families of sets of pairs $\langle \preceq,\leq\rangle$, where these are linear orders of subsets of $X$ and the first extends properly to the second, and where in each set in family, the first order $\preceq$ is the same. So the desired choice function is selecting such a pair, which in effect is selecting a particular extension $\leq$ of $\preceq$.)

Here is one way to view the so-called ordering principle as a selection principle.

Theorem. The following are equivalent over ZF set theory:

1. Every set admits a linear order.
2. For every set $X$, there is a choice function choosing for each linear order of a proper subset of $X$ a proper extension of that order to a linear order of a subset of $X$.

In 2, the proper extension can add just one or a lot of new points, as it likes.

Proof. For the implication $(1\to 2)$, suppose that we have a set $X$. We may fix a linear order $\leq$ of $X$. Now, given a linear order $\preceq$ of a proper subset $Y\subseteq X$, we can simply extend $\preceq$ by placing all the other elements of $X-Y$ on top and in the order induced by $\leq\upharpoonright(X-Y)$.

For the implication $(2\to 1)$, suppose that we have a function $F$ that chooses larger linear orders for any given linear order of a proper subset of $X$. Define $\langle X_\alpha,\leq_\alpha\rangle$ by recursively applying the function, starting with the empty order $X_0=\emptyset$, applying $F$ at successor stages, and taking unions at limits. Since the set of all linearly ordered subsets of $X$ is a set in ZF, it has a Hartog number, and so this recursion cannot go forever through the ordinals. But the only way it stops is if $X_\alpha=X$ for some $\alpha$. And thus $X$ is linearly orderable as desired. $\Box$

(We can formulate statement 2 as a selection principle, by considering families of sets of pairs $\langle \preceq,\leq\rangle$, where these are linear orders of subsets of $X$ and the first extends properly to the second, and where in each set in family, the first order $\preceq$ is the same. So the desired choice function is selecting such a pair, which in effect is selecting a particular extension $\leq$ of $\preceq$.)

Here is one way to view the so-called ordering principle as a selection principle.

Theorem. The following are equivalent over ZF set theory:

1. Every set admits a linear order.
2. For every set $X$, there is a choice function choosing for each linear order of a subset of $X$ a proper extension of that order to a larger linear order of a subset of $X$.

Proof. For the implication $(1\to 2)$, suppose that we have a set $X$. We may fix a linear order $\leq$ of $X$. Now, given a linear order $\preceq$ of a subset $Y\subseteq X$, we can simply extend $\preceq$ by placing all the other elements of $X-Y$ on top and in the order induced by $\leq\upharpoonright(X-Y)$.

For the implication $(2\to 1)$, suppose that we have a function $F$ that chooses larger linear orders for any given linear order of a subset of $X$. Define $\langle X_\alpha,\leq_\alpha\rangle$ by recursively applying the function, starting with the empty order $X_0=\emptyset$, applying $F$ at successor stages, and taking unions at limits. Since the set of linearly ordered subsets of $X$ is a set in ZF, it has a Hartog number, and so this recursion cannot go forever through the ordinals. But the only way it stops is if $X_\alpha=X$ for some $\alpha$. And thus $X$ is linearly orderable as desired. $\Box$

(We can formulate statement 2 as a selection principle, by considering families of sets of pairs $\langle \preceq,\leq\rangle$, where these are linear orders of subsets of $X$ and the first extends properly to the second, and where in each set in family, the first order $\preceq$ is the same. So the desired choice function is selecting such a pair, which in effect is selecting a particular extension $\leq$ of $\preceq$.)

Here is one way to view the so-called ordering principle as a selection principle.

Theorem. The following are equivalent over ZF set theory:

1. Every set admits a linear order.
2. For every set $X$, there is a choice function choosing for each linear order of a proper subset of $X$ a proper extension of that order to a linear order of a subset of $X$.

Proof. For the implication $(1\to 2)$, suppose that we have a set $X$. We may fix a linear order $\leq$ of $X$. Now, given a linear order $\preceq$ of a proper subset $Y\subseteq X$, we can simply extend $\preceq$ by placing all the other elements of $X-Y$ on top and in the order induced by $\leq\upharpoonright(X-Y)$.

For the implication $(2\to 1)$, suppose that we have a function $F$ that chooses larger linear orders for any given linear order of a proper subset of $X$. Define $\langle X_\alpha,\leq_\alpha\rangle$ by recursively applying the function, starting with the empty order $X_0=\emptyset$, applying $F$ at successor stages, and taking unions at limits. Since the set of all linearly ordered subsets of $X$ is a set in ZF, it has a Hartog number, and so this recursion cannot go forever through the ordinals. But the only way it stops is if $X_\alpha=X$ for some $\alpha$. And thus $X$ is linearly orderable as desired. $\Box$

(We can formulate statement 2 as a selection principle, by considering families of sets of pairs $\langle \preceq,\leq\rangle$, where these are linear orders of subsets of $X$ and the first extends properly to the second, and where in each set in family, the first order $\preceq$ is the same. So the desired choice function is selecting such a pair, which in effect is selecting a particular extension $\leq$ of $\preceq$.)