Properties of binary relations

Subsection 6.1.2 Properties of binary relations

Definition 6.1.2.1.

A relation \(R\) on a set \(A\) is reflexive if, for every \(a\) in \(A\text{,}\) we must have \(aRa\)

🔗

Proof Technique 6.1.2.2. Show \(R\) is reflexive.

Suppose \(R\) is a relation on a set \(A\text{,}\) and we want to prove \(R\) is reflexive.

Fix a generic element \(a\) in \(A\text{.}\)
🔗

🔗
Deduce \(aRa\text{.}\)
🔗

🔗
Conclude \(R\) is reflexive.
🔗

🔗

🔗

Definition 6.1.2.3.

A relation \(R\) on a set \(A\) is symmetric if, for every \(a\) and \(b\) in \(A\text{,}\) whenever \(bRa\) , we must have \(a\,R\,b\text{.}\)

🔗

Proof Technique 6.1.2.4. Show \(R\) is symmetric.

Suppose \(R\) is a relation on a set \(A\text{,}\) and we want to prove \(R\) is symmetric.

Fix generic elements \(a\) and \(b\) in \(A\) such that
🔗

🔗
Deduce \(b R a\text{.}\)
🔗

🔗
Conclude \(R\) is symmetric.
🔗

🔗

🔗

Definition 6.1.2.5.

A relation \(R\) on a set \(A\) is antisymmetric if, for any \(a\) and \(b\) in \(A\text{,}\) whenever \(a\,R\,b\) and \(bRa\text{,}\) we must have \(a=b\text{.}\)

🔗

Definition 6.1.2.6.

A relation \(R\) on a set \(A\) is transitive of \(a\,R\,b\) if, for every \(a\text{,}\) \(b\text{,}\) and \(c\) in \(A\text{,}\) whenever \(a\,R\,b\) and \(bRc\text{,}\) we must have \(aRc\text{.}\)

🔗

Proof Technique 6.1.2.7. Show \(R\) is transitive.

Suppose \(R\) is a relation on a set \(A\text{,}\) and we want to prove \(R\) is transitive.

Fix generic elements \(a\text{,}\) \(b\text{,}\) and \(c\) in \(A\) such that
🔗

🔗
Deduce \(aRc\text{.}\)
🔗

🔗
Conclude \(R\) is transitive.
🔗

🔗

🔗

Example 6.1.2.8. Less than or equal to.

Let \(R\) be the relation on \(\ZZ\) defined by \(\leq\text{,}\) so that \(a\,R\,b\) if and only if \(a\leq b\text{.}\)

Since \(a\leq a\) for every integer \(a\text{,}\) we have \(aRa\) for
🔗

🔗
Since \(1\leq 2\text{,}\) but \(2 \not\leq 1\text{,}\) we have \(1R2\) but not
🔗

🔗
Whenever \(a\leq b\) and \(b\leq a\text{,}\) we must have \(a = b\text{.}\)
🔗

🔗
Whenever \(a\leq b\) and \(b\leq c\text{,}\) we must have \(a\leq c\text{.}\)
🔗

🔗

🔗

Example 6.1.2.9. Non-reflexive, non-antisymmetric, but transitive.

Let \(R\) be the relation on \(\{1,2,3,4\}\) that is given by

\begin{equation*} R = \{(2,2), (2,3),(2,4),(3,2),(3,3),(3,4)\}. \end{equation*}

Then \(R\) is not reflexive since \((1,1)\) is not in \(R\text{.}\) It is not symmetric since \((2,4)\) is in \(R\) but \((4,2)\) is not in \(R\text{.}\) It is not antisymmetric since \((2, 3)\) is in \(R\) and \((3,2)\) is in \(R\text{,}\) but \(2 \neq 3\text{.}\) It is transitive since if \((a,b)\) is in \(R\) and \((b,c)\) is in \(R\text{,}\) then \((a,c)\) is in \(R\text{.}\)

🔗

Example 6.1.2.10. Non-reflexive, non-symmetric, non-transitive.

Let \(R\) be the relation on \(\{1,2,3,4\}\) that is given by

\begin{equation*} R = \{(1,3), (1,4),(2,3),(2,4),(3,1),(3,4)\}. \end{equation*}

Then \(R\) is not reflexive since \((1,1)\) is not in \(R\text{.}\) It is not symmetric since \((1,4)\) is in \(R\text{,}\) but \((4,1)\) is not in \(R\text{.}\) It is not antisymmetric since \((1,3)\) is in \(R\) and \((3,1)\) is in \(R\text{,}\) but \(1 \neq 3\text{.}\) It is not transitive since \((1,3)\) is in \(R\) and \((3,1)\) is in \(R\text{,}\) but \((1,1)\) is not in \(R\text{.}\)

🔗

Example 6.1.2.11. Reflexive, symmetric, transitive, non-antisymmetric.

Let \(R\) be the relation on \(\{1,2,3,4\}\) that is given by

\begin{equation*} R = \{(1,1), (1,2),(2,1),(2,2),(3,3),(4,4)\}. \end{equation*}

Then \(R\) is reflexive since \((1,1)\text{,}\) \((2,2)\text{,}\) \((3,3)\text{,}\) and \((4,4)\) are all in \(R\text{.}\) It is symmetric because whenever \((a,b)\) is in \(R\text{,}\) we have \((b,a)\) is in \(R\text{.}\) It is transitive since if \((a,b)\) is in \(R\) and \((b,c)\) is in \(R\text{,}\) then \((a,c)\) is in \(R\text{.}\) It is not antisymmetric since \((1,2)\) is in \(R\) and \((2,1)\) is in \(R\text{,}\) but \(1 \neq 2\text{.}\)

🔗

Prev Top Next