3.1 Properties of relations

When using relations in logic formulas, there are two things going on:

• relations themselves, as mathematical entities, and
• formulas involving symbols, which must be interpreted as specific relations.

We'll start with a couple of equivalent ways of defining relations, and then discuss a common subclass of relations: binary relations.

Relations as subsets

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

If binary relations are subsets of pairs of the domain, what might a unary relation be? Simply, subsets of the domain.

If unary and binary relations make sense, what about ternary, etc. , relations? Sure! In general, a $k$ -ary relation (or,

relation of arity $k$

As with propositions, rather than writing

$R(x, y)$ is true

$R(x, y)$

Relations as functions

The relation $\mathrm{nhbr}$ , which we're defining as a set (of pairs), could also be thought of being a function.We say that the indicator function of a set is a Boolean function indicating whether its inputis in the set or not. So instead of being given the set $\mathrm{nhbr}$ , you would have been equally happy withits indicator function $f_{\mathrm{nhbr}}$ , where (for example) $f_{\mathrm{nhbr}}(B, C)=\mbox{true}$ and $f_{\mathrm{nhbr}}(B, Q)=\mbox{false}$ . Similarly, if you know that $f_{\mathrm{hasPirate}}(K)=\mbox{true}$ and that $f_{\mathrm{hasPirate}}(L)=\mbox{false}$ , then this is enough information to conclude that $K\in \mathrm{hasPirate}$ and $L\notin \mathrm{hasPirate}$ . The set and the function are equivalent ways of modeling the same underlying relation.