Antisymmetric relation

In mathematics, an antisymmetric relation is a binary relation R on a set X with the property that no two distinct elements are related to each other in both directions: whenever a is related to b and b is related to a, it follows that a = b. Together with reflexivity and transitivity, antisymmetry constitutes the defining axiom of a (non-strict) partial order, and it is accordingly one of the fundamental properties studied in the theory of binary relations. The canonical example is the familiar order relation "less than or equal to" (≤) on the real numbers: if a ≤ b and b ≤ a, then necessarily a = b. Despite its name, antisymmetry is not the logical negation of symmetry; a relation may be symmetric, antisymmetric, both, or neither.

Definition and Equivalent Formulations

A binary relation R on a set X is antisymmetric if

∀a, b ∈ X: (aRb ∧ bRa) → a = b.

Several equivalent formulations are commonly used:

• Contrapositive form: for all a, b ∈ X, if a ≠ b, then at most one of aRb and bRa holds.
• Relational-algebraic form: the symmetric part of R, namely the intersection R ∩ R⁻¹ (where R⁻¹ denotes the converse relation), is contained in the identity relation Δ = {(x, x) : x ∈ X}.
• Matrix form: representing R by its Boolean matrix M, the relation is antisymmetric if and only if no two symmetrically placed off-diagonal entries are both equal to 1, that is, mᵢⱼ = mⱼᵢ = 1 never occurs for i ≠ j.
• Graph-theoretic form: in the directed graph of the relation, there is no pair of distinct vertices joined by directed edges in both directions (no two-element directed cycles); loops at single vertices are unrestricted.

It is important to distinguish antisymmetric from asymmetric. A relation is asymmetric if aRb implies that bRa fails. Every asymmetric relation is antisymmetric (vacuously, since the antecedent aRb ∧ bRa can never hold), but the converse fails: the relation ≤ is antisymmetric yet not asymmetric, because a ≤ a holds.

Examples and Non-examples

Examples of antisymmetric relations:

• The relations ≤ and ≥ on the natural numbers, integers, or real numbers.
• The subset relation ⊆ on any collection of sets: if A ⊆ B and B ⊆ A, then A = B by the axiom of extensionality.
• The divisibility relation "|" on the natural numbers: if a divides b and b divides a, then a = b. Notably, the same relation fails to be antisymmetric on the integers, since 2 divides −2 and −2 divides 2 although 2 ≠ −2.
• The identity relation, in which each element is related only to itself.
• The proper-subset relation ⊂ and the relation "is an ancestor of" among people, both of which are antisymmetric vacuously because no element can stand in the relation to itself or return the relation.
• The lexicographic (dictionary) ordering on sequences of symbols.

Non-examples:

• Congruence modulo n: since 1 ≡ 3 (mod 2) and 3 ≡ 1 (mod 2) while 1 ≠ 3, this symmetric congruence relation is not antisymmetric.
• "Has the same birthday as" on a set of people: symmetric, but generally not antisymmetric.
• "Is a sibling of," since siblings are related in both directions while remaining distinct.

Basic Properties

The antisymmetry of a relation interacts with other relational properties as follows:

• Compatibility with symmetry. A relation is both symmetric and antisymmetric if and only if it is contained in the identity relation (a "partial identity"). If such a relation is also reflexive, it is exactly the identity relation. Thus the only relations that are simultaneously reflexive, symmetric, and antisymmetric are trivial.
• Independence from reflexivity and transitivity. Antisymmetry neither implies nor is implied by either property. The relation {(x, y) : x < y + 1} on the integers, for instance, is antisymmetric and reflexive but not transitive; the three-cycle relation {(a,b), (b,c), (c,a)} is antisymmetric and not transitive.
• Vacuous cases. On a one-element set, every relation is antisymmetric. Any asymmetric relation is antisymmetric.
• Subrelation and restriction. Every subrelation of an antisymmetric relation, and the restriction of an antisymmetric relation to any subset, is again antisymmetric.
• Totality does not suffice for transitivity. A relation that is both antisymmetric and connex (any two distinct elements are comparable) need not be transitive, as shown by the three-cycle example above; adding transitivity yields a total (linear) order.

Preservation under Operations and Constructions

Antisymmetry is preserved by some natural constructions and violated by others:

