# 2.2 Equivalence Relations, and Partial order

- Page ID
- 7443

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

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

Definition

An equivalence relation on a non-empty set \(S\) 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 color. 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 relations 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**