5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Cohen showed countable choice cannot be proven in ZF without choice, despite what your intuition tells you. $\endgroup$ – hardmath Apr 12 '13 at 17:21
  • 1
    $\begingroup$ Did I say anything that implied otherwise? (This is a serious question. I didn't think I had, but this is a very tricky area and not all the implications are clear to me.) $\endgroup$ – MJD Apr 12 '13 at 17:23
  • 1
    $\begingroup$ Maybe I misunderstood your remark about ZF implying $AC_Z$ "even without AC". Of course I assumed you were serious and just wanted to raise the possibility that forcing could shed light on a hierarchy of choice-conditioned-on-cardinality axioms. $\endgroup$ – hardmath Apr 12 '13 at 17:32
  • 1
    $\begingroup$ Doesn't ZF imply AC$_z$ without AC? AC$_z$ is not the axiom of countable choice. I used AC$_\omega$ to denote the axiom of countable choice. $\endgroup$ – MJD Apr 12 '13 at 17:35
  • 1
    $\begingroup$ You need AC to choose a bijection for all $s$ at once. To use Conway's terminology, products of counted sets are inhabited, but products of countable sets could be anything. $\endgroup$ – Zhen Lin Apr 12 '13 at 19:51
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I don't understand how that can be. If $\mathcal C$ is a collection of nonempty finite sets, then why can't we say that for each $S\in\mathcal C$ there is a bijection $f_S$ between $S$ and some nonempty initial segment of $\omega$, and then $c: S\mapsto f_S(0)$ is a choice function for $\mathcal C$? $\endgroup$ – MJD Apr 12 '13 at 17:43
  • 2
    $\begingroup$ I'm just glad I grabbed a couple of upvotes before the Axiom-of-Choice upvote back-hole which is you came around! ;-) $\endgroup$ – user642796 Apr 12 '13 at 17:43
  • 1
    $\begingroup$ @MJD: Because you have to choose those bijections. That's why! $\endgroup$ – Asaf Karagila Apr 12 '13 at 17:50
  • $\begingroup$ @Arthur: It's lucky that I bought a tablet and I can use the internet in places which are not my own study room... Otherwise this answer would have been written in about an hour from now! $\endgroup$ – Asaf Karagila Apr 12 '13 at 17:51
  • 1
    $\begingroup$ @MJD: It depends on what is $z$, and on a broader note, what is $\Phi$ which defines the particular property. If these are just limitations on the cardinality, or even on "there is a group structure" (for example) then it is indeed a mistake, and $\sf ZF$ does not imply such thing. But it might be reasonable to produce a statement $\Phi$ which is strong enough so that $\sf ZF$ does prove this sort of choice. For example $\Phi$ stating that all the sets are sets of ordinals. $\endgroup$ – Asaf Karagila Apr 12 '13 at 18:50
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I arrived at this question because I was wondering if Russell's socks example wasn't misleading, and if it might be possible to define a choice function for any large collection of pairs of socks. $\endgroup$ – MJD Apr 12 '13 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.