Naive Set Theory: Relations

Relations


Given a particular set $S$, we may want to express a relationship between its elements. For example, given a set $F = \{\text{Mom}, \text{Dad}, \text{Brother}, \text{Sister} \}$, we may want to express the concept of descendant-ness. In this case, we would want to express that $\text{Brother}$ is a descendent of $\text{Mother}$ as well as a descendent of $\text{Father}$, and likewise for $\text{Sister}$. Alternatively, we may want to express the concept of sibling-ness, where $\text{Brother}$ is a sibling of $\text{Sister}$ and likewise that $\text{Sister}$ is a sibling of $\text{Brother}$.

On a more mathematical note, if we are thinking about the integers, we may want to express the fact that $2$ is less than $3$, and $3$ is less than $4$. Or perhaps if we are thinking about the rational numbers, we may want to express that $\dfrac{2}{3}$ is equivalent to $\dfrac{4}{6}$, even though the two fractions technically consist of different numbers. In order to express such a general concept of "relatedness," the set-theoretic object we're looking for must itself be quite general.

Such a concept is called a relation. A relation is a set of ordered pairs. The domain of a relation $R$ is the set of all first coordinates of ordered pairs in $R$, and is written as $\text{dom}(R)$. Likewise, the image set of a relation $R$ is the set of all second coordinates of ordered pairs in the relation, and is written as $\text{img}(R)$. A binary relation is a relation whose domain and image are both subsets of the same set. Equivalently, a binary relation is a subset of the cartesian product of a set with itself.

For example, a binary relation $S \subseteq F \times F$ expressing the sibling relationship could be $R = \{ (a, b) \in A \times A : a \text{ is a sibling of } b \}$. Then $R = \{ (\text{Brother}, \text{Sister}), (\text{Sister}, \text{Brother}) \}$. However, it is a bit verbose to write something like $(\text{Sister}, \text{Brother}) \in R$ to express set membership in a relation. Instead, we express a relation as $aRb$, where $(a,b) \in R$. In the preceding example, we would write $\text{Sister}R\text{Brother}$.

If the $aRb$ notation seems awkward, consider the fact that we don't need to use a letter to denote a relation. Instead, we could use a symbol like $<$. For example, we could define a relation $<$ for a set $V = \{\text{bicycle}, \text{car}, \text{jet}\}$ to be $< \; = \{ (a,b) \in V \times V : b \text{ is faster than } a\}$. So $\text{bicycle} < \text{jet}$ and $\text{car} < \text{jet}$ would denote valid members of the relation.

The definition of a relation is general enough to capture the idea of "this thing is somehow connected to that thing" while leaving the nature of that connection up to further specification. For example, The sibling relation is symmetric: $A$ is a sibling of $B$ if and only if $B$ is a sibling of $A$. However, that property isn't true of the descendant relation! Additional properties like symmetry (or anti-symmetry) turn generic relations into useful expressions of meaningful mathematical concepts.


Problems

  1. Let $F = \{\text{Mother},\text{Father},\text{Son},\text{Daughter},\text{You},\text{Spouse}\}$. Define the $\diamond$ relation to be $\diamond = \{ (a,b) \in F \times F : a \text{ is a descendant of } b \}$. List all of the members of $\diamond$ using both the regular bracket format and the special relation format.

    Bracket format: $\diamond = \{(\text{You}, \text{Father}), (\text{You}, \text{Mother}), (\text{Daughter}, \text{You}), (\text{Son}, \text{You}), (\text{Daughter}, \text{Spouse}), (\text{Son}, \text{Spouse}) \}$.

    Relation format: $\text{You}\diamond\text{Father}, \text{You}\diamond\text{Mother}, \text{Daughter}\diamond\text{You}, \text{Son}\diamond\text{You}, \text{Daughter}\diamond\text{Spouse}, \text{Son}\diamond\text{Spouse}$.

    Show Answer
  2. A relation $K$ is symmetric if for every $(a, b) \in K$, $(b, a) \in K$.

    Let $R$ be a binary relation on a set $A$, and let $T$ also be a binary relation on $A$ defined by $\{ (a, b) : (b, a) \in R\}$. Show that $R$ is symmetric if and only if $R = T$.

    $\implies$: If $R$ is symmetric, then for each $(a, b) \in R$, it is also true that $(b, a) \in R$. Because $(a, b) \in R$, by definition $(b, a) \in T$. Likewise, because $(b, a) \in R$, it is also true that $(a, b) \in T$. Thus every element that is in $R$ is also in $T$, and vice versa. Therefore $R = T$.

    $\impliedby$: Let $(a, b) \in R$. Because $R=T$, it follows that $(a, b) \in T$. By the construction of $T$, it also follows that $(b, a) \in T$. Because $R=T$, it follows again that $(b, a) \in R$. Because for every $(a, b) \in R$ it is the case that $(b, a) \in R$, $R$ is symmetric. 

    Show Answer