Rings¶
Congratulations on getting this far — we are finally ready to introduce rings!
I will begin by reminding you of some properties that the real numbers have.
Firstly, \((\mathbb{R}, +)\) is an Abelian group, where the identity element is \(0\).
Secondly, \((\mathbb{R}, \times)\) — that is, the set \(\mathbb{R}\) together with multiplication — is a monoid, where the identity element is \(1\).
Thirdly, multiplication distributes over addition. What this means is that for all \(x, y, z \in \mathbb{R},\)
Now we will consider a different set: the set of truth-values \(\{T, F\}\), which from now on I will call \(\mathrm{Bool}\). I will first introduce a new operation on \(\mathrm{Bool}\) called exclusive-or or XOR for short, written \(\oplus\):
| \(P\) | \(Q\) | \(P \oplus Q\) |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
An easy way to remember this is that \(P \oplus Q\) is true if and only if \(P\) is different from \(Q\).
Firstly, \((\mathrm{Bool}, \oplus)\) is an Abelian group, with identity \(F\) (check this yourself if you want to).
Secondly, \((\mathrm{Bool}, \land)\) is a monoid, with identity \(T\) (we saw this monoid earlier on, in the monoids chapter).
Thirdly, \(\land\) distributes over \(\oplus\); that is, for all \(P, Q, R \in \mathrm{Bool},\)
I also encourage you to check this for yourself. Note that there are eight possibilities to consider, since we need to check that this works for any choice of \(P, Q,\) and \(R\).
The last example I will talk about before giving you the definition of a ring is \(\mathbb{Z}_3\), the set of integers modulo \(3\), which we saw in the previous chapter. Recall that \(\mathbb{Z}_3\) has three elements:
We saw in the previous chapter how to define an addition operation on \(\mathbb{Z}_3\) so that \((\mathbb{Z}_3, +)\) is an Abelian group, with identity \(\overline{0}\).
I will now reveal that we can define a multiplication operation in \(\mathbb{Z}_3\), which I will write as \(\cdot\), like this:
For example, \(\overline{1} \cdot \overline{2} = \overline{1 \times 2} = \overline{2}\), and \(\overline{2} \cdot \overline{2} = \overline{2 \times 2} = \overline{4} = \overline{1}\).
This makes \((\mathbb{Z}_3, \cdot)\) into a monoid, with identity \(\overline{1}\).
Finally, multiplication distributes over addition in \(\mathbb{Z}_3\) too; we sort of get this “for free” since we have defined multiplication and addition in terms of normal multiplication and addition in \(\mathbb{Z}\).
Putting all this together, we see that \(\mathbb{Z}_3\) is a ring. In fact, \(\mathbb{Z}_m\) is a ring for any positive integer \(m\), with multiplication defined in exactly the same way. So for example, in \(\mathbb{Z}_{12}\), we have \(\overline{5} \cdot \overline{6} = \overline{30} = \overline{6}\).
The definition¶
Now that you have seen some examples, I will give you the definition of a ring. A ring is a set \(R\) equipped with two binary operations \(+\) and \(\cdot\), called “addition” and “multiplication” respectively, such that the three following laws hold:
- \((R, +)\) is an Abelian group.
- \((R, \cdot)\) is a monoid.
- Multiplication distributes over addition. That is, for all \(x, y, z \in R,\)
From now on I will generally omit the \(\cdot\) symbol and represent multiplication by writing two symbols next to each other; that is, I will write \(xy\) to mean \(x \cdot y\).
We call the the identity element of the group \((R, +)\) the additive identity of the ring \(R\). The additive identity is written as \(0_R\) or just \(0\) when it’s clear from context which ring \(R\) we are talking about. Similarly, we call the identity element of the monoid \((R, \cdot)\) the multiplicative identity of the ring \(R\). The multiplicative identity is written as \(1_R\) or simply \(1\) when it’s clear which ring we are using.
Since \(R\) forms a group under addition, every element \(x \in R\) has an additive inverse, which we will write \(-x\). We also write \(x - y\) as a shorthand for \(x + (-y)\).
An important thing to note is that in a ring, multiplication need not be commutative! A ring in which the multiplication operation is commutative is called a commutative ring. So far, all the rings we have seen have commutative, but we will soon see some examples of non-commutative rings.
One last thing that I should mention quickly: just as there is a trivial monoid and a trivial group, there is a trivial ring with just one element, usually written \(\{0\}\). This ring is called the zero ring. It is not very interesting so we often rule it out by saying we a dealing with a “non-zero ring”; this phrase is nothing more than a shorthand for “any ring but the zero ring”.
Properties of rings¶
So I have just shown you three examples of rings: \(\mathbb{R}\), \(\mathrm{Bool}\), and \(\mathbb{Z}_m\). I will introduce a few more exotic examples of rings in subsequent chapters, but for now, we will establish a few properties which all rings have.
The first property is that \(\forall x \in R.\; 0x = 0\). That is, multiplying anything by \(0\) yields \(0\). We will prove this using just the ring laws, so that we know it is true for any ring.
Let \(R\) be a ring, and let \(x \in R\). Then:
- We know that \(0x = (0 + 0)x\), since \(0\) is the additive identity, and so anything is equal to itself plus \(0\).
- By the distributive law, \((0 + 0)x = 0x + 0x\).
- We now have that \(0x = 0x + 0x\). Because we know that \(R\) is a group under addition, we can subtract \(0x\) from both sides, yielding \(0 = 0x\), as required.
Another property which holds for all rings \(R\) is that \(\forall x, y \in R.\; (-x)y = -(xy)\). We can prove this too:
- By distributivity, we know that \(xy + (-x)y = (x + (-x))y.\)
- Since \(-x\) is the additive inverse of \(x\), we know that \((x + (-x))y = 0y.\)
- We proved a moment ago that \(\, 0y = 0.\)
- So \(\, xy + (-x)y = 0; \,\) subtracting \(xy\) from both sides yields \((-x)y = -(xy)\), as required.
Exercise 4.1. Let \(R\) be a ring. Prove that \((-x)(-y) = xy\) for all \(x, y \in R\). Maybe you will find this a satisfying explanation of why “a minus times a minus is a plus”!
Semirings¶
We might want to come up with a slightly weaker structure than a ring, in which we only require that \((R, +)\) is a commutative monoid rather than a group. Unfortunately, though, if we do this, our proof that anything times \(0\) is \(0\) will no longer work, because in the proof we used the fact that any ring forms a group under its addition operation.
Having multiplication by \(0\) always produce \(0\) is a useful property, though, so to make sure it still holds, we add it as an extra law. We then obtain the following:
A semiring is a set \(R\) equipped with two binary operations \(+\) and \(\cdot\), called “addition” and “multiplication” respectively, such that the three following laws hold:
- \((R, +)\) is a commutative monoid.
- \((R, \cdot)\) is a monoid.
- Multiplication distributes over addition. That is, for all \(x, y, z \in R,\)
- Anything multiplied by \(0\) is \(0\).
I won’t spend too much time talking about semirings in this guide, as most of the number systems you’re likely to be dealing with as a programmer have more structure. I’ll just give a couple of examples before we move on:
The natural example of a semiring is the natural numbers \(\mathbb{N}\); recall that \((\mathbb{N}, +)\) is a commutative monoid but not a group. Therefore, \(\mathbb{N}\) is a semiring but not a ring.
The simplest semiring which is not a ring is called the Boolean semiring. It has just two elements, \(0\) and \(1\), and it is defined by the equation \(1 + 1 = 1\). Note that we don’t need to specify the results of adding or multiplying any other elements, because the semiring laws already tell us what they will be. The Boolean semiring is different from the ring \(\mathrm{Bool}\) above; recall that in \(\mathrm{Bool}\), we have \(1 + 1 = 0\).