$A$ is a countable set if and only if exist a injective function $h: A \to \mathbb{N} $

I have the second implication: we know that $\mathbb{N}$ is countable then exist a injective function such that $h: A \to \mathbb{N}$ then $A$ is countable. But for first implication I don't know what I can do. I try with inverse function but, with my definition of countable set ($A$ is countable set if exist a surjective function $f: \mathbb{N} \rightarrow A$) and with composition I can't have the correct answer.

  • 2
    $\begingroup$ The function $f$ may not be invertible. However you can use it to define an injection from $A$ into $\mathbb{N}$ by mapping each element $a$ in $A$ to some element of the preimage $f^{-1}(\{a\})$. If you wish to avoid using the axiom of choice you can use the fact that $\mathbb{N}$ is well-ordered. $\endgroup$ – John Griffin Sep 30 '17 at 5:37
  • $\begingroup$ (1). I can never tell which implication in an iff is supposed to be the first. Please re-word this. I can answer but I dk what part you have difficulty with. (2). Countable means not uncountable . Countable means "finite or countably infinite". $\endgroup$ – DanielWainfleet Sep 30 '17 at 5:44
  • $\begingroup$ Counterexample: There is an injective function $h:\emptyset\to\mathbb N$ but $\emptyset$ is not countable by your definition, there is no surjective function $f:\mathbb N\to\emptyset.$ $\endgroup$ – bof Sep 30 '17 at 7:47

Suppose $A \neq \varnothing$ is countable. So there is $f: \mathbb{N} \to A$ surjective (your definition). To each $a \in A$, $f^{-1}(\{a\}) \neq \varnothing$, let $h(a) = \min f^{-1} (\{a\}) \in \mathbb{N}$ (because $\mathbb{N}$ is well ordered). Define $h: A \to \mathbb{N}: a \mapsto h(a)$.

Note, $$(f\circ h)(a) = f(h(a)) = f(\min f^{-1} (\{a\})) = a $$, then $h$ is injective.

  • $\begingroup$ Note, nor $f$ neither $h$ are bijective functions (in general). They are only "inverse" on one side and not on the other . $\endgroup$ – Thadeu Henrique Costa Sep 30 '17 at 5:50

Thadeu Henrique Costa gave a succinct response, but for educational purposes it seems worthwhile to provide more material and another angle to the method.

The student should study

Injection iff Left Inverse

and to round out the course,

Surjection iff Right Inverse.

We can avoid this theory for the OP's question, using, for instructional purposes, a direct approach:

By the Well ordering principle, every nonempty subset of $\mathbb{N}$ has a least element. So there is a function

$\tag 1 \mathcal M: \mathcal{P}^{*}(\mathbb{N}) \to \mathbb{N}$

mapping any nonempty subset of $\mathbb{N}$ to the smallest number of that set.

Exercise 1: Let $J$ and $K$ be two nonempty subsets of $\mathbb{N}$. Then

$\tag 2 J \cap K = \emptyset \; \Rightarrow \; \mathcal M(J) \ne \mathcal M(K)$

Now we can use the surjective $f$ enumeration to define another function

$\tag 3 \bar {f}^{-1}: A \to \mathcal{P}^{*}(\mathbb{N})$


$\tag 4 a \mapsto \{n \in \mathbb{N} \; | \; f(n) = a \} \ne \emptyset$

Exercise 2: Show that $\bar {f}^{-1}$ maps two different elements in $A$ to two disjoint subsets of $\mathbb{N}$. In particular, $\bar {f}^{-1}$ is an injective function.

We know that the composition of two injective functions in an injective function. Now $\mathcal M$ is not an injective function, but by both exercise 1 & 2, it is injective on the image set $\bar {f}^{-1}(A)$ in $\mathcal{P}^{*}(\mathbb{N})$.

The answer to the OP's question is that $\mathcal M \circ \bar {f}^{-1}$ is an injective function from $A$ to $\mathbb{N}$. The OP should be able to easily check that this function is exactly the same as the function $h$ defined by Thadeu Henrique Costa.


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.