"Proof" of $0=1$ in set theory

Question

Ok, so here is a proof of "$0 = 1$" I came up with today. You can do in set-theory, where natural numbers are defined in the usual way.

Proof: Let $\mathsf{Succ}$ be the function that takes any natural number and adds one to it. Then we have $\mathsf{Succ}(0) = 1$. The image of $\mathsf{Succ}$ on the empty set is of course empty; so we have $\mathsf{Succ}(\emptyset) = \emptyset$ and since by our definition of the natural numbers $0 = \emptyset$ this means $\mathsf{Succ}(0)= 0$. This gets us $0 = 1$ as desired. $\Box$

I think the mistake is subtle and I am interested to see what gets pointed out.

---

If you want a hint:

It abuses some conventional notation which leads to problems here.

Answer 1

For a function $f: A \to B$,

we use the notation $f(...)$ for two different things:

1. If $a\in A$, then $f(a)$ is the element of $B$ to which the element $a$ is mapped.
2. If $S\subseteq A$, then $f(S)$ is defined as $f(S)=\{f(s)|s\in S\}$.

---

You mix the two things up when you say that $\mathsf{Succ}(\emptyset)=\emptyset$. The statement is only true under interpretation (2) above, but you use it as if it was true under interpretation (1).

Under interpretation 1, $f(\emptyset) = \{\emptyset\}$.

---

To use unambiguous symbols, let's write functions as what they really are: relations.

Every function $f:A\to B$ is in fact a relation, i.e. a subset of $A\times B$, which satisfies the property that if $(a, b_1)\in f$ and $(a, b_2)\in f$, then $b_1=b_2$. The usual shorthand for $(a, b)\in f$ is $f(a)=b$, but in this case, the shorthand can cause confusion, so we will not use it.

We can still use the expression $f(S)$ for what it was before, so we can say that $f(S)=\{b| (a, b)\in f \land a\in S\}$.

OK, with these definitions, let's rewrite the "proof" and see the error jump out at us:

---

Proof: Let $\mathsf{Succ}$ be the function that takes any natural number and adds one to it. Then we have $(0, 1)\in \mathsf{Succ}$. The image of $\mathsf{Succ}$ on the empty set is of course empty; so we have $\mathsf{Succ}(\emptyset) = \emptyset$ and since by our definition of the natural numbers $0 = \emptyset$ this means $(0,0)\in \mathsf{Succ}$. This gets us $0 = 1$ as desired. $\Box$

The error in reasoning is clear now. The (true) statement $$\mathsf{Succ}(\emptyset)=\emptyset$$ is not the same as the (untrue) statement $$(\emptyset, \emptyset)\in\mathsf{Succ},$$ but in the final sentence, that's exactly what is assumed.