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