Are there versions of the axiom of choice that restrict the size of the factors?

372 Views Asked by At

One formulation of the axiom of choice is that an arbitrary product of nonempty sets must be nonempty. The axiom of countable choice AC$_\omega$ is known to be strictly weaker than AC, but still independent of ZF; it is equivalent to the statement that a countable product of nonempty sets is nonempty.

Can one obtain a nontrivial but weaker version of AC by restricting the size of the factor sets in the product, rather than the size of the index set over which the product is taken?

For a non-example, say that AC$_z$ is the statement that an arbitrary product of countable sets is nonempty. Certainly ZF + AC implies ZF + AC$_z$. But it seems to me that ZF implies AC$_z$ even without AC: Let the index set be $\mathcal C$. Since for each factor set $s\in\mathcal C$ in the product there is a bijection $f_s: s\leftrightarrow \Bbb N $, the set $\{f_s(0): s\in\mathcal C\}$ is an element of the product.; Or equivalently if $\mathcal C$ is a family of countable sets, then the function $c:{\mathcal C} \to \bigcup{\mathcal C}$ which takes $s\mapsto f_s(0)$ is a choice function for $\mathcal C$, and exists in ZF without need for AC$_z$ as a separate axiom.

Let's say that the "restricted choice axiom" $AC_\Phi$ is the statement

If $\mathcal C$ is an arbitrary collection of sets, and $\Phi(X)$ holds for each element $X\in\mathcal C$, there is a choice function for $\mathcal C$.

Depending on $\Phi$, $AC_\Phi$ could be very weak, or it could be as strong as AC itself. My question is:

Is there $\Phi$ such that ZF + $AC_\Phi$ proves strictly more than ZF but strictly less than ZFC?

If I've made any errors of fact or logic in this post, I would be grateful for corrections.

2

There are 2 best solutions below

7
On BEST ANSWER

In most cases $\sf ZF$ cannot prove that choice from families of restricted sets (rather restricted families) exists. In fact limitation on the size of the family is often independent from the limitation on the size of the members of the family.

In fact even $\sf AC_{fin}$ which states "every family of non-empty finite sets admits a choice function" is independent from $\sf ZF$, but strictly weaker than $\sf ZFC$.

In the texts which deal a lot with fine versions of choice (see P. Howard, Rubin & Rubin, E. Hall, and so on) you will often see $C(X,Y)$ where $X$ is a limitation on the size of the family, and $Y$ is a limitation on the size of the members of the family.

Something of interest, there has been a work of classifying choice from families of finite sets, e.g. choice from pairs does not imply choice from triplets and vice versa. You can find the details in Jech, The Axiom of Choice, chapter 7.

In the same book, on chapter 8, Jech has a proof that $\sf DC_{\kappa}$ cannot prove that there is a choice function on a family of $\kappa^+$ pairs.

More examples include Cohen's first model in which the axiom of countable choice fails; but every well-ordered family of well-ordered sets admits a choice function (i.e. we can choose well-ordered uniformly). On the other hand, assuming that every well-ordered family admits a choice function cannot even prove that every uncountable set has a subset of size $\aleph_1$.

There are tons of intricate relations between the many different ways of weakening the axiom of choice. The general rule of thumb is that whenever something can go wrong, it will. Much like Murphy's Law.

1
On

As a basic example, $\mathsf{AC}(\mathrm{fin})$, the statement that the Axiom of Choice holds for all families of finite sets, is known to be implied by the Ordering Principle (that every set can be linearly ordered), but is strictly stronger than $\mathsf{ZF}$ (the existence of a Russell sequence (a countable sequence of two elements sets without a Choice function) is consistent with $\mathsf{ZF}$ and would clearly contradict $\mathsf{AC}(\mathrm{fin})$).

(See Horst Herrlich's Axiom of Choice for some limited information about $\mathsf{AC}(\mathrm{fin})$ and Horst Herrlich & Eleftherios Tachtsis _On the number of Russell's socks or $2 + 2 + 2 + \cdots = ?$ for some basic information about Russell sequences.