Back to the on-screen lesson ·
Reflexive, symmetric, antisymmetric and transitive as quantified statements, and the two combinations that name almost every relation worth having.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to test a relation against the four properties by quoting their definitions, refute one with a single element, pair or triple, and classify a relation as an equivalence relation, a partial order or neither. You will also be able to say why symmetry and antisymmetry are not opposites, why reflexivity does not follow from the other two, and what a property holding vacuously means.
Lesson 12 ended by noting that a relation on $A$ is a subset of $A \times A$, and that there are far too many of them to count usefully. The properties in this lesson are how the useful ones are picked out, and each property is a quantified statement of the kind lesson 4 taught you to read.
A relation $R$ on $A$ is a subset of $A \times A$; $a R b$ means $(a, b) \in R$. It is reflexive when $a R a$ for every $a$, symmetric when $a R b$ forces $b R a$, antisymmetric when $a R b$ and $b R a$ force $a = b$, and transitive when $a R b$ and $b R c$ force $a R c$.
Each property is a statement with quantifiers, and the number of elements it quantifies over is worth noticing, because it tells you what a counterexample looks like.
| Property | Says | Refuted by |
|---|---|---|
| reflexive | $\forall a\, (a R a)$ | one element |
| symmetric | $\forall a, b\, (a R b \Rightarrow b R a)$ | one pair |
| antisymmetric | $\forall a, b\, (a R b \wedge b R a \Rightarrow a = b)$ | one pair of distinct elements |
| transitive | $\forall a, b, c\, (a R b \wedge b R c \Rightarrow a R c)$ | one triple |
Two combinations account for most of the relations in mathematics.
Equivalence relation: reflexive, symmetric, transitive. These are the relations that mean the same in some respect — congruence modulo $m$, having the same number of digits, being similar triangles. The next lesson shows that such a relation carves the set into classes, which is the reason they matter.
Partial order: reflexive, antisymmetric, transitive. These mean at most as much as — $\le$ on the integers, $\subseteq$ on sets, divisibility on the positive integers. Partial is the operative word: $2$ and $3$ divide neither the other, and neither of $\{1\}$ and $\{2\}$ contains the other, so an order can leave two elements simply incomparable.
Symmetry and antisymmetry are not opposites. Symmetry says every reversed pair is related; antisymmetry says a pair related both ways must be equal. Equality itself has both. A relation can also have neither, which is the ordinary case.
Another way: steps
To classify a relation:
Another way: example
$|a - b| \le 1$ on the integers is reflexive ($|a - a| = 0$) and symmetric (the absolute value does not care about order), and it is not transitive: $1$ and $2$, $2$ and $3$, but not $1$ and $3$. So it is neither structure — and a single triple was enough to say so.
Every one of the four properties is a universal statement, so lesson 9's asymmetry applies in full. To refute transitivity, exhibit one triple. To establish it, argue about arbitrary $a$, $b$ and $c$ — which is a proof, usually three or four lines by the direct method.
So the efficient order of work is: hunt briefly for a counterexample to each property, and only start proving the ones that survive the hunt. Ten minutes of looking for a bad triple is often the whole of the answer, and when it fails it has usually shown you why the proof works.
One trap: a property can hold vacuously. The empty relation is symmetric and transitive because there are no pairs to check, and a relation on the empty set has all four properties. Vacuous truth is not a loophole — it is what lesson 1's implication table says — but it is where an argument that 'obviously' something must be related goes wrong.
Treating antisymmetric as not-symmetric. They are different conditions and equality satisfies both.
Checking transitivity on the pairs you can see. Transitivity is about every triple, and the failing one is usually the one you have not written down.
Assuming reflexivity comes free. It does not follow from the other two, and the empty relation shows it.
*Reading partial as incomplete.* A partial order is not a defective total order; leaving two elements incomparable is the normal and useful case, and $\subseteq$ is the example to keep in mind.
It is a set of pairs, nothing more. That is why the empty relation and the relation containing every pair are both perfectly good relations, and why the four properties are checked against the pairs rather than against the intention behind them. When a relation is described in words — is a friend of, is similar to — the words suggest properties the set of pairs may not have, and the check is always against the pairs.
$a \sim b$ when $5$ divides $a - b$. Reflexive: $a - a = 0$ and five divides zero.
One element at a time.
Symmetric: if $a - b = 5k$ then $b - a = -5k$, also a multiple of five.
One pair.
Transitive: if $a - b = 5k$ and $b - c = 5\ell$ then $a - c = 5(k + \ell)$. All three hold, so it is an equivalence relation — and its classes are the five remainders, which is the next lesson.
One triple, and the algebra is one addition.
Divisibility on the positive integers. Reflexive: $a = a \cdot 1$. Transitive: proved in lesson 6.
Two properties already in hand.
Antisymmetric: if $a \mid b$ and $b \mid a$ with both positive then $a \le b \le a$, so $a = b$.
The positivity is doing real work here.
So it is a partial order. And $2$ and $3$ are incomparable — neither divides the other — which is exactly what $\le$ on the integers never does, and what makes the divisibility order more interesting than a line.
Incomparability is a feature.
Reflexive: every number has the same last digit as itself, so yes.
One element.
Symmetric: if $a$ and $b$ share a last digit then so do $b$ and $a$. Yes.
One pair.
Transitive: sharing a last digit with $b$, and $b$ with $c$, gives the same digit throughout. So it is an equivalence relation, with ten classes — one per digit. Notice that this is congruence modulo ten in disguise, which is the usual outcome when a relation says the same in some respect.
Take the relation $a \mid b$ on the positive integers. For each property write $1$ if it holds and $0$ if it does not.
| $1$ for yes, $0$ for no | |
|---|---|
| Reflexive | |
| Symmetric | |
| Transitive |
Is $a \le b$ on the integers an equivalence relation, a partial order, or neither?
Match each property of a relation to what it says.
| Every element is related to itself | Whenever $a$ is related to $b$, $b$ is related to $a$ | Whenever $a$ is related to $b$ and $b$ to $c$, $a$ is related to $c$ | The only way $a$ and $b$ can be related both ways is for them to be equal | |
|---|---|---|---|---|
| Reflexive | ||||
| Symmetric | ||||
| Transitive | ||||
| Antisymmetric |
Mark every relation on the integers below that is transitive.
This task has no paper form; do it on a device.
Somebody argues: 'If $R$ is symmetric and transitive it must be reflexive. Take any $a$; there is some $b$ with $a R b$; by symmetry $b R a$; by transitivity $a R a$.' Where does the argument go wrong?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Take the relation $a \sim b$ when $a - b$ is a multiple of $5$. For each property write $1$ if it holds and $0$ if it does not.
| $1$ for yes, $0$ for no | |
|---|---|
| Reflexive | |
| Symmetric | |
| Transitive |
You can test a relation against the four properties and name the structure it forms. Say in your own words what a counterexample to transitivity looks like, and why a partial order may leave two elements incomparable. Next: what an equivalence relation does to the set it lives on.
10. Your turn: classify 'has the same last digit as' on the positive integers, step 3