7
$\begingroup$

We start with $ZF$.

The axiom of countable choice, $AC_\omega$, says that any set product of nonempty sets with a countable index set is nonempty. For any $ZF$-definable set $A$, we should be able to define $AC_A$ in an analogous manner: any product of nonempty sets with index set $A$ is nonempty.

What is the implication structure of these axioms? There is the obvious fact that if $A$ injects into $B$ (or rather, if that can be proven by $ZF$), then $AC_B$ implies $AC_A$ (Proof: choose $1$-element sets for $B\backslash A$, and restrict the choice function); is there anything else beyond the trivial?

Also, the axiom of choice implies that all of these axioms are true; is the converse true?

$\endgroup$
6
  • $\begingroup$ I would say the converse (That $AC_X$ is true for all sets $X$ implies $AC$) holds. But if you want only definable $X$, that's a bit more subtle. Also, you are probably missing some "nonempty" conditions in your description, but it is clear what you mean. $\endgroup$
    – David Roberts
    Commented May 1, 2018 at 1:55
  • $\begingroup$ @DavidRoberts I do want to do it for more than definable $X$, but it seems to me that that runs into problems with whether you are working "in-model" or over several models, though I'd appreciate any way to correct that! I'll try to clean up the missing nonempties. $\endgroup$
    – user44191
    Commented May 1, 2018 at 1:59
  • $\begingroup$ You cannot express the axiom that restricts the statement only to definable $X$, since the property "$X$ is definable" is not definable. $\endgroup$ Commented May 1, 2018 at 3:00
  • $\begingroup$ @JoelDavidHamkins That prevents me from making a single axiom that unites all of these (at least, in the naive way), but for any definable $X$, I can write the statement $AC_X$, right? $\endgroup$
    – user44191
    Commented May 1, 2018 at 3:04
  • $\begingroup$ Yes, that's right. $\endgroup$ Commented May 1, 2018 at 3:13

1 Answer 1

12
$\begingroup$

Yes, the axiom of choice is equivalent to the assertion that $\text{AC}_X$ holds for every definable $X$.

One usually has to take a little care with foundational matters when definability is involved, since one cannot ordinarily express assertions of the form "every definable $X$ has a certain property", as the class of definable $X$ is not itself necessarily definable.

Nevertheless, in your case, it turns out that we can get around this obstacle. Specifically, you may be surprised to hear that I claim that there is a single definable set $X$, such that $\text{ZF}$ proves that $\text{AC}_X$ is equivalent to the axiom of choice. That is, we need only to consider one suitably defined set $X$, and $\text{AC}$ is provably equivalent to this special single instance of your axiom $\text{AC}_X$ for this specific definable set $X$.

My set $X$ is: the smallest set $V_\theta$, a rank initial segment of the cumulative hierarchy, such that there is an $X$-indexed family of nonempty sets with no choice function, if there is such a family, and $X=\emptyset$, otherwise.

This is a perfectly good definition of a set $X$ in the theory $\text{ZF}$. If the axiom of choice holds, then $\text{AC}_X$ holds for every set $X$, including the one I just defined. Suppose conversely that the axiom of choice fails. So there is some index set $I$ and indexed family $\langle A_i\mid i\in I\rangle$ of nonempty sets $A_i$ having no choice function. The set $I$ must be contained in some $V_\theta$, since every set is a subset of some rank initial segment of the universe. Let $A_i=\{0\}$ for all $i\in V_\theta\setminus I$. So now we have a family $\langle A_i\mid i\in V_\theta\rangle$ of nonempty sets, and still there can be no choice function. So there is such a $\theta$ as in the definition of my set $X$. Thus, by design, it cannot be that $\text{AC}_X$ holds for this set $X$.

Of course, this is a kind of trick. It is like saying that every natural number has a certain property if a certain single number $n$ has the property, where $n$ is defined to be the smallest counterexample, if there is one, and $0$ otherwise. If that number $n$ has the property, then every number does.

Many years ago I was at a party in Berkeley at the home of Ken Ribet and a mischevious Hendrik Lenstra mentioned to me and a small group of my fellow graduate students that although it was not known whether there are infinitely many prime pairs, nevertheless there is a number $N$ such that if there is any prime pair above $N$, then there are infinitely many prime pairs. "If we could only find that $N$!," he said, with a wink in his eye. The other students nodded at this profound-seeming statement, but I thought a bit and said: case 1 is that there are only finitely many pairs, and we can take any $N$ above them; case 2 is that there are infinitely many pairs, in which case we can take $N=17$ or anything. Lenstra shook my hand and said, yes, it is really trivial, isn't it?

$\endgroup$
4
  • $\begingroup$ Heh. This is a great answer to my second question, and it at least points towards some implication structure beyond the trivial obtained from basic axioms. I'm thinking of splitting the question, so that this stands as a full answer. $\endgroup$
    – user44191
    Commented May 1, 2018 at 6:59
  • $\begingroup$ For the other question, one interesting thing to say is that if $\text{AC}_\alpha$ holds for every ordinal $\alpha$, then DC holds. $\endgroup$ Commented May 1, 2018 at 10:11
  • 1
    $\begingroup$ Your comment to Lenstra relies on LEM. Does this have interesting ramifications? $\endgroup$ Commented May 1, 2018 at 10:16
  • $\begingroup$ Yes, indeed, the argument uses that either there are infinitely many prime pairs or there are not. $\endgroup$ Commented May 1, 2018 at 10:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .