Orchid XP v8 wrote:
> But there are surely *more* rational numbers than natural numbers?
> 
> Actually, let's try something easier: Common sense tells you that the 
> number of 2D coordinates is obviously [vastly] greater than the number 
> of 1D points. Yet set theory asserts that both sets are exactly the same 
> size. How can this be?


First, we need a clear definition of `size' which will work for infinite 
sets:

Given two sets, A, and B, we'll say that B is at least as large as A (B 
 >= A) if there is a function which maps every element in A into a 
unique element in B.

If no such function is possible, then we say that A is larger than B (A 
 > B).

If A >= B and B >= A. Then A and B are of the same size (A <=> B).

(Note my ASCII isn't standard here, but I think it works intuitively 
enough).


Let's start even simpler, and show that the set of natural numbers, N, 
is the same size as the set of integers, I.  Clearly I >= N, since it's 
trivial to map easy natural number into a unique integer.

To show that N >= I, consider the function

function f(i) {
	if i < 0 {
		return -2*i - 1
	} else {
		return 2*i
	}
}

You can check that (assuming I didn't make a mistake) this function maps 
each integer into a unique natural number.  This N >= I

Since we have I >= N and N >= In so I <=> N.


Also note that there's a trick that works for proving that N >= S for 
many different sets S -- just show that you can represent every element 
in S exactly in a computer program.  Since the program can be compiled 
to binary, the compiler does the work of defining the function from 
element in S to a unique element in N for you.

Post a reply to this message