
# 2.2 Equivalence Relations and Partial order

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

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

Definition

An equivalence relation is a relation that is reflexive(R), symmetric(S) and transitive(T).

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

Definition

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{2}$$:

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

Equivalence classes are:

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

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

Equivalence classes are:

Theorem:

If $$R$$  is an equivalence relation over a non-empty set $$S$$, then every $$a \in S$$  belongs to exactly one equivalence class.

Theorem $$\PageIndex{1}$$

If $$R$$  is an equivalence relation over a non-empty set $$S$$. Then

Then the set of all equivalence classes is denoted by  $$\{[a]| 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

Add proof here and it will automatically be hidden if you have a "AutoNum" template active on the page.

Note

For every equivalence class over $$S$$,  $$S$$ has a partition.

Definition

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

Example $$\PageIndex{4}$$: $$\leq$$

Definition

Hasse diagram