6.2 Properties of relations

There are two special classes of relations that we will study in the next two sections: equivalence relations and ordering relations. The prototype for an equivalence relation is the ordinary notion of numerical equality, \(=\). The prototypical ordering relation is \(\leq\). Each of these has certain salient properties that are the root causes of their importance. In this section, we will study a compendium of properties that a relation may or may not have.

A relation that has three of the properties we’ll discuss:

  1. reflexivity
  2. symmetry
  3. transitivity

is said to be an equivalence relation; it will in some ways resemble \(=\).

A relation that has another set of three properties:

  1. reflexivity
  2. anti-symmetry
  3. transitivity

is called an ordering relation; it will resemble \(\leq\).

Additionally, there is a property known as irreflexivity that many relations have.

There are a total of 5 properties that we have named, and we will discuss them all more thoroughly. But first, we’ll state the formal definitions. Take note that these properties are all stated for a relation that goes from a set to itself. Indeed, most of them wouldn’t even make sense if we tried to define them for a relation from a set to a different set.

Table 6.1: Properties that relations may (or may not) have.
A relation \(\mathsf{R}\) on a set \(S\) is reflexive iff \[\forall a \in S, \quad a \mathsf{R}a \] “Everything is related to itself.”
A relation \(\mathsf{R}\) on a set \(S\) is irreflexive iff \[\displaystyle \forall a \in S, \quad a \not\mathsf{R}a \] “Nothing is related to itself.”
A relation \(\mathsf{R}\) on a set \(S\) is symmetric iff \[\forall a,b \in S, \quad a \mathsf{R}b \; \implies \; b \mathsf{R}a \] “No one-way streets.”
A relation \(\mathsf{R}\) on a set \(S\) is anti-symmetric iff \[\forall a,b \in S, \quad a \mathsf{R}b \; \land b \mathsf{R}a \quad \implies \quad a=b \] “Only one-way streets.”
A relation \(\mathsf{R}\) on a set \(S\) is transitive iff \[\forall a,b,c \in S, \quad a \mathsf{R}b \; \land \; b \mathsf{R}c \quad \implies \quad a \mathsf{R}c\] “Whenever there’s a roundabout route, there’s a direct route.”

The digraph of a relation that is reflexive will have little loops at every vertex. The digraph of a relation that is irreflexive will contain no loops at all. Hopefully it is clear that these concepts represent extreme opposite possibilities — they are not however negations of one another.

Exercise 6.3 Find the logical denial of the property that says a relation is reflexive \[ {\lnot}(\forall a \in S, \quad a \mathsf{R}a). \] How does this differ from the defining property for “irreflexive”?

If a relation \(\mathsf{R}\) is defined on some subset \(S\) of the reals, then it can be graphed in the Euclidean plane. Reflexivity for \(\mathsf{R}\) can be interpreted in terms of the line \(L\) defined by the equation \(y=x\). Every point in \((S \times S) \cap L\) must be in \(\mathsf{R}\). A similar statement can be made concerning the irreflexive property. If a relation \(\mathsf{R}\) is irreflexive its graph completely avoids the line \(y=x\).

Note that the reflexive and irreflexive properties are defined with a single quantified variable. Symmetry and anti-symmetry require two universally quantified variables for their definitions.

Definition 6.1 A relation \(\mathsf{R}\) on a set \(S\) is symmetric iff \[ \forall a,b \in S, \quad a \mathsf{R}b \; \implies \; b \mathsf{R}a. \]

This can be interpreted in terms of digraphs as follows: If a connection from \(a\) to \(b\) exists in the digraph of \(\mathsf{R}\), then there must also be a connection from \(b\) to \(a\). In Table 6.1, this is interpreted as “no one-way streets” and while that’s not quite what it says, that is the effect of this definition. Since if a connection exists in one direction, there must also be a connection in the other direction, it follows that we will never see a one-way connection.

Because most of the properties we are studying are defined using conditional statements, it is often the case that a relation has a property for vacuous reasons. When the “if” part doesn’t happen, there’s no need for its corresponding “then” part to happen either — the conditional is still true. In the context of our discussion on the symmetry property of a relation, this means that the digraph in Figure 6.7 is the digraph of a symmetric relation (although it is neither reflexive nor irreflexive).

A digraph illustrating vacuously symmetric.

Figure 6.7: A digraph illustrating vacuously symmetric.

Anti-symmetry is described as meaning “only one-way streets” but the definition is given as:

Definition 6.2 A relation \(\mathsf{R}\) on a set \(S\) is anti-symmetric iff \[\forall a,b \in S, \quad a \mathsf{R}b \; \land b \mathsf{R}a \quad \implies \quad a=b.\]

It may be hard at first to understand why the definition we use for anti-symmetry is the one above. If one wanted to insure that there were never two-way connections between elements of the set it might seem easier to define anti-symmetry as follows:

Definition 6.3 (Alternate definition) A relation \(\mathsf{R}\) on a set \(S\) is anti-symmetric iff \[\forall a,b \in S, \quad a \mathsf{R}b \; \implies \; b \not\mathsf{R}a.\]

