36
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Have you tried searching the site? $\endgroup$
    – Asaf Karagila
    Commented Jun 7, 2013 at 14:27
  • $\begingroup$ Yes, I did and found some technical stuff too. $\endgroup$ Commented Jun 8, 2013 at 3:44
  • $\begingroup$ @VishalGupta Can u plzz explain how |$Q^N$| =$|N|$? $\endgroup$
    – anonymous
    Commented May 12, 2017 at 19:01

5 Answers 5

60
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ Thanks for the lovely answer. $\endgroup$ Commented Jun 8, 2013 at 3:40
  • 9
    $\begingroup$ A lovely use of currying indeed. $\endgroup$
    – Alex Vong
    Commented Jun 6, 2017 at 4:37
  • $\begingroup$ @Alex Vong I'm sorry but can someone explain this more clearly for me? I'm getting confused by the two "n" subscripts for f. I understand that R can be mapped bijectively to set of all functions from N to {0,1} but the part after that isn't clear. $\endgroup$ Commented Feb 20, 2021 at 6:17
7
$\begingroup$

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\}$?

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the very nice intuitive explanation. Yeah, I got the other question also, thanks to your hint; the cardinality is greater than equal to that of power set of real numbers. But is it equal to the cardinality of power set of real numbers? $\endgroup$ Commented Jun 8, 2013 at 3:42
  • 2
    $\begingroup$ @Santiago Canez Can you give some intuitive idea about the converse too, that is every real sequence can be put into as numbers between 0 and 1 $\endgroup$
    – Saravanan
    Commented Jan 20, 2017 at 9:49
7
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for the nice answer. But how did you say so, it ends up,$\left| \mathbb{R}^{\mathbb{N}} \right| =\left| \mathbb{Q}^{\mathbb{N}} \right|= c$? And could you give some reference to the last formula? $\endgroup$ Commented Jun 8, 2013 at 3:38
  • $\begingroup$ So a little bit of elaboration on $\left| \mathbb{R}^{\mathbb{N}} \right| =\left| \mathbb{Q}^{\mathbb{N}} \right|= c$. The one on the left you know from your own research; i.e. the cardinality of the sequences of the real numbers is the same as that of the reals. The one on the right works because there's an injection from $\mathbb{R}$ to $\mathbb{Q}^\mathbb{N}$ and another from $\mathbb{Q}^\mathbb{N}$ to $\mathbb{R}^\mathbb{N}$. I thought I had seen the last formula somewhere but now I'm not so sure. $\endgroup$ Commented Jun 8, 2013 at 6:21
  • $\begingroup$ I think your formula holds under GCH. Specifically, $P^Q = \beth_\alpha^{\beth_\beta}$ in GCH, for some ordinals $\alpha$ and $\beta$. If $\alpha$ has a predecessor $\gamma$, then we have $P^Q = \left ( 2^{\beth_\gamma} \right )^{\beth_\beta} = 2^{\max \{ \beth_\gamma,\beth_\beta \}}= 2^{\beth_{\max \{ \gamma,\beta \}}}$. Now if $P>\mathcal{P}(Q)$ then $\gamma \geq \beta$; if $P<\mathcal{P}(Q)$ then $\gamma<\beta$; if $P=\mathcal{P}(Q)$ then $\gamma=\beta$. In any of these cases we get what was wanted. I'm not sure what to do if $\alpha$ is a limit ordinal. $\endgroup$
    – Ian
    Commented Sep 14, 2014 at 20:25
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks. But could you be a little more explanatory? Also, could you answer what is the cardinality of all real functions? $\endgroup$ Commented Jun 7, 2013 at 14:10
  • $\begingroup$ For $A=\mathbb{R}$, it turns out that $|A^\mathbb{N}|=|A|$, as proved here. $\endgroup$
    – vadim123
    Commented Jun 7, 2013 at 14:12
  • $\begingroup$ Yeah, I had seen that before posting. However, I do not understand how he got the third equality in that line. $\endgroup$ Commented Jun 7, 2013 at 14:19
  • $\begingroup$ This comes from $\aleph_0\times\aleph_0=\aleph_0$. See, e.g. here. $\endgroup$
    – vadim123
    Commented Jun 7, 2013 at 16:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .