Equivalences and Orderings

There are a number of special kinds of relations that are ubiquitous in mathematics. We have already studied functions-as-relations. Now we will explore two other kinds of common relations:

1. The equivalence, which captures the notion of equality between objects in a universe
2. The ordering, which captures the notion of, literally just that, ordering between objects.

Equivalences

Like functions, equivalences are a refinement of relations. In particular, a relation that enjoys these three properties, reflexivity, symmetry, and transitivity, is considered an equivalence.

These three concepts form the definition of an equivalence relation.

The standard equality relation $(=)$ over the natural numbers $N$ is an equivalence relation as it fulfills all three properties of an equivalence:

Reflexive : Identical numbers are considered equal.

Symmetric : Order doesn't matter when asserting equality between numbers.

Transitive : When declaring $x=y$ and $y=z$, we know that these two facts establish that $x$ and $y$ are the same number and $z$ and $y$ are the same number. From this, we can conclude that $x$ and $z$ must also be the same number.

Reasoning About Equivalences

To formally show that a relation is an equivalence, we must show that it obeys the three properties of an equivalence: reflexivity, symmetry, and transitivity. We show the outline of such a proof using the following real-world example, arithmetic expressions, e.g., $3+5$ or $3\cdot (2-1)$.

Let $(\equiv )$ be the following relation:

$$(\equiv )=\{(e_1,e_2)\mid \text{e1 and e2 are arithmetic expressions that evaluate to the same value v}\}$$

Claim: $(\equiv )$ is an equivalence relation.

To show that $(\equiv )$ is an equivalence relation, we must show that it is reflexive, symmetric, and transitive.

Equivalence Closures

The closure of a set $S$ under a property $P$ is the (smallest) set $S^{\ast }\subseteq S$ whose elements all satisfy $P$. The concept of closure lifts to relations in the expected way. For example, let $U=\{0,.,10\}$ and $P$ be the property of symmetry $\forall x,y.(x,y)\in R\to (y,x)\in R$, then if $R$ is the relation:

$$R=\{(0,3),(2,5),(6,9),(5,2)\},$$

Then the symmetric closure of $R$ is the relation $R^{\ast }$:

$$S=\{(0,3),(3,0),(2,5),(5,2),(6,9),(9,6)\}.$$

We can compute the closure of any relation under a property by repeatedly applying the property to generate new pairs to add to the relation until we can no longer add new pairs.

We can apply the notion of closure to all the properties of an equivalence relation simultaneously to form an equivalence closure of a set of elements. Intuitively, the equivalence closure of a set of elements captures all the different equalities induced by the properties of equivalences.

For example, consider an artificial set $S=\{a,b,c\}$ and suppose we know that some relation $R$ relates the elements as follows:

$$(a,b)\in R,(b,c)\in R.$$

If we furthermore know that $R$ ought to be an equivalence relation, then we can compute the equivalence closure of $R$ as follows:

• The reflexive closure of the relation relates every element to itself: $(a,a),(b,b),(c,c)\in R$.
• The symmetric closure of the relation relates every pair "in the other direction": $(b,a),(c,b)\in R$.
• The transitive closure of the relation connects every transitive pair of elements: $(a,c)\in R$.
• Finally, we also have to consider the symmetric closure again for this new pair: $(c,a)\in R$.

In this particular case, the equivalence closure of $R$ is all nine possible pairs of $S$ with itself, i.e., $S\times S$. This case captures the intuition that the two original equalities are sufficient to deduce that all the elements of $S$ are equal.

Equivalence Classes

Intuitively, an equivalence relation captures some notion of equality between objects. We can then think about grouping together sets of mutually equal objects. For example, let's return to arithmetic expressions. The following expressions are all equivalent to each other:

• $10$.
• $5+5$.
• $2\times (2+3)$.

Because they all evaluate to $10$. Consider creating a set of such expressions, call it $S_4$ with the property that they all evaluate to $4$:

$$S_4=\{e\mid \text{ e is an arithmetic expression that evaluates to 4}\}.$$

Any pair of expressions within $S_4$ are equivalent to each other. We call such a set an equivalence class.

Recall that $x\mathrm{mod}y$ is the whole-number remainder of $x÷y$. Because of the nature of division, the result of $x\mathrm{mod}y$ takes on the values $0,\dots ,y-1$. Because of this, we can consider, e.g., the equivalences classes induced by taking a number and modding it by 3. $x\mathrm{mod}3$ takes on three values, $0$, $1$, and $2$, and thus, $\mathrm{mod}3$ induces three equivalence classes:

• $E_1=\{0,3,6,9,\dots \}$.
• $E_2=\{1,4,7,10,\dots \}$.
• $E_3=\{2,5,8,11,\dots \}$.

In the context of the modulus operator, we can say that any pair of numbers in an equivalence class are equivalent modulo 3, e.g., $4$ and $11$ are equivalent modulo $3$.

Orderings

There are many ways that we might order data. For a collection of strings, for example, we might order by:

• Simple length. For example, "dog" is less than "doghouse" since it is shorter.
• Lexicographical, i.e., dictionary order, comparing letter-by-letter. For example, "alphabet" is less than "zoo" in lexicographical ordering.
• A more arbitrary measure such as the number of consecutive trailing constants in the word. For example, "correctness" (-ss) comes before "algorithms" (-thms).

What is the essential nature of these relationships that make it a valid "ordering?" Let's start with the properties from an equivalence—reflexivity, symmetry, and transitivity—and use them In other words, which of the three properties of an equivalence—reflexivity, symmetry, and transitivity—are necessary for a relation to be considered an ordering? Let's consider numeric ordering $(\le )$ as our quintessential example of orderings and each of these properties in turn:

• Reflexivity: $(\le )$ appears to be reflexive because any number is equal to itself!
• Symmetry: $(\le )$ appears to not be symmetric. For example, $3\le 5$ but $5\nleqq 3$.
• Transitivity: $(\le )$ also appears to be transitive. If we establish that $x\le y$ and $y\le z$, we form the following chain of comparisons $x\le y\le z$ with the understanding that this notation implies that $x\le z$, too.

So it seems like an ordering is reflexive, transitive, but not symmetric! However, it seems like we need to say something stronger than "not symmetric." To see this, observe that we never want different numbers to be related to each other in both directions. In other words, it should never be the case that $x\le y$ and $y\le x$ for different $x$ and $y$! We call this property anti-symmetry:

Observe how we have to define this "zero-or-one" property in the same way we do with uniqueness. Intuitively, the formal definition of anti-symmetry says that whenever two elements are related in both directions, they must be the same element.

With the definition of anti-symmetry, we can now formally define a partial ordering:

As an example of a partial ordering, consider a hierarchy of employees where an employee has a manager, their manager has a manager, and so forth. We say that one employee is higher in the hierarchy than another if the first employee is the direct or indirect manager (i.e., manager of their manager, manager of their manager's manager, etc.) of the second. We can consider the following notion of employee equality:

$$({=}_e)=\{(e_1,e_2)\mid \text{e1 and e2 have the same position}\}$$

Along with an ordering based on the employee hierarchy:

$$({\le }_e)=\{(e_1,e_2)\mid \text{e1=ee2 or e2 is higher than e1 in the company hierarchy. }\}$$

We can show that this relation obeys the properties of a partial ordering:

Note that two employees that don't have a direct manager in common are incomparable by this definition because they don't appear in each other's chain of managers to the top of the hierarchy. This is why partial orders are named as such: some employees are incomparable to each other under this relation. To obtain this property, we add it directly to our definition, giving us a total ordering: