Prove that every subset of $\Bbb N$ is countable.
This is a very standard fact,that is proved at an introductory course on real analysis (as this is the case with me and we have just started real analysis in college). I saw many proofs of this fact. I was presented a proof, which goes like this:
Let $A\subset \Bbb N.$ If $A=\phi,$ or $A$ contains a finite number of elements, then $A$ is finite and so countable.
Suppose $A$ is not finite. Then we want to show that there exists a bijection $f:\Bbb N\to A.$
We define $f$ by induction as follows:
$f(1)=$smallest element of $A.$ This choice is possible by well-ordering property of $\Bbb N.$ Suppose $f(1),f(2),...,f(k)$ are all defined. Then define $f(k+1)=$ smallest element of $A-\{f(1),f(2),...,f(k)\}.$ Note that $A-\{f(1),f(2),...,f(k)\}\neq \phi,$ otherwise $A$ is finite as $f:\{1,2,3,...k\}\to A$ is bijective.
Thus, $f(n)$ is defined for all $\forall n\in\Bbb N.$
By definition, $f:\Bbb N\to A$ is injective.
[ If $m,n\in \Bbb N$ and $m<n$ then $f(n)\in A-\{f(1),f(2),...,f(m),...,f(n-1)\}$ ]
We next show that $f:\Bbb N\to A$ is surjective.
Let $a\in A$ be any element. By the injectivity of $f$ we have $$f(N)\not \subset \{1,2,3,...,a\}. \implies \exists m\in\Bbb N $$ such that $f(m)>a.$ Let $S=\{n\in\Bbb N:f(n)\geq a\}.$ Then $m\in S$ and so, $S$ is non-empty. Hence, $S$ has a least element say, $m_a, f(m_a)\geq a.$ Then, for all $n<m_a$ we have $$f(n)<a\implies a\notin \{f(1),f(2),...,f(m_a-1)\}.$$ By definition, $f(m_a)=$ the smallest element of $$A-\{f(1),f(2),...,f(m_a-1)\}\implies f(a)\leq a. $$ So, $f(m_a)=a.$ So, $f$ is surjective. Thus $f$ is bijective. Hence, $A$ is countably inffinite.
However, I feel this proof hard to follow. I think this proof is extremely convoluted. I tried understanding the proof but I was stuck at the portion where $f$ was shown to surjective (I have marked the portion in italics font.) This was the portion when my head started to reel as the argument is stated in an unnecessary complex way. The intention might have been to make the proof much more rigorous, but to me it seemed, more like an unnecessary rigorization of the proof, which makes the argument extremely confusing as well as, difficult to contemplate (as it seems to me at least).Therefore, I stopped reading further and I tried devising a simpler proof.
The proof I devised, is very much similar to the above proof, but there I made a few changes which I anticipated would make my proof more easy to contemplate. I tried making my proof as rigorous as possible. My proof goes like this:
We were given a subset of $\Bbb N.$ We call this subset $A.$
If $A$ is either empty or finite, then $A$ is countable, indeed, as all empty sets and finite sets are countable. Now, we consider the more interesting case, when $A$ is not finite, i.e infinite.
If $A$ is not finite then we must prove that, there exists a bijection, $f:\Bbb N\to A$ such that we can conclude, $A$ to countably infinite and hence, $A$ is then countable. Now, we try constructing the bijective mapping $f:\Bbb N\to A.$
We define $f(1)$ to be the smallest element in $A.$
[ We can guarantee the existence of the smallest element of $A,$ from the Well-ordering Property of $\Bbb N$ which states that : " Every non-empty subset of $\Bbb N$ contains a least element."]
Then, we proceed to define $f(2)$ as the 2nd smallest element in $A.$ In other words, we define $f(2)$ as the smallest element in the set $A-\{f(1)\}.$ Similarly, we define $f(3)$ as the 3rd smallest element in the set $A$. This can stated more precisely by saying , that $f(3)$ is defined to be the smallest element of the set $A-\{f(1),f(2)\}.$ Continuing like this, we define $f(k)$ as the smallest element of $A-\{f(1),f(2)\},...,f(k-1)\}.$ Now, from this, it becomes obvious, that $f$ is an injective mapping and $f$ is truly, a well-defined mapping. So, what remains to prove is the fact that $f$ must indeed be a surjection.
We consider any element $a\in A.$ If, $a$ is the least element of $f$ then, according to the definition of $f$, we have, $f(1)=a,$ and we are done. Now, we consider the case when $a$ is not the least element of $A.$ Then, $a$ must be the $mth$ smallest element of $A,$ for some natural number $m$ ( as, $A$ is a subset of $\Bbb N$). Then, by the definition of the function $f$ we can easily conclude, that $f(m)=a.$ This proves, that $f$ is a surjection as well.
Thus, we can say, that $f:\Bbb N\to\Bbb A$ is a bijective mapping.
Hence, we prove that if $A$ is any arbitrary subset of $\Bbb N$ then $A$ is either empty or finite or countably infinite, which implies that $A$ is a countable set. This, completes the proof as well.
I think, the above proof although similar in some sense to the previous quoted proof, looks simpler than it( at least to me). Can my proof be considered an alternative proof? Also, the part, where I proved, $f$ is a surjective mapping is vastly different from the previous one. Can this be an alternate way, to prove that $f$ is a surjection ?
Yes, your proof works.
But just to give a complete argument, you can justify the statement "Then a must be the mth smallest element of A" further.
Indeed, consider $a \in A$. Consider the finite set $S_a = \{1,2,...,a\} \cap A$. This is a finite set. Then $a = f(m)$ where $m = |S_a|$.
This shows that $f$ is indeed a mapping of $\mathbb{N}$ onto $A$.