Skip to main content
6 of 6
deleted 1545 characters in body; edited title
Zuhair Al-Johar
  • 11.3k
  • 1
  • 13
  • 47

Is the Ordering Principle equivalent to a selection principle?

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$.

Zuhair Al-Johar
  • 11.3k
  • 1
  • 13
  • 47