aiwiki.page
English
Mathematics / Discrete Math & Logic / antisymmetric-relation

Antisymmetric Relation

An antisymmetric relation is a binary relation in which two elements can be related in both directions only if they are equal.

15 keywords2 linked from3 not yet writtenWritten by AI
Binary RelationPartial OrderCartesian Produc…Ordered PairReal NumberSubsetIntegerEquivalence Rela…Antisymmet…

An antisymmetric relation is a binary relation in which no two distinct elements are related to each other in both directions. Formally, a relation RR on a set AA is antisymmetric if, for all a,b∈Aa,b\in A, the conditions aRbaRb and bRabRa together imply a=ba=b. 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 AA is a subset R⊆A×AR\subseteq A\times A, where A×AA\times A is the Cartesian product of AA with itself. The notation aRbaRb means that the ordered pair (a,b)(a,b) belongs to RR.

The formal definition of antisymmetry is

∀a,b∈A,(aRb∧bRa)⟹a=b.\forall a,b\in A,\qquad (aRb\land bRa)\Longrightarrow a=b.

Equivalently, for any distinct elements,

a≠b⟹¬(aRb∧bRa).a\ne b\Longrightarrow \neg(aRb\land bRa).

Thus, for each pair of distinct elements aa and bb, the relation may contain (a,b)(a,b), contain (b,a)(b,a), or contain neither, but it cannot contain both.

There is no restriction on whether an individual diagonal pair (a,a)(a,a) belongs to RR. An antisymmetric relation may contain every diagonal pair, some diagonal pairs, or none.

Another formulation uses the converse relation

R−1={(b,a):(a,b)∈R}R^{-1}=\{(b,a):(a,b)\in R\}

and the diagonal relation

ΔA={(a,a):a∈A}.\Delta_A=\{(a,a):a\in A\}.

Then

R is antisymmetric⟺R∩R−1⊆ΔA.R\text{ is antisymmetric} \quad\Longleftrightarrow\quad R\cap R^{-1}\subseteq\Delta_A.

If RR is also reflexive, the inclusion becomes equality:

R∩R−1=ΔA.R\cap R^{-1}=\Delta_A.

Examples and nonexamples

Numerical order

The relation ≤\leq on the real numbers is antisymmetric because

a≤b and b≤a⟹a=b.a\leq b\ \text{and}\ b\leq a \quad\Longrightarrow\quad a=b.

The strict relation << is also antisymmetric. In this case, a<ba<b and b<ab<a 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:

X⊆Y and Y⊆X⟹X=Y.X\subseteq Y\ \text{and}\ Y\subseteq X \quad\Longrightarrow\quad X=Y.

This is why proving two inclusions establishes equality between sets.

Divisibility

Divisibility on the positive integers is antisymmetric. If a∣ba\mid b and b∣ab\mid a, then a=ba=b.

The domain matters, however. Divisibility on all integers is not antisymmetric: 2∣−22\mid -2 and −2∣2-2\mid 2, although 2≠−22\ne -2. 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 ΔA\Delta_A has both properties.

The empty relation is also antisymmetric, since it contains no pairs that could violate the defining condition.

Failure of antisymmetry

On A={1,2,3}A=\{1,2,3\}, the relation

R={(1,1),(1,2),(2,3)}R=\{(1,1),(1,2),(2,3)\}

is antisymmetric. Adding (2,1)(2,1) destroys antisymmetry because 1R21R2 and 2R12R1 would hold while 1≠21\ne2.

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 (aRb∧bRa)⟹a=b(aRb\land bRa)\Longrightarrow a=b
[[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; ≤\leq is an example.
  • A relation is asymmetric exactly when it is antisymmetric and irreflexive, meaning that aRaaRa 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 {1}⊆{2}\{1\}\subseteq\{2\} nor {2}⊆{1}\{2\}\subseteq\{1\} 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 ⪯\preceq, define

a∼b⟺a⪯b and b⪯a.a\sim b \quad\Longleftrightarrow\quad a\preceq b\ \text{and}\ b\preceq a.

This is an equivalence relation. Replacing elements by their equivalence classes produces a partial order:

[a]≤[b]⟺a⪯b.[a]\leq[b] \quad\Longleftrightarrow\quad a\preceq b.

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 a→ba\to b whenever aRbaRb. Antisymmetry means that no two distinct vertices have edges in both directions. Self-loops are permitted.

Antisymmetry does not imply acyclicity. For example,

R={(a,b),(b,c),(c,a)}R=\{(a,b),(b,c),(c,a)\}

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 A={a1,…,an}A=\{a_1,\ldots,a_n\}, let MM be the adjacency matrix of the relation, with Mij=1M_{ij}=1 when aiRaja_iRa_j and 00 otherwise. Antisymmetry is equivalent to

MijMji=0for every i≠j.M_{ij}M_{ji}=0 \qquad\text{for every }i\ne j.

The diagonal entries are unrestricted. This condition must not be confused with the condition MT=−MM^{\mathsf T}=-M 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 (a,b)(a,b), and another (b,a)(b,a), for distinct aa and bb.

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 nn elements, the number of antisymmetric relations is

2n 3(n2).2^n\,3^{\binom n2}.

Each of the nn diagonal pairs can independently be included or omitted. For each of the (n2)\binom n2 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 3(n2)3^{\binom n2} reflexive antisymmetric relations; these are not necessarily partial orders because transitivity has not been imposed.