mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a

binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...

R

on a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

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, b \in X,

\text \,aRb\, \text \,a \neq b\, \text \,bRa\, \text,

or equivalently,

\text \,aRb\, \text \,bRa\, \text \,a = b.

The definition of antisymmetry says nothing about whether

aRa

actually holds or not for any

a

. An antisymmetric relation

R

on a set

X

may be reflexive (that is,

aRa

for all

a \in X

), irreflexive (that is,

aRa

for no

a \in X

), or neither reflexive nor irreflexive. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.

Examples

The

divisibility In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a ''Multiple (mathematics), multiple'' of m. An integer n is divis ...

relation on the

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

s is an important example of an antisymmetric relation. In this context, antisymmetry means 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.

For example, 12 is divisible by 4, but 4 is not divisible by 12. The usual order relation

\,\leq\,

on the

real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...

s is antisymmetric: if for two real numbers

x

and

y

both inequalities

x \leq y

and

y \leq x

hold, then

x

and

y

must be equal. Similarly, the subset order

\,\subseteq\,

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:

A \subseteq B \text B \subseteq A \text A = B

A real-life example of a relation that is typically antisymmetric is "paid the restaurant bill of" (understood as restricted to a given occasion). Typically, some people pay their own bills, while others pay for their spouses or friends. As long as no two people pay each other's bills, the relation is antisymmetric.

Properties

Partial and

total order In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( re ...

s are antisymmetric by definition. A relation can be both symmetric and antisymmetric (in this case, it must be coreflexive), and there are relations which are neither symmetric nor antisymmetric (for example, the "preys on" relation on biological

species A species () is often defined as the largest group of organisms in which any two individuals of the appropriate sexes or mating types can produce fertile offspring, typically by sexual reproduction. It is the basic unit of Taxonomy (biology), ...

). Antisymmetry is different from

asymmetry Asymmetry is the absence of, or a violation of, symmetry (the property of an object being invariant to a transformation, such as reflection). Symmetry is an important property of both physical and abstract systems and it may be displayed in pre ...

: a relation is asymmetric if and only if it is antisymmetric and irreflexive.

References

* *
nLab antisymmetric relation
{{DEFAULTSORT:Antisymmetric Relation Properties of binary relations

Examples

Properties

See also

References