OK, next installment.
Let's look at the 'size' of sets.
We need to start with the 'natural numbers'. These are ordinary counting numbers, starting at 0, so 0,1,2,3,4,5,...
We say a set is *finite* if there is some natural number that 'counts' the things in that set. So, for example, the set {1,2,3,4} has 4 things in it. So it is a finite set. The set of all numbers between 100 and 200, inclusive, has 101 elements in it, so it is finite.
A set which is not finite is said to be infinite.
So, the collection of ALL natural numbers, {0,1,2,3,4,5,..} is an infinite set.
The set of all even numbers is also infinite.
Now, we say two sets are the 'same size' if there is a way to pair them off. If two sets, A and B, are the same size, we write #(A) = #(B). In my previous post, I showed how the set of all natural numbers and the set of all even numbers are the 'same size' by this definition. This is true even thought the set of even numbers is a *subset* of the set of natural numbers.
And, in fact, this is a property that *characterizes* infinite sets: there is always a (proper) subset of the 'same size' as the whole set. This never happens for finite sets, but ALWAYS happens for infinite ones.
Next, we compare sizes. If a set A is the 'same size' as a subset of B, then we say that the size of A is less than or equal to the size of B. We write #(A)<= #(B). It is a theorem that if two sets, A and B, have both #(A)<= #(B) and #(B)<= #(A), then #(A)=#(B) using these definitions.
So, at this point, we have finite sets, where #(A)=n for some natural number n. And we have infinite sets for which this does not happen.
A natural question is whether all infinite sets are the 'same size'. And the answer is a definite NO.
To see this, we look at decimal numbers. A good example is pi, but so are the square root of 2, and others. These are numbers that have either a finite decimal expansion or an infinite one. But don't get too excited, the fraction 1/3 has an infinite expansion, 0.33333..... Those 3's never stop.
In fact, every fraction has a decimal expansion that eventually cycles. For example,
1/7=0.142857 142857 142857....
1/4 =0.25000000000....
But there are decimal numbers whose decimal expansion *never* cycles, like
0.1234567891011121314151617181920.....
where I am simply writing out each number in turn after the decimal point.
Anyway, the collection of all decimal numbers is a *larger* infinite size than the set of natural numbers!
I'll show you how to see this. Suppose I have a pairing of natural numbers and decimal numbers. I will give (the beginning of) a specific pairing, but I will try to keep the argument general. So suppose that
1 <--> 0.228487528047....
2 <--> 0.789872349879...
3 <--> 0.274729874987...
4 <--> 0.624976149879...
5 <--> 0.912879017912...
...
...
...
I wills how that no matter what pairing you have, you are guaranteed to miss some decimal number! here's how.
Construct a new number by letting it's first decimal digit be different than the first digit of the first number (avoid 0 and 9 for technical reasons). So, in my list above, I need the first digit to be different than 2. Let's pick 5.
Now, let the second digit be different than the second digit of the second number on the list. In this case, I want something different than 8, so I pick, say, 3.
Next, let the third digit be different than the third digit of the third number on my list. In this case, the third number has 4 as the third digit, so I pick something different, say 7.
Keep doing this. Let each digit of the new number be different than the corresponding digit of the corresponding element of my list.
In this case, I might get the number
.53724....
This number is nowhere on the list! it is different than the first number because it differs in the first digit. It is different than the second number because it is different in the second digit. it is different than the third number because it is different in the third digit. This continues and shows my new number is not on the list!
In other words, the two infinite sizes are different! It is easy enough to show one is smaller (by the above definition).
This generalizes. For *any* infinite set, there is an infinite set that is larger in size! So there are infinitely many sizes of infinite sets!