# 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

A binary relation is an equivalence relation on a non-empty set \(S\) if and only if the relation is reflexive(R), symmetric(S) and transitive(T).

Definition

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

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:

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]\).

Note

For every equivalence relations over a nonempty set \(S\), \(S\) has a partition.

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

Definition

Let S be a non empty set and let \(R\) be a partial order relation on \(S\). Then two elements \(a\) to \(b\) of \(S\) are connected if \( a R b\). This diagram is called** Hasse diagram.**