Prove the cardinality of $\mathbb{Z}$ and $\mathbb{N}$ is the same. Prove the cardinality of $\mathbb{Z}$ and $\mathbb{N}$ is the same.


For the cardinality to be the same, there must exists a bijective function $f:\mathbb{N}\mapsto\mathbb{Z}$. If there exists a bijective function, then there exists an inverse $g:\mathbb{Z}\mapsto\mathbb{N}$ of it.

Suppose there exists such function. Then if $n\in\mathbb{N}$ and $z\in\mathbb{Z}$,

\begin{align}
(g\circ f)(n)&amp;=n\\
g(f(n))&amp;=n\\
g(z)&amp;=n\\
f(g(z))&amp;=f(n)\\
z&amp;=f(n)\\
f(n)&amp;=f(n)\\
f(n)-f(n)&amp;=0\\
0&amp;=0
\end{align}

Clearly this is true, so there exists such bijective function. Which means $\mathbb{Z}$ and $\mathbb{N}$ have the same cardinality.



But I feel this is incorrect, because if instead of $\mathbb{Z}$ and $\mathbb{N}$ I have to prove the equality of the cardinalities of $\mathbb{Z}$ and $\mathbb{R}$, the conclusion would be the same, but clearly this is not true.
This appears to be your argument, boiled down to the essentials:

"If a bijection exists, then it follows that 0=0.  Clearly 0=0 is true.  Therefore a bijection must exist."

The problem is that this is NOT a valid argument.  This is an instance of a logical fallacy known as 'Affirming the Consequent'.
Suppose such bijective function $f:\mathbb{N}\mapsto\mathbb{Z}$ doesn't exist.

Let $z\in\mathbb{Z}$ and $n\in\mathbb{N}$.

Then $\forall f:\mathbb{Z}\mapsto\mathbb{N}:(\text{$f$ is not a injection $\lor$ $f$ is not a surjection})$. 

\begin{align}
\forall f:\mathbb{N}\mapsto\mathbb{Z}:(\text{$f$ is not a injection } \lor \text{$f$ is not a surjection})\\
\forall f:((\exists n_1,n_2:\lnot(f(n_1)=f(n_2)\implies n_1=n_2))\lor(\exists z:z\neq f(n))\\
\forall f:((\exists n_1,n_2:(f(n_1)=f(n_2)\land n_1\neq n_2))\lor(\exists z:z\neq f(n))\\
\end{align}

If this is false we are done.

Let $f:\mathbb{N}\mapsto\mathbb{Z}$ be arbitrary. We now need to show $(\exists n_1,n_2:(f(n_1)=f(n_2)\land n_1\neq n_2))\lor(\exists z:z\neq f(n))$.

If $\exists n_1,n_2:(f(n_1)=f(n_2)\land n_1\neq n_2)$ we have $n_1\neq n_2$ and applying $f$ to both sides:

$$f(n_1)\neq f(n_2)\tag{contradiction}$$

We concluded that $\exists n_1,n_2:(f(n_1)=f(n_2)\land n_1\neq n_2)$ must be false, so for the condition to be true $\exists z:z\neq f(n)$ must be true. So we need to find a function that takes a natural number as argument and maps it to the whole range of integers. Because we can construct a surjective function

$$
g(n)=\begin{cases}
n/2 &amp; \text{$n$ is even}\\
-(n-1)/2 &amp; \text{$n$ is odd}
\end{cases}
$$

that takes a natural number and can return every value of the integers the last statement is false, which means that supposing a bijective function $f$ does not exist has lead to a contradiction. Hence, a bijective function must exist. So the cardinality of $\mathbb{Z}$ and $\mathbb{N}$ must be the same.