Can you help me understand this proof of countable infinity?
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.
This question is in the General Section. Responses must be helpful and on-topic.