1
$\begingroup$

This question already has an answer here:

I recently finished a discrete mathematics class, and near the end of the semester, the prof (very superficially) touched on countable and uncountable infinities. His explanation of countable infinities began and ended with the example of the cardinal number set, while he explained that, for example, the set of all functions $f$ such that $f:\mathbb{R}\mapsto\mathbb{R}$ is, in fact, uncountable.

My question is threefold:

  • Does it make sense to say that any uncountable infinity is larger than any countable infinity?

  • Does it make sense to say that certain countable infinities are larger than others?

  • Finally, does it make sense to say that certain uncountable infinities are larger than others?

For example, is the set of all reals larger than the set of reals between any two integers? Can arithmetic-like rules be applied if this is true (addition of infinities makes them larger)?

$\endgroup$

marked as duplicate by Ross Millikan, MJD, Henning Makholm, user127096, Mark Bennet Apr 19 '14 at 16:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Yes, no, yes. It all depends, of course, on a convention. The standard convention is that a set $A$ has smaller size than a set $B$ if there is an injection from $A$ to $B$, but not vice versa. If you choose a different convention, the answers may well change. $\endgroup$ – Andrés E. Caicedo Apr 19 '14 at 15:23
  • $\begingroup$ does this question cover what you want? $\endgroup$ – Ross Millikan Apr 19 '14 at 15:25
  • $\begingroup$ @AndresCaicedo It's always been my understanding that math is very universal about its conventions, and that conflicts like this rarely exist. What are the different kinds of conventions that apply to this? $\endgroup$ – Jules Apr 19 '14 at 15:29
  • $\begingroup$ @RossMillikan the answerer doesn't really cover whether the different kinds of infinities have comparable sizes - so no. But that thread has a lot of interesting stuff nonetheless. $\endgroup$ – Jules Apr 19 '14 at 15:30
  • $\begingroup$ @JulesMazur You may decide that "size" is to be understood in terms of density (in terms of asymptotic density, there are twice as many natural numbers than there are positive even numbers), or in terms of certain measures (the Cantor set has measure $0$, the interval $(a,b)$ has measure $b-a$), rather than in set theoretic terms. It all depends on what the purpose at hand is. If what you want is a way of discussing sizes of arbitrary infinite sets, the set theoretic convention is the way to go. (As for comparability: All sets are comparable, this follows from the axiom of choice.) $\endgroup$ – Andrés E. Caicedo Apr 19 '14 at 15:38
3
$\begingroup$

There are standard answers to all three of your questions, if one assumes the axiom of choice (as is almost always done these days).

First, we have two reasonable definitions for what it means to say that cardinal $\alpha$ is greater than cardinal $\beta$. Say set $A$ has cardinality $\alpha$ and $B$ has cardinality $\beta$. If there is a one-one function from $B$ to $A$, then we say $\alpha\geq\beta$. Or alternately, if there is a function from $A$ onto $B$, then we say $\alpha\geq\beta$. Given the axiom of choice, one can prove that these are equivalent. (Also one can prove that these definitions do not depend on the choice of $A$ and $B$: if $A'$ and $B'$ also have cardinalities $\alpha$ and $\beta$, then you get the same results.)

We say that $\alpha=\beta$ if there is a one-one onto function from $A$ to $B$, and finally $\alpha>\beta$ if $\alpha\geq\beta$ but there is no one-one onto function from $A$ to $B$.

With these definitions, here are the answers (without proofs):

(a) Yes, every uncountable infinity is greater than every countable infinity.

(b) No, all countable infinities are the same: if $A$ and $B$ are both countable and infinite, then $\alpha=\beta$.

(c) Yes, some uncountable infinities are greater than others. For example, if $A$ is set of all functions from the real numbers to the real numbers, and $B$ is the set of real numbers, than $\alpha>\beta$.

However, the set of all reals between $x$ and $y$, $x<y$, has the same cardinality as the set of all reals. So intuition can be misleading.

Cantor proved in general that $2^\alpha>\alpha$ for any cardinal number $\alpha$. (Here, $2^\alpha$ is the cardinality of the set of all subsets of $A$.) So one can construct the so-called beth sequence: $$\beth_0=\aleph_0; \beth_1=2^{\beth_0}; \beth_2=2^{\beth_1}; etc.$$ and $$\beth_0<\beth_1<\beth_2<\ldots$$ Here, $\aleph_0$ is the cardinality of any infinite countable set.

Cantor also proved that for any cardinal $\alpha$, there is a next bigger cardinal: a cardinal $\alpha'>\alpha$, such that there are no cardinals strictly in-between $\alpha$ and $\alpha'$. So we also have the $\aleph$ sequence: $$\aleph_1=\aleph_0'; \aleph_2=\aleph_1'; \aleph_3=\aleph_2'; etc.$$ and $$\aleph_0<\aleph_1<\aleph_2<\ldots$$ The conjecture that the aleph sequence is the same as beth sequence is known as the Generalized Continuum Hypothesis (GCH). GCH cannot be proved or disproved from the usual axioms of set theory, leading to lots of philosophical discussion on the nature of mathematical reality.

There are arithmetical rules, but they are not what you might expect. If $\alpha\geq\beta$, and $\alpha$ is infinite, then $\alpha+\beta=\alpha$: the larger infinite cardinality "absorbs" all smaller (or equal) cardinalities. In fact, if $\alpha\geq\beta$, and $\alpha$ is infinite and $\beta\neq 0$, then $\alpha\cdot\beta=\alpha$.

To repeat, all this is assuming the axiom of choice, and omitting all proofs.

Kaplansky's Set Theory and Metric Spaces is a nice introduction to all this.

$\endgroup$
  • $\begingroup$ A second the recommendation of Set Theory and Metric Spaces. I wonder if you also want to mention that $S<\wp(S)$, which is elementary, and I think does a lot to establish the nature of infinity. $\endgroup$ – MJD Apr 19 '14 at 16:51

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