Return to Answer

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)| = 1$ (i.e., $2^m$ is undefined), then $|\phi(T(m))|$ is either 2 or 3.

Now we construct a paradoxical set. Let $c$ be the smallest cardinal number such that $|\phi(c)|$ is finite. Specker proves that $|\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.

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.

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)| = 1$ (i.e., $2^m$ is undefined), then $|\phi(T(m))|$ is either 2 or 3.

Now we construct a paradoxical set. Let $c$ be the smallest cardinal number such that $|\phi(c)|$ is finite. We show that $|\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.

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)| = 1$ (i.e., $2^m$ is undefined), then $|\phi(T(m))|$ is either 2 or 3.

Now we construct a paradoxical set. Let $c$ be the smallest cardinal number such that $|\phi(c)|$ is finite. Specker proves that $|\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.

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. Thus, $m$ is in 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)| = 1$ (i.e., $2^m$ is undefined), then $|\phi(T(m))|$ is either 2 or 3.

Now we construct a paradoxical set. Let $c$ be the smallest cardinal number such that $|\phi(c)|$ is finite. We show that $|\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.

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)| = 1$ (i.e., $2^m$ is undefined), then $|\phi(T(m))|$ is either 2 or 3.

Now we construct a paradoxical set. Let $c$ be the smallest cardinal number such that $|\phi(c)|$ is finite. We show that $|\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.