Relations as Sets

Definition Binary relation

A binary relation on a set $A$ is a subset of $A^2 = A \times A$ . If $R \subseteq A^2$ is a binary relation on $A$ and $x, y \in A$ , we write $xRy$ for $(x, y) \in R$ .

The relation is indeed a rule that defines the set $R$ of pairs. The most basic relation is identity relation where elements relate themselves $(x, x) \in R$ when $x \in A$ , denoted as $\text{Id}_A$ .

Example

Let $A = \{ \textit{shorts}, \textit{t-shirt}, \textit{sweater}, \textit{socks} \}$ , when we define a relation "items that are normally worn together" the result would be

R = \{ (\textit{shorts}, \textit{t-shirt}), (\textit{sweater}, \textit{socks}) \}.

This may remind you of relational databases. Each row consist of pairs in $R$ such as $(\textit{shorts}, \textit{t-shirt})$ and elements are the columns. If we were to define three columns, we would need to define relation of relations $((\textit{shorts}, \textit{t-shirt}), \textit{sandals})$ .

Special Properties of Relations

Some kinds of relations turn out to be so common that they have been given special names. To get at exactly how these relations are similar, and how they differ, we categorize them according to some special properties that relation can have. It turns out that some of these special properties are especially important: orders and equivalence relations.

Definition Reflexivity

A relation $R \subseteq A^2$ is reflexive iff, for every $x \in A$ , $xRx$ .

Definition Transitivity

A relation $R \subseteq A^2$ is transitive iff, whenever $xRy$ and $yRz$ , then also $xRz$ .

Definition Symmetry

A relation $R \subseteq A^2$ is symmetric iff, whenever $xRy$ , then also $yRx$ .

The anti-symmetric relation is the opposite of symmetric relation, where the reverse is never true except when $x = y$ . However, the relation may not be reflexive.