# Proof of cardinality

• Aug 5th 2011, 07:32 AM
Alexrey
Proof of cardinality
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.
• Aug 5th 2011, 07:49 AM
Plato
Re: Proof of cardinality
Quote:

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.

Would you kindly state very simply and concisely what are you asking?
• Aug 5th 2011, 07:54 AM
Also sprach Zarathustra
Re: Proof of cardinality
Quote:

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.

I don't understand you.

f(x)=x^2

f(-1)=1=f(1)

So f is clearly not injective.
• Aug 5th 2011, 07:54 AM
MoeBlee
Re: Proof of cardinality
Quote:

Originally Posted by Alexrey
if two sets have the same cardinality then the function that maps one set to the other must be a bijective function

That needs to be restated:

X and Y have the came cardinality if and only if there exists a bijection between X and Y.

There is no "the" function that maps one to another, since there are many functions that map one to the other. And for equal cardinality, it is not required that all such functions be bijections but rather it is required only that there exists at least one bijection from one to the other.

Quote:

Originally Posted by Alexrey
Define f: N(o) --> N, where n |--> n+1
Let f be one-to-one.

No, don't say "Let f be 1-1." Rather, say, "We need to PROVE that f is is 1-1."

Quote:

Originally Posted by Alexrey
Let f be onto.

No, don't say "Let f be onto N." Rather, say, "We need to PROVE that f is onto N".

Quote:

Originally Posted by Alexrey
Define f: R --> R, where x |--> x^2

Let f be one-to-one.

No, don't say "Let f be 1-1".

Quote:

Originally Posted by Alexrey
n^2 = m^2 which implies that n = m.

But that's false, as you know.

Quote:

Originally Posted by Alexrey
Let f be onto.

No, don't say "Let f be onto."

Quote:

Originally Posted by Alexrey
Let n be an element of R, then sqrt(n) is an element of R

But that's false, as you know.
• Aug 5th 2011, 08:48 AM
topspin1617
Re: Proof of cardinality
These are two completely different functions. You can't just copy one proof, replace all of the N's with R's and +1's with ^2's, and expect that it should work, or that the two should have anything to do with each other at all.

They are two different situations and should be treated as such.
• Aug 7th 2011, 05:45 AM
Alexrey
Re: Proof of cardinality
Maybe I need to just wrap my head around it a bit more. It just seems like the only thing that the proof is doing is restating the definitions of surjectivity and injectivity.