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

  • Page ID
    7426
  • [ "stage:draft", "article:topic", "authorname:thangarajahp", "Binary Relations", "license:ccbyncsa", "showtoc:yes" ]

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

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

    Definition

    Let \(S\) be a set. Then any subset \(R\) of \(S \times S\) is said to be a relation over \(S\).  In other words,  a relation is a rule that is defined between two elements in \(S\).  Intuitively,  if \(R\) is a relation over \(S\), then the statement  \(a R b\)  is either  true  or false for all \(a,b\in S\).

    Example \(\PageIndex{1}\):

    Let \(S=\{1,2,3\}\).  Define \(R\) by \(a R b\) if and only if \(a < b\), for \(a, b \in S\).

    Then  \(1 R 2, 1 R 3, 2 R 3 \) and \( 2 \not R 1\).

     We can visualize the above binary relation as a graph, where the vertices are the elements of S, and there is an edge from \(a\)  to \(b\) if and only if  \(a R b\) , for \(a,b\in S\).

    sog8mVfmrjo7_-GoB-mBjEQ.png

    The following are some examples of relation defined on \(\mathbb{Z}\).

    Example \(\PageIndex{2}\):

    1. Define \(R\) by \(a R b\) if and only if \(a < b\), for \(a, b \in \mathbb{Z}\).
    2. Define \(R\) by \(a R b\) if and only if \(a >b\), for \(a, b \in \mathbb{Z}\).
    3. Define \(R\) by \(a R b\) if and only if \(a \leq b\), for \(a, b \in \mathbb{Z}\).
    4. Define \(R\) by \(a R b\) if and only if \(a \geq b\), for \(a, b \in \mathbb{Z}\).
    5. Define \(R\) by \(a R b\) if and only if \(a = b\), for \(a, b \in \mathbb{Z}\).

    Next, we will introduce the notion of "divides".

    Definition

    Let \( a\) and \(b\) be integers.  We say that \(a\) divides \(b\) is denoted \(a\mid b\), provided we have an integer \(m\) such that \(b=am\).  In this case we can also say the following:

    • \(b\) is divisible by \(a\)
    • \(a\) is a factor of \(b\)
    • \(a\) is a divisor of \(b\)

    Example \(\PageIndex{3}\):

    \(4 \mid  12\) and  \(12 \not\mid 4\)

     Note that if  \(a\mid b\), for \(a, b \in \mathbb{Z_+}\) then  \(a \leq b\), but the converse is not true.  For example: \(2 <3\), but  \(2 \not\mid 3\).

    Example \(\PageIndex{4}\):

    According to our definition \(0 \mid 0\).

    Definition

    An integer is even provided that it is divisible by \(2\).

    Properties: 

    Definition

    Let \(S\) be a set and \(R\) be a binary relation on \(S\).  Then \(R\)  is said to be reflexive if  \( a R a, \forall a \in S.\) 

    Example \(\PageIndex{5}\): Visually

    Pamini Thangarajah

    \(\forall  a \in S,  a R a\) holds.

    We will follow the template below to answer the question about reflexive.

    Example \(\PageIndex{6}\):

    Define \(R\) by \(a R b\) if and only if \(a < b\), for \(a, b \in \mathbb{Z}\).  Is \(R\) reflexive?

    Counter Example:

    Choose \(a=2.\)

    Since \( 2 \not< 2\), \(R\) is not reflexive.

    Example \(\PageIndex{7}\):

    Define \(R\) by \(a R b\) if and only if \(a \mid b\), for \(a, b \in \mathbb{Z}\).  Is \(R\) reflexive?

    Proof: 

    Let \( a \in  \mathbb{Z}\). Since \(a=(1) (a)\),  \(a \mid a\).

    Thus \(R\)  is reflexive. \( \Box\)

    Definition

    Let \(S\) be a set and \(R\) be a binary relation on \(S\).  Then \(R\)  is said to be symmetric if the following statement is true:

    \( \forall a,b \in S\), if  \( a R b \) then \(b R a\),  in other words, \(   \forall a,b \in S, a R b \implies b R a.\)

    Example \(\PageIndex{8}\): Visually

    \(\forall a,b \in S, a R b \implies b R a.\) holds!

     We will follow the template below to answer the question about symmetric.

    stXO_6c-DcCh0t5duFY2Ejw.png 

    Example \(\PageIndex{7}\):

    Define \(R\) by \(a R b\) if and only if \(a < b\), for \(a, b \in \mathbb{Z}\).  Is \(R\) symmetric?

    Counter Example:

    \(1<2\) but \(2 \not < 1\).

    Example \(\PageIndex{8}\):

    Define \(R\) by \(a R b\) if and only if \(a \mid b\), for \(a, b \in \mathbb{Z}\).  Is \(R\) symmetric?

    Counter Example:

    \(2 \mid 4\) but \(4 \not \mid 2\).

    Definition

    Let \(S\) be a set and \(R\) be a binary relation on \(S\).  Then \(R\)  is said to be antisymmetric if the following statement is true: 

    \( \forall a,b \in S\),  if  \( a R b \) and \(b R a\), then \(a=b\).

    In other words, \( \forall a,b \in S\), \( a R b \wedge b R a  \implies  a=b.\)

    Example \(\PageIndex{9}\): VISUALLY

     \( \forall a,b \in S\), \( a R b \wedge b R a  \implies  a=b \) holds!

    We will follow the template below to answer the question about anti-symmetric.

     

    Example \(\PageIndex{10}\):

    Define \(R\) by \(a R b\) if and only if \(a < b\), for \(a, b \in \mathbb{Z}\).  Is \(R\) antisymmetric?

    Example \(\PageIndex{11}\):

    Define \(R\) by \(a R b\) if and only if \(a \mid b\), for \(a, b \in \mathbb{Z_+}\).  Is \(R\) antisymmetric?

    Definition

    Let \(S\) be a set and \(R\) be a binary relation on \(S\).  Then \(R\)  is said to be transitive if the following statement is true

     \( \forall a,b,c \in S,\) if  \( a R b \) and \(b R c\), then \(a R c\) .

    In other words,   \( \forall a,b,c \in S\), \( a R b \wedge b R c  \implies  a R c\).

    Example \(\PageIndex{12}\): VISUALLY

     \( \forall a,b,c \in S\), \( a R b \wedge b R c  \implies  a R c\) holds!

     We will follow the template below to answer the question about transitive.

    ssUmTK4d9hHGQc-mZjO6p5g.png

    Example \(\PageIndex{13}\):

    Define \(R\) by \(a R b\) if and only if \(a < b\), for \(a, b \in \mathbb{Z}\).  Is \(R\) transitive?

    Example \(\PageIndex{14}\):

    Define \(R\) by \(a R b\) if and only if \(a \mid b\), for \(a, b \in \mathbb{Z_+}\).  Is \(R\) transitive?

    Summary:

    In this section we learned about binary relation and the following properties:

    Reflexive

    Symmetric

    Antisymmetric

    Transitive