In Why is the axiom of choice separated from the other axioms?, a comment on the top answer mentions how 'Choice is special in that it isn't a special case of the problematic Unrestricted Comprehension principle', which to me implies that the Axiom of Choice cannot be derived from the Unrestricted Comprehension Principle--can someone explain why that is?

  • 3
    $\begingroup$ But unrestricted comprehension is inconsistent, so it implies everything. $\endgroup$ – Rene Schipperus Nov 9 '17 at 19:03
  • $\begingroup$ That's not quite a logical statement by itself because of the inconsistency of unrestricted comprehension. I think the point is that other than AC, the other axioms are generally letting you build sets through comprehension, more or less. (In particular, you can build sets through comprehension over an existing set.) AC doesn't give sets of the form $\{ x \in A : P(x) \}$ for any explicit $P$ (because you already have those). $\endgroup$ – Ian Nov 9 '17 at 19:06
  • $\begingroup$ Unrestricted comprehension gives you $\{\,x:\Phi(x)\,\}$, but it is evil as it confuses some barbers who do not know whether or not they should shave themselves. Many ZF axioms can be formulated as comprehensions with special properties $\Phi$; in other words, we allow comprehension as long as $\Phi$ is not "too general". For example, the Axiom of Pairing uses $\Phi(x)\equiv x=a\lor x=b$ (with parameters $a,b$), Axiom of Union uses $\Phi(x)\equiv \exists y\colon x\in y\land y\in a$, Power Set uses $\Phi(x)\equiv x\subseteq a$, and Comprehension uses $\Phi(x)\equiv x\in a\land \Psi(x)$ (cont.) $\endgroup$ – Hagen von Eitzen Nov 9 '17 at 19:18
  • $\begingroup$ (cont) And the Axiom of Infinity can we rewritten to use $\Phi(x)\equiv$"$x$ is a finite ordinal". However, the Axiom of Choice does not produce a set of this form. In fact, for sets guaranteed by AC, it is impossible do describe a property of its elements - or else there would exist a nice predicate that determines whether a given real number is an element of a somehow specific Hamel basis over $\Bbb Q$. Instead of producing a set, AC tells us that a certain set (the set of choice functions) is not empty. Then again, the Axiom of Regularity does a similar thing, I guess. $\endgroup$ – Hagen von Eitzen Nov 9 '17 at 19:26
  • 1
    $\begingroup$ @J.P.Escarcega As others have stated, since full comprehension is inconsistent that's not really a coherent question ... $\endgroup$ – Noah Schweber Nov 10 '17 at 0:39

This a problematic question. First of all, unrestricted comprehension is inconsistent, so you can prove anything from it.

But if we try to avoid explosion-style argument, which is often something productive from a pedagogical point of view, we still can't say much.

The axiom of choice can be formulated in many different equivalent ways. One specific way would be that if $R$ is a relation, then there is a function $F\subseteq$ such that $\operatorname{dom}(F)=\operatorname{dom}(R)$.

But now we can ask, can we actually specify this choice function? Well, again, using the unrestricted comprehension schema we can prove everything, which means this is useless to us.

So let's restrict the question and ask, if $R$ is a given relation, can we prove the existence of $F$ as above, without using the axiom of choice, and just the basic axioms of $\sf ZF$?

The answer, of course, is negative. As in the case such thing is provable, we would have that $\sf AC$ is provable from $\sf ZF$, and we know that if $\sf ZF$ is consistent, then the axiom of choice is not provable from $\sf ZF$. So the whole thing would be a proof that $\sf ZFC$ is inconsistent, and a lot of the mathematics we do will require closer re-examining.

More to the point, there is no way to prove the unrestricted schema does not imply choice, as it is inconsistent. However its bounded part does not imply choice.

The intuition for the fact that $\sf ZF$, with restricted comprehension, does not imply the axiom of choice, comes from the fact that in general, having a function $F\subseteq R$ would require us to literally specify the properties of $F$ as a subset of $R$ which is impossible. If you want to argue otherwise, sure, let's try at first with a choice of elements from every set of reals, and remember most sets are not intervals.


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.