# $2^n$ subsets of set with $n$ elements $\overset{?}{\implies}$ $\mathbb{R}$ has $2^\infty=\infty$ subsets

I'm told that there are $2^n$ subsets of a set with $n$ elements, but does this imply that $\mathbb{R}$ has $2^\infty=\infty$ subsets?

-
No, there are $2^{\infty}$ subsets, it has different cardinality than $\infty$ subsets. – Arjang Apr 29 '13 at 5:40
In any case it is plain that $\mathbb{R}$ has infinitely many subsets because it has infinitely many elements. – Adam Saltz Apr 29 '13 at 5:41
$\infty$ is not a number. And reasoning about finite numbers is not accurate when looking at infinite sets. Anyway, yes, once one defines things properly, the size of the power set of a set $X$ is $2^{|X|}$, where $|X|$ is the size of $X$. On the other hand, $2^{|X|}>|X|$, so writing $2^\infty=\infty$ is not correct. – Andrés Caicedo Apr 29 '13 at 5:41
Expressions like "pretty easy" and "plain" I feel will never lead you to success in life. – Trancot Apr 29 '13 at 5:42

## 4 Answers

The are four number systems in this context:

1. Cardinal numbers,
2. Real numbers,
3. Ordinal numbers,
4. Natural numbers.

When we talk about finite operations (i.e. addition, multiplication and exponentiation with finitely many terms) the natural numbers embed into each of the other three, and behave the same way. This is why we can think of $n$ as cardinal, an ordinal, and so on.

But when we move to infinitary operations, and processes involving limits then no number system is like another. In particular the limit process of $2^n$ as $n$ grows larger is not the same in any of the systems:

1. In the cardinal numbers the power function is not continuous, $\sup 2^n=\aleph_0<2^{\sup n}=2^{\aleph_0}$.
2. In the ordinal numbers the exponentiation is continuous, $\sup 2^n=\omega=2^\omega$ (note, $\omega$ is sometimes used to denote the cardinal $\aleph_0$, but this context is ordinal exponentiation, and not cardinal exponentiation as above).
3. In the real numbers $2^n$ does not have a finite limit, so we write it as $\infty$, since we allow fractions we can ask in a meaningful way whether another sequence $a_n$ grows "faster" or "slower" than $2^n$ and have some meaning we can extract from $\frac\infty\infty$ and similar indeterminate situations.
4. While the above consideration can be meaningfully investigated in the context of the natural numbers as well, since the results often ends up being something other than an integer we don't really investigate in the integers, but rather in the real numbers. For this reason I say that in the natural numbers there is no meaning to limits and infinitary operations (i.e. addition/multiplication/exponentiation with infinitely many terms).

So when saying that $2^n\to2^\infty$ you switch context from the real numbers to cardinal numbers, and there you run into two other problems:

1. The fact that the cofinality of the real numbers is countable (i.e. you have a countable unbounded set in the real numbers), but if we consider the cardinal $2^{\aleph_0}$ then it has uncountable cofinality (whenever we partition the real numbers into countably many sets, one will be of size continuum).
2. You have used the ordinal exponentiation, which is continuous at limit points, rather than cardinal exponentiation which isn't, so your result is wrong as well.
-
Thank you for your effort here. I appreciate it. – Trancot Apr 29 '13 at 8:11

Kinda... but not really.

Note that two sets $A$ and $B$ are said to have the same cardinality if there is a one-to-one function $h : A \to B$ which maps onto $B$. We then devise abstract numbers to denote the cardinality of sets, and write $|A|$ for the cardinality of the set $A$. For finite sets these numbers are the usual counting numbers; for infinite sets we have to be more careful, but the details are not strictly necessary. After this is done, we can define certain arithmetic operations on these cardinal numbers. As one example:

Given two cardinal numbers $\kappa$ and $\lambda$ we define the exponent $\lambda^\kappa$ to be the cardinality of the set $$\{ f : f\text{ is a function from }A\text{ into }B \}$$ where $A$ and $B$ are any two sets with $|A| = \kappa$ and $|B| = \lambda$.

In particular, $2^\kappa$ is the cardinality of the set $$\{ f : f\text{ is a function from }A\text{ into }\{ 0,1 \} \}$$ where $A$ is any set with $|A| = \kappa$.

One can show that this definition agrees on the finite cardinals; i.e., if $m,n$ are natural numbers (say not both $0$ to avoid the $0^0$ case), then the cardinal exponent $n^m$ agrees with the usual arithmetic exponent.

Moreover, it can be shown that $2^\kappa$ is equal to the cardinality of the power set $\mathcal{P} (A)$ where $A$ is any set with $|A| = \kappa$.

Define a function $h : \{ f : f\text{ is a function from }A\text{ into }\{ 0,1 \} \} \to \mathcal{P} (A)$ by $$h (f) = \{ x \in A : f(x) = 1 \}.$$

However, the genesis of set theory was the discovery by Cantor that there are different magnitudes of infinity. Even though the sets

• $\mathbb{N}$, the set of natural numbers;
• $\mathbb{Z}$, the set of integers;
• $\mathbb{Q}$, the set of rational numbers

have the same cardinality, the set $\mathbb{R}$ has strictly larger cardinality, in the sense that there are one-to-one functions $f : \mathbb{N} \to \mathbb{R}$, but no such function maps onto $\mathbb{R}$; this is Cantor's famous diagonalisation proof. As such the symbol $\infty$ cannot stand for the cardinality of all infinite sets, and so $2^\infty$ is meaningless in the set-theoretic context; we have to be much more precise. (Note, also, that there is no largest infinite cardinal number. Given any set $A$, the power set $\mathcal{P} (A)$ can be shown to have strictly largest cardinality; this is a fact known as Cantor's Theorem.)

-
Thank you, I appreciate your work. – Trancot Apr 29 '13 at 7:01

$\mathbb N$ has $\aleph_0$ elements and $2^{\aleph_0}=\mathbf c$ subsets. $\mathbb R$ has $\mathbf c$ elements and $2^{\mathbf c}$ subsets. The symbol $\infty$ is just that - a symbol for infinity (as used e.g. in $\lim_{n\to\infty}a_n$ or $\sum_{n=0}^\infty a_n$, where the use of $\aleph_0$ or $\omega$ would simply be wrong), not a denotation for any specific cardinality. So if anything at all, $\infty$ is a special element added (first of all) to $\mathbb N$ for topological completion, not a (natural, real, cardinal, ordinal) number.

-
Thank you, Mr./Ms. Hagen von Eitzen. – Trancot Apr 29 '13 at 5:44
Minor notational note, the cardinal of the continuum is often denoted with a Fraktur font, not boldface. That is, $\frak c$ rather than $\bf c$. – Asaf Karagila Apr 29 '13 at 19:11

No, there are $2^{\infty}$ subsets, it has different cardinality than $\infty$ subsets. The power sets of infinite sets have a higher cardinality than the original set.

-
Thank you Mr./Ms. Arjang. – Trancot Apr 29 '13 at 5:45
Note that $\infty$ is not a cardinality to begin with. – Asaf Karagila Apr 29 '13 at 19:11
@AsafKaragila : Thanks, I assumed $\infty$ is assumed to be same as the set of natural numbers, but it might not be the case. – Arjang Apr 29 '13 at 22:15