Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

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:

    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.