This definition may seem more straight-forward, but it turns out the original definition is easier to use in proofs. We need to convince ourselves that the (first) definition really accomplishes what we want. Namely, if a relation \(\mathsf{R}\) satisfies the property that \[\displaystyle \forall a,b \in S, \quad a \mathsf{R}b \; \land \; b \mathsf{R}a \quad \implies \quad a=b.\] then there will not actually be any pair of elements that are related in both orders. One way to think about it is this: suppose that \(a\) and \(b\) are distinct elements of \(S\) and that both \(a \mathsf{R}b\) and \(b \mathsf{R}a\) are true. The property now guarantees that \(a=b\) which contradicts the notion that \(a\) and \(b\) are distinct. This is a miniature proof by contradiction; if you assume there are a pair of distinct elements that are related in both orders, you get a contradiction, so there aren’t.

A funny thing about the anti-symmetry property is this: When it is true of a relation, it is always vacuously true. The property is engineered in such a way that when it is true, it forces that the statement in its antecedent never really happens.

Transitivity is an extremely useful property as witnessed by the fact that both equivalence relations and ordering relations must have this property. When speaking of the transitive property of equality we say “Two things that are equal to a third, are equal to each other.” When dealing with ordering we may encounter statements like the following. “Since ‘Aardvark’ precedes ‘Bulwark’ in the dictionary, and since ‘Bulwark’ precedes ‘Catastrophe’, it is plainly true that ‘Aardvark’ comes before ‘Catastrophe’ in the dictionary.”

Again, the definition of transitivity involves a conditional. Also, transitivity may be viewed as the most complicated of the properties we’ve been studying; it takes three universally quantified variables to state the property.

Definition 6.4 A relation \(\mathsf{R}\) on a set \(S\) is transitive iff \[\forall a,b,c \in S, \quad a \mathsf{R}b \; \land \; b \mathsf{R}c \quad \implies \quad a \mathsf{R}c.\]

We paraphrased transitivity as “Whenever there’s a roundabout route, there’s a direct route.” In particular, what the definition says is that if there’s a connection from \(a\) to \(b\) and from \(b\) to \(c\) (the roundabout route from \(a\) to \(c\)) then there must be a connection from \(a\) to \(c\) (the direct route).

You’ll really need to watch out for relations that are transitive for vacuous reasons. So long as one never has three elements \(a\), \(b\) and \(c\) with \(a \mathsf{R}b\) and \(b \mathsf{R}c\) the statement that defines transitivity is automatically true.

A very useful way of thinking about these various properties that relations may have is in terms of what doesn’t happen when a relation has them. Before we proceed, it is important that you do the following

Exercise 6.4 Find logical negations for the formal properties defining each of the five properties.

If a relation \(\mathsf{R}\) is reflexive, we will never see a node that doesn’t have a loop. (See Figure 6.8.)

An illustration of a relation that is not reflexive.

Figure 6.8: An illustration of a relation that is not reflexive.

If a relation \(\mathsf{R}\) is irreflexive we will never see a node that does have a loop! (See Figure 6.9.)

An illustration of a relation that is not irreflexive.

Figure 6.9: An illustration of a relation that is not irreflexive.

If a relation \(\mathsf{R}\) is symmetric we will never see a pair of nodes that are connected in one direction only. (See Figure 6.10.)

An illustration of a relation that is not symmetric.

Figure 6.10: An illustration of a relation that is not symmetric.

If a relation \(\mathsf{R}\) is anti-symmetric we will never see a pair of nodes that are connected in both directions. (See Figure 6.11.)

An illustration of a relation that is not anti-symmetric.

Figure 6.11: An illustration of a relation that is not anti-symmetric.

If a relation \(\mathsf{R}\) is transitive the thing we will never see is a bit harder to describe. There will never be a pair of arrows meeting head to tail without there also being an arrow going from the tail of the first to the head of the second. (See Figure 6.12.)

An illustration of a relation that is not transitive.

Figure 6.12: An illustration of a relation that is not transitive.

6.2.1 Exercises

  1. Consider the relation \(\mathsf{S}\) defined by \(\mathsf{S}= \{ (x,y) {\,:\,}\; x \, \mbox{is smarter than} \, y \}\). Is \(\mathsf{S}\) symmetric or anti-symmetric? Explain.

  2. Consider the relation \(\mathsf{A}\) defined by \(\mathsf{A}= \{ (x,y) {\,:\,}\; x \, \mbox{has the same astrological sign as} \, y \}\). Is \(\mathsf{A}\) symmetric or anti-symmetric? Explain.

  3. Explain why both of the relations just described (in exercises 1 and 2) have the transitive property.

  4. For each of the five properties, name a relation that has it and a relation that doesn’t.

  5. Show by counterexample that “\(\mid\)” (divisibility) is not symmetric as a relation on \({\mathbb Z}\).

  6. Prove that “\(\mid\)” is an ordering relation on the set of positive integers. (You must verify that it is reflexive, anti-symmetric and transitive).