Search

Text Color

Margin Size

Font Type

Enable Dyslexic Font

2.2: Equivalence Relations, and Partial order

Last updated

Nov 22, 2024
Save as PDF
- 2.1: Binary Relations
- 2.3: Arithmetic of inequality

$\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}$ . Define a relation $R$ on $S$ by $a R b$ if and only if $a=b.$ Is the relation $R$ on $S$ ,

a) reflexive, b) symmetric, c) antisymmetric, d) transitive, e) an equivalence relation, f) a partial order.

Solution:

$R$ is reflexive.

Proof:

Let $a \in \mathbb{R}$ . Since $a=a$ , $R$ is reflexive.◻

2. $R$ is symmetric.

Proof:

Let $a,b \in \mathbb{R}$ such that $a R b.$ Now, $a=b \implies b=a$ . Thus $b R a.$ Hence $R$ is symmetric.◻

3. $R$ is antisymmetric.

Proof:

Let s.t. and then clearly .◻

Yes is transitive.

Proof:

Let s.t. and .

We shall show that .

Since and it follows that

Thus .◻

Yes is an equivalence relation.

Proof:

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

4. Yes is a partial order.

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

Yes, is reflexive.

Proof:

We will show that is true.

Let that is .

Since , is reflexive.◻

No, is not symmetric.

Counterexample:

Let and which are both .

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

Thus is not symmetric.◻

Yes, is antisymmetric.

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 .◻

5. No, is not an equivalence relation on since it is not symmetric.

6. Yes, is a partial order on since it is reflexive, antisymmetric and transitive.

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:

$alt$

Example $\PageIndex{4}$ :

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

Equivalence classes are:

$alt$

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.$

Solution

is reflexive on .

Proof:

Let .

We will show that .

Since , .

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

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

$Hasse_1.png$

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

$hasse_2.png$

Definition: Partition

Hasse Diagram

Example 2.2.7\PageIndex{7}:

Example 2.2.8\PageIndex{8}:

Support Center

How can we help?

Example $\PageIndex{7}$ :

Example $\PageIndex{8}$ :