KindiakMath

Redefining Special Relations

In all the problems that follow, let R be a relation on a set K, and \mathrm{id}_K denote the identity relation on K.

Problem 1. Prove that R is reflexive if and only if \mathrm{id}_K \subseteq R.

(Click for Solution)

Solution. Let \phi(R) denote the predicate “R is reflexive”. We observe that

\begin{aligned}\phi(R) \quad &\iff \quad \forall x \in K\quad (x,x) \in R \\ &\iff \quad \forall x,y\in K\quad (x,y) \in \mathrm{id}_K \Rightarrow (x,y) \in R \\ &\iff \quad \forall u \in K \times K \quad u \in \mathrm{id}_K \Rightarrow u \in R \\ &\iff \quad \mathrm{id}_K \subseteq R.\end{aligned}

Problem 2. Prove that R is symmetric if and only if R \subseteq R^{-1}.

(Click for Solution)

Solution. The result follows from the observation

(x,y) \in R \Rightarrow (y,x) \in R\quad \iff \quad (x,y) \in R \Rightarrow (x,y) \in R^{-1}.

Remark. We can strengthen the right-hand side to R = R^{-1} since we can prove that R \subseteq R^{-1} \Rightarrow R^{-1} \subseteq R, left as an exercise.

Problem 3. Prove that R is antisymmetric if and only if R \cap R^{-1} \subseteq \mathrm{id}_K.

(Click for Solution)

Solution. We first observe that

\begin{aligned} (x,y) \in R \wedge (y,x) \in R \quad &\iff \quad (x,y) \in R \wedge (x,y) \in R^{-1} \\& \iff \quad (x,y) \in R \cap R^{-1} \end{aligned}

and

x=y \quad \iff \quad (x,y) = (x,x) \quad \iff \quad (x,y) \in \mathrm{id}_K.

Thus, antisymmetry is equivalent to the implication

(x,y) \in R \cap R^{-1} \quad \Rightarrow \quad \quad (x,y) \in \mathrm{id}_K,

which is equivalent to R \cap R^{-1} \subseteq \mathrm{id}_K.

Corollary 1. If R is symmetric and antisymmetric, then R \subseteq \mathrm{id}_K. In this case, R is reflexive if and only if R = \mathrm{id}_K.

Problem 4. Prove that R is transitive if and only if R \circ R \subseteq R.

(Click for Solution)

Solution. For any x,z \in K, we observe that

(x,z) \in R \circ R\quad \iff \quad (\exists y \in K : (x,y) \in R \wedge (y,z) \in R).

If R is transitive, then the right-hand side implies (x, z) \in R, which proves R \circ R \subseteq R. If R \circ R \subseteq R, then the left-hand side implies R is transitive.

—Joel Kindiak, 9 Feb 25, 1343H

,

Published by

joelkindiak

Leave a comment