Antisymmetric Relations

definitions
discrete-math
set-theory
relations
proof

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