1
$\begingroup$

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:

enter image description here

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

enter image description here

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

$\endgroup$
  • 2
    $\begingroup$ Can you give a specific example where of (1.),(2.) [of "Theorem"] one is true but the other is false? $\endgroup$ – coffeemath May 27 '18 at 7:08
  • $\begingroup$ They're all correct. There are many questions on this site which deal with the various ways to define countable sets, and I'm sure that if you put some energy into searching, you could find all the answers you're looking for. $\endgroup$ – Asaf Karagila May 27 '18 at 7:31
  • $\begingroup$ @AsafKaragila I have already put energy in searching. But it seems that I am a bit confused. I have came across these questions: 1, 2. But they talk about how surjectivity implies injectivity in the case of finite sets of equal sizes, which I understand. I have doubt in case of infinite sets. Can you please have a look at my comments (explaining my doubt) on all three answers on this question? $\endgroup$ – anir May 27 '18 at 12:32
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Help me understand proving $(1)\implies(2)$. We assume $f:S\rightarrow \Bbb N$ is injective. But injectivity does not means that there does not exist $n_i$ such that there does not exist $s_i$ for which $f(s_i)=n_i$. That is even though $f$ is injective, there can exist $n_i$ which is not mapped to any $s_i$ by $f$. For example, here (red boxed example) on wikipedia, we have injective $f:X\rightarrow Y$, but $g:Y \rightarrow X$ is not surjective, since $C$ in $Y$ is not mapped to any element in $X$. So injective $f$ does not imply surjective $g$, right? $\endgroup$ – anir May 27 '18 at 12:20
  • $\begingroup$ In 2nd paragraph, do you mean if $S=\emptyset$ instead of $D=\emptyset$? $\endgroup$ – anir May 28 '18 at 19:27
  • $\begingroup$ I will honestly love if you can explain $(2)\implies(3)$ with some other words or perhaps with example. I am really not able to get it. :( $\endgroup$ – anir May 29 '18 at 4:46
0
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ In (1), you said "Since $f$ is surjective, each $s∈S$ can be found in such a way"(i.e. $f(n)=s$). Really? Because, in this diagram-1, we cannot have any $n_i$ such that $f(n_i)=s_4$. Note that Also, you said "...contradicting $s≠t$". Why it should contradict? I guess, surjection allows $f(n_2)=\{s_2,s_3\}$ as in diagram-1, right? Thats how wikipedia page also gives example of surjection without injection. Also, diagram-1 is surjection without implying injection. I am thoroughly confused. Please help!!! :( $\endgroup$ – anir May 27 '18 at 10:08
  • $\begingroup$ In that diagram, $f$ is not even a function from $\mathbb N$ to $S$, since it would map $n_2$ to both $s_2$ and $s_3$, and functions have unique outputs. Moreover, even if $f$ were a function, you are completely correct that there is no $n_i$ so that $f(n_i)=s_4$, but by definition that means $f$ is not surjective. The function $g$ in that diagram is surjective, but it is going the wrong direction as far as your theorem is concerned, from $S$ to $\mathbb N$. $\endgroup$ – Hans Musgrave May 27 '18 at 13:18
  • $\begingroup$ Contradicting $s\neq t$: Because if $f(n)=s$ and $f(n)=t$, that means that $s=t$. Equality is transitive. Just like if $x=5$ and $y=5$ then $x=y$. This is no different, except for the value in common is a little more abstract and written as $f(n)$. Then the contradiction is that we have both $s=t$ and $s\neq t$. $\endgroup$ – Hans Musgrave May 27 '18 at 13:20
  • $\begingroup$ The wikipedia page can absolutely give a surjection without an injection (and vice versa). The key point is that the surjection and injection are not the same functions, or at least they don't have to be. They don't even go the same direction. The surjection is from $\mathbb N$ to $S$, and the injection goes from $S$ to $\mathbb N$. In that wikipedia example, there is an injection going the other direction. Define $g(D)=1$, $g(B)=2$, and $g(C)=3$. Alternatively you could use $h(D)=1$, $h(B)=2$, and $h(C)=4$. $\endgroup$ – Hans Musgrave May 27 '18 at 13:24
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Consider this red boxed example on wikipedia page. We have injective function $f:Y\rightarrow X$. Also we have $Y_3\cap Y_4=C\neq\emptyset$. So $g:X\rightarrow Y$ is not injective. Right? $\endgroup$ – anir May 27 '18 at 12:28
  • $\begingroup$ If there exists $f: X\to Y$ surjective then there exitst $g: Y\to X$ injective. However, if there exists $f: X\to Y$ injective, there not necessary exists $g: Y\to X$ injective. $\endgroup$ – Chuong Nguyen May 27 '18 at 18:09
  • $\begingroup$ In second statement, do you mean if there exists $f:X\rightarrow Y$ injective, there not necessary exist $g:Y\rightarrow X$ $ \color{red}{ surjective}$ ? $\endgroup$ – anir May 27 '18 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.