# Are there paradoxes in ZF + (the Axiom of Choice for finite sets)? [closed]

The good intuitive reasons that the Axiom of Choice (AC) for arbitrary sets-- that a function f with f(i) in S(i) for each i in {i}, for any non-empty sets {i} and all S(i), exists-- doesn't follow from just ZF, seem to be good for finite {i} and S(i) (i.e., for FAC-- AC for {i} and all S(i) finite) as well as for one or both being infinite (I may be challenged on this). Whether the Godel-Cohen proof of the independence of AC from ZF works with FAC substituted for AC, I don't know. However, the best-known very peculiar consequence of ZFC, the Banach-Tarski paradox, requires AC for infinite S(i) (and maybe infinite {i}--I don't remember that detail of its demonstration which I saw long ago.) My question is, are there any at least nearly as peculiar paradoxes which are consequences of ZF + FAC, or at least ZF + (AC for all S(i) finite)?

Perhaps this edit will make my question more nearly suitable for MO. The "good intuitive reasons" (I actually know of only one) that AC doesn't follow from ZF is the following (which of course is not a proof of that fact): Any proof of that fact on the basis of ZF would have to be simply that since each S(i) is non-empty, for each i there is an e(i) in S(i), so let f(i) = e(i). Then f is the required choice function. The reason that this isn't a proof is that the existence of an e(i) in S(i) doesn't specify what that e(i) is, so f isn't specified by the foregoing, and even its existence isn't established. Since the supposed proof as well as its fatal objection don't refer to any properties of {i} and the S(i)'s other than their being non-empty, the objection to the offered proof applies to even that for AC restricted to finite {i} and S(i)'s. The rigorous proof that this supposed proof is defective is of course Godel-Cohen.

Peter LeFanu Lumsdaine--Your mentioned proof, by ordinary induction on the size of {i}, that AC for finite {i} (and presumable countably infinite {i}) is provable in ZF and even in weaker systems must therefore be different from the above, defective supposed proof. I have no idea what it could be. Would you supply at least as outline of it, a link, or a citation?

• The Banach-Tarski paradox is not a logical paradox, but a psychological one: it shocks you, but it is an entirely true statement. What do you mean, then, by "paradox"? (Also, the lack of proper formatting makes your post very difficult to read.) – Alex M. May 18 '18 at 17:06
• The axiom of choice for finite index sets is provable in ZF (and indeed in weaker systems), by induction on the size of the set. So it certainly doesn’t have any counterintuitive consequences! On the other hand, I vaguely recall that the axiom of choice for families of finite sets (over an arbitrary index set) is equivalent to full AC — but I can’t remember how, so I may be misremembering. – Peter LeFanu Lumsdaine May 18 '18 at 17:17
• @PeterLeFanuLumsdaine-- This is not true; see here: pdfs.semanticscholar.org/7047/… – Monroe Eskew May 18 '18 at 17:26
• @PeterLeFanuLumsdaine, it may be too much to claim that something that is proveable in ZF therefore doesn't have any counterintuitive consequences. – LSpice May 19 '18 at 0:38
• if $AC(\infty,p)$ holds for each prime number $p$ less than or equal to $17,$ then $AC(\infty,63)$ holds (Exercise 2 at bottom of p. 106; solution provided). A very nice survey of this topic is given in the first few pages of John Horton Conway's paper Effective implications between "finite" choice axioms [pp. 439-458 in Mathias/Rogers (editors), Cambridge Summer School in Mathematical Logic, Lecture Notes in Mathematics #337, Springer-Verlag, 1973; MR 50 #12725; Zbl 279.02047]. – Dave L Renfro May 19 '18 at 8:43

## 1 Answer

As Peter pointed out, the axiom of choice for finite index sets is a theorem of ZF. So, what you're really asking for is a peculiar consequence of ZF, one nearly as weird as Banach-Tarski. I don't know if this will satisfy you, but here's an arguably paradoxical fact provable in far less than ZF:

Consider the following 2-player game of imperfect information: Player 1 begins by privately selecting a function $F: X \rightarrow \mathbb{R},$ where $X$ is the set of well-ordered subsets of $\mathbb{R},$ modded out by isomorphism. The next three turns each consist of Player 2 selecting a set $S \subset X$ and Player 1 revealing the function $F \restriction S.$ Finally, Player 2 selects some ordered pair $(x,y) \in X \times \mathbb{R}.$ Player 2 wins if $x$ is not in any of the sets $S$ Player 2 had previously selected, and $F(x)=y.$

Fact: There are strategies $\{\sigma_i\}_{i \in \mathbb{N}}$ for Player 2 such that, no matter which function Player 1 selects, at most one of the strategies $\sigma_i$ results in a loss for Player 2.

This is arguably a probabilistic paradox. Intuitively, if Player 1 selects a function $F$ "randomly," Player 2 has an infinitesimally small chance of success (since they ultimately have to determine the value of some $F(x) \in \mathbb{R},$ with no useful information). Yet, Player 2 can win with arbitrarily high probablity, simply by selecting an arbitrarily large $n,$ randomly selecting $i \le n,$ and then using $\sigma_i.$

(Also, see here for discussion about a similar problem that uses choice Probabilities in a riddle involving axiom of choice).

Edit: At Gro-Tsen's request I will sketch strategies $\sigma_1, \sigma_2$ such that only one can fail. Partition $X \cong 2 \times \omega \times X$ into 2 subsets $X_1, X_2,$ where $X_k=\{k\} \times \omega \times X.$ Notice that $X$ is naturally well-ordered, so each $X_k$ consists of an $|X|$-sequence of $\omega$-sequences. In $\sigma_i,$ Player 2 first selects $X_j,$ where $j=3-1.$ Player 1 reveals $F \restriction X_j.$

Player 2 determines the first two $\omega$-sequences $s^1, s^2$ in $X_j$ such that $F \restriction s^1$ and $F \restriction s^2$ (each treated as an $\omega$-sequence of reals) differ only finitely often. Let $n$ be least such that $F \restriction s^1, F \restriction s^2$ agree from the $n$th term onwards. Player 2 selects the set $S_2=\{i\} \times (\omega \setminus (n+1)) \times X,$ and Player 1 reveals $F \restriction S_2.$

On the third turn, Player 2 determines the first two $\omega$-sequences $t^1, t^2$ in $X_i$ such that $F \restriction t^1, F \restriction t^2$ differ only finitely often. Player 2 selects $\{(i, n, t^1)\},$ and Player 1 reveals $F((i, n, t^1)).$ Finally, Player 2 selects the ordered pair $((i, n, t^2), F((i, n, t^1))).$

Let $n_i$ be the number $n$ determined in the course of $\sigma_i.$ If $\sigma_i$ fails for some fixed $F,$ then $n_i<n_j,$ where $j=3-i,$ so only one of the two strategies can fail.

• Here's a surprising fact: $\sum_1^{\infty}n^{-2}=\pi^2/6$. If all we want is surprising facts, then the original question isn't much of a question, is it? – Gerry Myerson May 19 '18 at 0:29
• It's a surprising fact with a similar flavor to Banach-Tarski, which is what the questioner is asking for. – Elliot Glazer May 19 '18 at 0:30
• (a) "Player 2 wins if $x$ is not in any of the sets $S$…": I suppose you mean "is in in the set $S$" (there is only one set $S$, right?). (b) "There are strategies $\{\sigma_i\}_1^\infty$": indexed by what, precisely? (c) At the risk of spoiling the mystery, I think you should give a proof of your fact. – Gro-Tsen May 19 '18 at 5:10
• @Gro-Tsen (a) There are three $S$'s, one selected during each of three preceding turns. Player 2 needs to pick $x$ which is in none of these, or else he wins the game trivially. (b) I'm using the notation in the standard sense, so the indices are natural numbers. I will edit for clarity. (c) The strategies are rather complex to describe. I'll sketch out an argument for a weaker (but still paradoxical) fact. – Elliot Glazer May 19 '18 at 5:21
• Ah, I had missed the "three" (or rather, I had thought it referred to three half-turns, i.e., all that remains of the game). So now I want to know what happens for other values of "three"! Do you have a reference for this game or did you just make it up? – Gro-Tsen May 19 '18 at 5:24