1
Antisymmetric is not "not symmetric"
It says distinct elements never relate both ways. Equality is both symmetric and antisymmetric; many relations are neither.
Lesson · Sets, Relations, and Functions · Relations
Properties of Relations
Four properties, each a quantified sentence you can check. Then the three closures: the smallest relation containing yours that has the property you want.
reflexive ∀a. aRa
symmetric ∀a,b. aRb → bRa
antisymmetric ∀a,b. aRb ∧ bRa → a = b
transitive ∀a,b,c. aRb ∧ bRc → aRc
Four definitions to check, not recall
Core ideas
What this lesson establishes
Each property is a sentence from Logic and Proof. Deciding whether it holds is evaluating that sentence, and refuting it is naming one bad pair.
2
Transitivity is about two-step paths
Every path of length two must have a one-step shortcut. In the matrix that is a condition on the boolean square.
3
A closure adds the least it can
The transitive closure of R is the smallest transitive relation containing R — not any transitive relation containing it.
The material
The four properties and the three closures
Definitions, the pairs that decide them, and how to repair a relation.
Definition · The four properties
R on A is reflexive if ∀a ∈ A. (a,a) ∈ R; symmetric if ∀a,b. (a,b) ∈ R → (b,a) ∈ R; antisymmetric if ∀a,b. (a,b) ∈ R ∧ (b,a) ∈ R → a = b; transitive if ∀a,b,c. (a,b) ∈ R ∧ (b,c) ∈ R → (a,c) ∈ R.
Two remarks that prevent most of the confusion in this lesson. Antisymmetric is not the negation of symmetric. The equality relation is both. The relation {(1,2), (2,1), (1,3)} is neither. And irreflexive is not the negation of reflexive either: a relation with some but not all loops is neither reflexive nor irreflexive.
Each property is refuted by naming a specific witness, and a check that does not produce one has not really been done. The lab reports the witness on every failure for exactly this reason.
Example · Familiar relations, classified
= on ℤ: reflexive, symmetric, antisymmetric, transitive. ≤: reflexive, antisymmetric, transitive, not symmetric. <: transitive and antisymmetric, not reflexive. "divides" on positive integers: reflexive, antisymmetric, transitive. "a − b is even": reflexive, symmetric, transitive — and not antisymmetric.
Closures
Definition · Closure
The closure of R with respect to a property is the smallest relation containing R that has the property, when one exists.
reflexive closure R ∪ {(a,a) : a ∈ A} add the diagonal
symmetric closure R ∪ R⁻¹ add every reverse
transitive closure R ∪ R² ∪ R³ ∪ … add every path
The transitive closure is the interesting one. Its pairs are exactly the (a, b) joined by a path of one or more steps, so on an n-element set the union stops at Rⁿ — a longer path repeats a vertex and can be shortened. Computing it by taking powers is wasteful; Warshall's algorithm does it in n³ steps, and is what the lab runs.
Theorem · Warshall's algorithm
For k = 1 to n, and for every a, b: if a reaches k and k reaches b in the relation built so far, add (a, b). After the outer loop finishes, the relation is the transitive closure.
The invariant is that after stage k, the relation contains (a, b) exactly when a path from a to b exists using only 1 … k as intermediate points. Stage k+1 adds the paths that route through k+1, which is the only new possibility.
After stage n every intermediate point is permitted, so every path is represented — which is the transitive closure.
□
There is no such thing as an "antisymmetric closure": adding pairs can never remove a violation, since the offending pair (a,b) and (b,a) are already both present. A closure exists only for properties that adding pairs can establish.
Interactive
Relation properties
Decided by checking, not by name
Method
Deciding a property
Evaluate the sentence; produce the witness either way.
1
Reflexive: check the diagonal
Every (a, a) must be present, for every element of the set, not just the ones that appear in some pair.
2
Symmetric: check each pair's reverse
For each (a,b) in R, is (b,a) there? One missing reverse settles it.
3
Antisymmetric: look for two-way pairs between distinct elements
Both (a,b) and (b,a) with a ≠ b refutes it. Loops (a,a) never do.
4
Transitive: check every two-step path
For each (a,b) and (b,c), is (a,c) present? This is the expensive check, and the one people skip.
Properties
Score 0 / 0Choose the answer you can justify.
Classifying "divides" on {1, 2, 3, 4, 6}
a R b when a divides b.
reflexive? a | a always YES
symmetric? 2 | 4 but 4 ∤ 2 NO
antisymmetric? a | b and b | a with a, b positive ⟹ a = b YES
transitive? a | b and b | c ⟹ a | c YES
reflexive + antisymmetric + transitive ⟹ a PARTIAL ORDER
It is only PARTIAL: 2 and 3 are incomparable — neither divides
the other — so not every pair of elements is ranked.
The antisymmetry argument uses positivity. Over all integers it fails: 2 | −2 and −2 | 2 with 2 ≠ −2. A property of a relation depends on the set it is defined over, and dropping that qualification changes the answer.
Common mistakes
1
Reading antisymmetric as "not symmetric"They are independent. Equality is both; {(1,2),(2,1),(1,3)} is neither. The definition is about distinct elements relating both ways.
2
Checking reflexivity only on elements that appear in pairsEvery element of the underlying set needs its loop. An element in no pair at all is exactly what breaks reflexivity.
3
Stopping the transitivity check earlyEvery two-step path must be checked, including the ones through loops. A single missed triple is a wrong verdict.
Check your understanding
✓
Finish when you can name the witness for every verdict.
For each of =, ≤, <, ⊆ and "has the same remainder mod 3", state which of the four properties hold, and for each failure give the specific pair or triple. Naming the witness is the check; everything else is recall.
Note: Transitivity is expensive to verify: n³ triples in the worst case, against n for reflexivity and n² for symmetry. That asymmetry is why transitive closure has an algorithm with a name and the other two do not.