Properties of Relations: Reflexive, Symmetric, & Transitive
Define the Reflexive property for a relation \(R\) on a set \(A\) using formal notation.
A relation \(R\) on \(A\) is reflexive if: \[\forall x \in A, (x, x) \in R\] In a directed graph, this means every vertex has a self-loop.
Define the Symmetric property for a relation \(R\) on a set \(A\).
A relation \(R\) on \(A\) is symmetric if: \[\forall x, y \in A, \text{ if } (x, y) \in R, \text{ then } (y, x) \in R\] In a directed graph, if there is an arrow from \(x\) to \(y\), there must be a return arrow from \(y\) to \(x\).
Define the Transitive property for a relation \(R\) on a set \(A\).
A relation \(R\) on \(A\) is transitive if: \[\forall x, y, z \in A, \text{ if } (x, y) \in R \text{ and } (y, z) \in R, \text{ then } (x, z) \in R\] In a directed graph, if you can go from \(x\) to \(y\) and \(y\) to \(z\), there must be a direct shortcut from \(x\) to \(z\).
Let \(A = \{1, 2, 3\}\). Is \(R = \{(1, 1), (2, 2)\}\) reflexive on \(A\)?
No. For \(R\) to be reflexive on \(A\), every element in \(A\) must be related to itself. Since \((3, 3) \notin R\), the relation is not reflexive.
Consider \(A = \{1, 2, 3\}\) and \(R = \{(1, 2), (2, 1), (1, 1)\}\). Is \(R\) symmetric?
Yes. - For \((1, 2)\), the reverse \((2, 1)\) is in \(R\). - For \((2, 1)\), the reverse \((1, 2)\) is in \(R\). - For \((1, 1)\), the reverse is itself, which is in \(R\).
Let \(R\) be the relation on \(\mathbb{Z}\) defined by \(xRy \iff x < y\). Is \(R\) reflexive?
No. For any \(x \in \mathbb{Z}\), it is never true that \(x < x\). Therefore, \((x, x) \notin R\) for any \(x\).
Let \(R\) be the relation on \(\mathbb{Z}\) defined by \(xRy \iff x \le y\). Is \(R\) transitive?
Yes. If \(x \le y\) and \(y \le z\), then by the transitive property of real numbers, \(x \le z\). Thus, if \((x, y) \in R\) and \((y, z) \in R\), then \((x, z) \in R\).
What is the transitive closure of the relation \(R = \{(1, 2), (2, 3)\}\)?
The transitive closure \(R^t\) is the smallest transitive relation containing \(R\). We must add \((1, 3)\) to satisfy transitivity. \[R^t = \{(1, 2), (2, 3), (1, 3)\}\]
In a directed graph, how do you visually identify a symmetric relation?
Every edge between two distinct vertices must be “double-headed” (or have two arrows, one in each direction). If there is an arrow from \(u\) to \(v\), there must be one from \(v\) to \(u\).
Is the relation \(R = \{(1, 2), (2, 1)\}\) transitive on the set \(A = \{1, 2\}\)?
No. Since \((1, 2) \in R\) and \((2, 1) \in R\), transitivity requires that \((1, 1)\) must be in \(R\). Since \((1, 1) \notin R\), it is not transitive. (Similarly, \((2, 2)\) is also missing).
Prove that \(xRy \iff 3 \mid (x - y)\) is symmetric.
Let \(R\) be a relation on \(A = \{a, b, c\}\) represented by this matrix:
Is this relation reflexive, symmetric, and/or transitive?
All three. - Reflexive: Diagonal is all 1s. - Symmetric: The matrix is equal to its transpose. - Transitive: If \(xRy\) and \(yRz\), then \(x=y\) and \(y=z\), so \(x=z\). (This is the Equality relation).
If a relation is symmetric, does it have to be reflexive?
No. Example: \(A = \{1, 2\}\) and \(R = \{(1, 2), (2, 1)\}\). It is symmetric, but not reflexive because \((1, 1)\) and \((2, 2)\) are missing.
Determine if \(aRb \iff a+b\) is even is transitive on \(\mathbb{Z}\).
Yes. \(a+b\) is even \(\implies a, b\) have the same parity (both even or both odd). If \(a, b\) same parity and \(b, c\) same parity, then \(a, c\) must have the same parity. Therefore \(a+c\) is even.
True or False: A relation that is not symmetric must be “anti-symmetric.”
False. Symmetry and Anti-symmetry are not opposites. A relation can be: - Both (e.g., \(\{(1, 1)\}\)) - Neither (e.g., \(\{(1, 2), (2, 1), (2, 3)\}\)) - Just one or the other.