Ordered sets and relations

The reason why ordered pairs, and ordered sets in general, are useful, is because they allow us to encode more structured information than just normal, unordered sets. For example, suppose we want to represent the fact that for three people, Jamal, Kerry, and Zoltan, some are friends with one another, and some aren’t. For each person, we can create the set of friends of that particular person with normal sets.

Suppose the following. Jamal is friends with Kerry, Zoltan is friends with Jamal, but Kerry is not friends with Zoltan. For each person, we may specify the set of friends they have, so that $S_J=\{\text{Kerry}, \text{Zoltan}\}$, $S_K=\{\text{Jamal}\}$ and $S_Z=\{\text{Jamal}\}$. These would be the properties ‘is the friend of Jamal’, ‘is the friend of Kerry’ and ‘is the friend of Zoltan’, respectively.

However, with ordered sets, we can do all of this in one set, representing the relation ‘is friends with’. First, we can immediately specify: $$F=\{\langle\text{Jamal}, \text{Kerry}\rangle, \langle\text{Kerry}, \text{Jamal}\rangle, \{\text{Zoltan}, \text{Jamal}\}, \langle\text{Jamal}, \text{Zoltan}\rangle\}$$ Note that we included, for both Jamal and Kerry, and Jamal and Zoltan, the two names in both configurations. This is useful, since we may desire to add lopsided relations that are not mutual. For example, suppose we want to represent that Jamal is friends with Kerry, and Kerry is friends with Jamal, Zoltan is friends with Jamal and Jamal is friends with Zoltan, and also that Kerry thinks Zoltan is her friend, but Zoltan does not view Kerry as a friend. Then, we can encode this as: $$F'=\{\langle\text{Jamal}, \text{Kerry}\rangle, \langle\text{Kerry}, \text{Jamal}\rangle, \{\text{Zoltan}, \text{Jamal}\}, \langle\text{Jamal}, \text{Zoltan}\rangle, \langle\text{Kerry}, \text{Zoltan}\rangle\}$$ Here, $F'$ represents the ‘is friends with’ relation again (in a different situation). But using this blueprint, any relation can be represented, starting from such pairs to more elaborate ones, like ‘$x$ is in between $y$ and $z$’, which would be a set of triples, and so on.

Related to sets of ordered pairs are three important notions that are usually specified. First, a relation may be reflexive. This means that for any $x$ (that occurs in the ‘field’ of a relation $R$, see below), $\langle x, x\rangle \in R$. For example, if $L$ encodes the ‘loves’ relation, and everyone loves themselves, then for every person $x$, $\langle x, x\rangle \in L$. This way, $L$ would be reflexive. On the other hand, if there is a person $y$ such that $\langle y, y\rangle \notin L$, then $L$ would not be reflexive, because there would be a person who does not love themself.

Second, a relation may be symmetric, if whenever $\langle x, y\rangle \in R$, $\langle y, x\rangle \in R$ as well. This was already illustrated above with our three friends, Jamal, Kerry, and Zoltan. Specifically, $F$ was a relation that was symmetric, since whenever $x$ was a friend of $y$, $y$ was a friend of $x$. On the other hand, $F'$ was not symmetric, since there was a person, Kerry, who was friends with Zoltan, but Zoltan was not friends with Kerry.

Finally, a relation may be transitive. Transitive relations are everywhere in logic, though they are not always apparent. A transitive relation is more elaborate than the above two, since it is specified between three things. Namely, a transitive relation is such that if $\langle x, y\rangle \in R$, and $\langle y, z\rangle \in R$, then $\langle x, z\rangle \in R$. One relation that is usually transitive is airplane travel with connections. Suppose you can travel by plane from New York to Los Angeles, and from Los Angeles to Tokyo. Then, that also means that you can travel from New York to Tokyo (with a connecting flight in Los Angeles). In other words if $A$ represents the set of all pairs of cities reachable by air travel, if $\langle\text{NYC}, \text{LA}\rangle \in A$, and $\langle\text{LA}, \text{Tokyo}\rangle \in A$, then $\langle\text{NYC}, \text{Tokyo}\rangle \in A$. Since this holds for every three cities, the relation $A$ is transitive. Incidentally, this relation is also symmetric, since flights go back and forth (or perhaps in larger circles).

If you have taken an introductory logic course before, you may remember the connective ‘$\rightarrow$’, standing for ‘if …, then …’. You may also remember that in your proof system, you could show that if you had as premises $X \rightarrow Y$ and $Y \rightarrow Z$, then you could derive $X \rightarrow Z$. Some systems even have a dedicated rule for this, called the ‘hypothetical syllogism’ or ‘chain rule’. Now all this rule says is that $\rightarrow$ is transitive! In other words, if you take the set $I$ of all pairs $X$, $Y$ of propositions where $X \rightarrow Y$, and $\langle X, Y\rangle, \langle Y, Z\rangle \in I$, then $\langle X, Z\rangle \in I$ (at least in classical logic).

Note that relations can have many ‘places’, meaning they may be said to hold between several different things. A $2$-place relation, as noted above, is a set of pairs, since it holds (or does not hold) between two things. But you may take other relations like ‘$x$ is in between, $y$ and $z$’, which would be a $3$-place relation, and its representation would be a set of triples $\langle x, y, z\rangle$, because it holds (or does not hold) between 3 things. So in general, an $n$-place relation will be identified with a set of $n$-tuples, since it holds (or does not hold) between $n$ different things. Notice that in each case, an $n$-place relation $R$ is a subset of some set $S$ taken $n$ times with itself, i.e., $R \subseteq S^n$.