You are here

Relations as subsets

23 July, 2015 - 12:53
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at

Consider the set of WaterWorld locations Loc = {A, B, . . ., Z}. For this domain (also known as a universe), we'll say a binary relation is a set of (ordered) pairs of the domain.

Example 3.1

For instance, the nhbr relation of the previous section is the set {(A, B) , (A, G) , (B, A) , (B, C) , . . ., (Y, X) , (Y, Z) , (Z, Y)}.
That is, x is related to y if (x, y) is in the set nhbr.

Example 3.2

For the domain D = {Object, String, MutableString}, the relation subclass − of might be {(String, Object) , (MutableString, Object) , (MutableString, String)}.

In general, a binary relation over the domain D is a subset of D×D. Note that these are ordered pairs; just because x is related to y doesn't mean y has the same relation to x. For example, while (MutableString, Object) is in the relation subclass − of, the pair (Object, MutableString) most certainly is not.

Example 3.3

You can consider the relation hasStarredWith, over the domain of Hollywood actors. We won't list all the elements of the relation, but some related pairs are:

  • hasStarredWith(Ewan McGregor, Cameron Diaz), as witnessed by the movie A Life Less Or dinary, 1997.
  • hasStarredWith (Cameron Diaz, John Cusack), as witnessed by the movie Being John Malkovich, 1999.
If binary relations are subsets of pairs of the domain, what might a unary relation be? Simply, subsets of the domain.

Example 3.4

For the domain of vegetables, Ian defnes the relation yummy? as {tomatoes, okra, cucumbers, carrots, potatoes} and nothing else.

Example 3.5

In one particular game of WaterWorld, the relation hasPirate turned out to be {K, T, R, U, E}.

If unary and binary relations make sense, what about ternary, etc., relations? Surel In general, a k-ary relation (or, "relation of arityk") over the domain D is a subset of Dk . However, any given relation has a fixed arity. That is, a relation may be binary or ternary, but not both.

As with propositions, rather than writing " R (x, y) is true ", we'll simply write " R (x, y) ". In fact, notice that once you choose some particular pair of x and y, then R (x, y) can be treated as a single true/false proposition. (We'll soon extend the idea of propositions to include such relation symbols, and then allow formulas to include these terms.)

Example 3.6

"prime (18) " is a proposition that's false, assuming the standard interpretation (Interpretations) of prime.

Example 3.7

"safe (A) " is a proposition that is true on some boards and not others.