# Relations Expressing generality

The language of our formal logic gives us relation (predicate) symbols with any finite number of argument places, allowing us to represent relationships between two or more things, even where these cannot be decomposed into monadic properties of those things. We need at least binary relation symbols to capture such valid reasoning as

All goats are hairy.

Every footballer loves a goat.

Therefore whoever kicks a footballer kicks someone who
loves something hairy.

See Chapter 4 of these notes for a discussion of this example. There is no reason to stop at relations between just two things: there are theories and inferences requiring relations of arity three or higher.

Binary relations are, however, common and particularly important. It is therefore worthwhile devoting a separate page to them. A few examples of familiar binary relations will help focus things. Consider, then:

<: The "less than" relation between numbers.

⊆: The "subset" relation between sets.

'Knows': The relation between people such that one
knows the other.

There are several important properties that such relations
may or may not satisfy and which we can express in the
vocabulary of first order logic. We say that a
relation *R* is:

#### reflexive

if everything bears relation*R*to itself: ALL

*x Rxx*. For instance, ⊆ is reflexive (all members of a set

*s*are members of

*s*, of course), but < is not; 'knows' may be, if the injunction to "know thyself" is vacuous.

#### irreflexive

if nothing bears relation R to itself: ALL*x NOTRxx*. For instance, < is irreflexive because no number can be less than itself.

#### symmetric

if the relation is reversible: ALL(*x,y*:

*Rxy*)

*Ryx*. Plausibly, our third example is symmetric: it depends a bit on how we read 'knows', but maybe if I know you then it follows that you know me as well, which would make the knowing relation symmetric.

#### asymmetric

if the relation is irreversible: ALL(*x,y*:

*Rxy*) NOT

*Ryx*. Again < is the only asymmetric relation of our three.

#### transitive

if ALL(*x,y*:

*Rxy*) ALL(

*z*:

*Ryz*)

*Rxz*.

That is, if one thing is related to another and the other is related to a third, then the first is related to the third. Both ⊆ and < are transitive. Knowing people, however, is not transitive: for example, I know my brother and he knows his work colleagues, but I do not know all of them.

#### intransitive

if ALL(*x,y*:

*Rxy*) ALL(

*z*:

*Ryz*) NOT

*Rxz*.

#### antisymmetric

if no two distinct things are related to each other. That is, ALL(*x,y*: (

*Rxy*AND

*Ryx*))

*x*=

*y*. Set inclusion is a classic example of an antisymmetric relation, for if all members of

*a*are members of

*b*and all members of

*b*are members of

*a*, then

*a*and

*b*have the same members, which makes them one and the same set.

#### serial

if everything is related to something, ALL*x*SOME

*y Rxy*, so

*R*has no dead ends. Obviously every reflexive relation is serial, but the converse is not the case: < on the real numbers is serial but asymmetric, for instance.

Some combinations of these properties are also important. One important thing a relation can do is to order or rank things. Some orderings may partially rank things, but leave the order undetermined in some cases; others completely determine the order between all possible things in their domain of application.

A *quasi-order* (also called a *preorder*)
is just a relation which is transitive and reflexive. This
is a weak kind of ordering, but is quite common. For
example, we might say *a* is "as well qualified"
as *b* if *a* has all qualifications
that *b* has. This relation is a quasi-order.

A quasi-order is a *partial order* if it is also
antisymmetric. A *total order* is a partial order
such that
ALL*x* ALL*y* (*Rxy*
OR *Ryx*):
the vocabulary is a bit awkward, but it is standard. A relation
which is transitive and irreflexive, like < , is
sometimes called a *strict partial order*, or a
*strict total order* if it holds in one direction
or the other between every pair of distinct things. In
terms of our running examples, note that set inclusion is
a partial order but not a total order, while
< is a strict total order.

An *equivalence relation* is one which is
reflexive, symmetric and transitive. It partitions the
domain of discourse into "equivalence classes", so that
everything is related to everything in its own equivalence
class but to nothing outside. In a sense, mathematics is
the study of equivalence relations, starting with the
relation of numerical equality. The "parallel to" relation
in geometry is another example. Complexity classes in
computer science are yet another, consisting of sets of
problems (more properly, of formal languages) which can be
transformed into each other in a polynomially bounded
number of steps, so they are "equivalent" under the
relation of such transformation.

First order logic gives us one way to study properties of relations and prove theorems about them, but there are others. Those with a mathematical interest in logic may like to note two at this point: relation algebra and graph theory.