📋 Changes in this PR: State Machines and Finite Automata, Calendar, Contrapositive and Contradiction, Inference and Direct Proof, Logical Equivalence and Negation, Functional Programming, Graphs, Proving Non-Conditional Statements, Mathematical Induction, Loop Invariants, Predicates and Quantifiers, Propositional Logic, Recurrence Relations and Growth Rates, Recursion, Relations, Proofs with Sets, Sets, WWU CSCI 201 Syllabus, Trees, Expressions and Algorithms, Functions, Growth Rates, Math for Computer Science, Induction and Recursion, Notation, Number Systems, Proof Writing, Relations, Sets
💡 Tip: If change highlighting is glitchy, add the no-preview-highlights label to this PR to disable it.
Properties of relations
Example 1 (Reflexive and non-reflexive relations on the real numbers) On \(\mathbb{R}\), the relation \(=\) is reflexive, since \(a = a\) for every real number \(a\). The relation \(\le\) is also reflexive, since \(a \le a\) for every real number \(a\). The relation \(<\) is not reflexive, since \(2 < 2\) is false.
Example 2 (Symmetric and non-symmetric relations on the real numbers) On \(\mathbb{R}\), the relation \(=\) is symmetric: whenever \(a = b\), also \(b = a\). The relation \(\le\) is not symmetric, since \(2 \le 5\) is true but \(5 \le 2\) is false.
Equivalence relations
Example 3 (Integers with an even difference) On the integers, define the relation \(\sim\) by \(a \sim b\) when \(a - b\) is even. For example, \(7 \sim 3\), since \(7 - 3 = 4 = 2 \cdot 2\), but \(7 \not\sim 4\), since \(7 - 4 = 3\) is odd. The relation \(\sim\) is an equivalence relation.
Reflexive. For every integer \(a\), \(a - a = 0 = 2 \cdot 0\), so \(a \sim a\).
Symmetric. Suppose \(a \sim b\), so \(a - b = 2k\) for some integer \(k\). Then
\[
\begin{aligned}
b - a
&= -(a - b)
&& \text{(negate the difference)}
\\
&= -2k
&& \text{(} a - b = 2k \text{)}
\\
&= 2(-k),
&& \text{(factor out } 2 \text{)}
\end{aligned}
\]
and \(-k\) is an integer, so \(b \sim a\).
Transitive. Suppose \(a \sim b\) and \(b \sim c\), so \(a - b = 2j\) and \(b - c = 2k\) for some integers \(j\) and \(k\). Then
\[
\begin{aligned}
a - c
&= (a - b) + (b - c)
&& \text{(the } b \text{ terms cancel)}
\\
&= 2j + 2k
&& \text{(} a - b = 2j \text{ and } b - c = 2k \text{)}
\\
&= 2(j + k),
&& \text{(distributive law)}
\end{aligned}
\]
and \(j + k\) is an integer, so \(a \sim c\).
Definition 4 (Equivalence class) Let \(\sim\) be an equivalence relation on a set \(S\), and let \(a \in S\). The equivalence class (Wikipedia contributors 2026a) of \(a\) is the set of elements of \(S\) related to \(a\):
\[
[a] \stackrel{\text{def}}{=}{\mathopen{}\left\{b \in S : b \sim a\right\}\mathclose{}}.
\]
Example 4 (Equivalence classes of integers with an even difference) Let \(\sim\) be the equivalence relation of Example 3 on the integers. The equivalence class \([0]\) holds the integers \(b\) with \(b - 0\) even, which are the even integers: \([0] = \mathopen{}\left\{\ldots, -4, -2, 0, 2, 4, \ldots\right\}\mathclose{}\). The class \([1]\) holds the integers \(b\) with \(b - 1\) even, which are the odd integers: \([1] = \mathopen{}\left\{\ldots, -3, -1, 1, 3, 5, \ldots\right\}\mathclose{}\). The class \([2]\) is the same set as \([0]\), since \(2 \sim 0\).
Back to top