Take the 2-minute tour ×

i realize that there are multiple sizes of infinity so one can be larger than another, but how do you show that one infinity is larger. I'm not looking for proofs or anything but I just want the notation that would be used in a problem or anything. I read something about alphas and omegas to distinguish the sizes of infinity but I can't find any explanations.

share|improve this question
In this context (comparison of cardinals) we just use "<". For example, $\aleph_0 < 2^{\aleph_0}$. The first is the cardinality of the natural numbers, the second is the cardinality of the real numbers. –  Yuval Filmus May 16 '11 at 21:38
Look here: en.wikipedia.org/wiki/Aleph_number and here: en.wikipedia.org/wiki/Ordinal_number (if you just want "sizes of infinity", you're probably looking for the former). –  Alon Amit May 16 '11 at 21:55
add comment

1 Answer

Let $X$ and $Y$ be sets; we say that $X$ and $Y$ are equipollent if and only if there is a bijection $f\colon X\to Y$, and denote it by writing $|X|=|Y|$. The relation of equipollence is an equivalence relation, as is easy to prove.

Though the class of all sets is not a set, we can still think of this equivalence relation as partitioning the sets into equivalence classes.

We say that $X$ "has cardinality less than or equal to $Y$" if there is an injection from $X$ into $Y$. We write this as $|X|\leq |Y|$. We say $|X|\lt |Y|$ if and only if $|X|\lt |Y|$ and $|X|\neq|Y|$.

It is equivalent to the Axiom of Choice that given any two sets $X$ and $Y$, either $|X|\lt |Y|$, $|X|=|Y|$, or $|Y|\lt|X|$ (and exactly one holds); that is, the relation is trichotomic.

If we assume the Axiom of Choice, then there is also a special collection of representatives for the equivalence classes under equipollence, called the cardinal numbers. The classes corresponding to finite sets are represented by the natural numbers, $0$, $1$, $2$, etc; we write things like $|X|=7$ to mean that $X$ is equipollent with $7=\{0,1,2,3,4,5,6\}$, i.e., has seven elements.

For infinite sets, the equipollence classes are represented by the infinite cardinals, which are denoted by the aleph numbers (this may be what you dimly recall as "alphas"). The smallest such infinite cardinal is $\aleph_0$ (called "aleph nought" or "aleph zero", or "aleph null"); followed by $\aleph_1$ ("aleph one"), then $\aleph_2$, etc. The aleph numbers are indexed by ordinals, which are another special kind of sets (which correspond to "well orderings" in much the same way that cardinals correspond to "sizes"). The first infinite ordinal is $\omega$ (omega), which corresponds to the well-ordered set of natural numbers. There is an arithmetic of alephs, so that they can be added, multiplied, and other operations (such as exponentiation or infinite products).

And now, to put all of that together: to denote that one infinite set $X$ is (strictly) smaller than another set $Y$, we write $|X|\lt |Y|$. When working with alephs or more generally cardinal numbers, we dispense with the "absolute value bars" and simply write the expressions involving alephs, e.g., $\aleph_1\leq 2^{\aleph_0}$, or $\kappa\lambda = \kappa+\lambda$ if at least one of the cardinals $\kappa$ and $\lambda$ are infinite, etc.

I'm pretty sure you can find most of this in Halmos's Naive Set Theory, but I'm away from the office right now; I'll check tomorrow, and if not, give another reference.

Added. Halmos uses $X\sim Y$ for the case where $X$ and $Y$ are bijectable, and $X\stackrel{\lt}{\sim} Y$ for the case where $X$ is bijectable with a subset of $Y$ (that is, when there is an injection from $X$ to $Y$. (Section 22, on the Schroeder-Bernstein Theorem). He then uses $\prec$ for strict inequality of cardinals. At first he uses $\mathrm{card}\;a$ for the cardinality of the set $a$, then uses roman letters for cardinal numbers, and switches to the more common $\lt$ in Section 24 (Cardinal Arithmetic); he introduces the Alephs in the penultimate page of his book.

share|improve this answer
add comment

Your Answer


