18.2: Basics and Examples

Last updated
Save as PDF

Page ID: 83495

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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.

Definition: Equivalence Relation

a relation on a set that is reflexive, symmetric, and transitive

Definition: \(\mathord{\equiv}\)

symbol for an abstract equivalence relation (instead of the letter \(R\) that we've been using for abstract relations up until now)

Example \(\PageIndex{1}\)

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

Solution

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

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

Transitive. If \(A \Leftrightarrow B\) and \(B \Leftrightarrow 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 \Leftrightarrow C\text{.}\)

Here is an important equivalence relation on \(\mathbb{N}\) or on \(\mathbb{Z}\text{.}\)

Definition: Equivalence Modulo \(n\)

an equivalence of integers, where two integers are equivalent if they have the same remainder when divided by \(n\)

Definition: \(m_1 \equiv_n m_2\)

integers \(m_1,m_2\) are equivalent modulo \(n\)

Checkpoint \(\PageIndex{1}\)

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