# 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$.