Evaluating correctness of various definitions of countable sets

Question

I was trying to understand the definition of countable set (again!!!). Wikipedia has a very great explanation:

1. A set $S$ is countable if there exists an $\color{red}{\text{injective}}$ function $f$ from $S$ to the natural numbers $\mathbb N$.
2. If such an $f$ can be found that is also $\color{red}{\text{surjective}}$ (and therefore bijective), then $S$ is called countably infinite.
3. In other words, a set is countably infinite if it has $\color{red}{\text{bijection}}$ with the $\mathbb N$.

So I summarize:

1. $S$ is countable iff $S\xrightarrow{injection}\mathbb N$
2. $S$ is countably infinite iff $S\xrightarrow{bijection}\mathbb N$

But then wikipedia confuses by stating following points:

Theorem: Let $S$ be a set. The following statements are equivalent:

1. $S$ is countable, i.e. there exists an injective function $f : S → \mathbb N$.
2. Either $S$ is empty or there exists a surjective function $g : \mathbb N → S$.
3. Either $S$ is finite or there exists a bijection $h : \mathbb N → S$.

Q1. I feel 2nd statement is wrong, as it allows some element in $S$ to not to map to any element in $\mathbb N$. That is $\mathbb N \xrightarrow{surjection} S$ does not imply $S\xrightarrow{injection}\mathbb N$. Hence $S$ is not countable. Right?
Q2. 3rd statement defines countably infinite set, so its countable also. Right?
Q3. Also I dont get if the extra restrictions of emptyness and finiteness in statements 2 and 3 are required.

Wikipedia further says:

Corollary: Let $S$ and $T$ be sets.

1. If the function $f : S → T$ is injective and $T$ is countable then $S$ is countable.
2. If the function $g : S → T$ is surjective and $S$ is countable then $T$ is countable.

Q4. Here, too, I feel 2nd statement is incorrect for the same reason as 2nd statement in the theorem. Right?

Edit

I dont know if its correct to add this edit. But its the source of my confusion. So adding it anyway. All answers on this post go on explaining how sujectivity and injectivity imply each other and hence bijectivity. But does that means, whenever injective $f:X\rightarrow Y$ exists, there also holds surjective $g:Y\rightarrow X$ (and also a bijective)? I dont feel so, as the wikipedia gives examples of injective $f:X\rightarrow Y$, for which $g:Y\rightarrow X$ is not surjective:

On the same page, it gives example of surjective $g:Y\rightarrow X$, for which $f:X\rightarrow Y$ is not injective:

How can I reconcile these facts with given answers? I must be missing something very basic!!!

Answer 1

1. In fact, $f:\mathbb N \xrightarrow{surjection} S$ does imply $g:S\xrightarrow{injection} \mathbb N$. Since $f$ is a function, for each $n\in\mathbb N$ there exists a unique $s\in S$ so that $f(n)=s$. Since $f$ is surjective, each $s\in S$ can be found in such a way. To define $g$, for each $s\in S$ choose some $n\in\mathbb N$ so that $f(n)=s$. Define $g(s)=n$. This function must be injective, since if it weren't then two distinct $s,t$ would map to the same natural $n$. By construction, $f(n)=s$ and $f(n)=t$, contradicting $s\neq t$.

2. The third statement doesn't quite define a countable set. In the one case, if there is a bijection, yes that agrees with your definition of a countable set. In the other, a very small amount of work needs to be done to show that there is an injection from any finite set into the naturals. This isn't quite included in your definition.

3. $S$ being empty needs to be treated as a special case because functions need outputs. If $S$ is empty, no such function $g$ can be defined. In your other point, finiteness is also required since all finite sets are countable by your definition (Order them as $x_1,\dots,x_n$ and define $f(x_i)=i$. The details can be handled with induction.), but no finite set has a bijection with $\mathbb N$, so they have to be handled as a special case.

