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.