# 2.2: Equivalence Relations, and Partial order

$$\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}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

Definition: Equivalence Relation

A binary relation is an equivalence relation on a nonempty set $$S$$ if and only if the relation is reflexive(R), symmetric(S) and transitive(T).

Definition: Partial Order

A binary relation is a partial order if and only if the relation is reflexive(R), antisymmetric(A) and transitive(T).

Example $$\PageIndex{1}$$: $$=$$

Let $$S=\mathbb{R}$$ and $$R$$ be =. Is the relation a) reflexive, b) symmetric, c) antisymmetric, d) transitive, e) an equivalence relation, f) a partial order.

Solution:

Proof:

Let .

Then .

Hence is reflexive.◻

Proof:

Let .

If , then .

Hence is symmetric.◻

Proof:

Let s.t. and then clearly .◻

Proof:

Let s.t. and .

We shall show that .

Since and it follows that

Thus .◻

Proof:

Since is reflexive, symmetric and transitive, it is an equivalence relation.

Proof:

is a partial order, since is reflexive, antisymmetric and transitive.

Example $$\PageIndex{2}$$: Less than or equal to

Let and be . Is the relation a) reflexive, b) symmetric, c) antisymmetric, d) transitive, e) an equivalence relation, f) a partial order.

Solution

Proof:

We will show that is true.

Let that is .

Since , is reflexive.◻

Counterexample:

Let and which are both .

It is true that , but it is not true that .

Thus is not symmetric.◻

Proof:

We will show that given and that .

Since , s.t. .

Further, since , , .

Then .

Thus, .

Since, , thus .◻

4. Yes, is transitive.

Proof:

We will show that given and that .

Since , s.t. .

Further, since , , .

Then .

Since, , thus .◻

Definition: Equivalence Class

Given an equivalence relation $$R$$ over a set $$S,$$ for any $$a \in S$$ the equivalence class of a is the set $$[a]_R =\{ b \in S \mid a R b \}$$, that is
$$[a]_R$$ is the set of all elements of S that are related to $$a$$.

Example $$\PageIndex{3}$$: Equivalence relation

Define a relation that two shapes are related iff they are the same color. Is this relation an equivalence relation?

Equivalence classes are:

Example $$\PageIndex{4}$$:

Define a relation that two shapes are related iff they are similar. Is this relation an equivalence relation?

Equivalence classes are:

##### Definition: Partition

Let $$A$$ be a nonempty set. A partition of $$A$$ is a set of nonempty pairwise disjoint sets whose union is A.

Note

For every equivalence relation over a nonempty set $$S$$, $$S$$ has a partition.

Theorem $$\PageIndex{1}$$

If $$\sim$$ is an equivalence relation over a non-empty set $$S$$. Then the set of all equivalence classes is denoted by $$\{[a]_{\sim}| a \in S\}$$ forms a partition of $$S$$.

This means

1. Either $$[a] \cap [b] = \emptyset$$ or $$[a]=[b]$$, for all $$a,b\in S$$.

2. $$S= \cup_{a \in S} [a]$$.

Proof

Assume is an equivalence relation on a nonempty set .

Let . If , then we are done. Otherwise,

assume .

Let be the common element between them.

Let .

Then and , which means that and .

Since is an equivalence relation and .

Since and (due to transitive property), .

Thus and .

Hence .

Next, we will show that .

First we shall show that .

Let .

Then exists and .

Hence .

Thus .

Conversely, we shall show that .

Let .

Then for some .

Thus .

Thus .

Since and , then .◻

For the following examples, determine whether or not each of the following binary relations on the given set is reflexive, symmetric, antisymmetric, or transitive. If a relation has a certain property, prove this is so; otherwise, provide a counterexample to show that it does not. If is an equivalence relation, describe the equivalence classes of .

Example $$\PageIndex{5}$$:

Let $$S = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$$. Define a relation $$R$$ on $$A = S \times S$$ by $$(a, b) R (c, d)$$  if and only if $$10a + b \leq 10c + d.$$

Let . Define a relation on by if and only if .

Solution

1. is reflexive on .

Proof:

Let .

We will show that .

Since , then .

Since is reflexive on .◻

2. is not symmetric on .

Counter Example:

Let .

Note , specifically, is true.

However, , is false.

Since , is not symmetric on .◻

3. is antisymmetric on .

Proof:

Let s.t. and .

Since and , .

We will show that and .

by definition.

Since and , thus .

Since , .

Thus is antisymmetric on .◻​​​​

5. is transitive on .

Proof:

Let s.t. and .

We will show that .

Since , .

Thus is transitive on .◻

6. is not an equivalence relation since it is not reflexive, symmetric, and transitive.

Example $$\PageIndex{6}$$:

Let . Define a relation on , by if and only if

Solution

1. is reflexive on .

Proof:

Let we will show that .

Clearly since and a negative integer multiplied by a negative integer is a positive integer in .

Since , is reflexive on .◻​​​​​

2. is symmetric on .

Proof:

We will show that if , then .

Let s.t. , that is .

Since , .

Since , is symmetric on .◻

3. is not antisymmetric on .

Counter Example:

Let and then and .

Since , is not antisymmetric on .◻

4. is transitive on .

Proof:

Let s.t and s.t. .

There are two cases to be examined:

Case 1: and .

Since , thus .

Case 2: and .

Since , thus .

Since in both possible cases is transitive on .◻

5. Since is reflexive, symmetric and transitive, it is an equivalence relation. Equivalence classes are and .

Let , then

.

Case 1: , then .

.

.

Case 2: , then .

.

.

Note this is a partition since or . So we have all the intersections are empty.

.

Further, we have . Note that is excluded from .

### Hasse Diagram

Consider the set $$S=\{1,2,3,4,5\}$$.  Then the relation $$\leq$$ is a partial order on $$S$$. Check!

Partial orders are often pictured using the Hasse diagram, named after mathematician Helmut Hasse (1898-1979).

Definition: Hasse Diagram

Let S be a nonempty set and let $$R$$ be a partial order relation on $$S$$. Then  Hasse diagram construction is as follows:

• there is a vertex (denoted by dots)  associated with every element of $$S$$.
• if $$a R b$$ , then the vertex $$b$$ is positioned higher than vertex  $$a$$.
• if $$a R b$$ and there is no $$c$$ such that $$a R c$$ and $$c R b$$, then a line is drawn from a to b.

This diagram is called the Hasse diagram.

##### Example $$\PageIndex{7}$$:

Hasse diagram for $$S=\{1,2,3,4,5\}$$ with the relation $$\leq$$.

Solution

##### Example $$\PageIndex{8}$$:

Show that  $$\mathbb{Z}_+$$ with the relation $$|$$ is a partial order. Draw a Hasse diagram for  $$S=\{1,2,3,4,5,6\}$$ with the relation $$|$$.

Solution

This page titled 2.2: Equivalence Relations, and Partial order is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.