Equivalence Relation Calculator

Test reflexive, symmetric, and transitive properties, then build the closure.

Results are calculated automatically as you enter data.

Universe elements
Element
Relation Pairs

Property checks and repair steps
Result Enter a universe and relation.

▼ See explanations and tips below ▼

Related Calculators

What Is an Equivalence Relation?

An equivalence relation is a special kind of relationship on a set. It is used when different elements should be treated as belonging to the same group according to a precise rule.

Start with a set \(A\). A binary relation \(R\) on \(A\) is a collection of ordered pairs from \(A \times A\). If \((a,b) \in R\), then \(a\) is related to \(b\).

A relation becomes an equivalence relation when it behaves like a generalized form of equality. The relation must satisfy three conditions:

  • Every element is related to itself.
  • If one element is related to another, the relationship works in the reverse direction too.
  • If one element is related to a second, and the second is related to a third, then the first is related to the third.

These three conditions are called reflexive, symmetric, and transitive. When all three hold, the relation sorts the set into non-overlapping groups called equivalence classes.

For example, on the integers, “has the same remainder when divided by \(3\)” is an equivalence relation. The integers are sorted into three classes: numbers congruent to \(0\), numbers congruent to \(1\), and numbers congruent to \(2\) modulo \(3\).

Why Equivalence Relations Matter

Equivalence relations are useful because they turn a collection of pair-by-pair comparisons into clean groups.

Instead of checking every possible pair forever, you can ask a simpler question: which class does each element belong to? Once two elements are in the same equivalence class, they are equivalent under the rule being studied.

This idea appears throughout discrete mathematics, set theory, number theory, abstract algebra, graph theory, and computer science. It is also a common proof technique: once you prove that a relation is reflexive, symmetric, and transitive, you automatically get a partition of the underlying set.

For finite sets, equivalence relations are especially practical because they can be represented by ordered pairs, relation matrices, or grouped classes.

Key Terms to Know

  • Universe: The set of elements being studied. In formulas, it is often called \(A\).
  • Ordered pair: A pair such as \((a,b)\) where order matters. In general, \((a,b)\) and \((b,a)\) are different pairs.
  • Binary relation: A set of ordered pairs. A relation \(R\) on \(A\) is a subset of \(A \times A\).
  • Reflexive: Every element relates to itself.
  • Symmetric: Whenever \(a\) relates to \(b\), \(b\) also relates to \(a\).
  • Transitive: Whenever \(a\) relates to \(b\) and \(b\) relates to \(c\), \(a\) also relates to \(c\).
  • Equivalence relation: A relation that is reflexive, symmetric, and transitive.
  • Equivalence class: The group of all elements equivalent to a chosen element.
  • Partition: A way to split a set into nonempty, non-overlapping blocks whose union is the whole set.
  • Relation matrix: A \(0\)-\(1\) matrix where rows and columns represent elements. A \(1\) means the row element is related to the column element.
  • Equivalence closure: The smallest equivalence relation that contains a given relation.
  • Congruence modulo \(n\): A relation where two integers are equivalent when their difference is divisible by \(n\).

How Equivalence Relations Work

Let \(A\) be a set and let \(R\) be a relation on \(A\). To check whether \(R\) is an equivalence relation, test the three defining properties.

A relation is reflexive when every element has its self-pair:

$$ \forall a \in A,\ (a,a) \in R $$

A relation is symmetric when every related pair has its reverse pair:

$$ (a,b) \in R \implies (b,a) \in R $$

A relation is transitive when every two-step chain has the required direct pair:

$$ (a,b) \in R \land (b,c) \in R \implies (a,c) \in R $$

If all three statements are true, \(R\) is an equivalence relation.

For an equivalence relation, the equivalence class of \(a\) can be written as:

$$ [a]_R = \{x \in A : (a,x) \in R\} $$

This means \([a]_R\) contains all elements related to \(a\). Because equivalence relations are symmetric and transitive, any two classes are either exactly the same or completely disjoint. That is why equivalence classes form a partition of the set.

The connection also works in reverse. If a set is already split into blocks, you can define an equivalence relation by saying that two elements are related exactly when they are in the same block.

Smallest equivalence closure

A relation that fails one or more tests can often be repaired by adding missing pairs. The smallest equivalence closure is the relation that contains the original relation and adds only the pairs needed to make it reflexive, symmetric, and transitive.

For a finite relation, one way to understand the closure is to treat each related pair as a connection between elements. Elements connected by chains must end up in the same closure class. Then each closure class \(C\) is completed by adding every ordered pair in \(C \times C\):

$$ C \times C = \{(x,y) : x \in C \text{ and } y \in C\} $$

This completion ensures that every element in the class is related to every other element in that class, including itself.

Congruence modulo \(n\)

Congruence modulo \(n\) is a standard example of an equivalence relation on integers. For an integer modulus \(n \ge 2\):

$$ a \equiv b \pmod n \quad \text{means} \quad n \mid (a-b) $$

