Understanding Specker's disproof of the axiom of choice in New Foundations - MathOverflow

Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-22T05:39:04Z

Hi all! I am trying to understand Specker (1953)'s proof (found here) that the axiom of choice is false in New Foundations. I am stuck on the following point. At 3.5 Specker writes:

3.5. The cardinal numbers are well ordered by the relation "there are sets $a,b$ such that $a \in n, b \in m$ and $a \subseteq b$" (axiom of choice).

I am assuming that this is a consequence of the axiom of choice, which he is using to derive a contradiction. Is that true? If so, how is it a consequence of the axiom of choice?

Another, broader question: can anybody give an intuitive explanation of why AC fails in NF?

Thank you!

Answer by Miles for Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-22T06:16:19Z

I think the answer (to your first question) is "yes". I'm not very familiar with New Foundations, but I can describe how it works in ZF(C), and hopefully this will give some insight.

So, if you are using the axiom of choice, it's convenient to define a cardinal number to be a [von Neumann] ordinal that is not in bijection with any smaller ordinal. This works as a definition because AC says that every set can be well-ordered, and every well-ordered set is uniquely isomorphic to an ordinal number. The cardinals are then well-ordered because the ordinals are well-ordered. (Given a nonempty set $S$ of ordinals, take the successor of the union of $S$. This is then an ordinal that contains every element of $S$, so $S$ must have a least element.)

Let me know if that is too opaque. . . .

Answer by Andreas Blass for Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-22T16:10:30Z

First notice that one can carry out in NF Zermelo's proof that the axiom of choice implies that all sets can be well-ordered. It follows that the relation on cardinals defined in your quote from Specker satisfies the conditions for a linear ordering. (It's trivially reflexive and transitive. Antisymmetry is the Cantor-Schröder-Bernstein theorem. Linearity follows from well-ordering because, for any two well-ordered sets, one is in (order-preserving) bijection with an initial segment (possibly improper) of the other.) It remains to show that, in any nonempty collection $X$ of cardinals, there is a smallest one. I'll use the fact that there is a set $U$ so big that every cardinal in $X$ occurs as the cardinality of a subset of $U$. In ZFC-style set theories, I'd get $U$ by choosing a representative set for each cardinality in $X$ and taking the union of these representatives; in NF it's easier, since the universe $V$ is a set that can serve as $U$. Well-order $U$. By what I already said, each cardinal $x\in X$ is the cardinality of either $U$ or a proper initial segment of $U$. If all are the cardinality of $U$, then $X$ contains just one cardinal, which is obviously least. So suppose some $x\in X$ is represented by an initial segment of $U$. (The same $x$ may correspond to several initial segments; that's OK.) Among all those initial segments, for all $x\in X$, there is a shortest because $U$ is well-ordered. The correponding $x$ is the smallest cardinal in $X$.

Answer by Nick Thomas for Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-23T00:31:16Z

Thanks to Andreas Blass for answering my first question. Here's an attempt at my second question: an intuitive explanation of Specker's proof. Can anybody improve on it, or correct any mistakes?

Work in NF, and assume the axiom of choice. Then we can prove that in general, the cardinality of a set $A$ has greater or equal cardinality than the set of singletons drawn from $A$. For instance, the cardinality of the set of singletons is strictly less than the cardinality of the universe. The proof essentially proceeds by playing with this oddity to get a contradiction.

We define a nonincreasing function on cardinals $T(m)$, which goes from the cardinality of the set $A$ to the cardinality of the set of singletons drawn from $A$. We define an increasing function on cardinal numbers, $2^m$, which goes from the cardinality of the set of singletons drawn from $A$ to the cardinality of the power set of $A$. Thus $2^m$ is similar to the usual cardinal exponentiation, but in general it grows more quickly.

$2^m$ is not defined everywhere; in particular, $2^{|V|}$ is undefined, where $|V|$ is the cardinality of the universe, since $|V|$ is not the cardinality of a set of singletons, since the largest set of singletons (the set of all singletons) is strictly smaller. More generally, $2^m$ is undefined if and only if $m$ is strictly larger than the cardinality of the set of all singletons. This characterizes a certain final segment of the cardinals.

We define $\phi(m)$ as the set of cardinals ${m, 2^m, 2^{2^m}, ...}$, as far out as those are defined. Because $2^m$ is not defined everywhere, there are cardinals such that $|\phi(m)|$ (i.e., "the number of times we can use our modified power set operation before we fall off the egde of the universe") is finite. In particular, Specker proves that if $|\phi(m)|$ is finite, then $|\phi(T(m))| = |\phi(m)| + (1\ \text{or}\ 2)$.

Now we construct a paradoxical set. Let $c$ be the smallest cardinal number such that $|\phi(c)|$ is finite. Then $|\phi(T(c))|$ is also finite. Since $T$ is a nonincreasing function, we have $T(c) \leq c$, and since $c$ is the smallest cardinal with $|\phi(c)|$ finite, $c = T(c)$. Then $|\phi(c)| = |\phi(T(c))|$, but by the previous paragraph $|\phi(T(c))| = |\phi(c)| + (1\ \text{or}\ 2)$. By contradiction, the axiom of choice is false.

Answer by Randall Holmes for Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-23T07:55:55Z

There is no assurance that $T(c) \leq c$ from $T$ being a "nonincreasing function". It is quite possible for $T(k) \gt k$ to hold for some cardinals.

It is possible to show that if $|\phi(c))|$ so is $|\phi(T(c))|$ and also that if $|\phi(c)|$ is finite and $T^{-1}(c)$ exists (as it would if $T(c) \gt c$) then so is $|\phi(T^{-1}(c))|$. So $T(c) \lt c$ is impossible because $c$ is the smallest cardinal of the kind indicated, and $T(c) \gt c$ is impossible NOT because "$T$ is a nonincreasing function" but because we would then have $T(c) \gt c \gt T^{-1}(c)$ and $T^{-1}(c)$ would be a cardinal of the given sort smaller than $c$.

Unfortunately, the argument just isn't intuitive.

Answer by Thomas Forster for Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-26T10:11:03Z

``Work in NF, and assume the axiom of choice. Then we can prove that in general, the cardinality of a set A has greater or equal cardinality than the set of singletons drawn from A.''

I doubt this very much, except it be by some artifice such as the ex falso. The general view among NFistes is that the refutation of choice just is nasty, and it is not clear what is going on.

One way in is to consider the proof of the axiom of infinity in NF. That does make some sort of sense.

Merry Xmas, by the way

Answer by Thomas Forster for Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-26T19:17:42Z

Beware! Even in versions of NF that allow choice (one thinks of NFU) it is not the case that every wellordering is iso to an initial segment of the ordinals, and certainly not to a von Neumann ordinals. Every wellordering belongs to an ordinal - an ordinal is simply an isomorphism class of wellorderings. NF does not prove the ``counting principle'' that every wellordering is iso to the wellordering of its initial segments or to the wellorderings of the ordinals less than its own ordinal. The counting principle works for small ordinals, but fails in general