In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an asymmetric relation is a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
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 ...
where for all
if
is related to
then
is ''not'' related to
Formal definition
A binary relation on
is any subset
of
Given
write
if and only if
which means that
is shorthand for
The expression
is read as "
is related to
by
" The binary relation
is called if for all
if
is true then
is false; that is, if
then
This can be written in the notation of
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
as
A
logically equivalent definition is:
:for all
at least one of
and
is ,
which in first-order logic can be written as:
An example of an asymmetric relation is the "
less than
In mathematics, an inequality is a relation which makes a non-equal comparison between two numbers or other mathematical expressions. It is used most often to compare two numbers on the number line by their size. There are several different ...
" relation
between
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s: if
then necessarily
is not less than
The "less than or equal" relation
on the other hand, is not asymmetric, because reversing for example,
produces
and both are true.
Asymmetry is not the same thing as "not
symmetric": the less-than-or-equal relation is an example of a relation that is neither symmetric nor asymmetric. The
empty relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
is the only relation that is (
vacuously) both symmetric and asymmetric.
Properties
* A relation is asymmetric if and only if it is both
antisymmetric and
irreflexive
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
.
*
Restrictions and
converses
Chuck Taylor All-Stars or Converse All Stars (also referred to as "Converse", "Chuck Taylors", "Chucks", "Cons", "All Stars", and "Chucky Ts") is a model of casual shoe manufactured by Converse (a subsidiary of Nike, Inc. since 2003) that was i ...
of asymmetric relations are also asymmetric. For example, the restriction of
from the reals to the integers is still asymmetric, and the inverse
of
is also asymmetric.
* A
transitive relation
In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive.
Definition
A hom ...
is asymmetric if and only if it is irreflexive:
[ Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".] if
and
transitivity gives
contradicting irreflexivity.
* As a consequence, a relation is transitive and asymmetric if and only if it is a
strict partial order.
* Not all asymmetric relations are strict partial orders. An example of an asymmetric non-transitive, even
antitransitive relation is the relation: if
beats
then
does not beat
and if
beats
and
beats
then
does not beat
* An asymmetric relation need not have the
connex property. For example, the
strict subset relation
is asymmetric, and neither of the sets
and
is a strict subset of the other. A relation is connex if and only if its complement is asymmetric.
See also
*
Tarski's axiomatization of the reals – part of this is the requirement that
over the real numbers be asymmetric.
References
{{DEFAULTSORT:Asymmetric Relation
Binary relations
Asymmetry