3.1: The idea of a relation

A relation between a set \(X\) and \(Y\) is a subset of the Cartesian product. That one sentence packs in a whole heck of a lot, so spend a moment thinking deeply about it. Recall that \(X \times Y\) yields a set of ordered pairs, one for each combination of an element from \(X\) and an element from \(Y\). If \(X\) has 5 elements and \(Y\) has 4, then \(X \times Y\) is a set of 20 ordered pairs. To make it concrete, if \(X\) is the set { Harry, Ron, Hermione }, and \(Y\) is the set { Dr. Pepper, Mt. Dew }, then \(X \times Y\) is { (Harry, Dr. Pepper), (Harry, Mt. Dew), (Ron, Dr. Pepper), (Ron, Mt. Dew), (Hermione, Dr. Pepper), (Hermione, Mt. Dew) }. Convince yourself that every possible combination is in there. I listed them out methodically to make sure I didn’t miss any (all the Harry’s first, with each drink in order, then all the Ron’s, etc.) but of course there’s no order to the members of a set, so I could have listed them in any order.

Now if I define a relation between \(X\) and \(Y\), I’m simply specifying that certain of these ordered pairs are in the relation, and certain ones are not. For example, I could define a relation \(R\) that contains only { (Harry, Mt. Dew), (Ron, Mt. Dew) }. I could define another relation \(S\) that contains { (Hermione, Mt. Dew), (Hermione, Dr. Pepper), (Harry, Dr. Pepper) }. I could define another relation \(T\) that has none of the ordered pairs; in other words, \(T = \varnothing\).

A question that should occur to you is: how many different relations are there between two sets \(X\) and \(Y\)? Think it out: every one of the ordered pairs in \(X \times Y\) either is, or is not, in a particular relation between \(X\) and \(Y\). Very well. Since there are a total of \(|X|\cdot|Y|\) ordered pairs, and each one of them can be either present or absent from each relation, there must be a total of

\[2^{|X|\cdot|Y|}\]

different relations between them. Put another way, the set of all relations between \(X\) and \(Y\) is the power set of \(X \times Y\). I told you that would come up a lot.

In the example above, then, there are a whopping \(2^6\), or 64 different relations between those two teensey little sets. One of those relations is the empty set. Another one has all six ordered pairs in it. The rest fall somewhere in the middle. (Food for thought: how many of these relations have exactly one ordered pair? How many have exactly five?)

Notation

I find the notation for expressing relations somewhat awkward. But here it is. When we defined the relation \(S\), above, we had the ordered pair (Harry, Dr. Pepper) in it. To explicitly state this fact, we could simply say \[\text{(Harry, Dr.~Pepper)} \in S\] and in fact we can do so. More often, though, mathematicians write:

Harry \(S\) Dr. Pepper.

which is pronounced “Harry is \(S\)-related-to Dr. Pepper." Told you it was awkward.

If we want to draw attention to the fact that (Harry, Mt. Dew) is not in the relation \(S\), we could strike it through to write

Harry --\(S\)-- Mt. Dew