An antisymmetric relation is a binary relation in which no two distinct elements are related to each other in both directions. Formally, a relation on a set is antisymmetric if, for all , the conditions and together imply . Antisymmetry is a defining property of a partial order, alongside reflexivity and transitivity. Despite its name, it does not mean simply “not symmetric.”
Definition and equivalent formulations
A relation on is a subset , where is the Cartesian product of with itself. The notation means that the ordered pair belongs to .
The formal definition of antisymmetry is
Equivalently, for any distinct elements,
Thus, for each pair of distinct elements and , the relation may contain , contain , or contain neither, but it cannot contain both.
There is no restriction on whether an individual diagonal pair belongs to . An antisymmetric relation may contain every diagonal pair, some diagonal pairs, or none.
Another formulation uses the converse relation
and the diagonal relation
Then
If is also reflexive, the inclusion becomes equality:
Examples and nonexamples
Numerical order
The relation on the real numbers is antisymmetric because
The strict relation is also antisymmetric. In this case, and can never both hold, so the implication in the definition is always satisfied. Antisymmetry does not require that any pair actually be related in both directions.
Set inclusion
The subset relation is antisymmetric:
This is why proving two inclusions establishes equality between sets.
Divisibility
Divisibility on the positive integers is antisymmetric. If and , then .
The domain matters, however. Divisibility on all integers is not antisymmetric: and , although . Mutual divisibility determines an integer only up to multiplication by a unit, which in this domain means a sign.
Equality and the empty relation
Equality is antisymmetric and symmetric at the same time. More generally, any relation contained in has both properties.
The empty relation is also antisymmetric, since it contains no pairs that could violate the defining condition.
Failure of antisymmetry
On , the relation
is antisymmetric. Adding destroys antisymmetry because and would hold while .
To prove that a relation is not antisymmetric, it is enough to find one such pair of distinct, mutually related elements.
Distinction from symmetry and asymmetry
Three properties with similar names have different meanings:
| Property | Defining condition |
|---|---|
| [[symmetric-relation | Symmetry]] |
| Antisymmetry | |
| [[asymmetric-relation | Asymmetry]] |
Symmetry requires every related pair to have its reverse. Antisymmetry forbids reverse pairs only between distinct elements. Asymmetry forbids reverse pairs altogether, including diagonal pairs.
Consequently:
- Every asymmetric relation is antisymmetric.
- An antisymmetric relation need not be asymmetric; is an example.
- A relation is asymmetric exactly when it is antisymmetric and irreflexive, meaning that never holds.
- A relation is both symmetric and antisymmetric exactly when it is a subset of the diagonal relation.
Antisymmetry is therefore not the logical negation of symmetry. A relation can have both properties, either one alone, or neither.
Role in order theory
A partial order is a relation that is reflexive, antisymmetric, and transitive. Antisymmetry ensures that two elements cannot be distinct while each lies below the other.
It does not require every two elements to be comparable. Under set inclusion, for example, neither nor holds. A partial order in which every pair is comparable is a total order.
A preorder is reflexive and transitive but need not be antisymmetric. For a preorder , define
This is an equivalence relation. Replacing elements by their equivalence classes produces a partial order:
Transitivity makes this definition independent of the chosen representatives. Antisymmetry then holds because mutual comparability in both directions means that the two classes are identical. This construction identifies precisely those elements whose distinction prevents the original preorder from being antisymmetric.
Graph and matrix representations
A relation can be represented by a directed graph, with an edge whenever . Antisymmetry means that no two distinct vertices have edges in both directions. Self-loops are permitted.
Antisymmetry does not imply acyclicity. For example,
on three distinct elements is antisymmetric despite containing a directed cycle. A directed acyclic graph has no directed cycles of any length, whereas antisymmetry only excludes cycles of length two between distinct vertices. If the relation is also transitive, a cycle through distinct vertices would force reverse edges and violate antisymmetry.
For a finite set , let be the adjacency matrix of the relation, with when and otherwise. Antisymmetry is equivalent to
The diagonal entries are unrestricted. This condition must not be confused with the condition for a skew-symmetric matrix: the two notions describe different properties.
Preservation and counting
Every subrelation of an antisymmetric relation is antisymmetric, since removing ordered pairs cannot create a forbidden pair of opposite directions. Thus, restricting an antisymmetric relation to a smaller underlying set preserves antisymmetry, as does taking its converse.
Intersections of antisymmetric relations on the same set are antisymmetric. Unions need not be: one relation may contain , and another , for distinct and .
Taking a transitive closure need not preserve antisymmetry either. The three-cycle above is antisymmetric, but its transitive closure contains both directions between every pair of vertices.
On a fixed labeled set of elements, the number of antisymmetric relations is
Each of the diagonal pairs can independently be included or omitted. For each of the unordered pairs of distinct elements, there are exactly three choices: include one direction, include the other direction, or include neither. Requiring reflexivity fixes all diagonal choices, leaving reflexive antisymmetric relations; these are not necessarily partial orders because transitivity has not been imposed.