24
$\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 Jun 7 '13 at 14:27
  • $\begingroup$ Yes, I did and found some technical stuff too. $\endgroup$ – Vishal Gupta Jun 8 '13 at 3:44
  • $\begingroup$ @VishalGupta Can u plzz explain how |$Q^N$| =$|N|$? $\endgroup$ – sani May 12 '17 at 19:01
41
$\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
  • $\begingroup$ Thanks for the lovely answer. $\endgroup$ – Vishal Gupta Jun 8 '13 at 3:40
  • 6
    $\begingroup$ A lovely use of currying indeed. $\endgroup$ – Alex Vong Jun 6 '17 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$ – Agile_Eagle Feb 20 at 6:17
6
$\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
  • $\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$ – Vishal Gupta Jun 8 '13 at 3:42
  • 1
    $\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 Jan 20 '17 at 9:49
5
$\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
  • $\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$ – Vishal Gupta Jun 8 '13 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$ – Ben Grossmann Jun 8 '13 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 Sep 14 '14 at 20:25
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$ – Vishal Gupta Jun 7 '13 at 14:10
  • $\begingroup$ For $A=\mathbb{R}$, it turns out that $|A^\mathbb{N}|=|A|$, as proved here. $\endgroup$ – vadim123 Jun 7 '13 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$ – Vishal Gupta Jun 7 '13 at 14:19
  • $\begingroup$ This comes from $\aleph_0\times\aleph_0=\aleph_0$. See, e.g. here. $\endgroup$ – vadim123 Jun 7 '13 at 16:25
3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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