Equivalence Relations

For upcoming articles we’ll need the concepts of equivalence relations and equivalence classes, so let’s review them now.

Definition of equivalence relation

An equivalence relation is essentially a relaxed form of equality; it’s a way of saying what properties you care about when deciding in some context whether two mathematical objects are essentially the same. Often the objects in question may be viewed as concrete representations of more abstract objects. It’s traditional to use ≡ or ∼ or ≈ or some other symbol that looks vaguely like equality for an equivalence relation. Here are some examples:

• One way of constructing the rational numbers from the integers is to say that two ordered pairs of integers (𝑎, 𝑏) and (𝑐, 𝑑) are equivalent if 𝑏 ≠ 0, 𝑑 ≠ 0, and 𝑎 ⋅ 𝑑 = 𝑐 ⋅ 𝑏. If we think of (𝑎, 𝑏) as representing the rational number 𝑎 / 𝑏, and (𝑐, 𝑑) as representing the rational number 𝑐 / 𝑑, then the condition given for equivalence just means that 𝑎 / 𝑏 = 𝑐 / 𝑑, that is, they represent the same rational number.

• In propositional logic we write 𝐴 ≡ 𝐵 to mean that 𝐴 and 𝐵 are logically equivalent, that is, they have the same satisfying truth assignments¹. There’s a sense in which 𝚊 ∨ 𝚋 and 𝚋 ∨ 𝚊 are semantically the same, differing only in unimportant syntactic details.

• We will later find it useful to consider two premises 𝑋 and 𝑌 to be equivalent if they yield the same probabilities for any query 𝐴 that contains no latent symbols: Pr(𝐴 | 𝑋) = Pr(𝐴 | 𝑌) for all such formulas 𝐴.

Formally, a binary relation 𝑅 on a set 𝑆 is said to be an equivalence relation if it has the following three properties:

• It is reflexive: 𝑥 𝑅 𝑥 for all 𝑥 ∈ 𝑆.

• It is symmetric: 𝑥 𝑅 𝑦 implies 𝑦 𝑅 𝑥, for all 𝑥,𝑦 ∈ 𝑆.

• It is transitive: 𝑥 𝑅 𝑦 and 𝑦 𝑅 z implies 𝑥 𝑅 z, for all 𝑥,𝑦,𝑧 ∈ 𝑆.

These are three fundamental properties of equality; the only one missing is substitutability².

Equivalence classes

It commonly occurs in mathematics that once you have defined a notion of equivalence, and you have this idea that equivalent objects are in some sense just different ways of representing some more abstract object, you then need some way of defining exactly what that more abstract object is. If you were writing a computer program, you might reduce things to some canonical form. For example, if an ordered pair of integers (𝑎, 𝑏) represents a rational number, you could reduce that to lowest terms, i.e., an equivalent pair (𝑎′, 𝑏′) where 𝑏′ > 0 and 𝑎′ and 𝑏′ have no common factors, and you could say this canonical form is what you mean by a rational number. This approach isn’t always satisfactory, though, because it can be difficult to find a suitable canonical form.

Instead, mathematicians typically make use of the notion of equivalence classes: if 𝑥 ∈ 𝑆 and 𝑅 is an equivalence relation on 𝑆, then the equivalence class to which 𝑥 belongs, written [𝑥]_𝑅, is the set of all elements of 𝑆 that are equivalent to 𝑥:

\(\left[x\right]_{R}\triangleq\left\{ y\in S\colon y\,R\,x\right\} .\)

When 𝑅 is obvious from context one typically drops the subscript and just writes [𝑥]. The members of an equivalence class are sometimes called representatives of the equivalence class. So 𝑥 is a representative of [𝑦] iff 𝑥 ≡ 𝑦.

The more abstract object that 𝑥 represents is then defined to be the entire equivalence class [𝑥]. For example, the rational number 4/3 is defined to be the entire infinite set of integer pairs equivalent to (4, 3):

\(\left\{ (4,3),(-4,-3),(8,6),(-8,-6),(12,9),(-12,-9),\ldots\right\} .\)

This may seem a bit extravagant, but fortunately the Platonic world of mathematics is not subject to storage space limitations.

Operations on equivalence classes

It is often easiest to define operations on equivalence classes in terms of operations on their representatives. One often sees definitions following this pattern:

\(F\left(\left[x\right]\right)\triangleq\left[f(x)\right].\)

For example, in the case of our equivalence relation used to define the rational numbers, we might define negation as

\(-\left[\left(a,b\right)\right]\triangleq\left[\left(-a,b\right)\right].\)

But a definition like this is only valid if there is no ambiguity, that is, if the result does not depend on which representative of the equivalence class we use in applying the definition. In the case of defining negation on the rational numbers, this is guaranteed by the fact that

\(\left(-a,b\right)\equiv\left(-c,d\right)\mbox{ whenever }\left(a,b\right)\equiv\left(c,d\right).\)

Once we start talking about functions on equivalence classes, it is natural to want to have a notation for the domains of such functions. If 𝑅 is an equivalence relation on a set 𝑆, then we write 𝑆 / 𝑅, pronounced “𝑆 mod 𝑅,” for the set of equivalence classes on 𝑆 defined by 𝑅. This set is a partition of 𝑆: every element of 𝑆 belongs to exactly one of the equivalence classes in 𝑆 / 𝑅.

Up Next

In the next article on metric spaces we’ll see how Cauchy sequences provide a notion of convergence that doesn’t require us to supply a limiting value that the sequence is converging to. The notion of equivalence classes can then be used to complete the metric space, i.e. fill in any missing limits, much in the same way that completing the space of rational numbers yields the real numbers.

1. When we consider truth assignments that assign values to all the propositional symbols in either formula.

2. Substitutability refers to the fact that if 𝑥 = 𝑦 than you can replace 𝑥 with 𝑦 anywhere within a term.