Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was reading Simmons' book and he states that there are infinite cardinal numbers > $\mathfrak{c}$ where $\mathfrak{c}$ denotes the number of Real Numbers.

For this, he states that we can construct a class consisting of the subsets of the set of Real Numbers and that it is not possible to have one-to-one correspondence with the 2 sets thus proving that there are numbers of higher cardinality.

What I don't understand is how he went about proving the absence of 1-to-1 correspondence. He assumes that it is possible then establishes it via contradiction. ( I did not follow the proof at all but that's another story).

Why can't we simply prove it by induction? If we take a set of 1 element, the "number of elements" in the set and the set of all it's subsets is different. (2^n specifically) so 1-to-1 correspondence is not possible. So, base case is proved. If we assume for k, k+1 th case is proved similarly. So, can't we state that for ANY set, 1-to-1 correspondence is not possible with the set of it's subsets?

share|cite|improve this question
Induction only proves the claim for finite sets. – Qiaochu Yuan Jun 28 '12 at 13:28
Just a comment: You have to be careful about using induction here. Since you've started with a set of finite elements, you'll "never reach" an infinite countable set, let alone deal with higher infinite cardinalities. – Neal Jun 28 '12 at 13:28
The same "proof" would show that if you add one element to a set you get a set of higher cardinality. True for finite sets, false for infinite. – Gerry Myerson Jun 28 '12 at 13:30
You don't need to use contradiction. Once you accept Cantor's theorem, given a finite set of cardinals larger than the reals you can construct an even bigger one (by taking subsets) and so there are infinitely many such cardinals. This is a direct proof. – Qiaochu Yuan Jun 28 '12 at 13:48
Proving Cantor's theorem just involves showing for some arbitrary cardinal $\kappa$ that $\kappa < |\mathcal{P}(\kappa)|$. Since the axioms of ZF say that the powerset of every set exists, for any cardinal there is always a larger one. So the class of cardinals is unbounded. – Benedict Eastaugh Jun 28 '12 at 13:48
up vote 6 down vote accepted

Suppose you have a set $S$. Let $T$ be the family of all subsets of $S$. We will prove that there is no one-to-one correspondence between $S$ and $T$.

Suppose we have some function from $S$ to $T$, say $f$. Then for each $x\in S$ we have $f(x)$ is some element of $T$, which is a subset of $S$. The element $x$ might be an element of this subset, or it might not.

Now for each $x$, we will paint $x$ blue if $x\in f(x)$, or green if $x\notin f(x)$. Every element of $S$ is now painted blue or green.

Let $G$ be the set of all green elements of $S$. $G$ is a subset of $S$ and since $T$ is the family of all subsets of $S$, $G$ is an element of $T$.

I claim there is no element $g$ such that $f(g) = G$. Let's suppose that there were and see what happens.

Every element of $S$ is painted blue or green. If there were a $g$ with $f(g) = G$, then $g$ would be either blue or green.

If $g$ were green, it would be an element of $G$, the set of all green elements. But we would have painted $g$ green only if we found that $g\notin f(g) = G$. So $g$ cannot be green.

Perhaps $g$ is blue. We would have painted $g$ blue if we found that $g\in f(g) = G$. But $G$ is the set of all green elements, so if $g$ is blue, it is not in $G$, and we would not have painted it blue in the first place. So again we have a contradiction.

Something is seriously wrong. Certainly we can paint the elements as we said. The only plausible error is our claim that there is a $g$ for which $f(g)= G$. So the function $f$ is not in fact a one-to-one correspondence because there is no $g$ for which $f(g) = G$.

We can apply this argument for any proposed function $f$ and show that $f$ is not a one-to-one correspondence. And the argument works for any set $S$.

If you're still puzzled, try doing this construction for a finite set, such as $\{\mathrm{fish}, \mathrm{dog}, \mathrm{carrot}\}$.

Addendum: The argument above proves that there's no one-to-one correspondence between $S$ and $T$, but it's at least conceivable that $S$ is bigger than $T$. But the obvious mapping that takes $x$ to the set $\{x\}$ shows that there is a proper subset of $T$ that is the same size as $S$, so $T$ is at least as big.

Interesting note: We don't need to assume the existence of a bijective function and then show there is a contradiction. Instead we let $f$ be an arbitrary function and then show constructively that it is not a surjection by producing a specific example of an element not in its range. This is a stronger result than the proof by contradiction would have been.

share|cite|improve this answer
+1: Nicely intuitive! – Cameron Buie Jun 28 '12 at 13:56
Thank you. I like paint. – MJD Jun 28 '12 at 14:06

The reason we cannot use induction, as Mark said, is the property of the real numbers being Dedekind-infinite, namely: if we remove one element from the real numbers the cardinality does not decrease.

Induction helps when we can step through the cases, if we want to make this proof parallel to the finite case doing this by induction would mean that we assume it happens for sets of size $\mathfrak c-1$, but $\mathfrak c-1=\mathfrak c$, so we assume what we want to prove. That's not very helpful in general.

There are ways of generalizing induction to the infinite case, but they are not applicable here. For several possible reasons:

  1. The idea of "remove one point, use the induction hypothesis" only work for Dedekind-finite sets. In our case the real numbers are not Dedekind-finite so it won't work.

  2. Even if we could find a clever way of proving this by induction on the cardinality (where the step would be successor cardinals) this would require the axiom of choice to hold for the general case (and at least some choice for the case of $\mathfrak c$).

    Furthermore the actual value of $\frak c$ is independent of the usual axioms of set theory (ZFC) and we could get stuck at limit stages, that is cardinalities that are not successor cardinals. (Just to give an example it is consistent that there uncountably many cardinals between $\aleph_0$ and $\frak c$ and that $\frak c$ is not a successor cardinal, e.g. $\aleph_{\omega_1}$ - whatever that means).

  3. Another reasonable idea would be to run the induction on iterations of the power set function, that is Cantor's diagonal argument assures us that $\aleph_0<\frak c$, but that would ultimately consist of proving Cantor's theorem and the induction is not necessary here. The general case is provable quickly without it.

  4. If we merely wants to show that there are larger cardinalities than $\frak c$ there are other constructions, beautiful and interesting. However those often require much more set theory than Cantor's theorem (which merely requires a basic understanding of the definition of cardinality, power set, and surjective function).

    One example is taking $\kappa$ to be the Hartogs number (whatever this means) of $\mathbb R$, then considering $\kappa+\frak c$ as a larger cardinal (we need addition since without the axiom of choice it is possible that $\kappa$ and $\frak c$ are incomparable).

share|cite|improve this answer

Suppose $X$ is a set and $\mathscr{P}(X)$ the set of its subsets, and BWOC, suppose they are in one-to-one correspondence, so there is a bijection $f:X\to\mathscr{P}(X)$. Let $D=\{x\in X:x\notin f(x)\}$. Now, $f$ is surjective, so there is some $x\in X$ such that $f(x)=D$. But if $x\in D$, then by definition of $D$ we have $x\notin f(x)=D$, and if $x\notin D=f(x)$, then by definition of $D$ we have $x\in D$. Hence, we have our contradiction.

As Quiaochu and Neal point out, the induction you describe only shows that no finite set is in one-to-one correspondence with its set of subsets. It doesn't carry over to arbitrary infinite sets. It is possible that even transfinite induction can't pull it off, for if the Axiom of Choice fails, then there is no well-ordering of the cardinals that we can use.

share|cite|improve this answer
BWOC? ${}{}{}{}$ – MJD Jun 28 '12 at 14:02
By way of contradiction. – Cameron Buie Jun 28 '12 at 14:03
Proof Chicken is on the job! – MJD Jun 28 '12 at 14:07

I'm posting another answer to address a separate point, your proposed proof by induction:

Why can't we simply prove it by induction? If we take a set of 1 element, the "number of elements" in the set and the set of all it's subsets is different. (2^n specifically) so 1-to-1 correspondence is not possible. So, base case is proved. If we assume for k, k+1 th case is proved similarly. So, can't we state that for ANY set, 1-to-1 correspondence is not possible with the set of it's subsets?

You could prove the theorem this way, but only for finite sets, as several others have pointed out. Consider this analogous proof that all sets are finite:

The empty set is finite, and a set of 1 element is finite. So, base case is proved. Now assume that sets with $k$ elements are finite, and consider a set $S$with $k+1$ elements. If we delete an element from this set, we have a set with $k$ elements, which is finite by hypothesis. So $S$ is the union of two finite sets, one with $k$ elements and one with 1 element, and so is finite also. Therefore, by induction, all sets are finite.

Well, that's wrong, but you can use that argument to prove that all natural numbers are finite.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.