posted on Nov, 25 2004 @ 02:22 PM
slank: actually, your thesis is right, in a certain sense. proof a:
let's call N the set of all positive integers (0,1,2,3,4,...)
let's say if we've got set A and set B then they have the same size if and only if you can "pair up" members of A and B so that every member of A
has a unique matching item in B, and every member of B has some member in A so that A is paired with B (for the mathematicians, you want the
"pairing" to be an injective and surjective map from A to B, or alternatively a bijective map from A to B, but if you already know those terms
you've probably seen all that's coming next).
So, are there any sets that are the same size as N? Sure; how about we call
Z the set of all positive and negative integers, ie, (...-2,-1,0,1,2,...)
is Z bigger than N? You might be inclined to say yes, because everything in N is in Z but not everything in Z is in N, but using our definition of
same size I can show you that N and Z are the same size:
match:
0 with 0
1 with 1
2 with -1
3 with 2
4 with -2
5 with 3
6 with -3
etc.,
and you can check that every member of N gets a unique member of Z, whereas every member of Z gets a unique member of N, so in fact using the "same
size" definition above N and Z are the same size.
There's also a way to show that the rationals -- let's call them Q -- are the same size as N, but it's a bit trickier to write down. For now, take
my word that the size of the rationals and the size of the integers is the same.
So, what about irrationals/the rest of the real numbers? follow amantine's advice and google the diagonalization argument, or look at this
summary:
every number between 0 and 1 can be expressed as an infinite binary string:
0.1 = one half
0.11 = 3/4
0.01 = 1/4, etc.,
and since every number between 0 and 1 can be expressed like that, let's let R = the set of all infinite binary strings (padding finite strings like
0.1 with 0000's all the way to infinity). We need to be careful here:
0.11111111111111111111111111111111111...etc
is actually just 1,
and more generally, if we've got a string that ends like this
.....0111111111111111 (all 1s)
then it's the same as
----100000000000000
so we need to be careful about that; it's easiest just to throw away all strings that end in infinite 1s. Having done that, what would it mean if R
was the "same size" as N? we'd have to be able to "pair off" strings from N and R, right? So, we could write a table like this:
0 , 0.100110101001
1, 0.101110100110
2, 0.101001101010
etc., (i'm just using random strings on the right side), and every string in R would be paired with a number from N. But, what if we did this:
the nth digit of x is 1 if the nth digit of the nth string above is 0, and the nth digit of x is 0 if the nth digit of the nth string above is 1...
then x would be an infinite string of 0s and 1s, and thus in R (again, you have to be careful to make sure that it's not all 1s at the end, but this
can be done), but because x's nth digit disagrees with the nth digit of the nth string in our table, x isn't in our table; thus we've contradicted
ourself and we can conclude that it's impossible to pair up the sets N and R.
Since R is just a small part of the real numbers (being only from 0 to 1 instead of - infinity to + infinity ) then all the real numbers are clearly a
bigger set than N. Thus, yes, there's a sense in which the irrationals greatly outnumber the rationals.