Send to a Friend

Mariah's avatar

Can you help me understand this proof of countable infinity?

Asked by Mariah (25883points) September 6th, 2012

My textbook is trying to show that, to prove a set is countably infinite, you can prove that the set has the same cardinality as the set of natural numbers, which is countably infinite. You prove equal cardinality by showing there is a bijection between the two sets. The example in the book is of odd positive integers.

It first proves that there is an injection like so:

“Consider the function f(n) = 2n-1” (I understand that they are defining an odd number here.)
“Suppose f(n) = f(m). Then 2n-1= 2m-1, so n=m.”

Then it proves there is a surjection:

“Suppose t is an odd positive integer. Then t is 1 less than an even integer 2k, where k is a natural number. Hence t = 2k-1 = f(k).”

I guess I’m having a hard time wrapping my mind around how either one of these proofs works. I understand what an injection and a surjection are, but something with the notation they’re using here has got my brain scrambled. Care to translate for me? I’d appreciate it a whole lot.

Using Fluther

or

Using Email

Separate multiple emails with commas.
We’ll only use these emails for this message.