Let us look at the mathematical concept of equivalence relations. The idea is based 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 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.

Here is the diagram to summarize these laughing ideas. The relation R as "is the same sex/gender as" is reflexive, since

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

Does a rule apply to itself? If so, the rule is reflexive.

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

Except for negation, most logical (not human) rules are reflexive.

Do some people apply rules to others but not to themselves?

Whenever 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. In such a case, one might call the person a "hypocrite" using the modern sense of the word.

The pattern becomes more clear with a diagram. The rule applies to everyone, which includes self. Negation results in interesting ideas.

• Math proof that disproves itself (incompleteness)
• Halting problem that detects itself halting (incomputability)
• Minimal programs that detect randomness

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.

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.

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.

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.

What might I mean when I say that "rap music is a degenerate form of music"? 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 it 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.