||This article is written like a manual or guidebook. (January 2010) (Learn how and when to remove this template message)|
|This article needs additional citations for verification. (January 2010) (Learn how and when to remove this template message)|
In mathematics, a binary relation R on a set X is anti-symmetric if there is no pair of distinct elements of X each of which is related by R to the other. More formally, R is anti-symmetric precisely if for all a and b in X
- if R(a,b) and R(b,a), then a = b,
- if R(a,b) with a ≠ b, then R(b,a) must not hold.
As a simple example, the divisibility order on the natural numbers is an anti-symmetric relation. And what anti-symmetry means here is that the only way each of two numbers can be divisible by the other is if the two are, in fact, the same number; equivalently, if n and m are distinct and n is a factor of m, then m cannot be a factor of n.
In mathematical notation, this is:
The usual order relation ≤ on the real numbers is anti-symmetric: if for two real numbers x and y both inequalities x ≤ y and y ≤ x hold then x and y must be equal. Similarly, the subset order ⊆ on the subsets of any given set is anti-symmetric: given two sets A and B, if every element in A also is in B and every element in B is also in A, then A and B must contain all the same elements and therefore be equal:
Partial and total orders are anti-symmetric by definition. A relation can be both symmetric and anti-symmetric (e.g., the equality relation), and there are relations which are neither symmetric nor anti-symmetric (e.g., the "preys on" relation on biological species).
The relation "x is even, y is odd" between a pair (x, y) of integers is anti-symmetric:
Every asymmetric relation is also an anti-symmetric relation.