Advance warning: This is a post about a standard foundational construction in mathematics – constructing the integers from the natural numbers. It’s partly a prelude to another post, and I plan to do the details in slightly more generality than is normally done, but if you’re interested in this subject it’s probably nothing new and if it’s something new you’re probably not interested in this subject. Also a lot of this is going to be spelled out in way more detail than you’re likely to care about.
Second warning: I’m pretty sure my lecturer when he did this proof for me back more than a decade ago in my first year of my maths degree added the caveat “And now you should forget about this proof and never do it again”. So I’m going against the health advisory of a trained mathematician. Some maths contained herein may be hazardous to your health.
This post is about the following theorem:
Let G be a set with operations + and * such that they obey all the axioms of a ring except for the existence of additive inverses, but have the additional property that + cancels in the sense that if x + z = y + z then x = y.
There is a ring R and an isomorphic embedding \(f : G \to R\). Further, there is a unique (up to isomorphism) minimal such G.
First, let’s prove uniqueness, as it will motivate the construction.
Lemma: Suppose R is minimal. Then every element of R can be written as \(f(x) – f(y)\) for \(x, y \in G\).
Proof: We need only show that the set of such elements form a ring, then the result will follow by minimality.
It suffices to show that it’s closed under the ring operations, but this is just simple algebra:
\[-(f(x) – f(y)) = f(y) – f(x)\] \[(f(x) – f(y)) + (f(u) – f(v)) = f(x + u) – f(y + v)\] \[(f(x) – f(y)) * (f(u) – f(v)) = f(x * u + y * v) – f(x * v + y * u)\]
So this set is a subring of R containing f(G), so it must be R due to minimality. QED
As an aside, note that it is not necessarily the case that every element of R is f(x) or -f(x) for some \(x \in G\). Consider for example \(G = \{ x \in \mathbb{N} : x > 1 \}\).
Now suppose we have another minimal isomorphic embedding \(f’ : G \to R’\). We want to construct an isomorphism \(h : R \to R’\) such that \(h \cdot f = f’\). This will prove uniqueness.
We construct h as follows:
Let \(r = f(x) – f(y)\). Define \(h(r) = f'(x) – f'(y)\).
First we must show this is well defined.
Specifically we will show that if \(f(x) – f(y) = f(u) – f(v)\) then \(f'(x) – f'(y) = f'(u) – f'(v)\). This turns out to just be basic manipulation of the fact that \(f\) and \(f’\) are both isomorphic embeddings:
\[
\begin{aligned}
f(x) – f(y) &= f(u) – f(v) \\
f(x) + f(v) &= f(u) + f(y) \\
f(x + v) &= f(u + y) \\
x + v &= u + y \\
f'(x + v) &= f'(u + y) \\
f'(x) + f'(v) &= f'(u) + f'(y) \\
f'(x) – f'(y) &= f'(u) – f'(v) \\
\end{aligned}
\]
So as a result, \(h\) is well defined. Additionally, you can construct \(h’ : R’ \to R\) in exactly the same manner, and it’s clear by definition that \(h\) and \(h’\) are inverses, so \(h\) is a bijection.
If we pick \(b \in G\) then
\[
\begin{aligned}
h(f(x)) &= h(f(x + b) – f(b)) \\
&= f'(x + b) – f'(b) \\
&= f'(x) \\
\end{aligned}
\]
So we’ve proven that \(h(f(x)) = f'(x)\) and thus \(h \cdot f = f’\).
We still need to show that \(h\) is an isomorphism, but this follows simply from our formulae for \(+\) and \(*\) on things of the form \(f(x) – f(y)\): Each operation you can convert into operations in the original set, pass to \(f’\) and then convert back.
QED
This uniqueness proof nicely informs the construction too. Every element in our target ring is going to be the difference of two elements in our set. Therefore we construct the target ring as the set of differences. But of course two differences might result in the same element, so we define an equivalence relation for when this should happen and quotient out by that.
So we will now construct our ring:
Let \(R = G^2 / \sim\), where \((x,y) \sim (u, v)\) if \(x + v = y + u\) (i.e. if \(x – y = u – v\)).
First we must show this is an equivalence relation. Reflexivity is obvious, symmetry follows from commutativity of addition. We only need to show transitivity.
We’ll need some notation: If \(a = (x, y)\), write \(x = a^+\) and \(y = a^-\).
(This will give us slightly fewer variables to keep track of).
Suppose \(a \sim b\) and \(b \sim c\).
Then
\[\begin{aligned}
a^+ + b^- &= a^- + b^+\\
b^+ + c^- &= b^- + c^+\\
a^+ + b^- + b^+ + c^- &= a^- + b^+ + b^- + c^+\\
a^+ + c^- + (b^- + b^)&= a^- + c^+ + (b^- + b^)\\
a^+ + c^- &= a^- + c^+ \\
a &\sim c \\
\end{aligned}\]
(note we had to use the cancellation property for + here)
Fix \(b \in G\) and define \(f : G \to R\) as \(f(x) = [(x + b, b)] \). (We’re not guaranteed a 0 element in G, which is why we can’t just map it to \([(x, 0)]\)).
We will now prove that \(R\) is a ring and \(f\) an isomorphic embedding into it.
First note that f does not depend on the choice of b.
Proof: \((x + b, b) \sim (x + b’, b’)\) because \(x + b + b’ = x + b’ + b\).
Now note that f is injective: This is because of the cancellation property we required on addition: If \((x + b, b) \sim (y + b, b)\) then \(x + 2b = y + 2b\) and so by cancellation \(x = y\).
In order to show that it’s an isomorphic embedding we first need to construct a ring structure on R.
We’ll use our formulae from above. Define:
\[(x, y) + (u, v) = (x + u, y + v)\] \[(x,y) * (u, v) = (x * u + y * v, x * v + y * u)\]
We first need to show that these are compatible with the equivalence relation \(\sim\).
Now suppose \(a,b,c,d \in G^2\) with \(a \sim c\) and \(b \sim d\).
We first want to show that \(a + b \sim c + d\). i.e. that \((a + b)^+ + (c + d)^- = (a + b)^- + (c + d)^+\).
\[\begin{aligned}
(a + b)^+ + (c + d)^- &= a^+ + b^+ + c^- + d^-\\
&= (a^+ + c^-) + (b^+ + d^-)\\
&= (a^- + c^+) + (b^- + d^+)\\
&= (c^+ + d^+) + (a^- + b^-) \\
&= (c + d)^+ + (a + b)^- \\
&= (a + b)^- + (c + d)^+ \\
\end{aligned}\]
So \(+\) is compatible with the equivalence relation, and thus can be inherited by \(R\).
We now have to do the same with \(*\). To simplify the calculation we’ll show that \(a * b \sim a * d\). The proof that \(a * d \sim c * d\) will be identical, and the whole result will follow from transitivity.
So
\[\begin{aligned}
(a * b)^+ + (a * d)^- &= a^+ * b^+ + a^- * b^- + a^+ * d^- + a^- * d^+ \\
&= a^+ * ( b^+ + d^-) + a^- * (b^- + d^+) \\
&= a^+ * ( b^- + d^+) + a^- * (b^+ + d^-) \\
&= a^+ * b^- + a^- * b^+ + a^+ * d^+ + a^- * d^- \\
&= (a * b)^- + (a * d)^+ \\
a * b &\sim a * d \\
\end{aligned}\]
So the operations are well defined on the equivalence classes.
Now all we have to do is show that they satisfy the ring operations. Ideally without losing the will to live.
It’s obvious by construction that + is commutative and associative (because it is on \(G\)).
The equivalence class \(0 = [(x, x)]\) is a unit for + (it should be evident that every choice of x produces an equivalent element because \(x + y = x + y\)).
Proof: Let \(a \in G^2\) and \(b = (x, x)\).
\[\begin{aligned}
(a + b)^+ + a^- &= a^+ + b^+ + a^- \\
&= a^+ + b^- + a^- \\
&= a^+ + (a + b)^- \\
a + b &\sim a \\
\end{aligned}\]
Negations exist because \(a + (a^-, a^+) = (a^+ + a^-, a^+ + a^-) \sim 0\).
So now we just have to prove that * is associative and distributes over +.
Associative:
\[\begin{aligned}
((a * b) * c)^+ &= (a * b)^+ * c^+ + (a * b)^- * c^- \\
&= a^+ * b^+ * c^+ + a^- * b^- * c^+ + a^- * b^+* c^- + a^+ * b^- * c^-\\
(a * (b * c))^+ &= a^+ * (b * c)^+ + a^- * (b * c)^- \\
&= a^+ * (b * c)^+ + a^- * (b * c)^- \\
&= a^+ * b^+ * c^+ + a^- * b^- * c^+ + a^- * b^+ * c^- + a^- * b^- * c^+ \\
&= ((a * b) * c)^+ \\
\end{aligned}\]
At this point I’m prepared to accept on faith that the negative half works out the same way. Are you? Good.
Distributive (just going to show left distributive. Right should follow similarly):
\[\begin{aligned}
(a * (b + c))^+ &= a^+ * (b + c)^+ + a^- * (b + c)^- \\
&= a^+ * b^+ + a^+ * c^+ + a^- * b^- + a^- * c^- \\
&= (a^+ * b^+ + a^- * b^-) + (a^+ * c^+ + a^- * c^- )) \\
& = (a * b)^+ + (a * c)^+ \\
(a * (b + c))^- &= a^+ * (b + c)^- + a^- * (b + c)^+ \\
&= a^+ * b^- + c^- + a^- * b^+ + a^- * c^+ \\
\end{aligned}\]
Which means we’re done. Phew. That was a lot of work.
Unfortunately, now on to the next lot of work!
Several things more to prove:
Theorem:
If G has a multiplicative unit, which we’ll call 1, then \(f(1)\) is a multiplicative unit for \(R\).
Proof:
\[\begin{aligned}
(x, y) * (1 + b, b) &= (x + x * b + y * b, x * b + y + y * b) \\
&= (x + (x * b + y * b), y + (x * b + y * b))\\
&\sim (x, y) \\
\end{aligned}\]
(Using the fact that (\(x + c, y + c) \sim (x, y) \)).
Theorem:
If \(*\) is commutative on \(G\) then it is commutative on \(R\).
Proof: Follows almost directly from how \(*\) on \(R\) is defined in terms of \(*\) on \(G\).
Ok. Now we’re done.
We apply this construction to \(\mathbb{N}\), and we get \(\mathbb{Z}\): The minimal commutative ring with a 1 that N embeds isomorphically into.
Time to relax.