How do the Properties of Relations work?

Question

This is simply not clicking for me. I'm currently learning math during the summer vacation and I'm on the chapter for relations and functions.

There are five properties for a relation:

Reflexive - $R \rightarrow R$

Symmetrical - $R \rightarrow S$ ; $S \rightarrow R$

Antisymmetrical - $R \rightarrow S$ && ($R \rightarrow R$|| $S \rightarrow S$)

Asymmetrical -$R \rightarrow S$ && !($R \rightarrow R$|| $S \rightarrow S$)

Transitive - if $R \rightarrow S$ && $S \rightarrow T$, then $R \rightarrow T$

If that's not what you call the properties in English, then please let me know- I have to study it in German, unfortunately, and these are my rough translations.

Continuing on, I just don't know what to do with this information practically. The examples of the book are horrible:

1. "Is the same age as" is apparently reflexive, symmetrical and transitive.
2. "Is related to" is also apparently reflexive, symmetrical and transitive.
3. "Is older than" is asymmetric, antisymmetric and transitive.

There are more useless examples like this. I have no idea how it comes to these conclusions because we're talking about a literal statement. I was hoping perhaps for some real mathematical examples, but the book falls short on those.

I would greatly appreciate it if somebody could explain the above example and perhaps give me a better use for Relations other than... that. Also, how can a relation be asymmetrical and antisymmetrical at the same time? Don't they cancel each other out?

Answer 1

I'd like to change the notation of your definitions, since $R$, $S$ and $T$ would usually be used to stand for the relations themselves (and $x, y$ and $z$ would be more commonly chosen for the objects that might bear the relation to each other).

Reflexive - For all $x: xRx$

Example reflexive relation: $xRy$ stands for '$x$ is a factor of $y$' (in the set of natural numbers)

Symmetric - For all $x,y$: if $xRy$ then $yRx$

Example symmetric relation: $xRy$ stands for '$x$ and $y$ are $2$ metres apart' (in the set of all people in a particular room)

Antisymmetric - For all $x,y$: if $xRy$ and $yRx$ then $x = y$

Example antisymmetric relation: $xRy$ stands for '$x$ is a factor of $y$' (in the set of natural numbers)

Asymmetric - For all $x,y$: if $xRy$ then not $yRx$

Example asymmetric relation: $xRy$ stands for '$x$ is taller than $y$' (in the set of all people)

Transitive - For all $x,y,z$: if $xRy$ and $yRz$ then $xRz$

Example transitive relation: $xRy$ stands for '$x$ is taller than $y$' (in the set of all people)

Answer 2

There are several important kinds of relations, each of which satisfy a different collection of properties:

Equivalence relations: These are reflexive, symmetric, and transitive. Essentially they're relations that "behave like equality." The most important elementary one is "equivalence modulo m," where say 1 = 6 = 11 modulo 5.

