Originally Posted by

**Alexrey** I know I must be missing something, since I've tried for the past 4 hours to understand some cardinality proofs, but they just don't make sense to me.

I know that if two sets have the same cardinality then the function that maps one set to the other must be a bijective function. I also know that for a function to be bijective, it has to be injective and surjective. I also understand completely what injective, surjective and bijective functions are... but I still can't make sense of the cardinality proofs given to me. Here is an example:

The set of all natural numbers including zero (call it N(o)) has the same cardinality as the set of natural numbers (call it N). To prove this, we have to find a bijective mapping from N(o) --> N.

Define f: N(o) --> N, where n |--> n+1

Let f be one-to-one. Let n, m be elements of N(o) such that f(n) = f(m), then n+1 = m+1, and hence n = m, so f is injective.

Let f be onto. Let n be an element of N, then n-1 is an element of N(o) and f(n-1) = n-1+1 = n. Hence f is surjective.

Therefore f is bijective and N(o) has the same cardinality as N.

That all fine and well, I can regurgitate that proof for other cardinality tests, but I don't truly know how what was stated above is enough to prove that a function f is bijective.

Take for instance this example:

Define f: R --> R, where x |--> x^2

This function is clearly not bijective since it is not injective or surjective, but using the same style of proof from above and regurgitating its contents I have the following:

Let f be one-to-one. Let n, m be elements of R such that f(n)= f(m), then n^2 = m^2 which implies that n = m.

Let f be onto. Let n be an element of R, then sqrt(n) is an element of R, such that f(sqrt(n)) = (sqrt(n))^2 = n.

Therefore f is bijective and R has the same cardinality of R.

I know that my proof was completely false, but how the heck can the first proof be enough to justify that f: N(o) --> N is bijective? I just don't get it!

If anyone could help me out I would really appreciate it, I'm getting sick of reading and then re-reading the proofs and definitions a million times without understanding why the cardinality proofs are valid.