Anti-Symmetric Relation

Definition

A relation $R:A\to A\to \mathrm{Prop}$ is anti-symmetric iff $\forall x,y:A.Rxy\to Ryx\to x=y.$

That is, if two elements are related in both directions, they must be equal.

Asymmetry

A stronger property is asymmetry: $R$ is asymmetric iff $\forall x,y:A.Rxy\to \neg Ryx.$

Every asymmetric relation is anti-symmetric (since $Rxy\to Ryx$ is vacuously false when $R$ is asymmetric), but not conversely. The strict less-than relation $<$ on $\mathbb{N}$ is asymmetric; the non-strict $\le$ is anti-symmetric but not asymmetric (since $x\le x$ holds for all $x$).

Examples

• $\le$ on $\mathbb{N}$ or $\mathbb{R}$: if $x\le y$ and $y\le x$ then $x=y$.
• The subset relation $\subseteq$: if $A\subseteq B$ and $B\subseteq A$ then $A=B$ (this is the axiom of extensionality).
• $<$ on $\mathbb{N}$: asymmetric, hence also anti-symmetric.

Role in Order Theory

Anti-symmetry is one of the defining properties of a partial order: a preorder that is additionally anti-symmetric is a partial order. It distinguishes partial orders from mere preorders, where distinct elements may be related in both directions.

Related Concepts

• Reflexive Relation
• Transitive Relation
• Symmetric Relation
• Partial Order
• Preorder