Partial orderings: These are reflexive, transitive, and (anti-symmetric or maybe asymmetric, I'm having trouble parsing your logical statements). Essentially they're relations that "behave like less than or equal to." An important elementary example is "divides" where we say a|b if the ratio b/a is an integer. Note that 2|6 but 6 does not divide 2. However if 2|4 and 4|8 certainly 2|8.

Answer 3

Asymmetric means simply "not symmetric". So in the binary case, it is NOT the case that if a is related to b, b is related to a.

Antisymmetric means that if a is related to b, and b is related to a, a = b.

To explain your third example: "is older than" is asymmetric because if Alice is older than Bob, Bob is NOT older than Alice. "is older than" is antisymmetric since if Alice is older than Bob, and Bob is older than Alice, Alice must be Bob because someone must be older (and if this is not the case, Alice simply has two names..). "is older than" is transitive since if Alice is older than Bob, and Bob is older than Charlie, Alice is also older than Charlie.

So asymmetric and antisymmetric don't cancel out because the first means it's sort of a one-way relation, whereas the second means, loosely, that if it you reverse the operands and both statements are true, the operands must be the same.

Answer 4

It's not clear what the question is asking. Is it asking for logical relations among the properties? e.g. a relation that is transitive and symmetric MUST be reflexive (unless the relation holds between no two objects).

Or is it asking for mathematical relations that have these properties? ">" is transitive, asymmetric and total or complete (for all distinct x,y either xRy or yRx). It is a strict total order. "greater or equal" is transitive, complete, symmetric, reflexive. This is a weak total order.

"x is a subset of y" is reflexive and antisymmetric but not necessarily transitive, symmetric (although it can be either of those things if you restrict yourself to the right sort of sets). "x is a proper subset of y" is asymmetric and irreflexive (for all x, it is not the case that xRx), and can be transitive if you restrict yourself to the right sort of sets.

Note that in both these cases, one can define one of each pair of relations in terms of the other (plus a notion of identity or non-identity).

In logic the notion of "x entails y" is transitive, reflexive.

The relation "x has the same integer part as y" over the real numbers is transitive, reflexive, symmetric. This is called an equivalence relation.

Answer 5

I think you're thinking about this in the wrong way. Properties don't "work", properties are things that are true for the given relation.

For instance, you say that the a relation has the reflexive property if it satisfies the condition that all elements are related to themselves. Similarly, it has the symmetric property if for all a and b, if a is related to b then b is related to a.

You could simply say that "∀a : a R a" each time, but because this is something that happens often, this particular property has been given a name, i.e. reflexivity.

Certain types of specific relations are also given names. For instance, a partial order is reflexive, antisymmetric and transitive, and equivalence relations are reflexive, symmetric and transitive. Again, these are just names that aren't strictly needed, but they make it more convenient talking about these kinds of things.

Answer 6

The calculus of relations is an algebra of operations over sets of pairs of individuals, where for any relation R, we can express the relation in the usual infix manner: x R y iff (x,y) ∈ R. This allows all of the properties of relations to be expressed in equational form.

There are four fundamental relations we want to define, each of which make non-useless examples of three of your five properties of relations, plus one other useful property, irreflexivity:

• Eq = {(x,x) | for each individual x}. This is the diagonal or equality relation that holds only between something and itself. It is reflexive, symmetric and transitive, which is to say it is an equivalence relation.
• All = {(x,y) | for all individuals x,y}. The whenever relation, it is also an equivalence relation.
• Neq = {(x,y) | for all individuals x,y for which x ≠ y}: the inequality relation that holds between anything different. It is symmetric and irreflexive, but not transitive.
• Never is the empty set. It is symmetric and transitive, and irreflexive.

Three basic binary operations on relations, and one unary relation:

• R∩S = {(x,y) | (x,y) ∈ R and (x,y) ∈ S};
• R–S = {(x,y) | (x,y) ∈ R and (x,y) ∉ S};
• R⋅S = {(x,z) | there is some y such that (x,y) ∈ R and (y,z) ∈ S} (composition);
• tr(R) = {(y,x) | (x,y) ∈ R} (transpose).

Observe that Never = All–All, and Neq = All–Eq.

We say R -> S when S holds whenever R holds. This is the same as saying either that R is a subset of S, or that R∩S=R, or that R-S=Never. So Never -> Eq, and Eq -> All.

Then we can express your five relations:

1. R is reflexive when Eq -> R; dually we have an additional property of a relation, where R is anti-reflexive when R -> Neq;
2. R is symmetric when R -> tr(R);
3. R is anti-symmetric when R ∩ tr(R) -> Eq, or equivalently when R ∩ tr(R) ∩ Neq = 0.
4. R is asymmetric when R ∩ tr(R)=Never: a relation is asymmetric when it is anti-symmetric and anti-reflexive;
5. R is transitive when R⋅R -> R.

Also, how can a relation be a- and antisymmetrical at the same time? Don't they cancel each other out? — Look at Eq: it is both symmetric and anti-symmetric, although it is not asymmetric. In fact, all asymmetric relations are anti-symmetric, but not vice versa: the difference is that asymmetric and anti-symmetric differ in what they assert about the diagonal: anti-symmetric doesn't care about what pairs there might be along the diagonal, whilst asymmetric insists that there are no pairs along the diagonal, which is irreflexivity.