Asymmetric relation
In mathematics, an asymmetric relation is a binary relation R on a set X such that for all a, b \in X, if a \, R \, b, then it is not the case that b \, R \, a.[1] This condition ensures that the relation never holds in both directions between any pair of elements, including when a = b, making asymmetric relations inherently irreflexive.[2] Asymmetric relations are a strengthening of antisymmetric relations, which only require that if both a \, R \, b and b \, R \, a, then a = b; every asymmetric relation is thus antisymmetric, but the converse does not hold.[1] They are also incompatible with symmetry, as symmetric relations allow reciprocity, whereas asymmetry forbids it entirely.[3] A key property is that any transitive and irreflexive relation on a nonempty set is automatically asymmetric.[1] Common examples include the strict less-than relation < on the natural numbers, where n < m implies m \not< n, and spatial relations like "is to the left of" among objects in a plane.[3] Asymmetric relations play a fundamental role in order theory, forming the basis for strict partial orders when combined with transitivity, and they appear in graph theory as directed graphs without bidirectional edges or loops.[2]Preliminaries
Binary relations
In mathematics, a binary relation R on a set X is defined as a subset of the Cartesian product X \times X, where X \times X consists of all ordered pairs (a, b) with a, b \in X.[4] This structure captures pairwise associations between elements of X, allowing R to specify which pairs satisfy the relation. The notation (a, b) \in R indicates that a is related to b under R, commonly abbreviated in infix form as aRb.[5] To illustrate, consider the equality relation on a set X, defined as the set \{(x, x) \mid x \in X\}; here, xRy holds if and only if x = y.[6] Another example is the strict less-than ordering on the set of real numbers \mathbb{R}, given by \{(x, y) \mid x < y, \, x, y \in \mathbb{R}\}, where xRy means x precedes y numerically.[6] These examples highlight how binary relations encode specific connections via their set-of-pairs composition, without imposing additional constraints at this foundational level. For finite sets, if |X| = n, then |X \times X| = n^2, and the set of all possible binary relations on X has cardinality $2^{n^2}, corresponding to the power set of X \times X. In contrast, for infinite sets, the cardinality of the set of binary relations is $2^{|X \times X|}; since |X \times X| = |X| for infinite cardinals |X| (assuming the axiom of choice), this yields $2^{|X|} possible relations, a consideration that arises in representations like directed multigraphs for infinite structures. Properties such as reflexivity, where aRa holds for all a \in X, provide building blocks for further analysis but are not part of the basic definition.Basic properties of relations
Binary relations on a set can exhibit various properties that describe how elements interact with each other and themselves. These properties provide a foundational framework for classifying relations and understanding their behavior in mathematical structures. The key properties include reflexivity, irreflexivity, symmetry, antisymmetry, and transitivity, each defined precisely in terms of the relation's action on the set.[7] A binary relation R on a set X is reflexive if every element is related to itself, formally: \forall a \in X, \, aRa. For example, the equality relation on the real numbers, where a = a for all a, is reflexive. A relation is irreflexive if no element is related to itself: \forall a \in X, \, \neg (aRa). The strict inequality relation < on the real numbers is irreflexive, as no number is less than itself.[7] Symmetry concerns the bidirectional nature of the relation: R is symmetric if \forall a, b \in X, \, aRb \implies bRa. The relation of similarity between triangles is symmetric, since if one triangle is similar to another, the reverse holds. In contrast, antisymmetry prevents mutual relations except for identical elements: \forall a, b \in X, \, (aRb \land bRa) \implies a = b. The "less than or equal to" relation \leq on the real numbers is antisymmetric, as equality is the only case allowing both directions.[7] Transitivity captures chaining of relations: R is transitive if \forall a, b, c \in X, \, (aRb \land bRc) \implies aRc. Parallelism among lines in a plane is transitive, as lines parallel to the same line are parallel to each other. These properties originated in the late 19th and early 20th centuries within the development of set theory and order theory, with formalizations by mathematicians such as Dedekind in the 1890s and Jourdain in 1912.[7][8] Relations often combine these properties to form important classes. For instance, a relation that is reflexive, symmetric, and transitive is called an equivalence relation, partitioning the set into disjoint equivalence classes where elements are interchangeable. The equality relation exemplifies this combination, serving as a prototype in many contexts. Other combinations, such as reflexive, antisymmetric, and transitive relations, define partial orders, but these build on the basic properties outlined here.[7]Definition
Formal definition
In mathematics, a binary relation R on a set X is said to be asymmetric if, for all a, b \in X, whenever a \, R \, b holds, it follows that b \, R \, a does not hold.[9] Formally, this is expressed as \forall a, b \in X \ (a \, R \, b \to \neg b \, R \, a). This condition ensures directed exclusivity: the relation cannot hold in both directions between any pair of elements.[10] This definition is logically equivalent to its contrapositive, \forall a, b \in X \ (b \, R \, a \to \neg a \, R \, b), which similarly prohibits mutual relatedness.[9] In order theory and related contexts, asymmetric relations are frequently denoted using symbols like <, as in strict orders where one element precedes another without reciprocity.[11] Asymmetry captures a fundamental property of one-way directedness without assuming reflexivity, distinguishing it from broader order structures that may impose additional constraints like transitivity.Immediate implications
A binary relation R on a set X that is asymmetric is necessarily irreflexive. To prove this, suppose toward a contradiction that R is asymmetric but not irreflexive. Then there exists some a \in X such that aRa. However, by the definition of asymmetry, aRa implies \neg (aRa), yielding the contradiction aRa \land \neg (aRa). Therefore, no such a can exist, so \forall a \in X, \neg (aRa).[12][13] This implication can be clarified via a truth table for the logical constraint imposed by asymmetry on the diagonal pairs (a, a). Let P denote aRa for a fixed a \in X. Asymmetry requires P \to \neg P:| P | \neg P | P \to \neg P |
|---|---|---|
| True | False | False |
| False | True | True |