Antisymmetric Relation

(Redirected from antisymmetric relation)
Jump to navigation Jump to search

An antisymmetric relation is a binary relation that is an asymmetric relationship, where for any [math]\displaystyle{ a,b }[/math], [math]\displaystyle{ TRUE(R(a,b)) }[/math] and [math]\displaystyle{ TRUE(R(b,a)) }[/math] implies that [math]\displaystyle{ a = b }[/math].



  • (Wikipedia, 2015) ⇒ Retrieved:2015-11-7.
    • In mathematics, a binary relation R on a set X is antisymmetric if there is no pair of distinct elements of X each of which is related by R to the other. More formally, R is antisymmetric precisely if for all a and b in X

      :if R(a,b) and R(b,a), then a = b,

      or, equivalently,

      :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 antisymmetric relation. And what antisymmetry 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: : [math]\displaystyle{ \forall a, b \in X,\ R(a,b) \and R(b,a) \; \Rightarrow \; a = b }[/math] or, equivalently, : [math]\displaystyle{ \forall a, b \in X,\ R(a,b) \and a \ne b \Rightarrow \lnot R(b,a) . }[/math] The usual order relation ≤ on the real numbers is antisymmetric: 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 antisymmetric: 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: : [math]\displaystyle{ A \subseteq B \and B \subseteq A \Rightarrow A = B }[/math] Partial and total orders are antisymmetric by definition. A relation can be both symmetric and antisymmetric (e.g., the equality relation), and there are relations which are neither symmetric nor antisymmetric (e.g., the "preys on" relation on biological species).

      Antisymmetry is different from asymmetry, which requires both antisymmetry and irreflexivity.


    • antisymmetric relation: A relation R on a set A is called antisymmetric if and only if for any a, and b in A, whenever [math]\displaystyle{ \lt a, b\gt R }[/math], and [math]\displaystyle{ \lt b,a\gt R, a = b }[/math] must hold. Equivalently, R is antisymmetric if and only if whenever <a, b> R, and [math]\displaystyle{ a b, \lt b, a\gt R }[/math]. Thus in an antisymmetric relation no pair of elements are related to each other.
    • Example 7: The relation < (or >) on any set of numbers is antisymmetric. So is the equality relation on any set of numbers.