Intuitive understanding of relations and their basic properties

Can anyone explain relations and the four basic properties of them (reflexive, symmetric, antisymmetric, transitive)- or direct me to a source that does.

Particularly, are these statements reflective? Symmetric? Antisymmetric? Transitive?

"is a sister of" "is a sibling of" "is a descendant of" "is divisible by"

How can I use this knowledge to choose the following:

Relation that is both symmetric and antisymmetric. Relation that is symmetric but not antisymmetric. Relation that is not symmetric but antisymmetric. Relation that is not symmetric nor antisymmetric.

In general, I'm just looking for a concise, understandable, intuitive explanation of what exactly relations are and how their properties (the four above) are defined.

Thank you!

EDIT: Here's another one: http://i.imgur.com/slBH1.jpg

• Before I try: have you yet seen the representation of relations as graphs? – Brian M. Scott Nov 13 '12 at 5:07
• Yes, I have, actually. – Bob John Nov 13 '12 at 5:16
• I'm sorry, I missed asymmetric and irreflexive. Do you mind including those as well? – Bob John Nov 13 '12 at 5:19

Defininitions

A binary relation $\sim$ on a set $X$ is reflexive if and only if, for all $a$ in $X$

• $a\sim a$

I binary relation on a set $X$ is said to be irreflexive (or antireflexive) if and only if for all $a$ in $X$,

• $a\not\sim a$. In other words, “no element is related to itself”. For example, the relation “is less than” is an irreflexive relation, since there is NO $n \in \mathbb{N} \text{ such that}\; n < n$.

A binary relation $\sim$ on a set $X$ is symmetric if and only if, for all $a$ and $b$ in $X$,

• if $a\sim b$, then $b\sim a$.

A binary relation $\sim$ on a set $X$ is antisymmetric if and only if, for all $a$ and $b$ in $X$,

• if $a \sim b$ and $b\sim a$, then $a \equiv b$.

$\quad$ or, equivalently

• if $a \sim b$ with $a \not\equiv b$, then $b\not\sim a$.
• A good example of an antisymmetric relation is the $\leq$ relation on, say, the set of integers. What would the conclusion be if we assume this premise: for any $m, n \in \mathbb{Z}$, if $m\leq n$ AND $n\leq m$ then...?

A binary relation on a set $X$ is said to be asymmetric if and only if it is NOT symmetric, that is,

• if and only if there exist $a, b \in X$ such that $a \sim b$ but $b \not\sim a$

A binary relation $\sim$ on a set $X$ is transitive if and only if, for all $a, b, c$ in $X$,

• if $a\sim b$ and $b\sim c$, then $a\sim c$.

For application to the relation "is a sibling of" (which we can denote using the notation $\sim_{s}$) on the set of all people:

• Reflexive?
Can anyone be a sibling to oneself? No. Hence reflexivity fails. Even more, since no one is a sibling of oneself, the relation is irreflexive.
• Symmetric?
If $a$ is the sibling of $b$, then $b$ is certainly a sibling of $a$.
• Antisymmetric?
If $a$ is a sibling of $b$ we know $b$ is a sibling of $a$ (because the relation is symmetric). But we know from the fact that the relation “is a sibling of” is not reflexive, if $a$ is a sibling of $b$, then $a$ cannot be the same person as $b$, since no one can be a sibling to oneself. So “is a sibling of" is NOT anti-symmetric. This provides you with an example of a relation that is symmetric but not anti-symmetric.
• Asymmetric?
No. Why not? Can it every occur that $a$ is a sibling of $b$, but $b$ is not a sibling of $a$?
• Transitive?
Suppose $a$ and $b$ are siblings, and that $b$ and $c$ are siblings. Is it necessarily the case that $a$ and $c$ are siblings? If we define "siblinghood" strictly (where siblings have both parents in common), then the relation is transitive. If we include in our definition of "siblinghood" the relation of being a half-sibling, then the relation is not transitive, because if $a$ and $b$ share only the same mother, and $b$ and $c$ share only the same father, it will not be the case that $a$ and $c$ are siblings.

How a relation is defined, and knowing the elements of the set on which it is defined is crucial.

I hope the example helps. Try to work with the definitions given above and reason through your other relations. "is a sister of" models this example. The same reasoning applies in that relation as it does for "siblinghood."

