7 Connect Everything
7.1 Preorders
7.2 Equivalence Relations
7.2.1 The Reflexive, Symmetric, and Transitive Properties
Definition 7.1 Let \(X\) be a set.
- A relation \(R\) on \(X\) is called reflexive if it satisfies the property \[\forall a\in X, (a,a)\in R.\]
- A relation \(R\) on \(X\) is called symmetric if it satisfies the property \[ \forall a,b \in X, (a,b)\in R \implies (b,a)\in R. \]
- A relation \(R\) on \(X\) is called transitive if it satisfies the property \[\forall a,b,c\in X, ((a,b)\in R \land (b,c)\in R) \implies (a,c)\in R.\]
Theorem 7.1 Let \(R\) and \(S\) be relations on \(X\) and let \(A\subseteq X.\)
- A relation \(R\) is reflexive if and only if \(I \subseteq R.\)
- A relation \(R\) is symmetric if and only if \(R^{-1}\subseteq R.\)
- A relation \(R\) is transitive if and only if \(R\circ R\subseteq R.\)
Proof. The proof of each part follows.
If \(R\) is reflexive, then \(I\subseteq R.\) \[ (x,y)\in I \Leftrightarrow y=x \implies (x,y)\in R \] Conversely, if \(I\subseteq R\), then \(R\) is reflexive. \[ x\in X \implies (x,x)\in I \implies (x,x)\in R \]
If \(R\) is symmetric, then \(R^{-1}\subseteq R.\) \[ (x,y)\in R^{-1}\Leftrightarrow (y,x)\in R \implies (x,y)\in R \] Conversely, if \(R^{-1}\subseteq R\), then \(R\) is symmetric. \[ (x,y)\in R \implies (y,x)\in R^{-1} \implies (y,x)\in R \]
If \(R\) is transitive, then \(R\circ R\subseteq R.\) \[ (x,y)\in R\circ R \Leftrightarrow \exists x\in X, (x,z)\in R \land (z,y)\in R \implies (x,y)\in R \] Conversely, if \(R\circ R\subseteq R\), then \(R\) is transitive. \[ (x,y)\in R \land (y,z)\in R \implies (x,z)\in R\circ R \implies (x,z)\in R. \] The proof is now complete.
Theorem 7.2 If \(R\) and \(S\) are reflexive, then \(R|_A\), \(R^{-1}\), \(S\circ R\), \(R\cup S\), and \(R\cap S\) are also reflexive, while \(R^c\) is not reflexive.
Proof. We find that \(R|_A\), \(R^{-1}\), \(S\circ R\), \(R\cup S\), and \(R\cap S\) are reflexive, whenever \(R\) and \(S\) are reflexive by the following arguments, respectively.
- \((x,x)\in R \land A\subseteq X \implies (x,x)\in R|_{A}\)
- \((x,x)\in R \implies (x,x)\in R^{-1}\)
- \((x,x)\in R \land (x,x)\in S \implies (x,x)\in S\circ R\)
- \((x,x)\in R \land (x,x)\in S \implies (x,x)\in R\cup S\)
- \((x,x)\in R \land (x,x)\in S \implies (x,x)\in R\cap S\)
Notice that \(R^c\) is not reflexive because \(I\subseteq R\implies I\not\subseteq R^c.\)
Theorem 7.3 If \(R\) and \(S\) are symmetric, then \(R|_A\), \(R^c\), \(R^{-1}\), \(R^{-1}\circ R\), \(R\cup S\), and \(R\cap S\) are also symmetric.
Proof. If \(R\) is symmetric, then \(R|_{A}\) is symmetric. \[\begin{align*} \qquad \qquad& (x,y)\in R|_A \Longleftrightarrow (x,y) \in (A\times A) \cap R \\ & \qquad \Longleftrightarrow (x,y)\in A\times A \land (x,y)\in R \Longleftrightarrow (y,x)\in A\times A \land (y,x)\in R \\ & \qquad \Longleftrightarrow (y,x) \in (A\times A) \cap R \Longleftrightarrow (x,y)\in R|_A \end{align*}\]
If \(R\) is symmetric, then \(R^c\) is symmetric. \[\begin{align*} & (x,y)\in R^c \Longleftrightarrow (x,y)\notin R \Longleftrightarrow \neg ((x,y)\in R) \\ & \qquad \Longleftrightarrow \neg( (y,x)\in R) \Longleftrightarrow (y,x)\notin R \Longleftrightarrow (y,x)\in R^c \end{align*}\]
If \(R\) is symmetric, then \(R^{-1}\) is symmetric. \[\begin{align*} \qquad (x,y)\in R^{-1} \Longleftrightarrow (y,x)\in R \Longleftrightarrow (x,y)\in R \Longleftrightarrow (y,x)\in R^{-1} \end{align*}\]
If \(R\) and \(S\) are symmetric, then \(R\cup S\) is symmetric. \[\begin{align*} \qquad & (x,y)\in R\cup S \Longleftrightarrow (x,y)\in R \lor (x,y)\in S \\ & \qquad \Longleftrightarrow (y,x)\in R \lor (y,x)\in S \Longleftrightarrow (y,x)\in R\cup S \end{align*}\]
If \(R\) and \(S\) are symmetric then the relation \(R\cap S\) is symmetric. \[\begin{align*} \qquad & (x,y)\in R\cap S \Longleftrightarrow (x,y)\in R \land (x,y)\in S\\ & \qquad \Longleftrightarrow (y,x)\in R \land (y,x)\in S \Longleftrightarrow (y,x)\in R\cap S \end{align*}\]
If \(R\) is symmetric, then \(R^{-1}\circ R\) is symmetric. \[\begin{align*} \qquad \qquad & (x,y)\in R^{-1}\circ R \Longleftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in R^{-1} \\ & \qquad \Longleftrightarrow \exists z\in X, (z,x)\in R^{-1} \land (y,z)\in R \\ & \qquad \Longleftrightarrow \exists z\in X, (y,z)\in R \land (z,x)\in R^{-1} \Longleftrightarrow (y,x)\in R^{-1}\circ R \end{align*}\]
The proof is now complete.
Theorem 7.4 Let \(R\) and \(S\) be relations on \(X\) and let \(A\subseteq X.\) If \(R\) and \(S\) are transitive, then \(R|_A\), \(R^{-1}\), \(R^2\), and \(R\cap S\) are also transitive, while \(R^c\) and \(R\cup S\) are not transitive.
Proof. If \(R\) is transitive, then \(R|_{A}\) is transitive. \[\begin{align*} \qquad \qquad & (x,y)\in R|_A \land (y,z)\in R|_A \\ & \qquad \Longleftrightarrow [(x,y)\in A\times A \land (x,y)\in R] \land [(y,z)\in A\times A \land (y,z)\in R]\\ & \qquad \Longleftrightarrow (x,z)\in A\times A \land (x,z)\in R \\ & \qquad \Longleftrightarrow (x,z)\in (A\times A) \cap R \Longleftrightarrow (x,z)\in R|_A \end{align*}\]
If \(R\) is transitive, then \(R^{-1}\) is transitive. \[\begin{align*} \qquad \qquad & (x,y)\in R^{-1} \land (y,z)\in R^{-1} \Longleftrightarrow (y,x)\in R \land (z,y)\in R \\ & \qquad \Longleftrightarrow (z,y)\in R \land (y,x) \in R \Longleftrightarrow (z,x)\in R \Longleftrightarrow (x,z)\in R^{-1} \end{align*}\]
If \(R\) is transitive, then \(R^2\) is transitive. \[\begin{align*} \quad \qquad \qquad & (x,y)\in R^2 \land (y,z)\in R^2 \\ & \Longleftrightarrow [\exists s\in X, (x,s)\in R \land (s,y)\in R] \land [\exists t\in X, (y,t)\in R \land (t,z)\in R] \\ & \Longleftrightarrow \exists s,t\in X, (x,s)\in R \land (s,y)\in R \land (y,t)\in R \land (t,z)\in R\\ & \Longleftrightarrow \exists s,t\in X, (x,s)\in R\land (s,t)\in R \land (t,z)\in R \\ & \Longleftrightarrow (x,t) \in R \land (t,z)\in R \Longleftrightarrow (x,z)\in R^2 \end{align*}\]
If \(R\) and \(S\) are transitive then the relation \(R\cap S\) is transitive. \[\begin{align*} & (x,y)\in R\cap S \land (y,z)\in R\cap S\\ & \qquad \Longleftrightarrow (x,y)\in R \land (x,y)\in S \land (y,z)\in R \land (y,z)\in S \\ & \qquad \Longleftrightarrow (x,z)\in R \land (x,z)\in S \Longleftrightarrow (x,z)\in R\cap S \end{align*}\]
If \(R\) and \(S\) are transitive then the relation \(R\cup S\) is not necessarily transitive. To see this let \(X=\{a,b,c\}\), \(R=\{(a,b),(b,c),(a,c)\}\) and \(S=\{(b,c),(c,d),(b,d)\}.\) Then \(R\) and \(S\) are transitive, however, \(R\cup S\) is not transitive since \((a,b), (b,d)\in R\cup S\) yet \((a,d)\notin R\cup S.\) If \(R\) is transitive then \(R^c\) is not necessarily transitive. To see this let \(X=\{a,b\}\) and \(R=I.\) The \(R\) is transitive and \(R^c=\{(a,b),(b,a)\}\) which is not transitive.
Definition 7.2 If a relation is reflexive, symmetric, and transitive, then it is called an equivalence relation.
Theorem 7.5 Let \(R\) and \(S\) be equivalence relations on \(X\) and let \(A\subseteq X.\) Then \(R|_A\), \(R^{-1}\), \(R^2\), and \(R\cap S\) are also equivalence relations.
Proof. The proof is left as Exercise 7.1.
Theorem 7.6 Let \(R\) and \(S\) be relations on \(X\) and let \(A\subseteq X.\)
- If \(R\) and \(S\) are symmetric, then \(S\circ R\) is symmetric if and only if \(R\circ S\subseteq S\circ R.\)
- If \(R\) and \(S\) are transitive and \(R\circ S\subseteq S\circ R\), then \(S\circ R\) is transitive, but not conversely.
- If \(R\) and \(S\) are equivalence relations, then \(S\circ R\) is an equivalence relation if and only if \(R\circ S\subseteq S\circ R.\)
Proof. The proof of each part follows.
- If \(R\) and \(S\) are symmetric and \(R\circ S\subseteq S\circ R\), then \(S\circ R\) is symmetric. \[\begin{align*} \qquad & (x,y)\in S\circ R \Longleftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in S \\ & \qquad \Longleftrightarrow \exists z\in X, (z,x)\in R \land (y,z)\in S \\ & \qquad \Longleftrightarrow \exists z\in X, (y,z)\in S \land (z,x)\in R \Longleftrightarrow (y,x)\in R\circ S\\ & \qquad \Longleftrightarrow (y,x)\in S\circ R \end{align*}\]
Conversely, assume \(R\), \(S\), and \(S\circ R\) are symmetric, then \(S\circ R=R\circ S.\) \[\begin{align*} \qquad & (x,y)\in S\circ R \Longleftrightarrow (y,x)\in S\circ R \\ & \qquad \Longleftrightarrow \exists z\in X, (y,z)\in R \land (z,x)\in S \\ & \qquad \Longleftrightarrow \exists z\in X, (z,y)\in R \land (x,z)\in S \\ & \qquad \Longleftrightarrow \exists z\in X, (x,z)\in S \land (z,y)\in R \Longleftrightarrow (x,y)\in R\circ S \end{align*}\]
- If \(R\) and \(S\) are transitive and \(R\circ S\subseteq S\circ R\), then \(S\circ R\) is transitive. \[\begin{align*} & (x,y)\in S\circ R \land (y,z)\in S\circ R \\ & \Longleftrightarrow [\exists s\in X, (x,s)\in R\land (s,y)\in S] \land [\exists t\in X, (y,t)\in R \land (t,z)\in S] \\ & \Longleftrightarrow \exists s,t\in X, (x,s)\in R \land (s,y)\in S \land (y,t)\in R \land (t,z)\in S \\ & \Longleftrightarrow \exists s,t,\in X, (x,s)\in R \land (s,t)\in R\circ S \land (t,z)\in S \\ & \Longleftrightarrow \exists s,t\in X, (x,s)\in R \land (s,t)\in S\circ R \land (t,z)\in S \\ & \Longleftrightarrow \exists s,t,w\in X, (x,s)\in R \land (s,w)\in R \land (w,t)\in S \land (t,z)\in S \\ & \Longleftrightarrow \exists w\in X, (x,w)\in R \land (w,z)\in S \Longleftrightarrow (x,z)\in S\circ R \end{align*}\]
Let \(X=\{a,b,c\}\), \(R=\{(a,a), (a,b)\}\), and \(S=\{(b,b),(b,c)\}.\) Then \(R\) and \(S\) are transitive and so is \(S\circ R=\{(a,b),(a,c)\}.\) However, \(R\circ S=\emptyset.\)
- If \(R\), \(S\), and \(S\circ R\) are equivalence relations on \(X\), then \(R\circ S \subseteq S\circ R.\) \[\begin{align*} \qquad S\circ R & \textrm{ is an equivalence relation} \\ & \Longleftrightarrow S\circ R \textrm{ is reflexive, symmetric, and transitive} \\ & \Longrightarrow S\circ R \textrm{ is symmetric } \Longleftrightarrow R\circ S \subseteq S\circ R \end{align*}\]
Conversely, if \(R\) and \(S\) are equivalence relations and \(R\circ S\subseteq S\circ R\), then \(S\circ R\) is an equivalence relation. \[\begin{align*} \qquad & R\circ S \subseteq S\circ R \land S, R \textrm{ are equivalence relations} \\ & \qquad \Longrightarrow S\circ R \textrm{ is reflexive, symmetric, and transitive } \\ & \qquad \Longleftrightarrow S\circ R \textrm{ is an equivalence relation } \end{align*}\] which completes the proof.
A beautiful concise characterization of equivalence relation is here in the next theorem.
::: {#thm-understanding-of-equivalence relation } Let \(R\) be a relation on \(X.\) Then \(R\) is an equivalence relation if and only if \[ R=I\cup R^{-1} \cup R^2. \] :::
Proof. Let \(R\) be a relation on \(X.\) If \(R\) is reflexive, symmetric, and transitive it follows \(I\subseteq R\), \(R^{-1} =R\), and \(R^2=R\); and thus \(I\cup R^{-1}\cup R^2=R.\) Conversely, assume \(R\) be a relation on \(X.\) If \(I\cup R^{-1}\cup R^2=R\), then \(I\subseteq R\), \(R^{-1} \subseteq R\), and \(R^2\subseteq R\); and therefore \(R\) is an equivalence relation.
Another characterization of equivalence relation is here in the next theorem.
Theorem 7.7 Let \(\sim\) be a relation on \(X.\) Then \(\sim\) is an equivalence relation if and only if the following property holds: \[\begin{equation} \forall \, a,b\in X, a\sim b \Leftrightarrow \forall \, c\in X, a\sim c \Leftrightarrow b\sim c. \end{equation}\]
Proof. Assume \(\sim\) is an equivalence relation on \(X.\) Assume \(a\sim b\) for arbitrary \(a,b\in X.\) Let \(c\in X.\) By symmetry and transitivity it follows that \[ a\sim c \implies c\sim a \implies c\sim b \implies b\sim c \] and conversely, \(b\sim c \implies a\sim c\) follows by transitivity. Therefore, by symmetry and transitivity we have \[ \forall a,b \in X, a\sim b \implies \forall c\in X, a\sim c \Leftrightarrow b\sim c. \] Assume for all \(c\in X\) that \(a\sim c \Leftrightarrow b\sim c.\) Let \(c=a.\) Then we have \(a\sim a \Leftrightarrow b\sim a.\) Since \(\sim\) is reflexive, \(a\sim b\) must hold. Whence, \[ \forall c\in X, (a\sim c \Leftrightarrow b\sim c) \implies a\sim b \] as desired.
Conversely, assume the given property holds. To show reflexivity, let \(a\in X.\) Since, \(a\sim a\) if and only if \(a\sim a\), obviously holds, it follows \(a\sim a\) is valid. To prove the symmetric property holds, assume \(a\sim b.\) Therefore the following holds, \(\forall c\in X, a\sim c \Leftrightarrow b\sim c.\) Equivalently, the following holds \(\forall c\in X, b\sim c \Leftrightarrow a\sim c.\) Thus is it obvious that, \(a\sim b \implies b\sim a\) holds; and therefore \(\sim\) is also symmetric. To show transitivity, let \(a,b,c\in X\) and assume \(a\sim b\) and \(b\sim c.\) Therefore the following holds, \[ [\forall c\in X, a\sim c \Leftrightarrow b \sim c] \land [\forall d\in X, b\sim d \Leftrightarrow c \sim d]. \] Let \(e\in X.\) Then the following holds, \[ a\sim e \Leftrightarrow b\sim e \Leftrightarrow c\sim e. \] Therefore, \(a\sim c\) and so \(\sim\) is also transitive. In conclusion, \(\sim\) is an equivalence relation.
Definition 7.3 If \(\sim\) is an equivalence relation on \(X\), then the set \[[a]=\{b\in X : b\sim a\}\] is called the equivalence class of \(a\) with respect to \(\sim.\)
Definition 7.4 A partition of \(X\) is a collection of pairwise disjoint nonempty sets whose union is \(X.\)
Theorem 7.8 Let \(\sim\) be a relation on \(X.\) Then \(\sim\) is an equivalence relation on \(X\) if and only if the set \[ P=\{\{b\in X: a\sim b \}: a\in X\} \] is a partition of \(X\) with the property \(\forall a,b\in X, a\sim b \Leftrightarrow \exists A\in P\) such that \(a,b\in A.\)
Proof. Assume \(\sim\) is an equivalence relation on \(X.\) We will prove that \(P\) is a partition of \(X\) with the desired property by proving the following four statements hold.
Claim 1: \(X\) is the union of all equivalence classes of \(\sim.\)
Proof: Since \(\sim\) is reflexive it follows that \[ x\in \bigcup_{a\in X}[a] \Leftrightarrow \exists a\in X, x\in [a] \Leftrightarrow x\in X. \]
Claim 2: For all \(a,b\in X\), \([a]\cap [b]\neq \emptyset \Leftrightarrow [a]=[b].\)
Proof: Assume \([a]\cap [b] \neq \emptyset.\) Since \(\sim\) is symmetric and transitive, it follows \[\begin{align*} x\in [a] & \Leftrightarrow x\sim a \Leftrightarrow x\sim a \land \, \exists y\in [a] \cap [b] \\ & \Leftrightarrow \exists y\in X, x\sim a \land y\sim a \land y\sim b \\ & \Leftrightarrow \exists y\in X, x\sim a \land a\sim y \land y\sim b \\ & \Leftrightarrow \exists y\in X, x\sim y \land y\sim b \Leftrightarrow x\sim b \Leftrightarrow x\in [b] \end{align*}\] Assume \([a]=[b].\) Since \(\sim\) is reflexive \[ a\in [a] \implies a\in [a] \land a\in [b] \\ \implies a\in [a] \cap [b] \\ \implies [a]\cap [b] \neq \emptyset \]
Claim 3: Every equivalence class of \(\sim\) is nonempty.
Proof: Since \(\sim\) is reflexive, it follows that \[ a\in X \implies a\sim a \implies a\in [a] \implies [a]\neq \emptyset. \]
Claim 4: For all \(a,b\in X\), \(a\sim b \Leftrightarrow [a]=[b].\)
Proof: Let \(a,b\in X\) and assume \(a\sim b.\) Then it follows that \[ x\in [a] \Leftrightarrow x\sim a \Leftrightarrow x\sim b \Leftrightarrow x\in [b]. \] Thus we have that \([a]=[b].\) Conversely, assume \([a]=[b]\) for all \(a,b\) in \(X.\) Then it follows that \[ a\in [a] \implies a\in [b] \implies a\sim b. \] and so \(a\sim b\) holds. Therefore we have shown that \(P\), the collection of equivalence class of \(\sim\), is a partition on \(X\) with the desired property.
Conversely, assume \(\sim\) is a relation on \(X\) and \(P\) is a partition of \(X\) with the stated property. First we notice \(\sim\) is reflexive since \[ a\in X \implies a\in\bigcup_{A\in P} A \implies \exists A\in P, a\in A \implies a\sim a. \] The symmetric property of \(\sim\) follows by \[ a\sim b \implies \exists A\in P, a\in A \land b\in A \implies b\sim a. \] We also notice \(\sim\) is transitive by the following \[ a\sim b \land b\sim c \Leftrightarrow \exists a, b\in P, a,b\in A\land b,c\in B \Longrightarrow A=B \Leftrightarrow a\sim c. \] In conclusion \(\sim\) is an equivalence relation where \(a\sim b\) is equivalent to the existence of a set \(A\in P\) with \(a,b\in A\), namely the equivalence class \(A=[a].\)
7.3 Exercise
Exercise 7.1 Prove Theorem 7.5.
7.4 Reflexive Closure
Theorem 7.9 Let \(R\) be relation on \(X\) and \(A\subseteq X.\) The reflexive closure of \(R\) is the relation \[ r(R)=R \cup I. \]
Proof. Let \(R\) b a relation, then \(r(R)=R\cup I.\) Notice \(R\cup I\) is reflexive since \[ x\in X \implies (x,x)\in I\implies (x,x)\in R\cup I. \] Let \(T\) be a reflexive relation containing \(R.\) Then \(R\cup I\subseteq T\) since \[\begin{align*} & (x,y)\in R\cup I \implies (x,y)\in R \lor (x,y)\in I \\&\qquad \implies (x,y)\in T \lor (x,y)\in I \implies (x,y)\in T \cup I =T \end{align*}\] Since \(R\subseteq R\cup I \subseteq T\) where \(T\) is an arbitrary reflexive relation containing \(R\), it follows \(r(R)=R\cup I.\)
7.5 Symmetric Closure
Theorem 7.10 Let \(R\) be relation on \(X\) and \(A\subseteq X.\) The symmetric closure of \(R\) is the relation \[ s(R)=R \cup R^{-1}. \]
Proof. Let \(R\) b a relation, then \(s(R)=R\cup R^{-1}.\) Notice \(R\cup R^{-1}\) is symmetric since \[\begin{align*} \qquad \qquad & (x,y) \in R\cup R^{-1} \implies (x,y)\in R \lor (x,y)\in R^{-1} \\ & \qquad \implies (y,x)\in R^{-1} \lor (y,x)\in R \implies (y,x)\in R^{-1} \cup R=R\cup R^{-1} \end{align*}\] Let \(T\) be a symmetric relation containing \(R.\) Then \(R\cup R^{-1}\subseteq T\) since \[\begin{align*} \qquad \qquad & (x,y) \in R\cup R^{-1} \implies (x,y)\in R \lor (x,y)\in R^{-1} \\ & \qquad \implies (x,y)\in T \lor (x,y)\in R^{-1} \implies (x,y)\in T \lor (y,x)\in T \\ & \qquad \implies (x,y)\in T \lor (x,y)\in T \implies (x,y)\in T \end{align*}\] Since \(R\subseteq R\cup R^{-1} \subseteq T\) where \(T\) is an arbitrary symmetric relation containing \(R\), it follows \(s(R)=R\cup R^{-1}.\)
7.6 Reflexive Transitive
Theorem 7.11 Let \(R\) be relation on \(X\) and \(A\subseteq X.\) The transitive closure of \(R\) and the reflexive transitive closure of \(R\) are \[ t(R)=\bigcup_{n\geq 1} R^n. \qquad \qquad rt(R)=\bigcup_{n\geq 0} R^n. \] respectively.
Define \(R^0=I\), then \[ rt(R)=r\left(\bigcup_{n\geq1}R^n\right) = \bigcup_{n\geq1}R^n\cup I = \bigcup_{n\geq1}R^n \cup R^0 = \bigcup_{n\geq0}R^n. \] which completes the proof.
7.7 Transitive Closure
Theorem 7.12 Let \(R\) be a relation on \(X.\) Then \(R\) is transitive if and only if \(R^n\subseteq R\), for \(n\geq 1.\)
Proof. Assume \(R\) is transitive. We will prove \(R^n \subseteq R\) for \(n\geq 1\) by induction. The basis step is obvious. The induction step is: \[ R^n\subseteq R \implies R^{n+1}\subseteq R \] Assume \(R^n\subseteq R\) for some \(n\geq 1.\) Then \[\begin{align*} (x,y)\in R^{n+1} & \Leftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in R^n \\ & \Leftrightarrow \exists z\in X, (x,z)\in R \land (z,y)\in R \implies (x,z)\in R \end{align*}\] Therefore, by induction \(R^n\subseteq R\), for all \(\geq 1.\) Conversely, assume \(R^n\subseteq R\), for all \(n\geq 1.\) Then \((x,y)\in R\land (y,z)\in R \implies (x,z)\in R^2 \implies (x,y)\in R.\) Thus, \(R\) is transitive.
Theorem 7.13 Let \(R\) be a relation on \(X.\) If \(R\) is reflexive, then \(s(R)\) and \(t(R)\) are reflexive.
Proof. If \(R\) is reflexive, then \(s(R)\) and \(t(R)\) are reflexive, then \[ I\subseteq R\subseteq s(R) \text{ and } I\subseteq R \subseteq t(R) \] as desired.
Theorem 7.14 Let \(R\) be a relation on \(X.\) If \(R\) is symmetric, then \(r(R)\) and \(t(R)\) are symmetric.
Proof. If \(R\) is symmetric, then \(r(R)\) and \(t(R)\) are symmetric. \[\begin{align*} & (x,y)\in r(R)=R\cup I \implies (x,y)\in R \lor (x,y)\in I \\ & \qquad \implies (y,x)\in R \lor (y,x)\in I \implies (y,x)\in R \cup I =r(R)\\ & (x,y)\in t(R)= \bigcup_{n\geq 1}R^n \implies \exists R^n, (x,y)\in R^n \\ & \qquad \implies \exists R^n, (y,x)\in R^n \implies (y,x)\in \bigcup_{n\geq 1}R^n=t(R) \end{align*}\] which completes the proof.
Theorem 7.15 Let \(R\) be a relation on \(X.\) If \(R\) is transitive, then \(r(R)\) is transitive; however, \(s(R)\) may not be transitive.
Proof. If \(R\) is transitive, then \(r(R)\) is transitive. \[\begin{align*} & (x,y)\in r(R) \land (y,z)\in r(R) \implies (x,y)\in R\cup I \land (y,z)\in R\cup I \\ & \qquad \implies ((x,y)\in R \lor (x,y)\in I)\land ((y,z)\in R \lor (y,z)\in I) \\ & \qquad \implies (x,z)\in R \lor (x,z)\in I \implies (x,z)\in R \cup I =r(R) \end{align*}\] Let \(X=\{a,b\}\) and \(R=\{(a,b)\}.\) Then \(R\) is transitive and \(s(R)=\{(a,b),(b,a)\}\) is not transitive. Therefore, the symmetric closure of a transitive relation may not be transitive.
Theorem 7.16 Let \(R\) be a relation on \(X.\) The following hold: \(rt(R)=tr(R)\), \(rs(R)=sr(R)\), \(st(R)\subseteq ts(R)\), and \(st(R)\subsetneq ts(R)\) can hold.
Proof. The proof of each part follows.
\(rt(R)=tr(R)\): \[ tr(R) =t(R\cup I)=\bigcup_{n\geq 1} (R\cup I)^n =\left(\bigcup_{n\geq 1}R^n \right) \cup I =\bigcup_{n\geq 0} R^n =rt(R) \]
\(rs(R)=sr(R)\): \[\begin{align*} & rs(R) = r(R\cup R^{-1}) = I\cup R\cup R^{-1} \\ & =r(R)\cup R^{-1} =r(R)\cup (R^{-1}\cup I) =r(R)\cup r(R)^{-1} = sr(R) \end{align*}\]
\(st(R)\subseteq ts(R)\):
Let \(A=\{a,b,c\}.\) Then \(st(R)=\{(a,b),(b,a),(b,c),(c,b),(a,c),(c,a)\}\) and \(ts(R)=A\times A\) which completes the proof.
7.8 Equivalence Relation Characterization
Theorem 7.17 Let \(R\) be a relation on a set \(X.\) Then \(R\) is an equivalence relation if and only if \(R=rts(R).\)
Proof. Assume \(R\) is an equivalence relation on \(X.\) Notice \(R\subseteq rts(R)\), where \(r\), \(s\), and \(t\) denote the reflexive, symmetric and transitive closure operators, respectively. Let \(T\) be an arbitrary equivalence relation on \(X\) containing \(R\). Since \(R\subseteq T\) and \(T\) is symmetric, if follows that \(s(R)\subseteq T\). Then \(ts(R)\subseteq t(T)=T\) and so \(rts(R)\subseteq r(T)=T\). Thus it follows \(rts(R)\) is contained in \(T\). Since \(R\) is an equivalence relation on \(X\) containing \(R\), it follows that \(rts(R)\subseteq R.\) Whence, \(R=rts(R).\)
Conversely, assume \(R\) is a relation on \(X\) such that \(R=rts(R).\) It is easy to check that \(ts(R)\) is symmetric and that \(rts(R)\) is symmetric and transitive. It follows that \(rts(R)\) is an equivalence relation. Thus \(R\) is an equivalence relation.
Theorem 7.18 Let \(\longrightarrow\) be a relation on \(X\) with transitive closure denoted by \(\stackrel{+}{\longrightarrow}.\) Then \(a\stackrel{+}{\longrightarrow} b\) if and only if there exists elements \(a=x_1, x_2, x_3, ..., x_n=b\) in \(X\) such that \(x_1\longrightarrow x_2 \longrightarrow \cdots \longrightarrow x_n.\)
Proof. The proof is left for the reader.
7.9 The Kernel and Image of a Function
Theorem 7.19 Let \(f:X\to X\) be a function and let \(\sim\) be the binary relation defined on \(X\) by \(a\sim b\) if and only if \(f(a)=f(b).\) Then \(\sim\) is an equivalence relation.
Proof. Since \(f(a)=f(a)\) holds for all \(a\in X\), it follows \(\sim\) is reflexive. Let \(a,b\in X\) and assume \(a\sim b.\) Then \(f(b)=f(a)\), and thus \(f(b)=f(a)\) also holds. Thus, \(b\sim a\) and so \(\sim\) is also symmetric. Let \(a,b,c\in X\) and assume \(a\sim b\) and \(b\sim c.\) Then \(f(a)=f(b)\) and \(f(b)=f(c).\) Thus \(f(a)=f(c)\) and so \(a\sim c\), which means \(\sim\) is also transitive; and in conclusion an equivalence relation on \(X.\)
Recall, if \(R\) is a binary relation on \(X\), then \(R(x)=\{y\in X : (x,y)\in R\}\), that is \(R(x)\) is the set of outputs of \(R\) for a given input \(x.\) Of course when \(R\) is a function \(R(x)\) is a singleton set for each \(x\in X.\) In general \(R(x)\) can have many elements.
Theorem 7.20 Let \(R\) be a binary relation on \(X\) and let \(\ker(R)\) be the relation defined on \(X\) by \((a,b)\in \ker(R)\) if and only if \(R(a)=R(b).\) Then \(\ker(R)\) is an equivalence relation.
Proof. Since \(R(a)=R(a)\) holds for all \(a\in X\), it follows \(\ker(R)\) is reflexive. Let \(a,b\in X\) and assume \((a,b)\in \ker(R).\) Then \(R(b)=R(a)\), and thus \(R(b)=R(a)\) also holds. Thus, \((b,a)\in\ker(R)\) and so \(\ker(R)\) is also symmetric. Let \(a,b,c\in X\) and assume \((a,b)\) and \((b,c)\in\ker(R).\) Then \(R(a)=R(b)\) and \(R(b)=R(c).\) Thus \(R(a)=R(c)\) and so \((a,c)\in\ker(R)\), which means \(\ker(R)\) is also transitive; and in conclusion an equivalence relation on \(X.\)
Recall, if \(R\) is a binary relation on \(X\), then \(R^{-1}(y)=\{x\in X : (x,y)\in R\}\), that is \(R^{-1}(y)\) is the set of inputs of \(R\) for a given output \(y.\) In general \(R(y)\) can have many elements.
Theorem 7.21 Let \(R\) be a binary relation on \(X\) and let \(\textnormal{im}(R)\) be the relation defined on \(X\) by \((a,b)\in \textnormal{im}(R)\) if and only if \(R^{-1}(a)=R^{-1}(b).\) Then \(\textnormal{im}(R)\) is an equivalence relation.
Proof. Since \(R^{-1}(a)=R^{-1}(a)\) holds for all \(a\in X\), it follows \(\textnormal{im}(R)\) is reflexive. Let \(a,b\in X\) and assume \((a,b)\in\textnormal{im}(R).\) Then \(R^{-1}(b)=R^{-1}(a)\), and thus \({R^{-1}(b)=R^{-1}(a)}\) also holds. Thus, \((b,a)\in\textnormal{im}(R)\) and so \(\textnormal{im}(R)\) is also symmetric. Let \(a,b,c\in X\) and assume \((a,b)\in\textnormal{im}(R)\) and \((b,c)\in\textnormal{im}(R).\) Then \(R^{-1}(a)=R^{-1}(b)\) and \(R^{-1}(b)=R^{-1}(c).\) Thus \(R^{-1}(a)=R^{-1}(c)\) and so \((a,c)\in\textnormal{im}(R)\), which means \(\textnormal{im}(R)\) is also transitive; and in conclusion an equivalence relation on \(X.\)
Theorem 7.22 Let \(R\) be a binary relation on \(X.\) Then \(R\) is an equivalence relation if and only if \(\ker(R)=R\) if and only if \(\textnormal{im}(R)=R\) if and only if \(R=R^*.\)
Proof. The proof is left as an exercise.
7.10 Exercises
7.11 Up-sets and Down-sets
Throughout we assume \((X,\geq)\) is an ordered set. By this we mean that \(X\) is a set and that \(\geq\) is binary relation on \(X\) that is reflexive, antisymmetric, and transitive.
Definition 7.5 A subset \(U\) of \(X\) is called an up-set if \[(x\in U, \, y\in X, \text{ and } y\geq x) \implies y\in U.\] A subset \(D\) of \(X\) is called a down-set if \[ (x\in D, \, y\in X, \text{ and } x\geq y) \implies y\in D.\]
Theorem 7.23 Let \((X,\geq)\) be an ordered set.
- The union or intersection of any family of up-sets is an up-set.
- The complement of an up-set is a down-set.
Proof. (1): Let \(\{U_i : i \in I\}\) be a family of up-sets. Let \[ U=\bigcup_{i\in I} U_i \quad \text{and} \quad F=\bigcap_{i\in I} U_i. \] We will show that \(U\) is an up-set. Let \(x\in U\), \(y\in X\) and assume \(y\geq x.\) Since \(x\in U\), it follows \(x\in U_i\) for some \(i.\) Since \(U_i\) is an up-set, it follows \(y\in U_i.\) Hence \(y\in U.\) Next we will show \(F\) is an up-set. Let \(x\in F\) and \(y\in X\) and assume \(y\geq x.\) Since \(x\in F\), it follows \(x\in U_i\) for all \(i\in I.\) Since \(U_i\) are all up-sets, it follows \(y \in U_i\) for all \(i\in I.\) Hence \(y\in F.\)
(2): Let \(U\) be an up-set and let \(D\) be the complement of \(U.\) Let \(x\in D\), \(y\in X\), and assume \(x\geq y.\) Assume \(y\in U.\) Since \(U\) is an up-set and \(x\geq y\), if follows \(x\in U.\) However, \(x\in U\) and \(x\in D\) is a contradiction. Thus, \(y\in D\) as needed.
Theorem 7.24 The union or intersection of any family of down-sets is a down-set. The complement of a down-set is an up-set.
Definition 7.6 If \(A\) is an arbitrary subset of \(X\) and \(x\in X\), then we define \[ {\uparrow}(A)=\{y\in X : \exists\, x\in A,\, y\geq x\}\quad \text{and} \quad {\uparrow}(x)=\{y\in X : y\geq x\}. \] \[ {\downarrow}(A)=\{y\in X : \exists\, x\in A,\, x\geq y\} \quad \text{and} \quad {\downarrow}(x)=\{y\in X : x\geq y\}, \] to be the up-closure of \(A\), up-closure of \(x\), down-closure of \(A\), and the down-closure of \(x\), respectively. Up-sets of the form \({\uparrow}(x)\) are called principal up-sets and dually, down-sets of the form \({\downarrow}(x)\) are called principal down-sets.
Important special cases are \({\uparrow}(X)=X\), \({\downarrow}(X)=X\), \({\downarrow}{\emptyset}=\emptyset\) and \({\uparrow}{\emptyset}=\emptyset.\) Clearly,
\[\begin{equation} \label{isoequiv1} \forall \ x,y\in X, \quad x\geq y \, \Longleftrightarrow \, {\uparrow}(x)\subseteq {\uparrow}{y} \, \Longleftrightarrow \, {\downarrow}(x)\supseteq {\downarrow}{y}. \end{equation}\]
To see this, suppose \(x\geq y\), and assume \(z\in {\uparrow}(x)\) and \(w\in {\downarrow}{y}.\) Then by transitivity of \(\geq\) we have \(z\in {\uparrow}{y}\) and \(w\in {\downarrow}(x).\) Conversely, both \({\uparrow}(x)\subseteq {\uparrow}{y}\) and \({\downarrow}(x)\supseteq {\downarrow}{y}\) imply that \(x\geq y\) which follows by the reflexive property.
Theorem 7.25 Assume \(A\subseteq X\) and \(x\in X.\) Then
- \({\downarrow}(A)\) is the smallest down-set containing \(A\),
- \(A\) is an down-set if and only if \(A=\, {\downarrow}(A)\), and
- \({\downarrow}(x)=\, {\downarrow}(x).\)
Proof. (1): Let \(x\in {\downarrow}(A)\), \(y\in X.\) Assume \(x\geq y.\) Since \(x\in {\downarrow}(A)\), there exists \(z\in A\) such that \(z\geq x.\) By transitivity \(z\geq y.\) Thus it follows \(y\in {\downarrow}(A).\) Therefore, \({\downarrow}(A)\) is an down-set. Let \(D\) be an down-set that contains \(A.\) We will show \({\downarrow}(A)\subseteq D.\) Let \(x\in {\downarrow}(A).\) Then there exists \(z\in A\) such that \(z\geq x.\) Since \(z\in A\), it follows \(z\in D.\) Since \(D\) is an down-set, it follows that \(x\in D\), as a needed.
(2): Suppose \(A={\downarrow}(A)\), then by part \(\eqref{basicpos1}\), it follows \(A\) is an down-set. Conversely, assume \(A\) is an down-set. By \(\eqref{basicpos1}\), \({\downarrow}(A)\) is the smallest down-set that contains \(A\), so it follows \({\downarrow}(A)\subseteq A\) since \(A\) is an down-set and \(A\subseteq A.\) Let \(x\in A.\) By the reflexive property of \(\geq\), it follows \(x\geq x\), and thus \(x\in {\downarrow}(A).\) Hence \({\downarrow}(A)=A.\)
(3): Immediately, \(y\in {\downarrow}(x) \Longleftrightarrow x\geq y \Longleftrightarrow y\in {\downarrow}(x)\).
Theorem 7.26 Let \((X,\geq)\) be an ordered set with \(A\subseteq X\) and \(x\in X.\)
- \({\uparrow}(A)\) is the smallest up-set containing \(A\).
- \(A\) is an up-set if and only if \(A=\, {\uparrow}(A).\)
- \({\uparrow}(x)=\, {\uparrow}(x)\).
Proof. (1): Let \(x\in {\uparrow}(A)\), \(y\in X.\) Assume \(y\geq x.\) Since \(x\in {\uparrow}(A)\), there exists \(z\in A\) such that \(x\geq z.\) By transitivity \(y\geq z.\) Thus it follows \(y\in {\uparrow}(A).\) Therefore, \({\uparrow}(A)\) is an up-set. Let \(U\) be an up-set that contains \(A.\) We will show \({\uparrow}(A)\subseteq U.\) Let \(x\in {\uparrow}(A).\) Then there exists \(z\in A\) such that \(x\geq z.\) Since \(z\in A\), it follows \(z\in U.\) Since \(U\) is an up-set, it follows that \(x\in U\), as a needed.
(2): Suppose \(A={\uparrow}(A)\), then by part \(\eqref{basicpos2}\), it follows \(A\) is an up-set. Conversely, assume \(A\) is an up-set. By \(\eqref{basicpos1}\), \({\uparrow}(A)\) is the smallest up-set that contains \(A\), so it follows \({\uparrow}(A)\subseteq A\) since \(A\) is an up-set and \(A\subseteq A.\) Let \(x\in A.\) By the reflexive property of \(\geq\), it follows \(x\geq x\), and thus \(x\in {\uparrow}(A).\) Hence \({\downarrow}(A)=A.\)
(3): Immediately, \(y\in {\uparrow}(x) \Longleftrightarrow y\geq x \Longleftrightarrow y\in {\uparrow}(x)\).
Theorem 7.27 For all \(x,y\in X\), \[ x\geq y \, \Longleftrightarrow \, {\downarrow}(x)\supseteq {\downarrow}{y} \, \Longleftrightarrow \, {\uparrow}(x)\subseteq {\uparrow}{y}. \]
Proof. Suppose \(x\geq y.\) Let \(z\in {\downarrow}{y}\) then \(y\geq z.\) By transitivity of \(\geq\) we have \(x\geq z\) and thus \(z\in {\downarrow}(x).\) Therefore we have shown, if \(x\geq y\) then \({\downarrow}(x)\supseteq {\downarrow}{y}.\) Conversely, assume \({\downarrow}(x)\supseteq {\downarrow}{y}.\) By reflexivity of \(\geq\) we have \(y\in {\uparrow}{y}\) and so \(y\in {\downarrow}(x)\), and thus \(x\geq y.\) Now suppose \(x\geq y.\) Let \(z\in {\uparrow}(x).\) Then \(z\geq x\) and so by transitivity of \(\geq\) we have \(z\geq y\), and therefore \(z\in {\uparrow}{y}.\) Conversely, assume \({\uparrow}(x)\subseteq {\uparrow}{y}.\) Then \(x\in {\uparrow}{y}\) and thus \(x\geq y.\)
Theorem 7.28 Let \((X,\geq)\) be an ordered set with \(A,B\subseteq X.\)
- \({\uparrow}(A)={\uparrow}({\uparrow}(A))\)
- \({\uparrow}(A\cup B)={\uparrow}(A)\ \cup {\uparrow}(B)\)
- \({\uparrow}(A\cap B)\subseteq {\uparrow}(A)\ \cap {\uparrow}(B)\)
- \({\uparrow}(A)=\bigcup_{x\in A} {\uparrow}(x)\)
- \(B\supseteq A\Rightarrow {\uparrow}(B)\supseteq {\uparrow}(A)\)
Proof. (1): Immediately we have \({\uparrow}(A)\subseteq {\uparrow}({\uparrow}(A)).\) Let \(x\in {\downarrow}({\downarrow}(A)).\) Then there exists \(y\in{\downarrow}(A)\) such that \(y\geq x\) and there exists \(a\in A\) such that \(a\geq y\geq x.\) Hence \(x\in {\downarrow}(A)\).
(2): Let \(x\in {\uparrow}(A\cup B).\) Then there exists \(y\in A\cup B\) such that \(x\geq y.\) If \(y\in A\), then \(x\in {\uparrow}(A).\) If \(y\in B\), then \(x\in {\uparrow}(B).\) Hence, \(x\in {\uparrow}(A)\ \cup {\uparrow}(B).\) Conversely, assume \(x\in {\uparrow}(A) \ \cup {\uparrow}(B).\) If \(x\in {\uparrow}(A)\), then there exists \(a\in A\) such that \(x \geq a.\) Hence \(a\in A\cup B\) with \(x\geq a\) which yields \(x\in {\uparrow}(A\ \cup B).\) If \(x\in {\uparrow}(B)\), then there exists \(b\in B\) such that \(x \geq b.\) Hence \(b\in A\cup B\) with \(x\geq b\) which yields \(x\in {\uparrow}(A\ \cup B)\).
(3): Let \(x\in {\uparrow}(A\cap B).\) Then there exists \(y\in A\cap B\) such that \(x\geq y.\) Hence \(y\in A\) with \(x\geq y\) and \(y\in B\) with \(x\geq y.\) Thus \(x\in {\uparrow}(A)\) and \(x\in {\uparrow}(B)\), and so \(x\in {\uparrow}(A)\ \cap {\uparrow}(B).\)
(4): Let \(z\in {\uparrow}(A).\) Then there exists \(a\in A\) such that \(z\geq a.\) Hence it follows that \(z\in {\uparrow}(a)\subseteq \bigcup_{x\in A} {\uparrow}(x)\).Conversely, assume \(z\in \bigcup_{x\in A} {\uparrow}(x).\) Then there exists \(x\in A\) such that \(z\in {\uparrow}(x).\) Hence we have \(x\in A\) with \(z\geq x.\) Thus it follows that \(z\in {\uparrow}(A)\) as needed.
Theorem 7.29 Let \((X,\geq)\) be an ordered set with \(A,B\subseteq X.\)
- \({\downarrow}(A)={\downarrow}({\downarrow}(A))\)
- \({\downarrow}(A\cup B)={\downarrow}(A)\ \cup {\downarrow}(B)\)
- \({\downarrow}(A\cap B)\subseteq {\downarrow}(A)\ \cap {\downarrow}(B)\)
- \({\downarrow}(A)=\bigcup_{x\in A} {\downarrow}(x)\)
- \(B\supseteq A\Rightarrow {\downarrow}(B)\supseteq {\downarrow}(A)\)
7.12 Monotone Mappings
Definition 7.7 Let \((X,\leq_1)\) and \((Y,\leq_2)\) be ordered sets. A mapping \(f: X \to Y\) is said to be isotone ( order-preserving) whenever \[ (\forall \, x,y\in X) \quad x \leq_1 y \implies f(x) \leq_2 f(y) \] or is said to be antitone ( order-reversing) whenever \[ (\forall \, x,y\in X) \quad x \leq_1 y \implies f(x) \geq_2 f(y). \] Furthermore, \(f\) is called monotone if \(f\) is either isotone or antitone.
Theorem 7.30 For every function \(f\) on an ordered set \((X,\geq)\), we denote it to be \(\uparrow\), \(\downarrow\), or \(\updownarrow\) according to whether it is isotone, antitone, or both. The following are some easy consequences:
- \(\uparrow \circ \downarrow = \downarrow \circ \uparrow = \downarrow\) (meaning that the composition of an isotone and an antitone maps is antitone),
- \(\uparrow \circ \uparrow = \downarrow \circ \downarrow = \uparrow\) (meaning that the composition of two isotone or two antitone maps is isotone),
- \(f\) is \(\updownarrow\) if and only if it is a constant on any chain in \(A\), and if this is the case, for every \(a\in A\), \(f^{-1}(a)\) is a maximal chain in \(A\).
Proof. An exercise for the reader as Exercise 7.2.
7.13 Exercises
Exercise 7.2 Prove Theorem 7.30.
Theorem 7.31 A mapping \(f:X\to Y\) is isotone if and only if the inverse image of every principal down-set of \(Y\) is a down-set of \(X\).
Proof. The proof follows as in MR2126425. First notice that \[\begin{equation} \label{eq-inverseprinds} \forall y\in Y, \quad x\in f^{-1}({\downarrow}(y)) \Longleftrightarrow y\geq f(x). \end{equation}\]
Suppose that \(f\) is isotone. Let \({\downarrow}(y)\) be an arbitrary principal down-set of \(Y\) and let \(A=f^{-1}({\downarrow}(y))\). Assume \(x\in A\), \(z\in X\), and \(x\geq z\). Since \(f\) is isotone, we have \(f(x)\geq f(z)\).
Since \(x\in A\) it follows by \(\eqref{eq-inverseprinds}\) that \(y\geq f(x)\); and so we have \(y\geq f(z)\) by transitivity of \(\geq\). Thus \(z\in A\) as needed. For conversely, notice that by reflexivity of \(\geq\) and \(\eqref{eq-inverseprinds}\) it follows that for every \(x\in X\) we have \(x\in f^{-1}({\downarrow}(f(x)))\). By hypothesis, \(f^{-1}({\downarrow}(f(x)))\) is a down-set of \(X\); so if \(y\in X\) is such that \(x\geq y\) we have \(y\in f^{-1}({\downarrow}(f(x)))\). By \(\eqref{eq-inverseprinds}\), it follows that \(f(x)\geq f(y)\) and therefore \(f\) is isotone.
Theorem 7.32 If \(X, Y\) are ordered sets and if \(f:X\to Y\) is any mapping then the following statements are equivalent.
- \(f\) is isotone;
- the inverse image of every principal down-set of \(Y\) is a down-set of \(X\);
- the inverse image of every principal up-set of \(Y\) is an up-set of \(X\).
Proof. (1)\(\Leftrightarrow\)(2): Suppose that \(f\) is isotone. Let \(y\in Y\) and let \(A=f^{\leftarrow}(y^{\downarrow})\). If \(A\neq\emptyset\) assume \(x\in A\). Then for every \(z\in X\) with \(z\leq x\) we have \(f(z)\leq f(x)\leq y\) whence \(z\in A\). Thus \(A\) is a down-set of \(X\). Conversely, notice that for every \(x\in X\) we have \(x\in f^{\leftarrow}[f(x)^{\downarrow}]\). By (2) this is a down-set of \(X\); so if \(y\in X\) is such that \(y\leq x\) we have \(y\in f^{\leftarrow}[f(x)^{\downarrow}]\). If follows that \(f(y)\leq f(x)\) and therefore \(f\) is isotone.
(1)\(\Leftrightarrow\)(2): Assume \(f\) is order preserving. Let \(y\in Y\) and let \(A=f^{\leftarrow}(y^{\uparrow})\) be the inverse image of a principal down-set of \(Y\). To show \(A\) is an up-set of \(X\), assume \(x\in A\). If \(z\in X\) with \(z\geq x\) we have \(f(z)\geq f(x) \geq y\) whence \(z\in A\) as needed. Conversely assume \(x\leq y\) and that \(\eqref{ipu}\) holds. Notice \(x\in f^{\leftarrow}(f(x)^{\uparrow})\) holds for all \(x\in X\). By assumption, \(f^{\leftarrow} (f(x)^{\uparrow})\) is an up-set of \(X\), and so it follows \(y\in f^{\leftarrow}(f(x)^{\uparrow})\). Whence \(f(y)\geq f(x)\) as needed.
Theorem 7.33 A mapping \(f: X \to Y\) is an order-isomorphism if and only if \(f\) is bijective and both \(f\) and \(f^{-1}\) are isotone.
Proof. The proof follows as in davey2002introduction. Assume \(f:X\to Y\) is a order-isomorphism. By definition \(f\) is surjective. Using the reflexive and antisymmetric properties we have \[\begin{align*} f(x)=f(y) & \Longleftrightarrow f(x)\geq f(y)\text{ and } f(y)\geq f(x) \\ & \Longleftrightarrow x\geq y \text{ and } y\geq x \\ & \Longleftrightarrow x=y \end{align*}\] Thus \(f\) is injective and so bijective. Since \[ \forall x,y\in X, \quad x=f^{-1}(f(x))=f^{-1}(f(y))=y \Longleftrightarrow f(x)\geq_2 f(y) \] it follows both \(f\) and \(f^{-1}\) are isotone. Conversely, assume \(f\) is bijective and both \(f\) and \(f^{-1}\) are isotone. Obviously, \(f\) is surjective. Let \(x,y\in X\). Assume \(x\geq y\). Then \(f(x)\geq f(y)\) since \(f\) is isotone. Now assume \(f(x)\geq f(y)\). Since \(f^{-1}\) is isotone and \(f^{-1}\) is the inverse of \(f\), we have \(x=f^{-1}(f(x))\geq y=f^{-1}(f(y))\) as needed to establish \(\eqref{red-iso}\).
Theorem 7.34 The mapping \(\phi: X\to \mathcal{X}\) defined by \[ \phi(x)= {\downarrow}(x). \] is an order-isomorphism onto the set of all principal down-sets of \(X\).
Proof. First notice that \(\phi\) is a bijection to the principal down-sets: \[ \phi(x)=\phi(y) \Longleftrightarrow {\downarrow}(x) = {\downarrow}(y) \Longleftrightarrow y\geq x \text{ and } x\geq y \Longleftrightarrow x=y. \] To show that \(\phi\) is a order-isomorphism, observe \(\eqref{isoequiv}\) yields \(x\geq y\) if and only if \(\phi(y) \subseteq \phi(x)\), and the claim follows.
7.14 Residuated Mappings
Let \((X,\geq)\) and \((Y,\succeq)\) be ordered sets.
Definition 7.8 A mapping \(f:X\to Y\) is called if the inverse image of every principal down-set of \(Y\) is a principal down-set of \(X\).
Theorem 7.35 A mapping \(f:X\to Y\) is residuated if and only if it is isotone and there exists a isotone mapping \(g:Y\to X\) such that \[\begin{equation} \label{adj} \forall \, x\in X, (g\circ f)(x) \geq x \quad \text{ and } \quad \forall y \, \in Y, y\succeq (f\circ g)(y). \end{equation}\]
Proof. The proof follows as in page 6 MR2126425. Assume \(f\) is residuated. It follows that \(f\) is isotone. Notice the definition of residuated means: for all \(y\in Y\) there exists \(x\in X\) such that \(f^{-1}({ \downarrow}(y)) = { \downarrow}(x)\). Now for every given \(y\in Y\) this element \(x\) is clearly unique [if \(f^{-1}({ \downarrow}(y))={ \downarrow}(x)\) and \(f^{-1}({ \downarrow}(y))={ \downarrow}(z)\), then \(z\geq x\) and \(x\geq z\)], so we can define a mapping \(g:Y\to X\) by setting \(g(y)=x\). It follows that \(g\) is isotone:
\[\begin{align*}
y_1\succeq y_2 & \implies {\downarrow}(y_2) \subseteq {\downarrow}(y_1) \implies f^{-1}({\downarrow}(y_2)) \subseteq f^{-1}({\downarrow}(y_1)) \\
& \implies {\downarrow}(x_2) \subseteq {\downarrow}(x_1) \implies {\downarrow}(g(y_2))\subseteq {\downarrow}(g(y_1)) \implies g(y_1)\geq g(y_2).
\end{align*}\] Further it follows \(g(y)\in {\downarrow}(g(y))= { \downarrow}(x)=f^{-1}({ \downarrow}(y))\), and so \(y\succeq (f\circ g)(y)\), for all \(y\in Y\); and \(x\in f^{-1}({\downarrow}(f(x)))={\downarrow}(g(f(x)))\) so that \((g\circ f)(x)\geq x\), for all \(x\in X\). Conversely, assume \(f\) and \(g\) are isotone mappings such that \(\eqref{adj}\) holds. Then on the one hand we have \[
y\succeq f(x) \implies g(y)\geq g(f(x)) \geq x
\] and on the other hand we have \[
g(y) \geq x \implies y \succeq f(g(y)) \succeq f(x).
\] It follows from these observations that \(y\succeq f(x)\) if and only if \(g(y)\geq x\). Therefore we have \(f^{-1}({ \downarrow}(y))={\downarrow}(g(y))\). Whence \(f\) is residuated.
Theorem 7.36 If \(f:X\to Y\) is a residuated, then an isotone mapping that satisfies \(\eqref{adj}\) is unique, and is called the of \(f\) and is denoted by \(f^+\).
Proof. Suppose that \(g, h:Y\to X\) are each isotone mappings that satisfy \(\eqref{adj}\). Then \[ \forall y\in Y, \quad h(y)\geq h((f\circ g)(y)) = (h\circ f)(g(y))\geq g(y) \] Similarly it follows \(g(y)\geq h(y)\) and therefore \(g=h\).
For every non-empty set \(X\) the residuated mappings on \(\mathcal{X}\) are completely described in the following result.
Theorem 7.37 Let \(X\) be a non-empty set and let \(R\) be a binary relation on \(X\). Then the mapping \(\zeta_R :\mathcal{X}\to\mathcal{X}\) defined by \[ \zeta_R(A)=\{y\in X : (\exists \, x\in A) \, \, (x,y)\in R\} \] is residuated. Moreover, every residuated mapping \(f:\mathcal{X}\to\mathcal{X}\) is of this form for some binary relation \(R\) on \(X\).
Proof. The proof follows as in p. 8 MR2126425.
Let \(\iota : \mathcal{X} \to \mathcal{X}\) be the antitone mapping that sends each subset of \(X\) to its complement and let \(\zeta_{R^{-1}}:\mathcal{X} \to \mathcal{X}\) be defined by \[ \zeta_{R^{-1}}(A)=\{y\in X : (\exists \, x\in A) \, \, (x,y)\in R^{-1}\}. \] The mapping \(\zeta_{R}^+:\mathcal{X} \to \mathcal{X}\) defined by \(\zeta_{R}^+=\iota\circ \zeta_{R^{-1}}\circ \iota\) is isotone. To see this, let \(A,B\in \mathcal{X}\). Then it follows that \[\begin{align*} A\subseteq B & \implies \iota(A)\supseteq \iota(B) \implies \zeta_{R^{-1}}(\iota(A))\supseteq \zeta_{R^{-1}}(\iota(B)) \\ & \implies (\iota\circ \zeta_{R^{-1}})(\iota(A))\subseteq (\iota\circ \zeta_{R^{-1}})(\iota(B)) \implies \zeta^+_R(A) \subseteq \zeta^+_R(B). \end{align*}\] We claim that \((\zeta_R^+\circ \zeta_R)(A)\supseteq A\), for all \(A\in \mathcal{X}\). It suffices to show \((\zeta_{R^{-1}}\circ \iota \circ \zeta_R)(A)\subseteq \iota(A)\) because then we have \((\zeta^+_R\circ \zeta_R)(A)=(\iota\circ \zeta_{R^{-1}})(A)\supseteq A\) as required. To this end notice that \[\begin{align*} y\in (\zeta_{R^{-1}}\circ \iota \circ \zeta_R)(A) \implies \exists z\in (\iota\circ \zeta_R)(A), (y,z)\in R \end{align*}\] Assume \(y\in A\). Then \(y\in A\) and \((y,z)\in R\) which yields \(z\in \zeta_R(A)\). However, \(z\notin \zeta_R(A)\). Hence \(y\notin A\) and so \(y\in \iota(A)\) as desired.
Next we claim that \((\zeta_R\circ \zeta_R^+)(A)\subseteq A\), for all \(A\in \mathcal{X}\). Equivalently we show that \((\zeta_R\circ \iota\circ \zeta_{R^{-1}})(A) \subseteq \iota(A)\), for all \(A\in \mathcal{X}\). Assume \(y\in (\zeta_R\circ \iota\circ \zeta_{R^{-1}})(A)\) and \(y\in A\). Then there exists \(z\in (\iota\circ \zeta_{R^{-1}})(A)\) such that \((y,z)\in R^{-1}\). Thus, \(z\in (\iota\circ \zeta_{R^{-1}})(A)\) and \(z\in \zeta_{R^{-1}}(A)\). This contradiction shows that \(y\notin A\) as desired.
To see that every residuated mapping \(f : \mathcal{X} \to \mathcal{X}\) is of this form for some binary relation \(R\) on \(X\), consider the relation \(R_f\) defined on \(X\) by \[ (x,y)\in R_f \Longleftrightarrow y\in f(\{x\}). \] Observe that \(\zeta_{R_f}(\{x\})=\{y\in X : (x,y)\in R_f\}\), so that \(f\) and \(\zeta_{R_f}\) agree on singletons. Now if \(k: \mathcal{X}\to \mathcal{X}\) is any residuated mapping then, since it is isotone, for every non-empty subset \(A\) of \(X\) we have \[\begin{equation} \label{kab} k(A)=k\left(\, \bigcup_{x\in A}\{x\}\right)=\bigcup_{x\in A} k(\{x\}). \end{equation}\] To see that \(\ref{kab}\) holds, notice that if \(B=\bigcup_{x\in A} k(\{x\})\) then clearly \(k(A)\supseteq B\). On the other hand, \(k(\{x\})\subseteq B\) for every \(x\in A\) and so \(\{x\}\subseteq k^+(B)\) whence \(A=\bigcup_{x\in A}\{x\}\subseteq k^+(B)\). and therefore \(k(A)\subseteq B\). Now \(\ref{kab}\) applied to both \(f\) and \(\zeta_{R_f}\), together with the fact that \(f\) and \(\zeta_{R_f}\) agree on singletons we now have \[ f(A) =\bigcup_{x\in A} f(\{x\}) =\bigcup_{x\in A} \zeta_{R_f} (\{x\}) =\zeta_{R_f} (A). \] Whence we obtain \(f=\zeta_{R_f}\).
Theorem 7.38 The set \(\text{Res}(X)\) of residuated mappings \(f : X \to X\) forms a semigroup, as does the set \(\text{Res}^+(X)\) of residual mappings \(f^+:X\to X\).
Proof. The proof follows as in p. 9 MR2126425. Clearly, \(g\circ f\) and \(f\circ g\) are isotone. Moreover, \[\begin{align*} & (f^+\circ g^+)\circ (g\circ f)\geq f^+\circ \text{id}_Y \circ f=f^+\circ f \geq \text{id}_X \\ & (g\circ f)\circ (f^+\circ g^+)\leq g\circ \text{id}_Y \circ g^+=g\circ g^+ \leq \text{id}_Y \end{align*}\] Thus by the uniqueness of residuals, \((g\circ f)^+\) exists and is \(f^+\circ g^+\). Therefore if \(f:X\to Y\) and \(g:Y\to X\) are residuated, then \(g\circ f\) is also residuated and \((g\circ f)^+=f^+\circ g^+\).
7.15 Closure Operators
Let \((X,\geq)\) be an ordered set.
Definition 7.9 An isotone mapping \(f : X \to X\) is a on \(X\) if it is such that \[ \forall \, x\in X, f(x)=(f\circ f)(x) \geq x \] and is called a on \(X\) if it is such that \[ \forall \, x\in X, x\geq f(x)=(f\circ f)(x) \]
Theorem 7.39 If \(X\) is an ordered set then \(f : X \to X\) is a closure if and only if there is an ordered set \(Y\) and a residuated mapping \(g : X \to Y\) such that \(f = g^+ \circ g\).
\(\Leftarrow\): Suppose conversely that there is an ordered set \(Y\) and a residuated mapping \(g : X \to Y\) such that \(f = g^+ \circ g\). Then on the one hand \(g^+ \circ g \geq \text{id}_X\); and on the other, by \(\ref{resprop}\), \(g = g \circ g^+ \circ g\), so that \(g^+ \circ g = (g^+ \circ g)^2\). Since \(g^+\circ g\) is isotone it follows that \(f=g^+\circ g\) is a closure on \(X\).
Theorem 7.40 Dually, \(f : X \to X\) is a dual closure if and only if there is an ordered set \(Y\) and a residuated mapping \(g : X \to Y\) such that \(f = g \circ g^+\).
If \(f : X \to X\) is a closure or a dual closure and if \(x \in \text{Im} f\) then \(x = f(y)\) for some \(y \in E\), whence we obtain \(f(x) = f^2(y) = f(y) = x\). Consequently, we see that \[ \text{Im}f = \{x \in E : f(x) = x\}, \] the set of of \(f\). In short, the image of a closure is its set of fixed points.
Definition 7.10 A subset \(A\) of an ordered set \(X\) is called a (dual) closure subset if there is a (dual) closure \(f : X \to X\) such that \(A = \text{Im} f\).
Theorem 7.41 A subset \(A\) of an ordered set \(X\) is a closure subset of \(X\) if and only if for every \(x\in X\) the set \(x^{\uparrow} \cap A\) has a bottom element.
Proof. The proof follows as in . Suppose that \(A\) is a closure subset of \(X\) and let \(f : X \to X\) be a closure such that \(A = \text{Im} f\). Then for every \(x \in X\) the set \(x^{\uparrow} \cap A\) is not empty since clearly it contains the element \(f(x)\). Moreover, if \(z \in x^{\uparrow} \cap A\) then \(x\leq z\) and \(f(x)\leq f(z)=z\). Consequently \(x^{\uparrow} \cap A\) has a bottom element, namely \(f(x)\). Conversely, suppose that for every \(x \in X\) the set \(x^{\uparrow} \cap A\) has a bottom element, \(x_*\) say, and consider the mapping \(f : X \to X\) given by \(f(x) = x_*\). If \(x\leq y\) then \(x^{\uparrow} \supseteq y^{\uparrow}\) gives \(x^{\uparrow} \cap A \supseteq y^{\uparrow} \cap A\) whence it follows that \(x_* \leq y_*\) and so \(f\) is isotone. Moreover, since \(f(x) = x_* \geq x\) for every \(x \in X\) we also have \(f\geq \text{id}_X\). Now for any \(y\in A\) we clearly have \(y=y_*=f(y)\in\text{Im} f\). Applying this to \(f(x)=x_* \in A\) we obtain \(f^2(x)=f(x)\). Hence \(f^2 =f\) and so \(f\) is a closure with \(\text{Im} f = A\).
is Connections
Galois connections are mathematical structures that allow us to model the relationships between objects in a given category. In this comprehensive guide, you’ll learn everything you need to know about these fascinating structures, including their properties and applications. With plenty of examples and exercises to help you along the way, this book is perfect for anyone looking to gain a deeper understanding of Galois connections.
In mathematics, a Galois connection is a structure that allows us to model the relationships between objects. In this comprehensive guide, you’ll learn everything you need to know about these fascinating structures, including their properties and applications. With plenty of examples and exercises to help you along the way, this book is perfect for anyone looking to gain a deeper understanding of Galois connections.
Galois connections are a type of relationship between two sets that allows for mappings between the two sets. These mappings preserve (or reverse) certain properties, such as order or containment.
Galois connections were first studied by French mathematician Evariste Galois, who developed the theory of algebraic equations. Galois connections have since been applied to fields such as computer science and linguistics. In computer science, they are used to define data structures and algorithms. In linguistics, they are used to describe the relationship between meaning and sound in language.
Galois connections are a powerful tool for understanding relationships between sets.
Galois connections have a number of interesting properties that make them useful for modeling relationships between objects.
First, every Galois connection has an associated closure operator. This operator takes a set and returns a new set that is “closed” under the given Galois connection. That is, if you have a set A and a Galois connection between A and B, then the closure of A will be a subset of B that contains all the elements of A, plus any additional elements that can be reached from A via the given Galois connection.
Second, every Galois connection has an associated interior operator. This operator takes a set and returns a new set that is “open” under the given Galois connection. That is, if you have a set A and a Galois connection between A and B, then the interior of A will be a subset of B that contains all the elements of A, minus any elements that can’t be reached from A via the given Galois connection.
Third, every Galois connection defines a partial order on its associated sets. That is, if you have a set A and a Galois connection between A and B, then the elements of A will be partially ordered by the given Galois connection.
Fourth, every Galois connection has an associated notion of distance. This distance is used to define a metric on the sets that are connected by the Galois connection. This metric allows us to measure how “far” one element is from another.
Finally, every Galois connection has an associated notion of connectedness. This allows us to determine whether two elements are “connected” by the given Galois connection.
Galois connections can be used to model a wide variety of relationships between objects. In computer science, they are used to define data structures and algorithms. In linguistics, they are used to describe the relationship between meaning and sound in language.
Galois connections are also used in category theory, a branch of mathematics that deals with the structure of objects and their relationships. In particular, Galois connections are used to define adjunctions between categories.
Finally, Galois connections can be used to study problems in physics and engineering. For example, they can be used to model the propagation of waves through a medium.
Galois connections are a powerful tool for understanding relationships between sets. This book is a complete guide to the theory of Galois connections, with plenty of examples and exercises to help you along the way.
There are two ways to construct a Galois connection. The first is to start with a closure operator and an interior operator, and then to define the associated mapping between the sets. The second is to start with a partial order and a metric, and then to define the associated closure and interior operators.
Let \((X,\preceq)\) and \((Y,\leqslant)\) be ordered sets.
Definition 7.11 If \(f_*:X\to Y\) and \(f^*:Y\to X\) are functions such that \[\begin{equation} \label{gc} f_*(x)\leqslant y \Longleftrightarrow x\preceq f^*(y) \end{equation}\] for all \(x\in X\) and all \(y\in Y\), then \((f_*, f^*)\) is called a Galois connection between \((X,\preceq)\) and \((Y,\leqslant)\).
There are several definitions of Galois connections in the literature; however they are all order-isomorphic to the definition above.
Theorem 7.42 Let \(f_*:X\to Y\) and \(f^*:Y\to X\) be functions. Then \((f_*, f^*)\) is a Galois connection if and only if
- both \(f_*\) and \(f^*\) are monotone,
- \(x\preceq (f^*\circ f_*)(x)\) for all \(x\in X\), and
- \((f_* \circ f^*)(y)\leqslant y\) for all \(y\in Y\).
Proof. Suppose \((f_*, f^*)\) is a Galois connection. By \(\eqref{gc}\) it follows \[ f_*(x)\leqslant f_*(x) \Longleftrightarrow x\preceq (f^*\circ f_*)(x). \] Since \(\leqslant\) is reflexive, \(x\preceq (f^*\circ f_*)(x)\) follows immediately. Similarly, by \(\eqref{gc}\) it follows \[ (f_*\circ f^*)(y)\leqslant y \Longleftrightarrow f^*(y)\preceq f^*(y) \] proving that \(\eqref{gc3}\) also holds. Assume \(x_1\preceq x_2\). By \(\eqref{gc2}\) we have \(x_2\preceq (f^*\circ f_*)(x_2)\). By \(\eqref{gc}\) it follows \(f_*(x_1)\leqslant f_*(x_2)\) and so \(f_*\) is monotone. Assume \(y_1\leqslant y_2\). By \(\eqref{gc3}\) we have \((f_*\circ f^*)(y_1)\leqslant y_1\). By \(\eqref{gc}\) it follows \(f^*(y_1)\preceq f^*(y_2)\) and so \(f^*\) is also monotone.
Conversely, assume \(\eqref{gc1}\), \(\eqref{gc2}\), and \(\eqref{gc3}\) all hold. Assume \(f_*(x)\leqslant y\). By \(\eqref{gc1}\) and \(\eqref{gc2}\), it follows \((f^*\circ f_*)(x)\preceq f^*(y)\) and \(x\preceq (f^*\circ f_*)(x)\), respectively. By transitivity of \(\preceq\), we have \(x\preceq f^*(y)\) as needed. Assume \(x\preceq f^*(y)\). By \(\eqref{gc1}\) and \(\eqref{gc3}\), it follows \(f_*(x)\leqslant (f_*\circ f^*)(y)\) and \((f_*\circ f^*)(y)\leqslant y\). By transitivity of \(\leqslant\), we have \(f_*(x)\leqslant y\) as needed. Therefore, \(\eqref{gc}\) holds and so \((f_*, f^*)\) is a Galois connection.
Theorem 7.43 Let \(f_*:X\to Y\) and \(f^*:Y\to X\) be mappings. Then \((f_*, f^*)\) is a Galois connection if and only if \[ f^*(y) \succeq x \Longleftrightarrow y \succeq f_*(x) \]
Proof. Suppose \(\eqref{gc}\) holds. Then \[ f_*(x) \succeq f_*(x) \Longleftrightarrow (f^*\circ f_*)(x) \succeq x. \] Since \(\succeq\) is reflexive, \((f^*\circ f_*)(x)\succeq x\) follows immediately. Similarly, by \(\eqref{gc}\) it follows \[ y \succeq (f_*\circ f^*)(y) \Longleftrightarrow f^*(y)\succeq f^*(y) \] proving that \(\eqref{galcon}\) holds.
Assume \(x_2\succeq x_1\). By \(\eqref{galcon}\) we have \((f^*\circ f_*)(x_2)\succeq x_2\succeq x_1\). By \(\eqref{gc}\) it follows \(f_*(x_2)\succeq f_*(x_1)\) and so \(f_*\) is isotone. Assume \(y_1\succeq y_2\). By \(\eqref{galcon}\) we have \(y_1\succeq y_2 \succeq (f_*\circ f^*)(y_2)\). By \(\eqref{gc}\) it follows \(f^*(y_1)\succeq f^*(y_2)\) and so \(f^*\) is also isotone.
Conversely, assume \(\eqref{galcon}\) holds. Assume \(y\succeq f_*(x)\). It follows \(f^*(y)\succeq (f^*\circ f_*)(x)\) and \((f^*\circ f_*)(x)\succeq x\) and so by transitivity of \(\succeq\) we have \(f^*(y)\succeq x\) as needed. Assume \(f^*(y)\succeq x\). It follows \((f_*\circ f^*)(y)\succeq f_*(x)\) and \(y\succeq (f_*\circ f^*)(y)\) and so by transitivity of \(\succeq\) we have \(y\succeq f_*(x)\) as needed. Therefore \(\eqref{gc}\) holds and so \((f_*, f^*)\) is a Galois connection.
Theorem 7.44 If \((f_*, f^*)\) is a Galois connection between \((X,\preceq)\) and \((Y,\leqslant)\), then
- \(f^*(y)=\max\{x\in X : y\succeq f_*(x)\}\),
- \(f_*\circ f^* \circ f_*=f_*\),
- \(x\in f^*(Y)\) if and only if \(x\) is a fixed point of \(f^*\circ f_*\),
- \(f^*(Y)=(f^*\circ f_*)(X)\), and
Proof. \(\eqref{gcmax}\): Let \(M=\{x\in X: y\succeq f_*(x)\}\). By \(\eqref{galcon}\) we have \(f^*(y)\in M\). Let \(x\in M\). Then \(y\succeq f_*(x)\) and since \(f^*\) is isotone, it follows \(f^*(y)\succeq (f^*\circ f_*)(x)\). By \(\eqref{galcon}\), we have \((f^*\circ f_*)(x)\succeq x\). By transitivity of \(\succeq\), we have \(f^*(y)\succeq x\) and thus \(f^*(y)\) is the maximum of \(M\). \(\eqref{gcprop1}\): By \(\eqref{galcon}\) we have \(f_*(x) \succeq (f_*\circ f^*\circ f_*)(x)\). By \(\eqref{gc}\) with \(x:=(f^*\circ f_*)(x)\) and \(y:=f_*(x)\) it follows \((f_*\circ f^* \circ f_*)(x)\succeq f_*(x)\) using that \(\succeq\) is reflexive.
Since \(\succeq\) is antisymmetric, it follows \(f_*(x)=(f_*\circ f^*\circ f_*)(x)\) for arbitrary \(x\). \(\eqref{gcprop3}\): Clearly \(x\in f^*(Y)\) is equivalent to \(f^*(y)=x\) for some \(y\in Y\). Then \[
(f^*\circ f_*)(x)=(f^*\circ f_* \circ f^*)(y)=f^*(y)=x
\] follows by the dual of \(\eqref{gcprop1}\). \(\eqref{gcprop5}\): It follows by \(\eqref{gcprop3}\) that \(f^*(Y)\subseteq (f^*\circ f_*)(X)\). Conversely, let \(x\in (f^*\circ f_*)(X)\). Then \(x=f^*(y)\) for some \(y\in f_*(X)\subseteq Y\). By definition, \(x\in f^*(Y)\) and so \((f^*\circ f_*)(X)\subseteq f^*(Y)\).
::: {#thm-galois connection-injective } If \((f_*, f^*)\) is a Galois connection, then \(f_*\) is injective if and only if \(f^*\) is surjective if and only if \(f_*\circ f^*\) is the identity. :::
Proof. By \(\ref{gcprop}\), every element of \(X\) is a fixed element of \(f^*\circ f_*\) if and only if \(f^*(Y)=X\). Thus \(f^*\) is surjective if and only if \(f^*\circ f_*\) is the identity of \(X\). Assume \(f^*\circ f_*\) is the identity of \(X\). Then \[ f_*(x)=f_(y)\implies x=(f^*\circ f_*)(x)=(f^*\circ f_*)(y)=y \] which shows \(f_*\) is injective. Conversely, if \(f_*\) is injective then, for arbitrary \(x\in X\), \((f_*\circ f^*\circ f_*)(x)=f_*(x)\) implies \((f^*\circ f_*)(x)=x\) and so \(f^*\circ f_*\) is the identity of \(X\).
Theorem 7.45 If \((f_*,g)\) and \((f_*, h)\) are Galois connections between \((X,\preceq)\) and \((Y,\leqslant)\), then \(g=h\). Likewise, if \((g, f^*)\) and \((h,f^*)\) are Galois connections between \((X,\preceq)\) and \((Y,\leqslant)\), then \(g=h\).
Proof. Let \(f_*:X \to Y\) and \(g:Y\to X\) be a Galois connection. Also let \(f_*\) and \(h:Y\to X\) be a Galois connection. By \(\eqref{gc}\) we have the following
\[
f_*(x) \leqslant y \Longleftrightarrow x\preceq g(y)
\] \[
f_*(x)\leqslant y \Longleftrightarrow x\preceq h(y)
\] By \(\eqref{ugc1}\) we have \((f_*\circ h)(y)\leqslant y \Longleftrightarrow h(y)\preceq g(y)\).
Notice \((f_*\circ h)(y)\leqslant y\) holds by \(\ref{gcch}\).\(\eqref{gc3}\); and thus \(h(y)\preceq g(y)\).
By \(\eqref{ugc2}\) we have \((f_*\circ g)(y)\leqslant y \Longleftrightarrow g(y)\preceq h(y)\).
Notice \((f_*\circ g)(y)\leqslant y\) holds by \(\ref{gcch}\).\(\eqref{gc3}\); and thus \(h(y)\preceq g(y)\).
Since \(\preceq\) is antisymmetric, it follows \(g(y)=h(y)\) for arbitrary \(y\). The second statement is the dual of the first and follows just as easily using \(\ref{gcch}\).\(\eqref{gc2}\).
Theorem 7.46 If \((f_*, f^*)\) is a Galois connection between \((X,\preceq)\) and \((Y,\leqslant)\), then
- \(f^*(y)=\textrm{the maximum of } \{x\in X : f_*(x)\leqslant y\}\) and
- \(f_*(x)=\textrm{the minimum of } \{y\in Y : x\preceq f^*(y)\}\).
Proof. Let \(M=\{x\in X: f_*(x)\leqslant y\}\). By \(\ref{gcch}\).\(\eqref{gc3}\) we have \(f^*(y)\in M\).
Let \(x\in M\).
Then \(f_*(x)\leqslant y\) and since \(f^*\) is monotone, it follows \((f^*\circ f_*)(x)\preceq f^*(y)\). By \(\ref{gcch}\).\(\eqref{gc2}\), we have \(x\preceq (f^*\circ f_*)(x)\). By transitivity of \(\preceq\), we have \(x\preceq f^*(y)\) and thus \(f^*(y)\) is the maximum of \(M\). For the second statement, let \(N=\{y\in Y : x\preceq f^*(y)\}\).
By \(\ref{gcch}\).\(\eqref{gc2}\) we have \(f_*(x)\in N\).
Let \(y\in N\). Then \(x\preceq f^*(y)\) and since \(f_*\) is monotone, it follows \(f_*(x)\leqslant (f_*\circ f^*)(y)\).
By \(\ref{gcch}\).\(\eqref{gc3}\), we have \((f_*\circ f^*)(y)\leqslant y\) and so by transitivity, it follows \(f_*(x)\leqslant y\). Thus \(f_*(x)\) is the minimum of \(N\).
Theorem 7.47 If \((f_*, f^*)\) is a Galois connection between \((X,\preceq)\) and \((Y,\leqslant)\), then
- \(f_*\circ f^* \circ f_*=f_*\), \(f^*\circ f_* \circ f^*=f^*\),
- \(x\in f^*(Y)\) if and only if \(x\) is a fixed point of \(f^*\circ f_*\),
- \(y\in f_*(X)\) if and only if \(y\) is a fixed point of \(f_*\circ f^*\),
- \(f^*(Y)=(f^*\circ f_*)(X)\), and \(f_*(X)=(f_*\circ f^*)(Y)\).
Proof. \(\eqref{gcprop1}\): Using \(\ref{gcch}\), we have \(f_*(x)\leqslant (f_*\circ f^*\circ f_*)(x)\). By \(\eqref{gc}\) with \(x:=(f^*\circ f_*)(x)\) and \(y:=f_*(x)\) it follows \((f_*\circ f^* \circ f_*)(x)\leqslant f_*(x)\) using that \(\preceq\) is reflexive. Since \(\leqslant\) is antisymmetric, it follows \(f_*(x)=(f_*\circ f^*\circ f_*)(x)\) for arbitrary \(x\), thus proving \(\eqref{gcprop1}\) holds. \(\eqref{gcprop3}\): By definition, \(x\in f^*(Y)\) is equivalent to \(f^*(y)=x\) for some \(y\in Y\). Then \[
(f^*\circ f_*)(x)=(f^*\circ f_* \circ f^*)(y)=f^*(y)=x
\]
follows by \(\eqref{gcprop1}\). \(\eqref{gcprop5}\): It follows by \(\eqref{gcprop3}\) that \(f^*(Y)\subseteq (f^*\circ f_*)(X)\). Conversely, let \(x\in (f^*\circ f_*)(X)\). Then \(x=f^*(y)\) for some \(y\in f_*(X)\subseteq Y\). By definition, \(x\in f^*(Y)\) and so \((f^*\circ f_*)(X)\subseteq f^*(Y)\).
Theorem 7.48 If \((f_*, f^*)\) is a Galois connection between \((X,\preceq)\) and \((Y,\leqslant)\), then
- \(x \preceq f^*(y) \Longleftrightarrow f_*(x)\leqslant (f_*\circ f^*)(y) \Longleftrightarrow f_*(x)\leqslant y \Longleftrightarrow (f^*\circ f_*)(x)\preceq f^*(y)\),
- \(f^*(x)\preceq f^*(y) \Longleftrightarrow (f_*\circ f^*)(x)\leqslant (f_*\circ f^*)(y) \Longleftrightarrow (f_*\circ f^*)(x)\leqslant y\)
- \(f_*(x)\leqslant f_*(y) \Longleftrightarrow (f^*\circ f_*)(x)\preceq (f^*\circ f_*)(y) \Longleftrightarrow x\preceq (f^*\circ f_*)(x)\),
- \(f^*(x)=f^*(y) \Longleftrightarrow (f_*\circ f^*)(x)=(f_*\circ f^*)(y)\), and
- \(f_*(x)=f_*(y) \Longleftrightarrow (f^*\circ f_*)(x)=(f^*\circ f_*)(y)\).
Proof. For the first statement we have \[\begin{align*} x \preceq f^*(y) & \implies f_*(x)\leqslant (f_*\circ f^*)(y) \implies f_*(x)\leqslant y \\ & \implies (f^*\circ f_*)(x) \preceq f^*(y) \implies x\preceq f^*(y) \end{align*}\] For the third statement we have \[\begin{align*} f^*(x) \preceq f^*(y) & \implies (f_*\circ f_*)(x)\leqslant (f_*\circ f^*)(y) \implies (f_*\circ f_*)(x)\leqslant y \end{align*}\] For the fourth statement we have \[\begin{align*} f^*(x)=f^*(y) & \Longleftrightarrow f^*(x)\preceq f^*(y) \land f^*(y) \preceq f^*(x) \\ & \Longleftrightarrow (f_*\circ f^*)(x)\leqslant (f_*\circ f^*)(y) \land (f_*\circ f^*)(y)\leqslant (f_*\circ f^*)(x) \\ & \Longleftrightarrow (f_*\circ f^*)(x)=(f_*\circ f^*)(y) \end{align*}\] The remaining statements are the dual and easily proved.
Definition 7.12 By an order isomorphism from an ordered set \(X\) to another ordered set \(Y\) we shall mean an isotone bijection \(f:X\to Y\) whose inverse \(f^{-1}: Y\to X\) is also an isotone.
Theorem 7.49 Ordered sets \((X,\preceq)\) and \((Y,\leqslant)\) are isomorphic if and only if there is a surjective mapping \(f:X\to Y\) such that \[ x\preceq y \Longleftrightarrow f(x)\leqslant f(y). \]
Proof. The necessity is clear. Suppose conversely that such a surjective mapping \(f\) exists. Then \(f\) is also injective; for if \(f(x)=f(y)\) then from \(f(x)\leqslant f(y)\) we obtain \(x\preceq y\) and from \(f(y)\leqslant f(x)\) we obtain \(y\preceq x\), so that \(x=y\). Hence \(f\) is a bijection. Clearly, \(f\) is isotone; and so also is \(f^{-1}\), since \(x\preceq y\) can be written \(f(f^{-1}))(x)\leqslant f(f^{-1})(y)\) which gives \(f^{-1}(x)\preceq f^{-1}(y)\).
Theorem 7.50 If \((f_*, f^*)\) is a Galois connection between \((X,\preceq)\) and \((Y,\leqslant)\), then \(f^*(Y)\) and \(f_*(X)\) are order-isomorphic.
Proof. This follows immediately from \(\ref{gcch}\) and \(\ref{posetiso}\).
Theorem 7.51 If \((f_*, f^*)\) is a Galois connection between \((X,\preceq)\) and \((Y,\leqslant)\), then \(f^*\circ f_*\) is a closure function for \(X\) and \(f_*\circ f^*\) is a co-closure function for \(Y\).
Proof. Let \(x\in X\). Then \(x\preceq (f^*\circ f_*)(x)\) follows by \(\ref{gcch}\).\(\eqref{gc2}\). Since both \(f^*\) and \(f_*\) are monotone we have, \(x_1\preceq x_2 \implies (f^*\circ f_*)(x_1)\preceq (f^*\circ f_*)(x_2)\). Thus \(f^*\circ f_*\) is also monotone. By associativity of functions and \(\ref{gcprop}\).\(\eqref{gcprop1}\) we have \[
(f^*\circ f_*)\circ (f^*\circ f_*)=f^*\circ (f_*\circ f^*\circ f_*)=f^*\circ f_*
\]
as needed. The dual statement is proved just as easily.
By \(\ref{gcprop}\), the closed elements of \(f^*\circ f_*\) and \(f_*\circ f^*\) are precisely the elements that are an image of some element under \(f^*\), respectively \(f_*\).
Theorem 7.52 If \(f\) is a closure (respectively co-closure) function, then there is a Galois connection \((f_*,f^*)\) such that \(f=f^*\circ f_*\) (respectively \(f=f_*\circ f^*\)).
Proof. Let \(f:X\to X\) be a closure over \((X,\preceq)\). Let \(\overline{X}\) be the set of closed elements of \(f\) that is \(f(X)=\overline{X}\). We will construct a Galois connection between \(\overline{X}\) and \(X\) using \(\ref{gcch}\). Let \(f_*=f\), that is \(f_*:X\to \overline{X}\) defined by \(f_*(x)=f(x)\) for all \(x\in X\). Let \(f^*:\overline{X}\to X\) be the inclusion mapping, that is \(f^*(x)=x\) for all \(x\in \overline{X}\). Notice \(f_*\circ f^*\) is the identity on \(\overline{X}\) and \(f^*\circ f_*=f\).
- Notice \(f_*\) is monotone since \(f\) is monotone and that \(f^*\) is monotone since the identity is monotone.
- Let \(x\in X\). Since \(f\) is extensive, we have \(x\preceq f(x)\). Thus it follows, \[ x\preceq f(x)=(f^*\circ f)(x)=(f^*\circ f_*)(x). \]
- Let \(y\in \overline{X}\). There exists \(x\in X\) such that \(y=f(x)\). Since \(f\) is idempotent we have \[ f(y)=(f\circ f)(y)\preceq y \] for all \(y\in \overline{X}\) as needed.
Therefore, \((f_*,f^*)=(f,f^*)\) where \(f^*:\overline{X}\to X\) is the inclusion mapping is a Galois connection between \((X,\prec0\) and \((\overline{X},\preceq)\).
Remark. A Galois connection is not uniquely determined by a closure.
Theorem 7.53 Let \(R\) be a relation between \(X\) and \(Y\) and let \[\begin{align} & f_R(A)=\{b\in Y:\forall a (a\in A\implies (a,b)\in R) \} \\ & f^R(B)=\{a\in X:\forall b (b\in B\implies (a,b)\in R) \}. \end{align}\] Then \((f_R, f^R)\) is a Galois connection between \((P(X),\subseteq)\) and \((P(Y),\supseteq)\)
Proof. Clearly, \(f_R:P(X)\to P(Y)\) and \(f^R:P(Y)\to P(X)\) are functions. By \(\eqref{gc}\) we must show
\[\begin{equation} \label{gcrel} f_R(A)\supseteq B \Longleftrightarrow A\subseteq f^R(B) \end{equation}\]
for all \(A\in P(X)\) and all \(B\in P(Y)\). Assume \(B\subseteq f_R(A)\). We will show \(A\subseteq f^R(B)\). Let \(x\in A\). If \(y\in B\), then \(y\in f_R(A)\). Then, by \(\eqref{gcrel1}\), it follows \((x,y)\in R\). So we have shown, \(y\in B\implies (x,y)\in R\) as needed to show \(x\in f^R(B)\) Conversely, assume \(A\subseteq f^R(B)\). We will show \(B\subseteq f_R(A)\). Let \(y\in B\). If \(x\in A\), then \(x\in f^R(B)\).Then, by \(\eqref{gcrel2}\), it follows \((x,y)\in R\). So we have shown, \(x\in A\implies (x,y)\in R\) as needed to show \(y\in f_R(A)\). Therefore, \(\eqref{gcrel}\) holds.
A relation \(R\) is a subset of \(X\times Y\) where \(X\) and \(Y\) are sets. If \((a,b)\in R\), then we say \(a\) is related to \(b\) by \(R\) and we write \(aRb\). Whenever \(X=Y\) we say that \(R\) is a relation on \(X\).
Definition 7.13 A relation \(R\) on a set \(X\) is called
- reflexive if \(aRa\) for all \(a\in X\),
- irreflexive if \(\neg(aRa)\) for all \(a\in X\),
- symmetric if \(aRb\) implies \(bRa\) for all \(a,b\in X\),
- asymmetric if \(aRb\) implies \(\neg(bRa)\) for all \(a,b\in X\),
- antisymmetric if (\(aRb \text { and } bRa) \Rightarrow a=b\) for all \(a,b\in X\),
- transitive if \((aRb \text{ and } bRc)\Rightarrow aRc\) for all \(a,b,c\in X\),
- antitransitive if \((aRb \text{ and } bRc)\Rightarrow \neg(aRc)\) for all \(a,b,c\in X\),
- a preorder if \(aRb \Leftrightarrow \big(\forall c\in X \ cRa \Rightarrow cRb\, \big)\) for all \(a,b,c\in X\),
- an equivalence relation if \(aRb \Leftrightarrow \big(\forall c\in X \ cRa \Leftrightarrow cRb\, \big)\) for all \(a,b,c\in X\).
The asymmetric part of a preorder \(\succeq\) (denoted by \(\succ\)) is called a , i.e. \(\succ\) is a strict preorder means there holds
\[\begin{equation} \forall \, a,b \in X \qquad a\succ b \Leftrightarrow (a\succeq b \text{ and } b\not\succeq a). \end{equation}\]
Associated with any preorder are its and , namely (respectively) subsets of the form \[
{{\downarrow}(a) = \{x\in X : a\succeq x\}}
\qquad \text{and} \qquad
{{\uparrow}(a) = \{x\in X : x\succeq a\}}.
\] If \(A\subseteq X\), then \(A\) is called an whenever \((x\in A, \, y\in X, \text{ and } y\succeq x) \Rightarrow y\in A\) and is called a whenever \((x\in A, \, y\in X, \text{ and } x\succeq y) \Rightarrow y\in A\). A preorder relation \(\succeq\) together with the underlying set is called a and is denoted by \({(X,\succeq)}\). In particular, if \(\succeq\) is also symmetric i.e. an equivalence relation (denoted by \(\sim\)), then sets of the form
\[
[a] = \{x \in X : a\sim x\} = {\uparrow}(a) = {\downarrow}(a).
\] are called equivalence classes (we denote the collection of all equivalence class by \(\overline{X}\)). It is interesting that whenever we have a preorder \(\succeq\) the relation \(\approx\) prescribed on \(X\) by
\[\begin{equation} \forall \, a,b \in X \qquad a\approx b \Leftrightarrow (a\succeq b \text{ and } b\succeq a) \end{equation}\]
is an equivalence relation. Further, we say an element \(a\) of a subset \(A\) of \(X\) is a maximum (resp. ) minimum for \(A\) whenever \(a\succeq x\) (\(x \succeq a\)) for all \(x\in A\). Let \(M(A)\) and \(m(A)\) denote the collection of maximums and minimums of a subset \(A\) of \(X\), respectively. In point, if either \(a,b\in M(A)\) or \(a,b\in m(A)\), then \(a\approx b\).
Definition 7.14 A mapping \(f: (X,\succeq) \to (Y,\succeq)\) between preordered sets is called
- isotone if \(a \succeq b \Rightarrow f(a) \succeq f(b)\) for all \(a,b\in X\),
- antitone if \(a \succeq b \Rightarrow f(b) \succeq f(b)\) for all \(a,b\in X\),
- monotone if it is either isotone or antitone.
Further, if \(Y=X\), then \(f\) is called 1. inflationary if \(f(a)\succeq a\) for all \(a\in X\), 2. deflationary if \(a\succeq f(a)\) for all \(a\in X\), 3. quasi-idempotent if \(f(a)\approx (f\circ f)(a)\) for all \(a\in X\), 4. idempotent if \(f(a)=(f\circ f)(a)\) for all \(a\in X\), 5. a closure operator if \(f(b)\succeq a \Leftrightarrow f(b)\succeq f(a)\) for all \(a,b\in X\), 6. a kernel operator \(a\succeq f(b) \Leftrightarrow f(a)\succeq f(b)\) for all \(a,b\in X\).
We call a preorder relation \(\geq\) on set \(X\) that is also antisymmetric a partial order and we say that \((X,\geq)\) is an ordered set. A mapping \(f:X\to Y\) between ordered sets \({(X,\geq)}\) and \({(Y,\succeq)}\) is called an isomorphism if it is surjective and \({x \geq y \Leftrightarrow f(x) \succeq f(y)}\) for all \(x,y\in X\); and is called a if it is surjective and \(x \geq y \Leftrightarrow f(y) \succeq f(x)\) for all \(x,y\in X\). A mapping \(f: X \to Y\) is an isomorphism if and only if \(f\) is bijective and both \(f\) and \(f^{-1}\) are isotone. For any set \(X\), the mapping \(\phi: X\to \mathcal{X}\) prescribed by \({\phi(x)= \, {\downarrow}{x}}\) is an isomorphism onto the set of all principal down-sets of \(X\).
It is straightforward to show that a mapping \(f\) on a preordered (ordered) set is a closure if and only if it is isotone, inflationary, and quasi-idempotent (idempotent). For example, the reflexive (symmetric, transitive) closure of a relation \(R\) is the intersection of all reflexive (symmetric, transitive) relations that contain \(R\), respectively. We denote these closures by \(r(R)\), \(s(R)\), and \(t(R)\) respectively, and we find there holds
\[\begin{equation} \label{relclsoure} r(R)=R \cup I_X, \qquad s(R)=R \cup R^{-1}, \qquad t(R)=\bigcup_{n\geq 1} R^n. \end{equation}\]
We say that a relation \(R\) generates an equivalence relation \(\sim\) whenever \(\sim = rts(R)\).
Definition 7.15 Let \(R\) and \(S\) be relations on sets \(X\) and \(Y\), respectively, and let \(f:X\to Y\) and \(g:Y\to X\) be mappings. The pair \((f,g)\) is called
- a covariant connection between \((X,R)\) and \((Y,S)\), denoted by \({(f,g):(X,R) \leftrightarrow (Y,S)}\) whenever \(g(b) \,R\, a \Leftrightarrow b\,S\,f(a), \forall \, a\in X, \forall \, b\in Y.\)
- an inverse covariant connection between \((X,R)\) and \((Y,S)\), denoted by \({(f,g):(X,R) \leftrightarrow (Y,S)}\) whenever \(a\,R\, g(b) \Leftrightarrow f(a)\,S\,b, \forall \, a\in X, \forall \, b\in Y.\)
- a contravariant connection between \((X,R)\) and \((Y,S)\), denoted by \({(f,g):(X,R) \leftrightarrow (Y,S)}\) whenever \(g(b)\,R\,a \Leftrightarrow f(a)\,S\,b, \forall \, a\in X, \forall \, b\in Y.\)
- an inverse contravariant connection between \((X,R)\) and \((Y,S)\), denoted by \({(f,g):(X,R) \leftrightarrow (Y,S)}\) whenever \(a\,R\,g(b) \Leftrightarrow b\,S\, f(a), \forall \, a\in X, \forall \, b\in Y.\)
Generically, we say \((f,g)\) forms a connection between \((X,R)\) and \((Y,S)\), denoted by \({(f,g):(X,R) \leftrightarrow (Y,S)}\) whenever \(\leftrightarrow\,\in\{\leftrightarrow, \leftrightarrow,\leftrightarrow,\leftrightarrow\}\). \footnote{The notation used here in defining a connection was found in (García-Pardo et al. 2013)).
Example 7.1 If \(f:X\to Y\) is a bijection then \((f,f^{-1}):(X,=)\leftrightarrow (Y,=)\) is a connection of any type. More generally, if \(f\) is injective, then \((f,f^{-1}):(X,=)\leftrightarrow (\text{Im} f,=)\) is a connection of any type.
Example 7.2 The collection of up-sets \(\tau^R\) of a preorder relation \(R\) on a nonempty set \(X\) forms an Alexandroff topology on \(X\). Conversely, if \(\tau\) is a topology on \(X\) and if \(R^\tau\) denotes the relation on \(X\) prescribed by
\[\begin{equation} b \ R^\tau a \ \Leftrightarrow \ \forall O\in \tau\, ( b\in O \Rightarrow a\in O ), \end{equation}\]
for all \(a,b\in X\), then \(R^\tau\) is a preorder relation on \(X\) (called the of \(\tau\)). Also notice that we have mappings prescribed by
- \(f:Q(X)\to A(X), \quad f(R)=\tau^R\)
- \(g:A(X)\to Q(X), \quad g(\tau)=R^\tau\)
where \(Q(X)\) and \(A(X)\) denote the collection of all preorder relations and all Alexandroff topologies on a set \(X\), respectively. Then for any preorder relation \(R\) on \(X\), and any Alexandroff topology \(\tau\) on \(X\), we have
\[\begin{equation} (g\circ f)(R)=R \qquad \text{ and } \qquad (f\circ g)(\tau)=\tau. \end{equation}\]
In other words, there is a natural bijection where \(f\) and \(g\) are inverses of each other. Hence \((f,g)\) forms a connection of any type and we see that preorder relations and Alexandroff topologies are essential the same. Of course the same can be said for the special case of equivalence relations and partitions.
The next four propositions are either elementary or can be found in .
Lemma 7.1 If \((f,g)\) and \((f, h)\) are contravariant connections between preordered sets \((X,\geq)\) and \((Y,\succeq)\), then \(g\approx h\).
Proof. Suppose we have maps \(f:X \to Y\), \(g:Y\to X\), and \(h:Y\to X\) such that
\[\begin{align} \label{ugc1} g(b)\geq a \Leftrightarrow f(a)\succeq b \qquad (\forall a\in X, \forall b\in Y) \\ \label{ugc2} h(b)\geq a \Leftrightarrow f(a)\succeq b \qquad (\forall a\in X, \forall b\in Y) \end{align}\]
We have \((f\circ h)(b)\succeq b\) if and only if \(g(b)\geq h(b)\). Notice \((f\circ h)(b)\succeq b\) holds; and thus \(g(b)\geq h(b)\). We have \((f\circ g)(b)\succeq b\) if and only if \(h(b)\geq g(b)\). Notice \((f\circ g)(b)\succeq b\) holds; and thus \(h(b)\geq g(b)\). Hence \(g(b)\approx h(b)\) for arbitrary \(b\).
Lemma 7.2 If \(f:X\to Y\), \(g:Y\to X\) are mappings between preordered sets \((X,\geq)\) and \((Y,\succeq)\), then the following are equivalent:
- \((f,g):(X,\geq) \leftrightarrow (Y,\succeq)\) is a contravariant connection
- \(f\) and \(g\) are antitone maps, and \(g\circ f\), \(f\circ g\) are inflationary maps
- \({\downarrow} f(a)=g^{-1}({\uparrow} a)\), for all \(a\in X\)
- \({\downarrow} g(b)=f^{-1}({\uparrow} b)\), for all \(b\in Y\)
- \(f\) is antitone and \(g(b)\in M(f^{-1}({\uparrow} b))\) for all \(b\in Y\).
- \(g\) is antitone and \(f(a)\in M(g^{-1}({\uparrow} a))\) for all \(a\in X\).
Proof. (1)\(\Rightarrow\)(2): Suppose \({g(b)\geq a \Leftrightarrow f(a)\succeq b}\) for all \(a\in X\) and \(b\in Y\). It follows that \((g\circ f)(a)\geq a\) and \((f\circ g)(b)\succeq b\) since \(\succeq\) is reflexive. Hence \(g\circ f\), \(f\circ g\) are inflationary maps. Assume \(a_1\geq a_2\) for any \(a_1, a_2\in X\). We have \((g\circ f)(a_1)\geq a_1\), and so by transitivity \((g\circ f)(a_1)\geq a_2\); hence \(f(a_2)\succeq f(a_1)\). Assume \(b_1\succeq b_2\) for any \(b_1, b_2\in X\). We have \((f \circ g)(b_1)\succeq b_1\), and so by transitivity \((f\circ g)(b_1)\succeq b_2\); hence \(g(b_2)\geq g(b_1)\).
(2)\(\Rightarrow\)(3):
On one hand we have \(f(a)\succeq b\) implies \({g(b) \geq (g\circ f)(a)\geq a}\) since \(g\) is antitone and \(g\circ f\) is inflationary. Conversely we have \(g(b)\geq a\) implies \({f(a)\succeq (f\circ g)(b)\succeq b}\) since \(f\) is antitone and \(f\circ g\) is inflationary. Hence \({f(a)\succeq b \Leftrightarrow g(b)\geq a}\) as needed to prove that \({\downarrow} f(a)=g^{-1}({\uparrow} a)\).
(3)\(\Rightarrow\)(4):
Let \(a\in X\) and \(b\in Y\) be arbitrary elements. We find \[\begin{align*}
g(b)\geq a \Leftrightarrow g(b)\in {\uparrow} a \Leftrightarrow b\in g^{-1}({\uparrow} a)={\downarrow} f(a)
\Leftrightarrow f(a)\succeq b \Leftrightarrow a\in f^{-1}({\uparrow} b).
\end{align*}\]
(4)\(\Rightarrow\)(5):
Assume that \(a_1\geq a_2\) for arbitrary elements \(a_1, a_2\in X\). Since \({f(a_1)\geq f(a_1)}\), clearly \(a_1\in f^{-1}({\uparrow} f(a_1))\).Further, since \(f^{-1}({\uparrow} f(a_1))={\downarrow} g(f(a_1))\) and \(a_1\geq a_2\), it follows that \(a_2\in f^{-1}({\uparrow} f(a_1))\). Hence \(f(a_2)\succeq f(a_1)\). For the second statement, let \(a\in f^{-1}({\uparrow} b)\). Then by hypothesis \(g(b)\geq a\), as needed.
(5)\(\Rightarrow\)(6):
Assume that \(b_1\succeq b_2\) for arbitrary elements \(b_1, b_2\in Y\). Since \({g(b_1)\in f^{-1}({\uparrow} b_1)}\) we have \((f\circ g)(b_1)\succeq b_1 \succeq b_2\). Hence \(g(b_1)\in f^{-1}({\uparrow} b_2)\) and so \(g(b_2)\geq g(b_1)\). Let \(a\in X\) be arbitrary and assume that \(b\in g^{-1}({\uparrow} a)\). Then \(g(b)\geq a\). Since \(f\) is antitone, we have \(f(a)\succeq (f\circ g)(b)\succeq b\) since \(g(b)\in f^{-1}({\uparrow} b)\).
(6)\(\Rightarrow\)(1):
Assume that \(g(b)\geq a\). Then \(b\in g^{-1}({\uparrow} a)\) and so \(f(a)\succeq b\) by hypothesis. Conversely, assume that \(f(a)\succeq b\). Then \(g(b)\geq (g\circ f)(a)\geq a\) as needed.
Lemma 7.3 If \({(f,g):(X,\geq) \leftrightarrow (Y,\succeq)}\) is a connection between preordered sets then \(f\circ g\) and \(g\circ f\) are closures Moreover, there holds
- If \((f,g)\) is a contravariant and inverse contravariant (covariant and inverse covariant) connection, then \((g\circ f)(a)\approx a\) for all \(a\in A\) and \((f\circ g)(b)\approx b\) for all \(b\in B\).
- If \((f,g)\) is a (contravariant or inverse contravariant) connect and a (covariant or inverse covariant) connection, then \(a_1\geq a_2\) implies \(f(a_1)\approx f(a_2)\) for all \(a_1,a_2\in X\) and \(b_1\succeq b_2\) implies \(g(b_1)\approx g(b_2)\) for all \(b_1,b_2\in Y\).
Proof. We prove this for the case of contravariant connections and leave the other cases for the reader as an exercise. Assume \({(f,g):(X,\geq) \leftrightarrow (Y,\succeq)}\) is a contravariant connection. By \(\ref{connprop}\), \(f\) and \(g\) are antitone and so it follows that \(f\circ g\) and \(g\circ f\) are isotone. Since \({f\circ g}\) is inflationary we have \({(f\circ g\circ f)(a)\succeq f(a)}\). Since \(g\circ f\) is inflationary we have \({(g\circ f)(a)\geq a}\) and so \(f(a)\succeq (f\circ g\circ f)(a)\) since \(f\) is antitone. Hence
\[\begin{equation} \label{equivclosure} {(f\circ g\circ f)(a)\approx f(a)} \end{equation}\]
for all \(a\in X\). Further since \(g\) is antitone we have \((g\circ f\circ g\circ f)(a) \succeq (g\circ f)(a)\) and \({(g\circ f)(a) \succeq (g\circ f\circ g\circ f)(a)}\). Thus \(g\circ f\) is quasi-idempotent. Since \(g\circ f\) is inflationary we have \({(g\circ f\circ g)(b)\succeq g(b)}\). Since \(f\circ g\) is inflationary we have \({(f\circ g)(b)\geq b}\) and so \({g(b)\succeq (g\circ f\circ g)(b)}\) since \(g\) is antitone. Hence \({(g\circ f\circ g)(b)\approx g(b)}\) for all \(b\in Y\). Further since \(f\) is antitone we have \((f\circ g\circ f\circ g)(b) \geq (f\circ g)(b)\) and \({(f\circ g)(b) \succeq (f\circ g\circ f\circ g)(b)}\). Thus \(f\circ g\) is quasi-idempotent.
- Suppose that \((f,g)\) is both a contravariant and inverse contravariant connection. Since \(g\circ f\) is both inflationary and deflationary, we have \((g\circ f)(a)\geq a\) and \(a\geq (g\circ f)(a)\) and so \((g\circ f)(a)\approx a\). Since \(f\circ g\) is both inflationary and deflationary, we have \((f\circ g)(b)\geq b\) and \(b\geq (f\circ g)(b)\) and so \((f\circ g)(b)\approx b\).
- Suppose that \((f,g)\) is both a contravariant and a covariant connection and assume that \(a_1\geq a_2\). Since \(f\) is isotone and antitone, we have \(f(a_1)\succeq f(a_2)\) and \(f(a_2)\succeq f(a_1)\) as needed. If \(b_1\succeq b_2\), then since \(g\) is isotone and antitone, we have \(g(b_1)\geq g(b_2)\) and \(g(b_2)\geq g(b_1)\) as needed.
Lemma 7.4 If \((X,\geq)\) and \((Y,\succeq)\) are preordered sets, there holds
\[\begin{equation} \label{connandpre} {(f,g):(X,\geq) \leftrightarrow (Y,\succeq)} \Rightarrow {(f_\approx,g_\approx):(\overline{X},\geqq) \leftrightarrow (\overline{Y},\succsim)} \end{equation}\]
where \(f_\approx([a])=[f(a)]\) for all \(a\in X\), \(g_\approx([b])=[g(b)]\) for all \(b\in B\), and \({\leftrightarrow\,\in\{\leftrightarrow, \leftrightarrow,\leftrightarrow,\leftrightarrow\}}\).
Proof. We prove this for the case of contravariant connections and leave the other cases for the reader as an exercise. Assume \({(f,g):(X,\geq) \leftrightarrow (Y,\succeq)}\) is a contravariant connection. We are assuming that \(g(b)\,\geq\,a \Leftrightarrow f(a)\,\succeq\,b\) for all \({a\in X, b\in Y}\). We must show that \({g_\approx([b])\,\geqq\,[a] \Leftrightarrow f_\approx([a])\,\succsim\,[b]}\) for all \({[a]\in \overline{X}, [b]\in \overline{Y}}\).
Suppose that \({g_\approx([b])\,\geqq\,[a]}\). Then \([g(b)]\,\geqq\,[a]\) and so \({g(b)\geq a}\), hence \({f(a)\succeq b}\). Thus we have that \({f_\approx([a])=[f(a)]\succsim [b]}\) as needed. Now suppose that \({f_\approx([a])\,\succsim\,[b]}\). Then \({[f(a)]\,\succsim\,[b]}\) and so \({f(a)\succeq b}\), hence \(g(b)\geq a\). Thus we have that \({g_\approx([b])=[g(b)]\succsim [a]}\) as needed.