Thread: 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.

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?

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.

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.

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."

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".

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".

Originally Posted by Alexrey

n^2 = m^2 which implies that n = m.

But that's false, as you know.

Originally Posted by Alexrey

Let f be onto.

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

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.

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.

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.