##### Exercise6.2.1

Find the logical denial of the property that says a relation is reflexive \begin{equation*} {\lnot}(\forall a \in S, a \relR a). \end{equation*}

How does this differ from the defining property for “irreflexive”?

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:

reflexivity

symmetry

transitivity

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

A relation that has another set of three properties:

reflexivity

anti-symmetry

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.

\begin{minipage}{.95\textwidth} \A relation \(\relR\) on a set \(S\) is reflexive iff
\\(\displaystyle \forall a \in S, a \relR a\)
“Everything is related to itself.” |

\begin{minipage}{.95\textwidth} \A relation \(\relR\) on a set \(S\) is irreflexive iff
\\(\displaystyle \forall a \in S, a \nrelR a\)
“Nothing is related to itself.” |

\begin{minipage}{.95\textwidth} \A relation \(\relR\) on a set \(S\) is symmetric iff
\\(\displaystyle \forall a,b \in S, a \relR b \; \implies \; b \relR a\)
“No one-way streets.” |

\begin{minipage}{.95\textwidth} \A relation \(\relR\) on a set \(S\) is anti-symmetric iff
\\(\displaystyle \forall a,b \in S, a \relR b \; \land b \relR a \implies a=b\)
“Only one-way streets.” |

\begin{minipage}{.95\textwidth} \A relation \(\relR\) on a set \(S\) is transitive iff
\\(\displaystyle \forall a,b,c \in S, a \relR b \; \land \; b \relR c \implies a \relR 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.

Find the logical denial of the property that says a relation is reflexive \begin{equation*} {\lnot}(\forall a \in S, a \relR a). \end{equation*}

How does this differ from the defining property for “irreflexive”?

If a relation \(\relR\) is defined on some subset \(S\) of the reals, then it can be graphed in the Euclidean plane. Reflexivity for \(\relR\) 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 \(\relR\). A similar statement can be made concerning the irreflexive property. If a relation \(\relR\) 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.

A relation \(\relR\) on a set \(S\) issymmetriciff \begin{equation*} \forall a,b \in S, a \relR b \; \implies \; b \relR a. \end{equation*}

This can be interpreted in terms of digraphs as follows: If a connection
from \(a\) to \(b\) exists in the digraph of \(\relR\), then there must also be a connection
from \(b\) to \(a\). In <<Unresolved xref, reference "tab_rel_props"; check spelling or use "provisional" attribute>> 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 following digraph *is* the digraph of a symmetric
relation (although it is neither reflexive nor irreflexive).

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

A relation \(\relR\) on a set \(S\) isanti-symmetriciff \\(\displaystyle \forall a,b \in S, a \relR b \; \land b \relR a \implies 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:

(Alternate definition) A relation \(\relR\) on a set \(S\) isanti-symmetriciff \\(\displaystyle \forall a,b \in S, a \relR b \; \implies \; b \nrelR 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 \(\relR\) satisfies the property that
\(\displaystyle \forall a,b \in S, a \relR b \; \land \; b \relR a \implies 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 \relR b\) and \(b \relR 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.

A relation \(\relR\) on a set \(S\) istransitiveiff \\(\displaystyle \forall a,b,c \in S, a \relR b \; \land \; b \relR c \implies a \relR 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 \relR b\) and \(b \relR 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

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

If a relation \(\relR\) is reflexive we will never see a node that doesn't have a loop.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi
If a relation \(\relR\) is irreflexive we will never see a node that *does* have a loop!

If a relation \(\relR\) is symmetric we will never see a pair of nodes that are connected in one direction only.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fiIf a relation \(\relR\) is anti-symmetric we will never see a pair of nodes that are connected in both directions.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi
If a relation \(\relR\) 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.

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

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

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

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

Show by counterexample that “\(\divides\)” (divisibility) is not symmetric as a relation on \(\Integers\).

Prove that “\(\divides\)” is an ordering relation (you must verify that it is reflexive, anti-symmetric and transitive).