In plain language, \(a\) and \(b\) are congruent modulo \(n\) when they have the same remainder after division by \(n\). For example, \(14 \equiv 2 \pmod 4\) because \(14-2=12\), and \(12\) is divisible by \(4\).

Examples of Equivalence Relations in Practice

Example 1: A relation that is already an equivalence relation

Let:

$$ A = \{1,2,3\} $$

and

$$ R = \{(1,1),(2,2),(3,3),(1,2),(2,1)\} $$

Check the three properties:

  • Reflexive: \((1,1)\), \((2,2)\), and \((3,3)\) are all present.
  • Symmetric: \((1,2)\) and \((2,1)\) are both present.
  • Transitive: the only nontrivial related group is \(\{1,2\}\), and all needed pairs inside that group are present.

So \(R\) is an equivalence relation.

Its equivalence classes are:

$$ \{1,2\} \mid \{3\} $$

The vertical bar is just a readable separator between classes.

Example 2: A relation that needs repair pairs

Let:

$$ A = \{a,b,c\} $$

and

$$ R = \{(a,b),(b,c)\} $$

This relation is not reflexive because it is missing \((a,a)\), \((b,b)\), and \((c,c)\).

It is not symmetric because it contains \((a,b)\) but not \((b,a)\), and it contains \((b,c)\) but not \((c,b)\).

It is not transitive because \((a,b)\) and \((b,c)\) together require \((a,c)\).

The original pairs connect \(a\), \(b\), and \(c\) into one closure class:

$$ C = \{a,b,c\} $$

The smallest equivalence closure must contain all pairs in \(C \times C\):

$$ C \times C = \{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\} $$

The original relation already had \((a,b)\) and \((b,c)\), so the repair pairs are:

$$ \{(a,a),(a,c),(b,a),(b,b),(c,a),(c,b),(c,c)\} $$

That is \(7\) repair pairs.

Example 3: Congruence classes with negative integers

Let:

$$ A = \{-3,-2,-1,0,1,2,3\} $$

Use congruence modulo \(3\). Two numbers are related when their difference is divisible by \(3\).

For example:

$$ -2 \equiv 1 \pmod 3 $$

because:

$$ -2 - 1 = -3 $$

and \(-3\) is divisible by \(3\).

The classes within this finite universe are:

$$ \{-3,0,3\} \mid \{-2,1\} \mid \{-1,2\} $$

These are the same-remainder groups, restricted to the elements that are actually in \(A\).

How to Interpret the Result

A relation is an equivalence relation only when reflexive, symmetric, and transitive all pass.

If the result says the relation is an equivalence relation, the listed classes are the actual equivalence classes of the relation. The repair-pair count should be \(0\) because no extra ordered pairs are needed.

If the result says the relation is not an equivalence relation yet, the failing property cards explain why. The repair-pair count tells how many ordered pairs must be added to create the smallest equivalence closure.

The listed classes in a failing case are closure classes. They show how the elements would be grouped after the relation is completed, not necessarily proof that the original relation already satisfied all three properties.

The relation matrix shows the current relation using \(1\) and \(0\) entries. A \(1\) means the row element is related to the column element. A \(0\) means that ordered pair is not currently in the relation. Unless the relation was already complete, the displayed matrix should not be confused with the matrix of the completed closure.

The property diagnostics are concrete clues. A missing self-pair points to a reflexivity problem. A missing reverse pair points to a symmetry problem. A missing direct pair caused by a two-step chain points to a transitivity problem.

The mathematical results are exact. Property checks, class counts, matrix entries, and repair-pair counts do not use decimal rounding.

Common Mistakes and Misconceptions

One common mistake is forgetting self-pairs. For a relation on \(\{a,b,c\}\) to be reflexive, it must include all of \((a,a)\), \((b,b)\), and \((c,c)\).

Another mistake is checking only one direction. If \((a,b)\) is in the relation, symmetry requires \((b,a)\) too. The order of the pair matters.

Transitivity is often the easiest property to miss. If \((a,b)\) and \((b,c)\) are both present, then \((a,c)\) must also be present. This requirement applies to every possible chain in the relation.

In matrix form, row and column order matters. If the universe is listed as \(a,b,c\), then the entry in row \(a\), column \(c\) represents \((a,c)\). Changing the order changes how the matrix should be read.

Pairs must use elements from the universe. A pair such as \((a,d)\) is not valid for a universe that contains only \(a\), \(b\), and \(c\).

Congruence rule mode requires integer-valued elements. Decimal labels, nonnumeric labels, and non-integer moduli do not fit the usual congruence-modulo relation.

Finally, do not assume closure classes mean the original relation passed. Closure classes describe the grouping after the smallest equivalence closure is formed. The original relation is an equivalence relation only if all three property checks pass before repair pairs are added.

When to Use Equivalence Relations

Use equivalence relations when you need to decide whether a rule groups elements consistently.