• Preserved: the converse R⁻¹ of an antisymmetric relation; the intersection of any family of antisymmetric relations; the reflexive closure (adding the identity pairs) of an antisymmetric relation.
• Not preserved in general: the union of two antisymmetric relations. For example, on {1, 2}, the relations {(a,b)} and {(b,a)} with a ≠ b are each antisymmetric, but their union contains both (a,b) and (b,a) and hence is not. Similarly, the composition of antisymmetric relations may fail to be antisymmetric: with R = {(a,b), (c,d)} and S = {(b,c), (d,a)} on a four-element set, both are antisymmetric while R ∘ S contains (a,c) and (c,a). The transitive closure of an antisymmetric relation can likewise fail antisymmetry whenever the relation contains a directed cycle of length greater than one.

Enumerative Aspects

The antisymmetry condition constrains relations in a combinatorially transparent way. On an n-element set, for each unordered pair of distinct elements there are exactly three antisymmetric possibilities — neither direction, the first direction only, or the second direction only — while each diagonal element admits two possibilities (loop present or absent). Hence the number of antisymmetric binary relations on an n-element set is

2ⁿ · 3ⁿ⁽ⁿ⁻¹⁾ᐟ²,

which equals 2 for n = 1, 12 for n = 2, and 216 for n = 3. By comparison, there are 2^(n²) binary relations in total and 3ⁿ⁽ⁿ⁻¹⁾ᐟ² asymmetric ones.

Role in Order Theory

Antisymmetry occupies a central position in the axiomatics of order. A binary relation that is reflexive, antisymmetric, and transitive is a partial order (poset structure); one that is irreflexive and transitive — which entails asymmetry and hence antisymmetry — is a strict partial order. Adding the comparability requirement (connexity) to these axioms yields total orders and strict total orders, respectively. The antisymmetry axiom is precisely what prevents distinct elements from being "tied" by the ordering, thereby enabling the graphical representation of posets by Hasse diagrams and the definition of order-theoretic notions such as minimal and maximal elements, upper and lower bounds, and least and greatest elements.

When a relation is reflexive and transitive but not antisymmetric (a preorder or quasi-order), the mutual-relation pairs form an equivalence relation, and the quotient of the underlying set by this equivalence carries a canonical induced partial order. This construction shows that antisymmetry can always be recovered "up to equivalence," a fact of considerable technical importance in lattice theory and domain theory.

Historical Development

The systematic study of binary relations originated in nineteenth-century algebraic logic, principally in the work of Augustus De Morgan, who introduced the notion of the converse of a relation, and of Charles Sanders Peirce, whose "logic of relatives" developed an algebraic calculus of relations. Ernst Schröder gave the tradition its most complete exposition in his Vorlesungen über die Algebra der Logik (1890–1905), where properties now called reflexive, transitive, symmetric, and related notions were studied in a unified framework. Early twentieth-century axiomatizations of order — associated with figures such as Felix Hausdorff, whose Grundzüge der Mengenlehre (1914) treated ordered sets rigorously, and Edward V. Huntington — consolidated antisymmetry as a standard postulate for ordering. The terminology and viewpoint became fully standard with the rise of lattice and order theory, notably Garrett Birkhoff's Lattice Theory (1940), and subsequent mid-century textbooks of set theory and foundations embedded the definition in essentially the form used today. The precise first use of the term "antisymmetric" is difficult to attribute, as older literature occasionally employed overlapping terminology, but the concept itself has been foundational to order theory since its inception.

Applications and Significance

Antisymmetric relations model one-directional comparison, precedence, hierarchy, and containment, and therefore appear throughout mathematics and its applications:

• Pure mathematics. Partial orders pervade algebra (subgroup and ideal inclusion), topology (the specialization order), analysis (pointwise ordering of functions), and logic (the ordering of truth values and of information states).
• Computer science. Comparison-based sorting and searching presume total orders; partial orders model task scheduling, build and dependency systems, version histories (directed acyclic graphs), and subtyping in type systems. The "happened-before" relation of Lamport (1978), fundamental to reasoning about causality in distributed systems, is irreflexive and transitive and hence antisymmetric. Domain theory, which underlies the semantics of programming languages, is built on antisymmetric orders of information content.
• Information organization. Taxonomic relations such as "is a subclass of" and part–whole relations in ontologies are required to be antisymmetric so that conceptual hierarchies do not collapse distinct categories into one another.

Conceptually, antisymmetry encodes the principle that between distinct objects a relation of ordering, containment, or precedence may hold in at most one direction