Skip to main content
Logo image

Section 18.2 Basics and examples

What properties should a relation on a set have to be useful as a notion of “equivalence”?
  • Each object in the set should be equivalent to itself. So the relation should be reflexive.
  • Equivalence should be bidirectional. That is, a pair of equivalent objects should be equivalent to each other. So the relation should be symmetric.
  • We should be able to infer equivalence from chains of equivalence. So the relation should be transitive.
equivalence relation
a relation on a set that is reflexive, symmetric, and transitive
\(\mathord{\equiv}\)
symbol for an abstract equivalence relation (instead of the letter \(R\) that we’ve been using for abstract relations up until now)

Worked Example 18.2.1.

Let \(\mathscr{L}\) be the set of all possible logical statements built out of the statement variables \(p_1, p_2, p_3, \dotsc\text{.}\) Show that logical equivalence of statements is an equivalence relation on \(\mathscr{L}\text{.}\)
Solution.

Reflexive.

We have \(A \lgcequiv A\) for every statement \(A\text{,}\) since \(A\) has the same truth table as itself.

Symmetric.

If \(A \lgcequiv B\text{,}\) then \(A,B\) have the same truth table, so \(B \lgcequiv A\text{.}\)

Transitive.

If \(A \lgcequiv B\) and \(B \lgcequiv C\text{,}\) then \(A\) has the same truth table as \(B\text{,}\) which has the same truth table as \(C\text{.}\) So \(A\) has the same truth table as \(C\text{,}\) i.e. \(A \lgcequiv C\text{.}\)
Here is an important equivalence relation on \(\N\) or on \(\Z\text{.}\)
equivalence modulo \(n\)
an equivalence of integers, where two integers are equivalent if they have the same remainder when divided by \(n\)
\(m_1 \equiv_n m_2\)
integers \(m_1,m_2\) are equivalent modulo \(n\)

Checkpoint 18.2.2.

Verify that equivalence modulo \(n\) is an equivalence relation.