17.2: Operations on Relations

Viewing relations as subsets of Cartesian products suggests ways to build new relations from old.

Definition: Union (of relations \(R_1,R_2\))

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

Definition: Intersection (of relations \(R_1,R_2\))

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

Definition: Complement (of relation \(R\))

the relation where \(a \mathrel{R^C} b\) means that \(a \mathrel{R} b\) is not true

Definition: \(a\ \not R\ b\)

alternative notation for \(a \mathrel{R^C} b\)

Note \(\PageIndex{1}\)

Considering relations as subsets of Cartesian products, the above relation operations mean precisely the same thing as the corresponding set operations.

Example \(\PageIndex{1}\): Union of “less than” and “equal to” relations.

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{.}\)

Example \(\PageIndex{2}\): Sibling relations.

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.

Example \(\PageIndex{3}\): Complement of the subset relation.

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.

Definition: Inverse (of a relation \(R\))

the relation where \(b \mathrel{R^{-1}} a\) means that \(a \mathrel{R} b\) is true

Note \(\PageIndex{2}\)

• 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{.}\)

Example \(\PageIndex{4}\): Parent/child relations.

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.

Example \(\PageIndex{5}\): Inverse of Division Relation.

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.

Example \(\PageIndex{6}\): Inverse of Logical Equivalence

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.

Definition: Empty Relation

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

Definition: Universal Relation

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.