Principles of Machine Mathematics (Part 2 of 3)

An Guide to Two's Complement from a Set Theoretical Perspective:

Part 2

Properties of Relations

Previously, we discussed the basics of set theory and relations. Here, we will consider some interesting properties of relations. Five fundamental properties of relations are listed below:

1. Reflexivity. A relation R is reflexive on a given set S if and only if, for every element x of the set S, the ordered pair <x,x> is in the relation R. For example, the identity relation contains every pair of the form (x,x); the identity relation on the letters of the alphabet would look like this: {<A,A>, <B,B>, <C,C>, ...}. Clearly, this relation is reflexive.
2. Irreflexivity. A relation is irreflexive on a set if and only if, for every element x in a set, <x,x> is NOT in the relation. The Rock, Paper, Scissors  the Rock, Paper, Scissors victory relation discussed in part 1 is irreflexive because no choice wins against itself; instead, a tie results if both players make the same choice. Curiously, it turns out that it is possible for a relation to be neither reflexive nor irreflexive. This is the case if some elements are related to themselves, and others are not.
3. Symmetry. A relation is reflexive if and only if, for every pair <x,y> in the relation, its reflection or mirror pair <y,x> is also in the relation. The identity relation described above is symmetric, because if we swap the elements in any given ordered pair in the relation, the mirrored ordered pair is the same, so it is still in the relation.
4. Antisymmetry. A relation R is antisymmetric on a given set S if and only if, for every pair of elements <x,y> which is both in the relation and also has its mirror pair <y,x> in the relation, x = y (x and y must be the same element). For example, the Rock, Paper, Scissors victory relation discussed in part 1 is antisymmetric. Since Paper beats Rock, Rock does not beat Paper. The identity relation is also antisymmetric, because no two distinct elements are related. It turns out that a relation can be both symmetric and antisymmetric!
5. Transitivity. A relation R is transitive on a set S if and only if for every subset of three (not necessarily distinct) elements {x,y,z} from S, if <x,y> is in R and <y,z> is in R, then <x,z> must also be in R. For example, the less-than sign is transitive; any number that is less than 10 is also less than 100 because 10 is less than 10. Conversely, Rock, Paper, Scissors is often called a "non-transitive game" because although Rock beats Scissors and Scissors beats Paper, Rock does not beat Paper (even though it beats something that beats Paper).

Thanks to Jordan Kodner for correcting me after I confused reflexivity and symmetry in this section.

Equivalence Relations

An equivalence relation is a special type of relation. Any relation which is reflexive, symmetric, and transitive is considered an equivalence relation. For example, the canonical equivalence relation is the identity relation R, where a pair of elements <x,y> is in R if and only if x = y. We discussed this relation above as an example for both reflexivity and symmetry, but it turns out that it is also transitive. If x = y and y = z, then x = z.

The identity relation is not, however, the only equivalence relation. In particular, there are two other relations that are of great interest to us when discussing two's complement. The first of these is the absolute value relation on the integers:

Represented by a formula:

Represented by an infinite set of ordered pairs:

Verify for yourself that the absolute value relation is an equivalence relation because it is reflexive, symmetric, and transitive. An interesting property of equivalence relations is that the partition a set into a set of equivalence classes where every element in a particular equivalence class is equivalent with respect to that particular equivalence relation. For example, the partitioning induced on the integers by the absolute value relation is shown below, where each equivalence class is represented as a set nested inside the set of all such classes, which represents the partition:

Another type of equivalence relation of interest two us is a modular congruence relation. We say that x is congruent to y modulo z, or in mathematical notation:

This means that the remainder of x after division by z is the same as the remainder of y after division by z, which is sometimes represented by the notation:

A really simple example of this is the distinction between odd and even numbers. Odd and even numbers are the two congruence classes modulo 2; all even numbers have the same remainder (0) when divided by 2, and all odd numbers have the same remainder (1) when divided by 2.

Modular congruence relation are more complex and harder to represent in notation than the absolute value notation, so I will simply describe the modular congruence relation modulo 2 by noting that every even number is related to every other even number and every odd number is related to every other odd number, but no even number is related to any odd number, or vice versa.

Arithmetic Invariance

Invariance is a special property of equivalence relations that describes whether or not the equivalence of any two objects or elements is preserved after identical operations are performed on these "equivalent" elements. For example, the "right invariance" of equivalence relations on strings of characters is particularly useful in discussions about the regular languages. In this context, we're going to deal with a much simpler type of invariance: arithmetic invariance.

An equivalence relation is invariant with respect to a particular operation if and only if, for any two elements in the same equivalence class as each other, both of these elements remain in the same equivalence class as each other after application of the operation in question with the same arguments (if any). Note that the elements do not have to end in the same equivalence class that they started in; they just need to continue being equivalent to each other.

For example, the absolute value relation is invariant to multiplication by integers. The numbers 2 and -2 are equivalent with respect to absolute value, as are the numbers 6 and -6, which are the numbers produced by multiplying the first pair of numbers by 3.

Another way of depicting this is as follows:

However, the absolute value relation is NOT addition-invariant. Although -2 and 2 are equivalent, 5 and 1 do not have the same absolute value, so addition by 3 does not preserve the equivalence of the elements (the number 3 was chosen completely arbitrarily for sake of example in both cases).

Because the absolute value relation is not invariant to addition, it is not arithmetic invariant. Arithmetic invariance requires that an equivalence relation is invariant to all the basic arithmetic operations.

You may have learned the rules at some point that any two even numbers add up to an even number, any two odd numbers add up to an even number, any even number plus any odd number equals an even number, any even number times any even number is even, any even number times any odd number is even, and any odd number times any odd number produces an odd number. The validity of these rules shows that the modular equivalence relation modulo 2 is invariant to both addition and multiplication. In general, modular congruence relations are fully arithmetic invariant. This property will be extremely important in the next and final installment of this topic when we finally discuss the use of two's complement to store negative numbers on a computer.

TO BE CONTINUED...