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

Question

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 1

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 2

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$.

THUS we have $c=T(c)$ and so $|\phi(c)| = |\phi(T(c))|$. But also we can show that $|\phi(T(c))| = T(|\phi(c)|)+$ (1 or 2) [NOT $|\phi(c)|+$ (1 or 2)]. Standard natural numbers are fixed by the $T$ operation, but general natural numbers do not have to be. We can show that $|\phi(c)| \equiv T(|\phi(c)|) \pmod 3$, and this is enough to get the contradiction.

Unfortunately, the argument just isn't intuitive.

Answer 3

``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 4

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

Answer 5

See lemma 2.2.1 in my dissertation of NF in 1989 (G. Wagemakers, New Foundations: A survey of Quine’s Set Theory). More info can be found there, for example that there is no relation between $n$ and $T(n)$ at all. The one can be larger, equal or smaller than the other.

You're asking for an intuitive explanation why AC fails in NF. Let me give that a try (terminology as in my document; note that I skip parentheses that are not essential).

For cardinals $m$ it is easy to prove the following ($\Omega = |V|$): \begin{cases} 2^{T\Omega}=\Omega\\ m \le T\Omega \implies 2^{Tm} = T2^m\\ \Omega > T\Omega\\ 2^m \ne \Lambda \implies m < 2^m \end{cases} This leads to a descending series of cardinals: $$\Omega > T\Omega > T^2\Omega > ...$$ If we would be able to form the set $Clos(\{\Omega\}, T)$ containing all these cardinals, then we would contradict AC as that set would not have a smallest element (the set of all cardinals, hence every subset of it, is well-ordered by $\le$). But, alas, this set cannot be formed as $T$ is type-raising. So we have to resort to a real set, intuitively containing at least the cardinal numbers in this list, and hope for the best. This set is $A = \{m \in NC |\Phi m \in Fin\}$, where \begin{cases} \Phi m = Clos(\{m\}, 2^{.}) - \{\Lambda\}\\ Fin = \bigcap Nn\\ Nn = Clos (\{0\}, . + 1) \end{cases} This set exists, as $2^.$ is type-preserving, and indeed contains $\Omega$ ($|\Phi \Omega| =1$), $T\Omega$ ($|\Phi T\Omega| =2$), etcetera (note that this fact doesn't helps us much, as this series of descending cardinals could be all larger than the minimum element of the set).

Assuming AC, A is well-ordered by $\le$ (NC is, and $A \subseteq NC$). Specker proceeds to derive an inconsistency: for the smallest element $n$ of this set, it can be derived that $n=Tn$. But then $|\Phi n| = |\Phi Tn| = T|\Phi n| + (1 \text{ or } 2)$, contradicting the fact that there can be no natural number $|\Phi n|$ having this property.

Obviously, a number of lemmata is required to derive these facts.

The conclusion is that the FULL axiom of choice AC does not hold in NF. Note that for cardinals m less than that of $A$, $AC(m)$ has not been disproved by Specker's argument.

Answer 6

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 7

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. . . .