Is the Ordering Principle equivalent to a selection principle?

Question

Working in the context of set theory $\sf ZF$, selection may be defined as a function from nonempty sets to their elements. Formally:

$\operatorname {selective}(c) \iff \operatorname {function}(c) \land \forall x \in dom(c): x \neq \emptyset \to c(x) \in x$

Restricted selections to be defined in a conditional manner by letting $c$ itself be the result of a function from prior parameters, i.e. we can have $c=F(x_1,..,x_n)$, this way we may say that $c$ is conditioned after $x_1,..,x_n$ and the function $F$, also we can impose conditions on the kind of sets from which selections are made. To capture that formally we write:

$ \forall x_1,..,\forall x_n \exists F \forall y \neq \emptyset : \Omega \to \exists z \in y: F(x_1,..,x_n)(y)=z $

Where $F$ may be used in $\Omega$.

This conditional selection principle is to be denoted $\mathcal S^\Omega$.

For example we write the axiom of dependent choice $\sf DC$, along those lines:

If $R$ is a set implementing a total relation on set $S$, denoted $R|^T S$, then we take the relation $$R^*=\{ \langle x, s \rangle \mid x \in S, s=\{y \in S \mid x \ R \ y \} \}$$. For short, we'll denote the above formula as: $\Psi$

$ \forall S \forall R \forall h \exists F \forall y \neq \emptyset: \\ \Big{(}R|^T S \land \exists R^* \exists x : \Psi \land h \in S \land y=R^*(x) \land \\ \big{[}x=h \lor \exists d \in S : x=F(S,R,h)(R^*(d)) \big{]} \Big{)} \\ \to \\ \exists z \in y: z=F(S,R, h)(y)$

So, dependent choice is one form of conditional selection!

To get the full axiom of choice, we set $n=1$, and $\Omega$ to be $y \in x$, then we get: $$\forall x \exists F \forall y \neq \emptyset : y \in x \to \exists z \in y: z=F(x) (y)$$

To get countable choice, we set $n=1$, and $\Omega$ to be $|x|=\omega \land y \in x $, then we get: $$\forall x \exists F \forall y \neq \emptyset: |x|=\omega \land y \in x \to \exists z \in y: z=F(x)(y)$$

Now, if we define choice principle over $\sf ZF$, in the following manner:

$\sf H$ is a choice principle if and only if we have a formula $\Omega$ such that both of the following are fulfilled:

\begin{align} \bullet \ \sf (ZF+H) \vdash (ZF+\mathcal S^\Omega)\\ \bullet \ \sf (ZF + \mathcal S^\Omega) \vdash (ZF + H) \end{align}

. And provided that: $\sf ZF \not \vdash \mathcal S^\Omega$

Then can we prove (in $\sf ZF$ or some suitable extension of it) that the Ordering Principle [every set can be linearly ordered] is a choice principle?

[Addendum] I should relate my personal output on that issue: principles like the Ordering Principle and the Small Violations of Choice principle [see Asaf's posting], which I think are spoken about in the context of what may be called as weak choice principles, meaning that they are fragments of $\sf AC$ that are not provable in $\sf ZF$. As, a terminology I'd prefer to call those pre-choice Principles. So, if they prove to be inequivalent with any selection principle, then they are proper pre-choice principles. This is to discriminate them from weak choice principles like $\sf DC, CC, etc..$ which are equivalent to selection principles, but weaker than $\sf AC$.

Answer 1

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.

Answer 2

Here is a variation on the same theme as Joel David Hamkins' answer.

Theorem. The following are equivalent over ZF set theory:

• Every set admits a linear order.
• For every set $X$, there is a function choosing for each subset $Y$ of $X$ a total preordering of $Y$ which is nontrivial unless $|Y| \leq 1$.

By preordering, I mean a reflexive transitive relation on a set; a total preordering is one where any two elements are comparable (perhaps both ways). A total preordering is nontrivial if there are two elements that are not comparable.