Skip to main content
1 of 6
Zuhair Al-Johar
  • 11.3k
  • 1
  • 13
  • 47

Can we adequately define Choice Principle this way?

For a suitable theory $\sf T$, A choice principle over $\sf T$ is what is bi-interpretable with a selection principle over $\sf T$.

In the context of set theory $\sf ZF$, selection can be defined as a function from nonempty sets to their elements. Restricted selections are defined in a conditional manner by letting the function be partial and requiring the nonempty sets to meet certain conditions for selection from them to be defined. So, generally we may write:

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

$c$ itself can 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$. Formally, this is:

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

So, here the formula $\Omega$ qualifies the parameters ($x_1,..,x_n$) of the selective function as well as the field of selection $(y)$, i.e. the sets from which selections are made.

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, my point is that we can define choice principle by saying that: $\sf H$ is a choice principle over say $\sf ZF$, if and only if, we have a formula $\Omega$, such that: $$\sf ZF + H \rightleftharpoons ZF + \mathcal S^\Omega$$, and provided that $\sf ZF \not \vdash \mathcal S^\Omega$

Where "$\rightleftharpoons$" signify "bi-interpretability".

Bi-interpretability can work across languages. If we are to work within a single language, then perhaps simple theoretic equivalence is nicer, then for the case of $\sf ZF$, demand: $$\sf (ZF+H) \vdash (ZF+\mathcal S^\Omega) \\ (ZF + \mathcal S^\Omega) \vdash (ZF + H) $$. And of course we have: $\sf ZF \not \vdash \mathcal S^\Omega$

Seeing Asaf's posting "What is a Choice Principle, really", mentions what can be a counter-example to the above, like the Ordering Principle, that every set can be linearly ordered. And also one answer to it mentioned the principle $\neg\text{Con}(\text{ZFC})\to\text{AC}$, which was regarded as a form of conditional choice, let's call it Inconsistency Choice Principle.

So, my main question is:

Are there clear intuitively justified choice principles that those definitions fail to capture?

Related questions: Along the line of definition of choice principle given here:

Can the Ordering Principle be proved to be a choice principle?

Can the Inconsistency Choice Principle be proved to be a choice principle?

By the way, I'm not sure if intuitively these two principles actually qualify as choice principles even though they may be mentioned as such, if this line contradicts that, then I'd be happy to dismiss those qualifications as imprecise.

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