Question

Bijection or injection for countable infinite proof

Answer 1

Let XX be an infinite set. I've been trying to prove that an injection from XX to NN implies that XX is countable. I know this boils down to showing that an injection from XX to NN implies the existence of a surjection from XX to NN. Or, equivalently, that a surjection from NN to XX implies the existence of an injection from NN to XX.
Answer: Let f:X→Nf:X→N be your injection. Let M=f[X]M=f[X]. First define a bijection g:N→Mg:N→M recursively as follows. First, g(0)=minMg(0)=minM. If n∈Z+n∈Z+, and g(k)g(k) has been defined for k<nk<n, letg(n)=min(M∖{g(0),…,g(n−1)}).g(n)=min(M∖{g(0),…,g(n−1)}).It’s straightforward to verify by induction that gg is a bijection.