7
$\begingroup$

Recently I read the following quote (for the umpteenth time):

The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma? — Jerry Bona

Normally, the equivalence of these three over ZF is given as a justification for Zorn's lemma, since AC is 'intuitively' true. However, I have always found it lacking because the equivalence crucially depends on transfinite induction via the axiom schema of replacement, which I find unintuitive, unlike the axioms of Zermelo set theory (which lacks both Replacement and Regularity). So my question is:

What are 'counter-intuitive' consequences of AC in ZC (Zermelo set theory)?

I understand that this is not a precise question, but I am looking for examples of the same sort as mentioned here and here. I consider these examples as 'near misses', because while many people consider them counter-intuitive, I do not since they all rely on being able to handle arbitrary real numbers or even sets of real numbers, which is not possible in the first place. Specifically, there is no issue with a conceptual choice function that picks one representative from every equivalence class even if it is not implementable, just as there is no issue with a conceptual oracle machine to solving the halting problem even though it is not implementable.

As for the Banach-Tarski paradox, I do not find it counter-intuitive because we cut up the ball not into nice pieces at all, but instead sets of point dust that can be rearranged. It is not much different from taking the countable set $S = \{ \exp(i{\large \frac{k}{2^m}}) : k,m \in \mathbb{N} \land m2^m \le k < (m+1)2^m \}$ as points in the complex plane and rotating it by $\exp(i)$, which is a rigid transformation of a bounded point set that has just made countably many points vanish (in fact, ordered around the unit circle, every other point has vanished), completely constructively.

Related to this question, based on the iterative conception of sets, we get roughly Replacement for countable sequences as stated by Boolos in the quote here. Thus I am also interested to know any 'counter-intuitive' consequences of AC in ZC plus Replacement for countable sequences.

$\endgroup$
  • 1
    $\begingroup$ Entirely too subjective, I'm afraid. Also, your intuition is probably calibrated to choice. So its consequences seem normal. $\endgroup$ – Asaf Karagila Apr 17 '17 at 14:39
  • $\begingroup$ "while many people consider them counter-intuitive, I do not since they all rely on being able to handle arbitrary real numbers or even sets of real numbers, which is not possible in the first place." Why is it impossible to handle arbitrary reals/sets of reals? While it certainly is impossible to do so in the physical universe, it's quite easy to do in the mathematical universe; and this kind of constructive restriction seems especially odd in the choicey context. I do find this question interesting, but I don't really have a good sense of what you're looking for right now. $\endgroup$ – Noah Schweber Apr 17 '17 at 14:50
  • $\begingroup$ @NoahSchweber: Well I don't disagree with anything in your comment. I might have been too imprecise, but what I meant was that people bring up those puzzle games as 'counter-intuitive' examples, but the reasoning that leads to classifying them as counter-intuitive requires one to be able to handle reals impossibly. Specifically consider the game of guessing a function's value based on all other points. It is clearly impossible if you can pick each point arbitrarily independently so the problem there is with the impossibility of uniformly randomly picking a real from $[0,1]$. $\endgroup$ – user21820 Apr 17 '17 at 15:06
  • $\begingroup$ @AsafKaragila: Aww.. I was hoping you might have some examples to share! I originally thought only DC was intuitive, but later I realized that perhaps my intuitive issue wasn't with the full AC but with Replacement. I'm still unsure that's why I would like to see the most bizarre theorems of AC in the absence of full Replacement. =) $\endgroup$ – user21820 Apr 17 '17 at 15:10
  • 4
    $\begingroup$ @user254665: Literally the consequence that the OP mentions as not-strange. $\endgroup$ – Asaf Karagila Apr 17 '17 at 20:48
3
$\begingroup$

To sum up some of the discussion in the comments, I think you are greatly overestimating the role of Replacement in applications of the axiom of choice. The vast majority of transfinite induction arguments do not use Replacement in any essential way. One key to many applications is the following theorem of Hartogs (which is valid in Zermelo set theory without Choice):

Theorem: Let $X$ be a set. Then there exists a well-ordered set $W$ such that there is no injection $f:W\to X$.

Proof: Define $W$ to be the set of isomorphism classes of well-orderings of subsets of $X$, ordered by length. A well-ordering of a subset of $X$ is a subset of $X\times X$, and an isomorphism class is a set of such subsets, so $W\subset\mathcal{P}(\mathcal{P}(X\times X))$ and is a set by Separation. Note that the well-ordering of $W$ is longer than any element of $W$, since each element of $W$ is isomorphic to a proper initial segment of $W$ (namely, its own set of proper initial segments). If there existed an injection $f:W\to X$, the ordering on $W$ would give a well-ordering of the image $f(W)\subseteq X$ which has the same length as the well-ordering of $W$. But the well-ordering of $f(W)$ is an element of $W$. This is a contradiction.

This theorem can, for instance, be used to prove Zorn's lemma without Replacement. Given a poset $X$ which is a counterexample to Zorn's lemma, let $W$ be as in the theorem. Now just follow the usual transfinite recursion argument, using $W$ as the index set of the recursion rather than the ordinals. The argument constructs a strictly increasing function $W\to X$, which is in particular an injection. This is a contradiction.

By a similar argument, the theorem can be used to prove the well-ordering principle: using a choice function on nonempty subsets of $X$, just define a function $f:W\to X$ by transfinite recursion which is injective as long as possible (that is, $f(w)$ is different from $f(v)$ for all $v<w$ unless such values $f(v)$ are already all of $X$). Since $f$ cannot be an injection, this means that it must be surjective, and this gives a well-ordering of $X$.

You also mentioned in a comment:

I also find theorems that use the cardinality of the reals to be unintuitive, such as that there is a subset of the plane that intersects every straight line in exactly 2 points.

Results like these do not use Replacement either: they merely use a well-ordering of the reals. Given that a well-ordering of the reals exists, you can take one of minimal length, and then use that well-ordering as a substitute for the cardinality of the reals everywhere.

$\endgroup$
  • $\begingroup$ Not exactly related, but I can't help but notice that Hartog theorem sounds a lot like the Axiom of Archimedes. Any relation? $\endgroup$ – eyeballfrog May 30 '17 at 20:28
  • $\begingroup$ Thanks for your answer; I'll accept it. I now wonder whether I'm finding this kind of results unintuitive only because I keep thinking of them as providing a completed collection, though I actually can reinterpret them constructively in the same way I did for Banach Tarski. $\endgroup$ – user21820 May 31 '17 at 16:38
1
$\begingroup$

Just a thought. In ZFC, let $k$ be the first uncountable strong limit cardinal. Then $(V_k,\in)$ satisfies ZC (includung Regularity) but not Relacement. Because with $a_0=\omega$ and $a_{n+1}=2^{a_n}$ we have $k=\sup_{n\in \omega}a_n,$ and we can write a formula of the form $\forall n\in \omega \exists ! x\; (F(x,n)),$ where $F(x,n)$ iff $x=a_n$ when $n\in \omega$, and such that this formula is absolute between $V$ and $(V_k,\in).$

Intuitively the formula "should" define a countable sequence. But $\{a_n\}_{n\in \omega}\not \in V_k$.... I am just wondering whether we could find some more-interesting properties of $V_k$ that make use of the occasional failure of certain countable sequences to exist in $V_k.$ So that, assuming Con(ZFC), these properties would be undecidable without Replacement.

$\endgroup$
  • 1
    $\begingroup$ This also happens much earlier than strong limits - $V_{\omega+\omega}$ is a model of ZC. Also, I don't think this really is connected with choice? $\endgroup$ – Noah Schweber May 30 '17 at 20:17

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.