Antisymmetric Relation
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].
- AKA: Asymmetric Relation.
- Context:
- Example(s):
- A Partial Order Relation which is also a Transitive Relation and a Reflexive Relation.
- A Total Order Relation which is also a Transitive Relation and a Total Relation.
- If R(a,b). “R(b,c) and R(c,c) are True then R(a,a). “R(b,b) are also True, but R(b,a) and R(c,b) are False. The relations of R(c,a) and R(a,c) however are undefined.
- Equal(A,B): Because IF a=b and b=a THEN a=b.
- LessThanOrEqualTo(a,b): Because IF a≤b and b≤a THEN a=b.
- Subset(A,B): Because a subset can be a subset with itself. (but not a ProperSubset()).
- PartOf(car,wheel) ⇒ False.
- …
- Counter-Example(s):
- a Symmetric Relation.
- ProperSubset(A,B), because a subset cannot be a proper subset to itself.
- See: Irreflexive Relation, IsSiblingTo, IsParentTo, Reflexive Relation, Binary Relation, Order Relation, Real Number, Subset Order.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/antisymmetric_relation 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.
- 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
2009
- http://www.cs.odu.edu/~toida/nerzic/content/relation/property/property.html
- 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.