# 2.2: Equivalence Relations, and Partial order

- Page ID
- 7443

This page is a draft and is under active development.

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**:

**Proof**:

**Proof**:

**Proof**:

**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**:

**Counterexample**:

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

**Proof**:

We will show that given and that .

**Proof**:

We will show that given and that .

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:

Example \(\PageIndex{4}\):

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

Equivalence classes are:

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,

Let be the common element between them.

Then and , which means that and .

Since is an equivalence relation and .

Since and (due to transitive property), .

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**

**Proof**:

**Counter Example**:

Since , is not symmetric on .◻

**Proof:**

Thus is antisymmetric on .◻

5. is transitive on .

**Proof:**

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**

**Proof**:

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**:

**Counter Example**:

Since , is not antisymmetric on .◻

**Proof**:

There are two cases to be examined:

Since in both possible cases is transitive on .◻

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

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

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

**Solution**

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**