Antisymmetric Relations
A relation is antisymmetric when no two different elements are related in both directions. It is the property that takes the place of symmetry in a partial order (partial-order-relations). In spite of the name it is not the opposite of symmetric. The other three properties are in reflexive-symmetric-and-transitive-relations. First met in 2026-09-22-partial-order-relations.
The definition
A relation \(R\) on a set \(S\) is antisymmetric if and only if \[\forall a, b \in S,\ (a \mathrel{R} b \text{ and } b \mathrel{R} a) \to (a = b).\]
There are two equivalent definitions:
\[\forall a, b \in S,\ (a \neq b) \to {\sim}(a \mathrel{R} b \text{ and } b \mathrel{R} a).\] \[\forall a, b \in S,\ (a \mathrel{R} b \text{ and } a \neq b) \to {\sim}(b \mathrel{R} a).\]
The first is the easiest for proving a relation antisymmetric, and the third is the most intuitive.
| In words | |
|---|---|
| first | If \(a\) and \(b\) are related both ways, they are the same element. |
| second | Two different elements are not related both ways. |
| third | If \(a\) is related to a different element \(b\), then \(b\) is not related back to \(a\). |
Why the three say the same thing
Write \(p\) for \(a \mathrel{R} b\), \(q\) for \(b \mathrel{R} a\) and \(r\) for \(a = b\). The three definitions are the conditionals
\[(p \land q) \to r, \qquad {\sim}r \to {\sim}(p \land q), \qquad (p \land {\sim}r) \to {\sim}q.\]
The second is the contrapositive of the first (conditional-statements). For the third, recall that a conditional is false in only one situation, a true hypothesis with a false conclusion. Work out that situation for each:
| Conditional | False exactly when |
|---|---|
| \((p \land q) \to r\) | \(p\) true, \(q\) true, \(r\) false |
| \({\sim}r \to {\sim}(p \land q)\) | \(r\) false, \(p\) true, \(q\) true |
| \((p \land {\sim}r) \to {\sim}q\) | \(p\) true, \(r\) false, \(q\) true |
It is the same situation each time, so the three are logically equivalent. Each one forbids exactly one thing: \(a \mathrel{R} b\) and \(b \mathrel{R} a\) with \(a \neq b\).
In the arrow diagram
Antisymmetric: no two different dots are joined by arrows both ways. Loops are not restricted. When \(a = b\) the first definition reads \((a \mathrel{R} a \text{ and } a \mathrel{R} a) \to (a = a)\), which is true whether or not there is a loop at \(a\).
Between two different elements there are three possibilities, and symmetry and antisymmetry each rule out a different one.
Figure 1: What symmetry and antisymmetry allow between two different elements. With no arrow, both are satisfied. A single arrow has no return, which breaks symmetry and is fine for antisymmetry. Arrows both ways are what symmetry asks for, and they break antisymmetry. So a symmetric relation has no single arrows, and an antisymmetric relation has no two-way pairs. A loop joins an element to itself and breaks neither.
Antisymmetric is not “not symmetric”
Antisymmetric \(\neq\) not symmetric. The two properties are independent, and all four combinations occur. The diagrams are the four of 2026-09-22-partial-order-relations.
| antisymmetric | not antisymmetric | |
|---|---|---|
| symmetric | Diagram 2. Only loops. Also: \(=\) on any set. | Diagram 3. Two-way pairs, no single arrows. Also: same parity on \(\mathbb{Z}\). |
| not symmetric | Diagram 4. Single arrows, no two-way pairs. Also: \(\leq\) on \(\mathbb{R}\), \(\subseteq\), divides on \(\mathbb{Z}^{+}\). | Diagram 1. A single arrow and a two-way pair. |
The definitions make the difference exact:
- not symmetric says there is an arrow with no return;
- antisymmetric says no arrow between different elements has a return.
A relation that is not symmetric can still have some two-way pairs, as Diagram 1 does, and then it is not antisymmetric either.
Both at once. If \(R\) is symmetric and antisymmetric, every arrow is a loop. Suppose \(a \mathrel{R} b\). Symmetry gives \(b \mathrel{R} a\), and then antisymmetry gives \(a = b\). So the only relations with both properties are those in which no element is related to anything but itself, like Diagram 2.
Proving and disproving
Antisymmetry is a “for all”, so it is proved with arbitrary elements and disproved with one witness.
| How | |
|---|---|
| To prove it | Let \(a, b \in S\) and suppose \(a \mathrel{R} b\) and \(b \mathrel{R} a\). Unfold both. Show \(a = b\). |
| To disprove it | Find two different elements \(a, b\) with \(a \mathrel{R} b\) and \(b \mathrel{R} a\). |
In the proof, write the goal down before starting: (Goal: show \(a = b\)). Both hypotheses will be needed.
Worked: divides on \(\mathbb{Z}^{+}\)
Worked in full in 2026-09-22-partial-order-relations. Let \(a, b \in \mathbb{Z}^{+}\) and suppose \(a \mid b\) and \(b \mid a\). (Goal: show \(a = b\).) Then \(b = ak\) and \(a = b\ell\) for some \(k, \ell \in \mathbb{Z}\). Substituting, \[b = ak = (b\ell)k = b(\ell k),\] and since \(b \neq 0\), \(\ell k = 1\). Now \(a, b > 0\) forces \(k > 0\) and \(\ell > 0\), and the only positive integers with product 1 are \(\ell = k = 1\). So \(a = b\).
The last step uses that the set is \(\mathbb{Z}^{+}\). See Examples for what goes wrong on \(\mathbb{Z}\).
Worked: a disproof
From practice-problems, Q2. On binary strings of length 6, let \(s \mathrel{\rho} t\) if and only if \(\operatorname{weight}(s) \leq \operatorname{weight}(t)\), where the weight is the number of ones. Take \(s = 100000\) and \(t = 010000\). Both have weight 1, so \(s \mathrel{\rho} t\) and \(t \mathrel{\rho} s\), but \(s \neq t\). So \(\rho\) is not antisymmetric.
Two different things with the same weight are related both ways. Any relation that compares elements through a number they can share fails in the same way.
The third form in a proof
The first definition is the easiest to prove from, but the third works too. The solution to practice-problems, Q1 uses it: suppose \(x \mathrel{\rho} y\) where \(x \neq y\); we must show that then \(y \mathrel{\not\rho} x\). Either is acceptable. State which you are using.
Examples
The standard examples, with reasons:
| Relation | on | Antisymmetric because |
|---|---|---|
| \(\leq\) | \(\mathbb{R}\) | \((x \leq y \text{ and } y \leq x) \to x = y\) |
| \(\geq\) | \(\mathbb{R}\) | the same, reversed |
| \(<\), \(>\) | \(\mathbb{R}\) | \(x < y\) and \(y < x\) never hold together |
| divides | \(\mathbb{Z}^{+}\) | proved above |
| \(\subseteq\) | any set \(S\) of sets | \((X \subseteq Y \text{ and } Y \subseteq X) \to X = Y\) |
\(<\) is antisymmetric vacuously. For no \(x, y\) are \(x < y\) and \(y < x\) both true. The hypothesis of the first definition is therefore always false, and a conditional with a false hypothesis is true (conditional-statements). In the diagram of \(<\) there are no two-way pairs, and no loops either.
\(\subseteq\) is the double-containment rule. Showing \(X \subseteq Y\) and \(Y \subseteq X\) to conclude \(X = Y\) is how set equality is proved (sets-and-set-notation). Antisymmetry of \(\subseteq\) is that rule under another name.
Divides is not antisymmetric on \(\mathbb{Z}\). \(2 \mid -2\), since \(-2 = 2 \cdot (-1)\), and \(-2 \mid 2\), since \(2 = (-2)(-1)\), but \(2 \neq -2\). This is why the statement is about \(\mathbb{Z}^{+}\). A relation is always a relation on a particular set, and the same rule on a bigger set can lose a property.
Not antisymmetric: any relation with two different elements related both ways. That includes congruence mod \(n\) for \(n \geq 1\), same parity, and every equivalence relation that has a class with more than one element.
Common mistakes
- Reading “antisymmetric” as “not symmetric”. See the four combinations above.
- Thinking a loop breaks antisymmetry. It does not. The property is about pairs of different elements.
- Proving it from an example. “\(2 \mid 4\) but \(4 \nmid 2\)” shows one pair behaves. Antisymmetry is about all pairs.
- Using only one hypothesis. A proof that starts “suppose \(a \mathrel{R} b\)” and never uses \(b \mathrel{R} a\) cannot reach \(a = b\).
- Disproving with \(a = b\). A witness needs two different elements. \(a \mathrel{R} a\) on its own shows nothing.
See also
- partial-order-relations — reflexive, antisymmetric and transitive together
- reflexive-symmetric-and-transitive-relations — the other three properties, and how to prove and disprove them
- conditional-statements — the contrapositive, and vacuous truth
- divisibility-and-factorisation — the definition of divides
- 2026-09-22-partial-order-relations — Lecture 25
- practice-problems — §32, with full worked solutions