4. Once this is dealt with in the theorem, it is dealt with here as well. Injectivity and surjectivity can be flipped when the order of the sets is flipped as well. Another way of thinking about this is that once the theorem is proven true, as hard as it might be to accept the corollary it must be true as well since it is such a small leap from the theorem itself.

Answer 2

There is nothing wrong with the theorem, and the three statements are indeed equivalent. My suggestion: Read the proof of that theorem carefully and you will understand. In fact,

Claim: Suppose there exists $f$ such that $f: A\to B$ is surjective, then there exists $g: B\to A$ such that $g$ is injective.

Here is how to construct $g$. For each $x\in B$, let $A_x=f^{-1}(x)$. Then $A_x \neq \emptyset$ since $f$ is surjective. In addition, $A_x\cap A_y=\emptyset$ since $f$ is a function. Thus, for each $x\in B$ pick an element in $A_x$ and define $g(x)$ to be that element. Then clearly, $g$ is injective.

One more thing, you can search for Schröder-Bernstein theorem. Actually, here you are https://en.wikipedia.org/wiki/Schröder–Bernstein_theorem

Answer 3

Doubts about the truth of a statement should all go overboard in the light of a proof. A proof for the equivalence between three statements is typically done by showing (1)$\implies$(2)$\implies$(3)$\implies$(1).

(1)$\implies$(2): Assume there exists an injective map $f\colon S\to\Bbb N$. we want to show that $S=\emptyset$ or there exists a surjective map $g\colon \Bbb N\to S$. If $D=\emptyset$, we are done, hence we may assume $S\ne \emptyset$ and pick an element $s_0\in S$. (Note that we could not pick $s_0$ if $S$ were empty). We define $g\colon \Bbb N\to S$ as follows $$ g(n)=\begin{cases}s&\text{if }f(s)=n\text{ for some }s\in S\\s_0&\text{otherwise}\end{cases}$$ Note that in the upper branch, $s$ is uniquely determined by injectivity of $f$. Also, $g$ is surjective because for $s\in S$, we fid that $g(f(s))=s$.

(2)$\implies$(3): Assume $S$ is empty or there exists a surjective map $g\colon \Bbb N\to S$. We want to show that $S$ is finite or there exists a bijection $h\colon \Bbb N\to S$. If $S$ is finite, we are done. Hence assume $S$ is infinite. In particular, $S\ne\emptyset$, hence there exists a surjection $g\colon \Bbb N\to S$. We define $h$ recursively as follows: Assume we have already defined $h(k)$ for all $k<n$. Let $m=m(n)$ be minimal with $g(m)\notin \{\,h(k)\mid k<n\,\}$. Such $m$ exists becasue the set on the right hand side is finite, so certainly not all of $S$, and $g$ is surjective. Then define $h(n)=g(m)$. The map $h\colon\Bbb N\to S$ defined this way is injective because $h(a)=h(b)$ with $b>a$ implies by construction that $h(b)\ne h(a)$. $h$ is also onto: By induction (using the recursion for $h$), one readily shows that for all $n\in\Bbb N$ there exists $k\le n$ with $h(k)=g(n)$. Indeed, If $g(n)\notin \{\,h(k)\mid k<n\,\}$ for some $n$, then the $m$ we pick at that stage is $\le n$. It we had $m<n$, this would mean $g(m)\notin \{\,h(k)\mid k\le m\,\}\subseteq \{\,h(k)\mid k<n\,\}$, contradicting the induction hypothesis. Using this, $h$ is onto because $g$ is.

(3)$\implies$(1): Assume $S$ is finite or there exists a bijection $h\colon S\to \Bbb N$. We want to show that there exists an injection $f\colon S\to \Bbb N$. If the bijection $h$ exists, it is at the same time injective, we can take $f=h$ and are done. Remains the case that $S$ is finite, and we have to show that then there exists an injective map $S\to\Bbb N$. This is left as an exercise. (If at this point we did not know that $S$ is finite, this exercise would fail).