Andrew Cooper

[callout headingicon=”noicon” textalign=”textleft” type=”basic”]Assumptions are the termites of relationships.

character of Arthur Fonzarelli, Happy Days

[/callout]

Now we are ready to consider some properties of relations. Our interest is to find properties of, e.g. motherhood. To do this, remember that we are not interested in a particular mother or a particular child, or even in a particular mother-child pair, but rather motherhood in general.

We’ll start with properties that make sense for relations whose source and target are the same, that is, relations on a set.

Definition. Let $R$ be a relation on the set $A$.

• We call $R$ reflexive if every element of $A$ is related to itself; that is, if every $x\in A$ has $x\operatorname{R} x$.
• We call $R$ irreflexive if no element of $A$ is related to itself.
• We call $R$ symmetric if $x\operatorname{R} y$ means the same thing as $y\operatorname{R} x$.
• We call $R$ asymmetric if $x\operatorname{R} y$ guarantees that $\sim(y \operatorname{R} x)$.
• We call $R$ antisymmetric if the only way for $x\operatorname{R} y$ and $y\operatorname{R} x$ to both be true is if $x=y$.
• We call $R$ transitive if $x\operatorname{R} y$ and $y\operatorname{R} z$ together guarantee $x\operatorname{R} z$.

Exercise. Explain why none of these relations makes sense unless the source and target of $R$ are the same set.

Exercise. Which of the above properties does the motherhood relation $M$ have?

Exercise. Write the definitions above using set notation instead of infix notation.

Exercise. Write the definitions of reflexive, symmetric, and transitive using logical symbols.

Checking whether a given relation has the properties above looks like:

E.g. `Divides’ (as a relation on the integers) is reflexive and transitive, but none of: symmetric, asymmetric, antisymmetric.

Proof. We’ll show reflexivity first. Suppose $m$ is an integer. Then $m=m\cdot 1$, so $m$ divides $m$.

Now we’ll show transitivity. Suppose $m$ divides $n$ and $n$ divides $p$. Then there are $k_1$ and $k_2$ so that $n=k_1m$ and $p=k_2 n$. Then $p=k_2k_1m$, so $m$ divides $p$.

Note that 2 divides 4 but 4 does not divide 2. This counterexample shows that `divides’ is not symmetric.

Note that 4 divides 4. This counterexample shows that `divides’ is not asymmetric.

Note that $-2$ divides $2$ and $2$ divides $-2$, but $-2\neq 2$. This counterexample shows that `divides’ is not antisymmetric. $\Box$

E.g. $<$ is irreflexive, asymmetric, transitive, and antisymmetric, but neither reflexive nor symmetric.

Exercise. Show that `divides’ as a relation on $\mathbb{N}$ is antisymmetric.