Properties of Relations – Foundations of Mathematics

Assumptions are the termites of relationships.

character of Arthur Fonzarelli, Happy Days

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.