Let $R$ be a relation on a set $A$, and let $G$ be the associated digraph. Recall that the elements of $A$ are the vertices of $G$, and there is an edge from $a$ to $b$ exactly when $\langle a,b\rangle\in R$. Think of the map as a street grid of some kind. If there is an edge from $a$ to $b$ but no edge from $b$ to $a$, I’ll call that edge a one-way street. If there are edges in both directions, from $a$ to $b$ and from $b$ to $a$, I’ll call them a two-way street.

• $R$ is reflexive if and only if $G$ has a loop at each vertex, i.e., an edge that connects the vertex to itself. This just says that $\langle a,a\rangle\in R$ for every $a\in A$.

• $R$ is symmetric if and only if every edge in $G$ is either a loop or a two-way street: there are no one-way streets. This says that whenever there’s an edge in one direction between $a$ and $b$, there’s also one in the other direction. In other words, whenever $\langle a,b\rangle\in R$, then $\langle b,a\rangle\in R$ as well. It’s perfectly all right, however, for neither of these pairs to be in $R$ (or, in terms of $G$, for there to be no street at all between $a$ and $b$).

• $R$ is antisymmetric if and only if $G$ has no two-way streets: all streets are either loops or one-way streets. This says that if $a\ne b$, $\langle a,b\rangle$ and $\langle b,a\rangle$ cannot both belong to $R$; either one of them can, or neither, but not both. Another way to say this is that if $\langle a,b\rangle\in R$ and $\langle b,a\rangle\in R$, then $a=b$, and the apparent two-way street is really just a loop.

• $R$ is asymmetric if and only if $G$ has only one-way streets: there are no loops and no two-way streets. This says that if $\langle a,b\rangle\in R$, then $\langle b,a\rangle\notin R$. In particular, this means that $\langle a,a\rangle$ cannot be in $R$: if it were, its reversal could not be in $R$, and that’s impossible, since it’s equal to its own reversal.

• $R$ is irreflexive if and only if $G$ has no loops. This says that pairs of the form $\langle a,a\rangle$, with both components the same, are never in $R$.

• Transitivity of $R$ is the only property that doesn’t fit altogether easily into this metaphor. Recall that $R$ is transitive if it has the following property: if $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$, then $\langle a,c\rangle\in R$. In terms of ‘streets’ this says that if there’s a street from $a$ to $b$ and a street from $b$ to $c$, then there’s also a street that goes directly from $a$ to $c$.

• How would you describe a transitive closure? – Bob John Nov 13 '12 at 7:16
• In particular, how can I tell the difference between $R^n$ for some positive integer $n$ and $R^*$? – Bob John Nov 13 '12 at 7:20
• @BobJohn: That last question is too vague, I’m afraid: it needs more context. – Brian M. Scott Nov 13 '12 at 7:40
• From your description, I understand transitivity, but I'm having trouble with transitive closure. What does it represent? – Bob John Nov 13 '12 at 7:51
• @BobJohn: It’s the smallest transitive relation on $A$ containing all of the ordered pairs in $R$. One way to get it is to start with $R$. If $R$ is transitive, you’re done. If not, find all of the failures of transitivity and add the missing pairs to $R$. That is, if you find that $\langle a,b\rangle,\langle b,c\rangle\in R$ but $\langle a,c\rangle\notin R$, and add $\langle a,c\rangle$ to $R$. Call the result $R^2$; $R^2$ may be transitive, in which case you’re done, or it may not, in which case you repeat the process to get $R^3$. Keep going; if $A$ is finite, you’ll reach a transitive ... – Brian M. Scott Nov 13 '12 at 7:59

Generally speaking a binary relation between some elements of a set $A$ and some elements of a set $B$ is any set $R\subset A\times B$. Be aware that some mathematicians understand a relation just as a linguistic notion, but it is safe to think about them in the set theoretic framework. For more - check Wikipedia.

Just one more funny thing about family relations, this example comes form "A Tour Through Mathematical Logic" by R. S. Wolf:

imagine that there are two gentelmen, each of them has a wife. They go for a trip and make a stop in the hotel. Because of some state law the desk clerk in the hotel is asking them: "Are you folks married" ? They say at the same time "Yes". Will they be accused of adultery? :) Is "beeing married" an unary or binary property ?