
# 2.2: Equivalence Relations, and Partial order


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:

1. Yes is reflexive.

Proof:

Let .

Then .

Hence is reflexive.◻

1. Yes is reflexive.

Proof:

Let  .

If , clearly .

Hence is symmetric.◻

1. Yes is antisymmetric.

Proof:

Let s.t. and then clearly .◻

1. Yes is transitive.

Proof:

Let s.t. and .

We shall show that .

Since and it follows that

Thus .◻

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

1. Yes, is reflexive.

Proof:

We will show that is true.

Let that is .

Since , is reflexive.◻

1. No, is not symmetric.

Counterexample:

Let and which are both .

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

Thus is not symmetric.◻

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

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

Proof

Assume is an equivalence relation on a non-empty 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 .◻

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

1. is reflexive on .

Proof:

Let .

We will show that .

Since , then .

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

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

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.