# Infinite sets and cardinality

1. Aug 27, 2008

### johndoe3344

The solution of Galileo's Paradox is that the set of natural numbers and the set of perfect squares are both infinite sets of the same cardinality (namely aleph 0). This I can understand. There can be established a 1:1 correspondence between each element of the two sets.

But then why is the set of real numbers larger than the set of natural numbers? Since the latter set is infinite, can't I use the same logic as above to show a 1:1 correspondence?

Can anyone explain this to me intuitively?

2. Aug 27, 2008

### CompuChip

No you can't
In fact, the subset [0, 1] of the real numbers is already "larger" than the set of all natural numbers. The way to show this (and a useful proof technique in general) is using Cantor's diagonal argument.

3. Aug 27, 2008

### CRGreathouse

You can make a list of the integers, just like you can make a list of the squares. In both cases the list is complete, in the sense that every integer (and every square) will appear at some finite position on the list. This is called countability. The integers, their squares, and even the rational numbers are countable.

The real numbers, as shown by Cantor's diagonal argument, are uncountable. As a result you can't make the bijection, so the argument falls through.