Let us look at the mathematical concept of equivalence relations. The idea is based the the concept of "equality".

What does it mean for two things to be "equal"?

• Is an orange "equal" to an apple?
• Is an apple "equal" to an apple?

The idea of equivalence and equality depends on the definition of equality that is being used.

Consider the part of the United States Declaration of Independence that goes as follows (July 4, 1776).

We hold these truths to be self-evident, that all men are created equal, that they are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty and the pursuit of Happiness

This appears to say that all men (presumably mankind, one place for discussion) are created (how were they created, another place for discussion) "equal". Do they stay "equal". And so forth. Let us return the the world of abstract mathematics (as symbol manipulation) and look at the concept of equivalence relations.

A mathematical "relation" is a comparison between two elements of a set (or population) where each comparison is either true or false.

Consider the relation R as "is the same sex/gender as" when comparing two people. Let us assume that this is possible to do (perhaps in a possibly non-politically correct manner).

For example purposes, let us use the set (or population) of people in the audience.

An "equivalence relation" is a relation R on a set A that is reflexive, symmetric, and transitive.

A relation R on set A is reflexive if for every x in A, x R x.

This can be written in mathematical form as follows.


This is read as "for all x in (set) A, (condition) x R x (is true)"

• The symbol "∀" is read as "for all".
• The symbol "∈" is read as "in" which is short for "is an element of" (the set that follows).
• The symbol ":" (colon) can be thought of as saying "such that" or "it is true that" (what follows).

The relation R as "is the same sex/gender as" is reflexive, since

person x "is the same sex/gender as" person x.

That is, does a rule apply to itself?

Are you the same sex, whatever that is, as yourself?

When someone says, "Do as I say, not as I do" they are applying a rule to others but not to them-self. That is, the rule, to them, is not a reflexive rule.

What are some instances of humans applying rules to others but not to themselves?

Self-referential statements are the source of many logical paradoxes. (more on this later)

A relation R on set A is symmetric if for every x and y in A, x R y implies that y R x.

This can be written in mathematical form as follows.

This is read as "for all x and y in (set) A, (condition) x R y implies (condition) y R x"

• The symbol "⇒" is read as "implies" where the result is true if when the left condition is true the right condition is true.

The relation R as "is the same sex/gender as" is symmetric, since

• person x "is the same sex/gender as" person y implies that
• person y "is the same sex/gender as" person x.

Note that the relation applies both ways, since the elements identified by x and y can be reversed.

That is, does the rule go both ways? Is it a commutative property?

A commutative property is a rule where the order does not matter.

Addition and multiplication are commutative/symmetric operations where order does not matter.

Subtraction and division are non-commutative/non-symmetric operations where order does matter.

A relation R on set A is transitive if for every x, y, and z in A, x R y and y R z implies that x R z.

This can be written in mathematical form as follows.
This is read as "for all x and y and z in (set) A, (condition) x R y and (condition) y R z implies (condition) x R z"

The symbol "∧" is read as "and" and means that both conditions must be true for the result to be true.

The relation R as "is the same sex/gender ass" is transitive, since

• person x "is the same sex/gender as" person y and
• person y "is the same sex/gender as" person z implies that
• person x "is the same sex/gender as" person z.

So, in summary, a relation R on set A is an equivalence relation if the following properties hold.

• reflexive: ∀ x ∈ A : x R x
• symmetric: ∀ x, y ∈ A : x R y ⇒ y R x
• transitive: ∀ x, y, z ∈ A : x R y ∧ y R z ⇒ x R z

Equivalence classes reduce the amount of information that must be considered when working with properties of the set A.

The general approach to the equivalence class methodology is as follows.

• Determine a relation.
• Verify that the relation has the reflexive, symmetric, and transitive properties.
• Determine equivalence classes using some method or algorithm.
• Use the equivalence classes as needed to solve some identified problem.

To review, here is the example.

• Let A be the set of "people in the audience".
• Let R be "is the same sex/gender as".
• Let x, y, and z be three different people in the audience.

Then relation R is an equivalence relation on set A. Thus if we assume that there are two possible sexes or genders, then there are (at most) two possible equivalence sets in the set of people in the audience.

• The audience may be all male.
• The audience may be all female.
• There may be no audience - the degenerate case.

Degenerate cases should also be handled, such as zero or one piece of data.

If I say that "rap music is a degenerate form of music", what might I mean? If I assume that music consists of melody, harmony, and rhythm, then, since rap music consists of primarily rhythm without discernible melody or harmony, then it is a degenerate form of music since not all parts of music are present. That does not mean that that is bad, it just means that, from an analysis point of view, not all possible components of music, from the above definition, are present.

Note that a melody of all the same duration of note without harmony is also a degenerate form of music. A common error in computation (e.g., programming) is a failure to handle degenerate instances of the problem.

In the case of determining the rules for the relation, there are two degenerate cases (see above) that can arise when one cannot determine a definite rules.

• 1. Everything is related to everything else.
• 2. Nothing is related to anything else.

In the first case where everything is related to everything else, the relation is always true, so every element belongs to the same and only equivalence class - which may not very useful. In the second case where nothing is related to anything else, the relation is always false, so each element is not related to any other item, and so each element is a separate equivalence class - which may not be very useful.

There are computer algorithms that, given two sets and a relation definition will determine the equivalence classes. These can be somewhat involved, both in implementation and performance analysis, and are omitted here.

In the well-known union-find problem, Find and Union are defined as follows.

• Find(x) returns the set identifier of the element x. Elements x and y are in the same set if Find(x) = Find(y).
• Union(x,y) merges the sets x and y and returns the merged set.

The heuristics for the union-find algorithm are as follows.

The heuristic for a Union is to always merge the smaller tree into the larger tree. For this problem, one of the sets will be known to be the smallest tree (i.e., a singleton set).

The heuristic for a Find is that path compression is used in that once the root of the tree is found, the path is traversed a second time so that all elements in the path point to the root.

The asymptotic worst-case complexity of the union-find algorithm, due to Tarjan, R. (1983). Data structures and network algorithms. Philadelphia, PA: Society for industrial and applied mathematics. , is O((m+n) α(n)) where

• n is the number of nonempty cells (i.e., starting singleton sets),
• m is the number of Union and Find operations, and
• α is the inverse Ackerman's function, which grows very slowly.

Many solutions to the convex hull problem require handling the Union-Find problem.

Note that one must determine the precise rule or relation first and then apply it to the set or population to get the equivalence sets.

Note that any given element can belong to one and only one equivalence set - due to the reflexivity property.

12 questions omitted (login required)