Common uses include:

  • Checking homework or examples in discrete mathematics, set theory, or abstract algebra.
  • Finding equivalence classes from ordered pairs or a relation matrix.
  • Understanding partitions of a finite set.
  • Studying congruence modulo \(n\) and same-remainder classes.
  • Finding the smallest equivalence relation that contains a relation that is almost correct.
  • Comparing relation representations, such as ordered pairs versus a \(0\)-\(1\) matrix.

Equivalence relations are especially helpful when the main question is not “which pairs are listed?” but “which elements belong together?”

Limitations and Things to Keep in Mind

This calculator works with a finite universe. It checks the relation only on the elements that are entered.

The universe cannot be empty, duplicate entries are rejected, and it is capped at \(18\) elements for readability.

In ordered-pair and matrix modes, elements are distinct labels, so duplicate labels are rejected. Every relation-matrix cell must be explicitly \(0\) or \(1\). In congruence rule mode, the universe elements must be safe integers with one label per integer, and the modulus must be a safe integer at least \(2\).

In matrix mode, a \(1\) means the row element is related to the column element and a \(0\) means it is not. Every matrix cell must be explicitly \(0\) or \(1\); blank cells are rejected.

In ordered-pair mode, zero or more pairs may be supplied, and every supplied pair must use elements from the current universe. An empty pair relation is analyzed normally.

Imported matrices must match the current universe size exactly. Imported pairs must also refer only to elements already in the universe.

The calculator gives property diagnostics and closure construction steps, but it does not replace a written proof in a course that asks for one. Use the diagnostics to see what is happening, then write the argument in terms of reflexivity, symmetry, and transitivity.

Very large lists of repair pairs or diagnostics may be shortened in the displayed tables. The count is still the important summary, but a truncated display may not show every missing pair.

Visual graph coordinates and image rendering details may use decimal formatting, but the relation checks and class results are exact mathematical results.

How to Use This Calculator

  1. Enter the universe elements, or paste/import them if that is easier.
  2. Choose the relation input mode: ordered pairs, relation matrix, or congruence rule.
  3. In ordered-pair mode, add each pair by choosing its first and second element.
  4. In matrix mode, enter \(1\) where the row element is related to the column element and \(0\) where it is not.
  5. In congruence rule mode, enter an integer modulus of at least \(2\) and use integer universe elements.
  6. Review the main result, property cards, diagnostics, equivalence or closure classes, and repair-pair count.
  7. Use the visual class diagram or download option if you need a partition-style picture.

Frequently Asked Questions

What are the three requirements for an equivalence relation?

A relation must be reflexive, symmetric, and transitive. Reflexive means every element relates to itself. Symmetric means every pair works in both directions. Transitive means every two-step chain has the required direct pair.

Are equivalence classes always disjoint?

For an equivalence relation, yes. Any two equivalence classes are either exactly the same class or have no elements in common. This is why equivalence classes form a partition of the underlying set.

What does the smallest equivalence closure mean?

The smallest equivalence closure is the completed relation obtained by adding the fewest necessary ordered pairs so the relation becomes reflexive, symmetric, and transitive. It must contain the original relation, but it should not add unrelated pairs beyond what the three properties force.

Does a repair-pair count of zero mean the relation is already an equivalence relation?

Yes. If no repair pairs are needed, the relation already contains the pairs required for reflexivity, symmetry, and transitivity. The property cards should all pass.

How is congruence modulo \(n\) an equivalence relation?

For integers, \(a \equiv b \pmod n\) means \(n\) divides \(a-b\). Every integer is congruent to itself, the relationship reverses because changing the sign of a divisible difference keeps it divisible, and two divisible differences can be added to prove transitivity.

Why does the matrix order matter?

A relation matrix uses the universe order for both rows and columns. The entry in row \(a\) and column \(b\) represents the ordered pair \((a,b)\). If you read the row or column order incorrectly, you may interpret the wrong pair.

Sources and References

Books and Open Textbooks

  1. Richard Hammack. Book of Proof. Third Edition, Edition 3.4, published by Richard Hammack, 2018. Chapter 11, especially Sections 11.1–11.5. https://richardhammack.github.io/BookOfProof/Main.pdf
  2. Oscar Levin. Discrete Mathematics: An Open Introduction. 4th Edition, Open Math Books. Section 2.6, “Relations and Graphs.” https://discrete.openmathbooks.org/dmoi4/sec_gt-relations.html

Online Educational Sources

  1. Alexander Brandt. Discrete Structures for Computing. University of Western Ontario, 2023. Section 3.3, “Matrices,” especially “Relations as Matrices” and “Relational Properties and Matrices.” https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter3/matrices.html
  2. University of Basel, Department of Mathematics and Computer Science. “Disjoint-set Data Structure/Union-Find.” Algorithms and Data Structures handout, April 30, 2026. Slides 22–23, “Connected Components and Equivalence Classes.” https://ai.dmi.unibas.ch/_files/teaching/fs26/ad/slides/ad-c03-handout.pdf