Chapter 35 Properties of relations

Symbolization keys allow us to assign two-place predicate symbols like ‘$R(x,y)$’ to English predicates with two gaps, e.g., ‘blank _x is older than blank _y’. This allows us to symbolize arguments such as:

• Rudolf is older than Kurt.

• Kurt is older than Julia.

• ∴
  ​

  Rudolf is older than Julia.

This argument is valid, but its symbolization in FOL,

• $R(r,k)$

• $R(k,j)$

• ∴
  ​

  $R(r,j)$

is not. That’s because the validity of the argument depends on a property of the relation ‘$x$ is older than $y$’, namely that if some person $x$ is older than a person $y$, and $y$ is also older than $z$, then $x$ must be older than $z$. This property of ‘older than’ is called transitivity . We can symbolize this property itself in FOL as:

Whenever the validity of an argument only depends on a property of a relation involved, and this property can be symbolized in FOL, we can add this symbolization to the argument and obtain an argument that is in fact valid in FOL:

• $\forall x\forall y\forall z((R(x,y)\wedge R(y,z))\to R(x,z))$

• $R(r,k)$

• $R(k,j)$

• ∴
  ​

  $R(r,j)$

Properties of relations such as transitivity are important concepts especially in applications of logic in the sciences. For instance, order relations between numbers such as and $\le$ (and also $>$ and $\ge$) are transitive. The identity relation $=$ is also transitive.

There are other properties of relations that are important enough to have names, and often show up in applications. Here are some:

We have already seen that transitivity can be symbolized in FOL. The others can, too:

• ‣
  ​

  $R$ is reflexive: $\forall xR(x,x)$

• ‣
  ​

  $R$ is symmetric:

  $$\forall x\forall y(R(x,y)\to R(y,x))$$
• ‣
  ​

  $R$ is anti-symmetric:

  $$\neg \exists x\exists y((R(x,y)\wedge R(y,x))\wedge \neg x=y)$$

  or, equivalently,

  $$\forall x\forall y((R(x,y)\wedge R(y,x))\to x=y)$$

Relations expressing an equivalence in some respect are reflexive, e.g., ‘is the same age as’, ‘is as tall as’, and the most stringent equivalence of them all, identity $=$. They are also symmetric: e.g., whenever $x$ is as tall as $y$, then $y$ is as tall as $x$. In fact, relations that are reflexive, symmetric, and transitive are called equivalence relations .

Equivalences aren’t the only symmetric relations. For instance, ‘is a sibling of’ is symmetric, but it is not reflexive (as no one is their own sibling).

Relations that are reflexive, transitive, and anti-symmetric are called partial orders . For instance, $\le$ and $\ge$ are partial orders. The relation ‘is no older than’, by contrast, is reflexive and transitive, but not anti-symmetric. (Two different people can be of the same age, and so neither is older than the other.)