Countability Definition

When is a set countable?

Definition: A set $A$ is countable if there exists an onto function $f:\mathbb N \to A$.

Do you see a problem with this definition?
What if $A$ is empty? Intuitively I would argue that there does not exist a function that maps a natural number to an empty thingy, but let’s prove it formally!

We need to have a formal definition of what constitutes a function.

  • Functions is a generalization of relations.
  • A relation $R$ from $X$ to $Y$ is a subset of $X\times Y$, i.e., $R\subseteq X\times Y$.
  • A function $f$ from $X$ to $Y$ is a relation that satisfies
    • For all $x\in X$, there exists a $y\in Y$ such that $(x,y)\in f$.
    • $(x,y_1)=(x,y_2)\implies y_1 = y_2$.

Formal Proof:
Let $A = \emptyset$. Assume for contradiction that there exists a function $f:\mathbb R \to A$.

  • $f$ is a function, then $f$ is a relation. Therefore, $f\subseteq \mathbb R\times A$.
  • Since $A = \emptyset$, $f\subseteq \mathbb R\times A = \mathbb R\times \emptyset = \emptyset$.
  • However, since $f$ is a function, for all $n\in\mathbb N$, there exists $a \in A$ such that $(n,a)\in f$.
  • Choose $n=0$. (Any other natural number also works.) Since $0\in\mathbb N$, there exists $a\in A$ such that $(0,a)\in f$.
  • However, $f \subseteq \emptyset \implies f = \emptyset$. $(0,a)\in f$ can never hold for any $a$. Hence, a contradiction.
  • Therefore, $f$ is not a function.

Now, let’s fix the definition of countability!
Definition: A set $A$ is countable if either $A$ is empty or there exists an onto function $f:\mathbb N \to A$.