# The set of rationals has the same cardinality as the set of integers

The set of rationals $\mathbb{Q}$ has the same cardinality as the set of integers $\mathbb{Z}$. True or false?

This was a question on an old exam for our class. The correct answer is true. However, I did some additional reading and came across Cantor's transfinite numbers. In the book I'm reading, it says that "there are more real numbers (which include rational and irrational numbers) than there are integers". So can it also be said that there are more rational numbers than integers? And so can we say that the above statement is false?

-
@Arturo lol oh come on not even discrete-mathematics?? – maq Nov 28 '10 at 4:01
@fprime: please stop abusing the (number-theory) tag. Number theory has nothing to do with counting. – Arturo Magidin Nov 28 '10 at 4:02
@fprime: no, not even discrete mathematics. This question is purely, simply, and squarely, an elementary set theory question. – Arturo Magidin Nov 28 '10 at 4:02
@fprime: not knowing what to tag it with does not excuse misusing other tags. A simple search of "cardinality" in this very site would have pointed you to numerous questions about cardinality. Most are tagged either (set-theory) or (elementary-set-theory). The only ones I can see tagged (number-theory) that came up with the search are the ones you mis-tagged. – Arturo Magidin Nov 28 '10 at 4:07
I don't understand the question at all. Why does learning that the real numbers are uncountable make you doubt that the rationals are countable? – Pete L. Clark Nov 28 '10 at 7:56

No. The statement is still true. The cardinality of the natural number set is the same as the cardinality of the rational number set. In fact, this cardinality is the first transfinite number denoted by $\aleph_0$ i.e. $|\mathbb{N}| = |\mathbb{Q}| = \aleph_0$. By first I mean the "smallest" infinity.

The cardinality of the set of real numbers is typically denoted by $\mathfrak{c}$. We have $\mathfrak{c} > \aleph_0$, since we can set up a bijection from $\mathbb{R}$ to the power set of the natural numbers and by Cantor's theorem, for any set $X$, we have $|X| < |2^{X}|$. So we have $|\mathbb{R}| = |2^{\mathbb{N}}| > |\mathbb{N}|$. So what this essentially says is that "there are more real numbers (which include rational and irrational numbers) than there are integers" in some sense.

The continuum hypothesis states that "there is no set whose cardinality is strictly between that of the natural numbers and that of the real numbers" which essentially means real numbers form the second "smallest" infinity.

-
@Sivaram: I think it is misleading to say the real numbers are the second "smallest" infinity, even with the CH disclaimer. In fact, CH is irrelevant to this: $|\mathbb{R}|=2^{\aleph_0} = |\mathcal{P}(\mathbb{N})|$, and Cantor's Theorem says that $|X|\lt |\mathcal{P}(X)|$ for any set $X$. – Arturo Magidin Nov 28 '10 at 4:26
@Arturo: Sorry. I might be wrong. But I have mentioned that $\aleph_1 > \aleph_0$ and by $\aleph_1$ I mean the cardinality of real number and by $\aleph_0$ I mean the cardinality of natural numbers. And CH says there are no transfinite numbers between $\aleph_0$ and $\aleph_1$. This is what I intended to convey in the post. Correct me if I am wrong. I should probably mention the first sentence of the second paragraph at the end of the second paragraph? To make better sense – user17762 Nov 28 '10 at 4:34
@Sivaram: I'm afraid you have fallen to a common misunderstanding: $\aleph_1$ is, by definition, the smallest cardinal strictly larger than $\aleph_0$; so we know that there is no cardinal between $\aleph_0$ and $\aleph_1$ by definition, not by CH. We know that the cardinality of $\mathbb{R}$ is $2^{\aleph_0}$. What CH says is that $2^{\aleph_0}=\aleph_1$ (and GCH says that $2^{\aleph_{\alpha}}=\aleph_{\alpha+1}$ for all ordinals $\alpha$). See en.wikipedia.org/wiki/Aleph_number – Arturo Magidin Nov 28 '10 at 4:48
@Arturo: Ok. I thought the cardinality of the set of real numbers is denoted by $\aleph_1$. Now I have edited my post. I understand that by CH, $\mathfrak{c} = \aleph_1$, where $\mathfrak{c}$ stands for the cardinality of real numbers. Kindly let me know if this makes sense now. I am using to forum to learn these things on mathematics. So kindly tolerate my mistakes (I think here the mistake was more of notational mistake and not conceptual mistake). – user17762 Nov 28 '10 at 4:59
@Sivaram: I would say "bijectable with" rather than "essentially", regarding $\mathbb{R}$ vs. the power set of $\mathbb{N}$. I would also put CH front and center in your final sentence, rather than parenthetically at the end, and clarify it (it's not about $\mathbb{R}$, but its cardinal); that is, "The Continuum Hypothesis says that $\mathfrak{c}$ is the second "smallest" infinity." You may want to link "Continuum hypothesis" to en.wikipedia.org/wiki/The_Continuum_Hypothesis – Arturo Magidin Nov 28 '10 at 5:05

You can say whatever you want. However, if you want to be correct, and you are talking about cardinalities, then you cannot say that there are more rationals than integers.

The reason we can say that there are more reals than rational numbers is because they actually have greater cardinality, not just because the set of reals properly contains the natural numbers. While we can find a bijection between $\mathbb{N}$ and $\mathbb{Q}$, no function from $\mathbb{N}$ to $\mathbb{R}$ is surjective (and, naturally, no function from $\mathbb{Q}$ to $\mathbb{R}$ can be surjective either).

-

Just because the integers are a proper subset of the rationals doesn't mean that the rationals have a higher cardinality than the integers. Actually, there is a theorem that says that a set is infinite if and only if it has the same cardinality to a proper subset of itself (so your logic would only apply to a finite set).

A set is countable, or has the same cardinality as the integers, if you can count the elements. In other words, you can label each element by a unique positive integer. We can see from the diagonals argument (see this image on Wikipedia for a good illustration) that this holds for that rational numbers. Once you get the hang of it, you can see that a lot of sets that seem to be a lot bigger than the set of integers are in fact the same "size" (have the same cardinality) as the integers. See Hilbert's Paradax of the Grand Hotel for a good example of this.

-