# 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., ‘blankx is older than blanky’. 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:

$\forall x\forall y\forall z((R(x,y)\wedge R(y,z))\rightarrow R(x,z))$

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))\rightarrow 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 $\leq$ (and also $>$ and $\geq$) 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:

• A relation $R$ is transitive if⁠f it is the case that whenever $R(x,y)$ and $R(y,z)$ then also $R(x,z)$.

• A relation $R$ is reflexive if⁠f for any $x$, $R(x,x)$ holds.

• A relation $R$ is symmetric if⁠f whenever $R(x,y)$ holds, so does $R(y,x)$.

• A relation $R$ is anti-symmetric if⁠f for no two different $x$ and $y$, $R(x,y)$ and $R(y,x)$ both hold.

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

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

• $R$ is symmetric:

$\forall x\forall y(R(x,y)\rightarrow R(y,z))$
• $R$ is anti-symmetric:

$\lnot\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))\rightarrow 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, $\leq$ and $\geq$ 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.)

## Practice exercises

A. Give examples of relations with the following properties:

1. 1.

Reflexive but not symmetric

2. 2.

Symmetric but not transitive

3. 3.

Transitive, symmetric, but not reflexive

B. Show that a relation can be both symmetric and anti-symmetric by giving an interpretation that makes both of the following sentences true:

 $\displaystyle\forall x\forall y(R(x,y)\rightarrow R(y,z))$ $\displaystyle\forall x\forall y((R(x,y)\wedge R(y,x))\rightarrow x=y)$