Equivalence relation

When defining types of objects, we often want to define a new notion of equality. For example, we have already defined equality for pairs, sets, functions, and cardinalities.

Whenever you redefine a familiar definition or operation, it is important not to change the fundamental properties that peoBold textple expect of that operation: people should still be able to reason about your operator the way they always have.

The properties that people expect "equals" to have are defined below; relations that satisfy all three are called equivalence relations. You should always check these properties if you ever define something called "equals" (for example, when overriding the `.equals()` method in Java or the `__eq__` method in Python).

Reflexivity

Definition: Reflexive

A binary relation [math]R [/math] on a set [math]A [/math] is reflexive if for every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], [math]\href{/cs2800/wiki/index.php/XRy}{xRx} [/math].

In a picture, this means that every element of [math]A [/math] has a self-loop: an edge back to itself.

Symmetry

Definition: Symmetric

A binary relation [math]R [/math] on a set [math]A [/math] is symmetric if for all pairs of elements [math]x [/math] and [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/XRy}{xRy} [/math], we also have [math]\href{/cs2800/wiki/index.php/XRy}{yRx} [/math].

In a picture, this means that every edge from [math]x [/math] to [math]y [/math] has a corresponding edge from [math]y [/math] back to [math]x [/math].

Transitivity

Definition: Transitive

A binary relation [math]R [/math] on a set [math]A [/math] is transitive if for all elements [math]x [/math], [math]y [/math], and [math]z \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/XRy}{xRy} [/math] and [math]\href{/cs2800/wiki/index.php/XRy}{yRz} [/math], we also have [math]\href{/cs2800/wiki/index.php/XRy}{xRz} [/math].

In a picture, this means that every path from [math]x [/math] to [math]y [/math] has a corresponding direct edge from [math]x [/math] to [math]y [/math].

Equivalence relation

Definition: Equivalence relation

A binary relation [math]R [/math] is an equivalence relation if [math]R [/math] is reflexive, symmetric, and transitive.

Reflexivity lets you plug in definitions to show that things are equal (for example, it lets you conclude that [math]2^2 = 4 [/math]). Symmetry lets you use equality in both directions (e.g. since x = y, we know that "... = y = x = ..."). Transitivity lets you chain together statements. (For example, we often write things like "[math]x_1 = x_2 = x_3 = x_4 [/math], so [math]x_1 = x_4 [/math]").