Operations and Closure

A set on its own is just a collection. What makes a set interesting for arithmetic is that you can take two of its elements and combine them to get a third element. Combining two things to get one thing is called an operation. This note is about operations, the idea of "staying inside" the set, and why "staying inside" is the property we will care about most.

01.Adding two integers

The most familiar operation is addition. Take two integers, say $3$ and $5$. Add them. You get $8$. Both $3$ and $5$ are integers, and so is $8$, the result.

Notice that addition on $\mathbb{Z}$ has a nice feature: no matter which two integers you start with, the answer is again an integer. Pick $7$ and $-12$: their sum is $-5$, an integer. Pick $0$ and $0$: their sum is $0$, an integer. There is no pair of integers whose sum is somehow not an integer. Once you are working inside $\mathbb{Z}$, addition keeps you there.

The same goes for multiplication on $\mathbb{Z}$: $3 \cdot 5 = 15$, $-7 \cdot 4 = -28$, $0 \cdot 100 = 0$. Always an integer.

Now try subtraction on the natural numbers $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$. Take $3$ and $5$, both naturals. Subtract: $3 - 5 = -2$. The answer is not in $\mathbb{N}$, because negative numbers are not natural numbers. Subtraction "leaks" out of $\mathbb{N}$.

Try division on the integers $\mathbb{Z}$. Take $1$ and $2$, both integers. Divide: $1 / 2$. The answer is not an integer. Division leaks out of $\mathbb{Z}$.

That little contrast (addition keeping you inside $\mathbb{Z}$ vs. subtraction leaking out of $\mathbb{N}$) is the whole motivation for the word closure.

02.Binary operations, formally

A binary operation on a set $S$ is a rule that takes two elements of $S$ and returns one element of $S$. The word "binary" means "takes two inputs". The word "operation" is just a fancy word for "rule".

Formally, a binary operation $*$ on $S$ is a function

$$* : S \times S \to S$$

that takes a pair $(a, b)$ with $a, b \in S$ and produces a single output, written $a * b$, that is also in $S$.

The set $S \times S$, called the Cartesian product, is the set of all ordered pairs of elements of $S$. So $\mathbb{Z} \times \mathbb{Z}$ is the set of all pairs $(a, b)$ where both $a$ and $b$ are integers.

The crucial part of the definition is the codomain: the function $*$ is required to land in $S$. If you put two elements of $S$ in, you get one element of $S$ out. Always.

Given that strict requirement, addition is a binary operation on $\mathbb{Z}$, and so is multiplication. But subtraction is not a binary operation on $\mathbb{N}$, because $3 - 5 = -2$ does not land in $\mathbb{N}$. Subtraction would only qualify on a set that contained the negatives, like $\mathbb{Z}$.

When an operation does land back in the set every time, we say the set is closed under that operation. Closure is the precise way to say "stays inside".

03.A worked check for closure

Let us verify, line by line, that addition is closed on $\mathbb{Z}$.

The claim: for every $a \in \mathbb{Z}$ and every $b \in \mathbb{Z}$, the value $a + b$ is in $\mathbb{Z}$.

The cases break into four, depending on the signs:

1. If $a \ge 0$ and $b \ge 0$, then $a + b \ge 0$, and $a + b$ is a natural number, so it is an integer.
2. If $a \ge 0$ and $b < 0$, the sum $a + b$ is the integer obtained by counting down $|b|$ steps from $a$. Either you stay non-negative or you cross zero into the negatives. Either way, the answer is in $\mathbb{Z}$.
3. If $a < 0$ and $b \ge 0$, mirror of case 2.
4. If $a < 0$ and $b < 0$, then $a + b$ is more negative than either of them, and is in the negative integers, so in $\mathbb{Z}$.

That covers all pairs, so addition is closed on $\mathbb{Z}$. The same kind of case analysis works for multiplication.

For subtraction on $\mathbb{N}$, the counter-example $3 - 5 = -2 \notin \mathbb{N}$ is enough. To say "this operation is not closed on this set", you only need one counter-example. To say "this operation is closed", you have to handle every possible pair, which is what we just did for $\mathbb{Z}$.

04.Why we care about closure

Closure is the property that lets you keep working without leaving the world you started in. If you are designing a piece of cryptographic hardware that handles 16-bit unsigned integers, you would like the operations you do (addition, multiplication, modular reduction) to stay inside the 16-bit range. If they leak out, you have a bug or you need a wider data type.

In the abstract language of this chapter, closure is the very first property a set needs in order to be a group, ring, or field. Those names come up in the next note. Each of them is a set together with one or two binary operations, and one of the first conditions every definition will demand is closure under those operations. Without closure, the rest of the structure cannot get off the ground.

05.Properties beyond closure

Closure is the floor, not the ceiling. Real arithmetic obeys a few more laws that you have known since elementary school but never named.

Associativity is the law that says it does not matter how you group the operands. For addition: $(a + b) + c = a + (b + c)$. For multiplication: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$. Subtraction is not associative: $(8 - 3) - 2 = 3$, but $8 - (3 - 2) = 7$. Two different answers.

Commutativity is the law that says the order of the two inputs does not matter. For addition: $a + b = b + a$. For multiplication: $a \cdot b = b \cdot a$. Subtraction is not commutative: $8 - 3 \neq 3 - 8$.

An identity element for an operation is an element $e$ that does nothing when combined with anything else. For addition on $\mathbb{Z}$, the identity is $0$, because $a + 0 = a$ for every $a$. For multiplication on $\mathbb{Z}$, the identity is $1$, because $a \cdot 1 = a$. Some operations have an identity and some do not.

An inverse of an element $a$, with respect to an operation that has an identity $e$, is an element $a'$ that combines with $a$ to give $e$. For addition, the inverse of $a$ is $-a$, because $a + (-a) = 0$. For multiplication on $\mathbb{Q}$ (not on $\mathbb{Z}$), the inverse of $a$ (assuming $a \neq 0$) is $1/a$, because $a \cdot (1/a) = 1$. The integer $5$ does not have a multiplicative inverse inside $\mathbb{Z}$, since $1/5$ is not an integer, but $5$ does have an inverse in $\mathbb{Q}$.

These four ideas (closure, associativity, commutativity, identities, inverses) show up again and again. They are the building blocks of the formal definitions in the next note.

06.A small exercise to check yourself

Consider the set $S = \{0, 1\}$ with the operation $+$ defined as ordinary integer addition.

• Is $S$ closed under $+$? Compute $1 + 1 = 2$. The result is not in $S$. So $S$ is not closed under ordinary addition.

Now redefine $+$ on $S$ by the rule "take the ordinary sum, then keep only the last bit", so $1 + 1 = 0$ and $0 + 0 = 0$ and $0 + 1 = 1$ and $1 + 0 = 1$.

• Is $S$ closed under this new $+$? Yes, every output is $0$ or $1$.
• Is the new $+$ commutative? Yes, addition does not see the order.
• Is there an identity? Yes, $0 + a = a$ for every $a \in S$.
• Does every element have an inverse? Yes, $0$ is its own inverse, and $1$ is its own inverse since $1 + 1 = 0$.

What you have just constructed, by tweaking ordinary addition to stay inside $\{0, 1\}$, is the simplest non-trivial example of modular arithmetic. The trick of "take the result, then reduce modulo $2$" is exactly what we are about to study in detail. Before that, the next note introduces the named structures (groups, rings, fields) that this modulo-$2$ system will turn out to be an example of.