Equality in $\mathbb{Z}$ versus equality in $\mathbb{Q}$

Question

I'm trying to rigorously understand a piece of a proof which involves the distinction between equality in $\mathbb{Z}$ and equality in $\mathbb{Q}$. To make this concrete, let $E$ denote the set of even natural numbers (I'll exclude $0$ for the moment) and define $f: \mathbb{N} \to E$ by $f(n) = 2n$. In an attempt to prove this map is injective, I would assume that $f(n) = f(m)$ for $n,m \in \mathbb{N}$. Then $2n = 2m$. I want to conclude that $n = m$ "by algebra," which would take the form of multiplying by $\frac{1}{2}$ and cancelling. My problem is: the "universe of discourse" here is the natural numbers, rather than the rational numbers. I think I could also say $2n = 2m$ implies $2n - 2m = 2(n-m) = 0$, and because $\mathbb{Z}$ lacks any zero divisors and $2 \neq 0$, we must have $n-m=0$. However, I think there is a way to justify the above algebra that I'm not seeing.

I'd appreciate any help in parsing this.

Answer 1

Working entirely in the naturals, you need:

Lemma 1: If $x,y,z$ are natural numbers with $x+y=x+z,$ then $y=z.$

Lemma 2: If $a$ is natural with $a\neq 0,$ then $a=b+1$ for some natural number $b.$

Lemma 3: If $m,n$ are natural with $m\neq n,$ then there exists a non-zero natural $a$ such that either $m=n+a$ or $n=m+a.$

You also need the axiom that $0$ is not the successor of a natural number.

Now, assume $2m=2n.$ If $m\neq n,$ then find $a\neq 0$ as in Lemma $3.$

We'll assume $m=n+a.$ The other case is similar.

Then $$2n+0=2n=2m=2(n+a)=2n+2a$$ and hence, by Lemma $(1),$ $0=2a.$ But since $a\neq 0,$ by Lemma 2, we can find $b$ such that $a=b+1.$ Then $$0=2(b+1)=(2b+1)+1,$$ with makes $0$ the successor of a natural number. Contradiction.

So $m=n.$

---

The lemmas are proven by induction of varying degrees of complexity. $(3)$ is the hardest.

$(2)$ can be proven using one of the most comical induction proofs, if we rephrase it as:

For all natural $a,$ either $a=0$ or $a=b+1$ for some natural $b.$