17.2: Operations on Relations
- Page ID
- 83490
Viewing relations as subsets of Cartesian products suggests ways to build new relations from old.
the relation where \(a \mathrel{(R_1 \cup R_2)} b\) means that at least one of \(a \mathrel{R_1} b\) or \(a \mathrel{R_2} b\) is true
the relation where \(a \mathrel{(R_1 \cap R_2)} b\) means that both \(a \mathrel{R_1} b\) and \(a \mathrel{R_2} b\) are true
the relation where \(a \mathrel{R^C} b\) means that \(a \mathrel{R} b\) is not true
alternative notation for \(a \mathrel{R^C} b\)
Considering relations as subsets of Cartesian products, the above relation operations mean precisely the same thing as the corresponding set operations.
Consider the relations \(\mathord{\lt}\) and \(\mathord{=}\) on \(\mathbb{R}\text{,}\) and let \(R\) be the union \(\mathord{\lt} \cup \mathord{=}\text{.}\) Then \(x \mathrel{R} y\) means that at least one of \(x \lt y\) or \(x = y\) is true. That is, \(R\) is the same as the relation \(\mathord{\le}\text{.}\)
Let \(H\) represent the set of all living humans. Let relations \(R_F, R_M \subseteq H \times H\) be defined by
- \(a \mathrel{R_F} b\) if \(a,b\) have the same father; and
- \(a \mathrel{R_M} b\) if \(a,b\) have the same mother.
Set \(R_P = R_F \cap R_M\text{.}\) Then \(a \mathrel{R_P} b\) means that \(a,b\) have the same parents.
Let \(U\) be a universal set and consider the relation \(\mathord{\subseteq}\) on \(\mathscr{P}(U) \text{.}\) Then \(A \mathrel{\subseteq^C} B\) means that \(A\) is not a subset of \(B\text{,}\) which can only happen if some elements of \(A\) are not in \(B\text{.}\) In other words, \(A \mathrel{\subseteq^C} B\) means that \(A \cap B^C \ne \varnothing \text{.}\)
- Careful.
-
Relation \(A \mathrel{\subseteq^C} B\) does not (necessarily) mean \(A \subseteq B^C \text{.}\) Draw a representative Venn diagram to see why.
Unlike functions, which can only be reversed if bijective, every relation can be reversed by simply stating the relationship in the reverse order.
the relation where \(b \mathrel{R^{-1}} a\) means that \(a \mathrel{R} b\) is true
- As subsets of Cartesian products, if \(R \subseteq A \times B\text{,}\) then \(R^{-1} \subseteq B \times A\text{,}\) and \((a,b) \in R\) if and only if \((b,a) \in R^{-1}\text{.}\)
- A relation \(R\) and its inverse \(R^{-1}\) express the same relationship between elements of two sets \(A\) and \(B\text{,}\) just phrased in the opposite order. In logical terms, \({b \mathrel{R^{-1}} a} \Rightarrow {a \mathrel{R} b}\text{.}\)
Let \(H\) represent the set of all living humans, and let \(R\) represent the relation on \(H\) where \(h_1 \mathrel{R} h_2\) means human \(h_1\) is the parent of human \(h_2\text{.}\) Then \(h_2 \mathrel{R^{-1}} h_1\) means human \(h_2\) is the child of human \(h_1\text{.}\) Both relations express the same information, but in a different order.
Recall that \(\mid\) is a relation on \(\mathbb{N}_{>0}\) where \(m \mid n\) means that \(m\) divides \(n\text{.}\) Then for the inverse relation, \(n \mid^{-1} m\) means \(n\) is a multiple of \(m\text{.}\) Both relations express the same information, but in a different order.
Let \(\scr{L}\) represent the set of all possible logical statements. We have a relation \(\equiv\) on \(\scr{L}\text{,}\) where \(A \equiv B\) means that logical statement \(A\) involves the same statement variables and has the same truth table as logical statement \(B\text{.}\) Since \(A \equiv B\) if and only if \(B \equiv A\text{,}\) we conclude that the logical equivalence relation on \(\scr{L}\) is its own inverse.
There are two more set-theoretic ideas we can reinterpret as relations.
the relation between sets \(A\) and \(B\) corresponding to the empty subset \(\emptyset \subseteq A \times B\text{,}\) so that \(a \mathrel{\emptyset} b\) is always false
the relation between sets \(A\) and \(B\) corresponding to the full subset \(U = {A \times B} \subseteq {A \times B}\text{,}\) so that \(a \mathrel{U} b\) is always true.