Skip to main content

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{;}\) that is, \(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.
PrevTopNext