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: ALLx 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: ALLx 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) NOTRyx. 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) NOTRxz.

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, ALLx SOMEy 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 ALLx ALLy (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.