About the Continuum Hypothesis

Question

Possible Duplicate:
Are there more rational numbers than integers?

The Continuum Hypothesis states:

There is no set whose cardinality is strictly between that of the integers and that of the real numbers

I'm not a mathematician, but it occurred to me that the cardinality of the set of rational numbers will fit strictly between that of the integers and that of the real numbers, won't it?

[edit] From the wikipedia-entry:

It turns out the rational numbers can actually be placed in one-to-one correspondence with the integers, and therefore the set of rational numbers is the same size (cardinality) as the set of integers: they are both countable sets.

How can this be? The one has all the integers PLUS fractions:

Two sets are said to have the same cardinality or cardinal number if there exists a bijection (a one-to-one correspondence) between them

Answer 1

In short: No.

There are as many rationals as there are natural numbers, both are countably infinitely many. They both share the cardinality $\aleph_0$.

Answer 2

One way of thinking about why the definition of equal cardinality in the infinite case is sensible is as follows.

First we think about cardinality in the finite case. You observe in your question that if you have one set $A$ strictly contained in another set $B$ (i.e. every element of $A$ is an element of $B$, but there are some of elements of $B$ that are not in $A$) then it would be nice to say that the size, or cardinality, of $B$ is larger than that of $A$, written $|B|>|A|$. This is a resonable definition to make, but it doesn't tell us much about what happens when one set is not contained in the other.

For example, let's take $A=\{0,1,2\}$ and $B=\{3,4,5,6\}$, so we have neither that $A$ is strictly contained in $B$, nor that $B$ is strictly contained in $A$. But we'd still like to give some meaning to our intuition that $B$ is larger. We could do this by counting elements, but we want to apply this reasoning to infinite sets later, where counting doesn't work quite so nicely, so we'll avoid that if possible. One think we could notice is that the function $A\to B$ defined by $0\mapsto 3$, $1\mapsto 4$ and $2\mapsto 5$, i.e. $x\mapsto x+3$, is injective, meaning that each element of $A$ is mapped to a different element of $B$. The existence of such a function turns out to be a good definition for $|A|\leq|B|$, as if $A$ had more elements than $B$ there couldn't be such a function. As we observe that there is no injective function $B\to A$, we have that $|B|\not\leq|A|$, so we should write $|A|<|B|$, which fits with our intuition.

As this definition doesn't depend on counting, it's a fairly natural definition to use in the case of infinite sets. The inclusion map ($x\mapsto x)$ from the integers to the rationals is clearly injective, so we find that $|\mathbb{Z}|\leq|\mathbb{Q}|$. However there are also various injections from $\mathbb{Q}\to\mathbb{Z}$, my favourite being that you should write each rational number as $\pm\frac{a}{b}$, with $a$ and $b$ positive and coprime, and then send that rational to the integer $\pm2^a3^b$ (the sign of the rational and the integer agree) - this is then injective by uniqueness of prime factorisation. So exactly as the integers sit inside $\mathbb{Q}$, there is a map which makes the rationals sit inside $\mathbb{Z}$ as well, and so it makes sense to say that $|\mathbb{Z}|=|\mathbb{Q}|$, even though $\mathbb{Z}$ is strictly contained in $\mathbb{Q}$.

Note also that while the inclusion is an injection $\mathbb{Z}\to\mathbb{R}$, there does not an exist an injection $\mathbb{R}\to\mathbb{Z}$, so $|\mathbb{Z}|<|\mathbb{R}|$.

Note: I've talked about two sets having an injection between them each way because this is a neater generalization of the notion of inclusion that you were talking about in the question, but it is equivalent to the existence of a bijection by the Cantor–Bernstein–Schroeder theorem.

Answer 3

You have discovered Galileo's paradox. Galileo observed that by one argument, there are the same number of perfect squares (1, 4, 9, 16…) as there are natural numbers, because each number has exactly one square and each square has exactly one square root. But by another argument, there are "obviously" more numbers than squares, since every square is a number, but not every number is a square.

This is exactly analogous to your puzzle about integers and rationals: by one argument, they are equinumerous, but by another argument, there "obviously" more rationals than integers.

Answer 4

This is too long to be a comment so I will post it here:

To me, defining to sets to be of equal cardinality using bijections seems a natural generalization of the idea of comparing the cardinality of finite sets. When working with sets like $A=\{1,2,3,4\}$ and $B=\{5,6,7,8\}$, we can easily count them to determine whether they have the same number elements. We could also have defined the function $f:A\rightarrow B$ by $f(a)=a+4$ for all $a \in A$. This example is contrived, but it illustrates the point that defining sets to be of equal cardinality through bijections follows our most basic intuition for size.

Infinite sets, however, violate our common ideas of size, as we cannot count them, so what notion of size can we give them? Suppose now that $A$ and $B$ are infinite sets. If $f:A \rightarrow B$ is a bijective function, then this says that each element of $A$ can be paired uniquely with an element of $B$ and that no element of $B$ is missed. To give a dull example, let $A=\mathbb{N}$ and let $B=10\mathbb{N}=\{10,20,30,...\}$. The bijective function between these two sets is obvious, as we can create the pairs $(1,10),(2,20),...,(m,10m)$ and so on.

I'm sure someone can link you to an explicit bijection between $\mathbb{N}$ and $\mathbb{Q}$. As Cantor's diagonal argument shows, assuming there exists a bijection from $\mathbb{N}$ to $\mathbb{R}$ produces a contradiction, as you can show there is an element of $\mathbb{R}$ which is not counted by the function.

Answer 5

There are many ways to compare sets. Cardinality is just one of them. For example, you might also compare sets using the relation "is a subset". Then you could say that the set of rational numbers is strictly between the set of natural numbers and the set of real numbers in the sense of inclusion. (This actually depends a bit on how you define these sets, though.)

So, why do we use cardinality? Because it is a natural generalization of how we count things. To understand it, try to imagine that you have not yet learned to count. You have a basket of apples and a basket of eggs, however, and you want to compare them. What you do, is the following: you take one apple and one egg out of the basket. Then you take another apple and another egg out. And another. If you run out of apples and eggs at the same time, there must have been the same number of them in the first place. We managed to pair them up.

The idea of cardinality just generalizes this. If it is possible to pair two sets up, we say they have the same cardinal number of elements. Note that in the case where sets are infinite, you can't just pair them up blindly anymore, as in the finite case, since in this way, there may be some elements left in only one of the sets. (This strange behaviour is characteristic of infinite sets.) What matters, though, is that there is at least one way of pairing them up.

In the case of integers and rationals, this basically amounts to numbering the rationals. Since it is possible to pair integers and rationals up in this way (try it!), they are of equal cardinality. However, Cantor has shown that it is impossible to pair up integers and reals. He did this by showing that any numbering of the reals must necessarily leave out some real numbers. And in this sense, there are more real numbers than natural numbers.

Answer 6

The set of rationals is countably infinite, as is the set of square numbers. This means that they can be put in a one-for-one correspondence with the integers. Since you say you're not a mathematician, you may need a way to visualise how to match 2 infinite lists.

For a simple example, take the square numbers. To see how they map to the integers, match the integers to the squares one by one, as follows:

1, 4, 9,16,25, ...

1, 2, 3, 4, 5, ...

As you can see, for every square there is just one integer; they match up one for one. Hence there are as many squares as there are integers, no more, no less.

The rationals can be matched to the integers in a similar but more complicated way. Rather than listing them here, this site shows explicitly how to go about it.