cardinality of all real sequences

I was wondering what the cardinality of the set of all real sequences is. A random search through this site says that it is equal to the cardinality of the real numbers. This is very surprising to me, since the cardinality of all rational sequences is the same as the cardinality of reals, and it seemed fairly intuitive to me that if cardinality of a set $A$ is strictly greater than the cardinality of the set $B$, then cardinality of $A^{\mathbb{N}}$ should be strictly greater than cardinality of $B^{\mathbb{N}}$. It turns out to be false.

Some technical answers have appeared in this forum elsewhere but I do not understand them. As I am not an expert in this topic, could some one explain me in simple terms why this is happening?

Also is the cardinality of all functions from reals to reals also the same as the cardinality of reals?

Solution 1:

Identify $\mathbb R$ as the set of functions $f : \mathbb N \to \{ 0,1\} $.

Then any sequence $\{ x_n \}$ becomes a sequence $\{f_n \}_n$ where $f_n : \mathbb N \to \{ 0,1\}$. But then, this is simply a function $g : \mathbb N \times \mathbb N \to \{ 0,1\}$:

$$g(m,n) =f_n(m) \,.$$

This way you can construct a bijection from the sequences of real numbers to the set of functions from $\mathbb N \times \mathbb N \to \{ 0,1\}$. Now, since $\mathbb N \times \mathbb N$ and $\mathbb N$ have the same cardinality, you get a bijection from the sequences of real numbers to the set of functions from $\mathbb{N} \times \mathbb{N} \to \{ 0,1\}$, which is just $\mathbb R$.

Solution 2:

You asked for an explanation in "simple terms" why this is happening, which I take to mean an intuitive explanation instead of a formal proof, so that's what I'll give.

Focus on numbers between $0$ and $1$. Such a number is determined by a countable amount of information, namely the digits in its decimal expansion. So, a sequence of numbers between $0$ and $1$ is determined by a countable amount of countable information. But the countable union of countable sets is countable, so this countable amount of countable information can in turn be expressed by a countable amount of information, namely a countable number of digits. This can then be used to define a single real number between $0$ and $1$ which encodes the original sequence.

This idea can be used to give a formal proof. As for your question about functions, what do you know about the set of functions from $\mathbb R$ to $\{0,1\}$?

Solution 3:

It depends on whether you are talking about finite sequences, infinite sequences, or "uncountable sequences". Here is an attempt to give you a little bit of an intuition for the mathematical territory:

If you are talking about the set of all finite real sequences, then we have the following argument: for any $n$, the cardinality of $\mathbb{R}^n$ is the same as the cardinality of $\mathbb{R}$ (which I will call $c$ for convenience). Thus, the set of finite sequences of a given length is a set of cardinality $c$. The cardinality of the arbitrary union of sets of cardinality $c$ gives you another set of cardinality $c$. Thus, the set of all finite sequences is of cardinality $c$. The same argument can be made regarding $\mathbb{Q}$ (which has cardinality $\aleph_0$)

The cardinality of infinite sequences is, however, a different story. Cantor's argument tells us that for any set $S$, we have $\left| \wp(S) \right|>\left| S \right|$. For every subset of the rational numbers, there is a corresponding sequence in $\mathbb{Q}^{\mathbb{N}}$. Real numbers, on the other hand, are uncountable, so no infinite sequence will contain every element. So, as it ends up, $\left| \mathbb{R}^{\mathbb{N}} \right| =\left| \mathbb{Q}^{\mathbb{N}} \right|= c$

Finally, we have the "uncountable sequences", that is, the set of functions from $\mathbb{R}$ to $\mathbb{R}$, which does have a greater cardinality. Here, we can use the previous argument as follows: for any subset $S \subseteq \mathbb{R}$, we can map $S$ to a function $f(x)$ for which $f(x)=0$ for any $x\in S$. This gives us an injective map from $\wp(\mathbb{R})$ to the set of functions from $\mathbb{R}$ to itself. Thus, the cardinality of the set of functions from $\mathbb{R}$ to $\mathbb{R}$ is greater than $c$.

A nice bit of cardinal arithmetic to have in your arsenal: for transfinite sets $P$ and $Q$: $$ \left| P^Q\right|=\max\{\left|P\right|,\left|\wp(Q)\right|\} $$ EDIT: I am not sure about that last formula, let's call it a conjecture.

Solution 4:

Let $k,m$ be infinite cardinals. Then

$$(2^k)^m = 2^{k \cdot m} = 2^{\max \{ k,m \}}.$$

Here I have used the axiom of choice in the second equality. The $\max$ there causes the non-strict monotonicity that surprised you.

Solution 5:

In simple terms, our number-sense intuition comes from dealing with finite sets, and has very little value when dealing with infinite sets. This is why a set can have the same cardinality as a proper subset, and why $B^\mathbb{N}$ can have the same cardinality as $A^\mathbb{N}$ even if one is a proper subset of the other.