This article covers advanced notions. For basic topics, see Relation (mathematics).
Transitive binary relations
v
t
e
Symmetric
Antisymmetric
Connected
Well-founded
Has joins
Has meets
Reflexive
Irreflexive
Asymmetric
Total, Semiconnex
Anti- reflexive
Equivalence relation
Y
✗
✗
✗
✗
✗
Y
✗
✗
Preorder (Quasiorder)
✗
✗
✗
✗
✗
✗
Y
✗
✗
Partial order
✗
Y
✗
✗
✗
✗
Y
✗
✗
Total preorder
✗
✗
Y
✗
✗
✗
Y
✗
✗
Total order
✗
Y
Y
✗
✗
✗
Y
✗
✗
Prewellordering
✗
✗
Y
Y
✗
✗
Y
✗
✗
Well-quasi-ordering
✗
✗
✗
Y
✗
✗
Y
✗
✗
Well-ordering
✗
Y
Y
Y
✗
✗
Y
✗
✗
Lattice
✗
Y
✗
✗
Y
Y
Y
✗
✗
Join-semilattice
✗
Y
✗
✗
Y
✗
Y
✗
✗
Meet-semilattice
✗
Y
✗
✗
✗
Y
Y
✗
✗
Strict partial order
✗
Y
✗
✗
✗
✗
✗
Y
Y
Strict weak order
✗
Y
✗
✗
✗
✗
✗
Y
Y
Strict total order
✗
Y
Y
✗
✗
✗
✗
Y
Y
Symmetric
Antisymmetric
Connected
Well-founded
Has joins
Has meets
Reflexive
Irreflexive
Asymmetric
Definitions, for all and
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.
All definitions tacitly require the homogeneous relation be transitive: for all if and then
A term's definition may require additional properties that are not listed in this table.
In mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain.[1] A binary relation over sets and is a set of ordered pairs consisting of elements from and from .[2] It is a generalization of the more widely understood idea of a unary function. It encodes the common concept of relation: an element is related to an element , if and only if the pair belongs to the set of ordered pairs that defines the binary relation. A binary relation is the most studied special case of an -ary relation over sets , which is a subset of the Cartesian product [2]
An example of a binary relation is the "divides" relation over the set of prime numbers and the set of integers , in which each prime is related to each integer that is a multiple of , but not to an integer that is not a multiple of . In this relation, for instance, the prime number is related to numbers such as , , , , but not to or , just as the prime number is related to , , and , but not to or .
Binary relations are used in many branches of mathematics to model a wide variety of concepts. These include, among others:
the "is greater than", "is equal to", and "divides" relations in arithmetic;
the "is congruent to" relation in geometry;
the "is adjacent to" relation in graph theory;
the "is orthogonal to" relation in linear algebra.
A function may be defined as a binary relation that meets additional constraints.[3] Binary relations are also heavily used in computer science.
A binary relation over sets and is an element of the power set of Since the latter set is ordered by inclusion (), each relation has a place in the lattice of subsets of A binary relation is called a homogeneous relation when . A binary relation is also called a heterogeneous relation when it is not necessary that .
Since relations are sets, they can be manipulated using set operations, including union, intersection, and complementation, and satisfying the laws of an algebra of sets. Beyond that, operations like the converse of a relation and the composition of relations are available, satisfying the laws of a calculus of relations, for which there are textbooks by Ernst Schröder,[4] Clarence Lewis,[5] and Gunther Schmidt.[6] A deeper analysis of relations involves decomposing them into subsets called concepts, and placing them in a complete lattice.
In some systems of axiomatic set theory, relations are extended to classes, which are generalizations of sets. This extension is needed for, among other things, modeling the concepts of "is an element of" or "is a subset of" in set theory, without running into logical inconsistencies such as Russell's paradox.
The terms correspondence,[7]dyadic relation and two-place relation are synonyms for binary relation, though some authors use the term "binary relation" for any subset of a Cartesian product without reference to and , and reserve the term "correspondence" for a binary relation with reference to and .[citation needed]
^Meyer, Albert (17 November 2021). "MIT 6.042J Math for Computer Science, Lecture 3T, Slide 2" (PDF). Archived (PDF) from the original on 2021-11-17.
^ abCodd, Edgar Frank (June 1970). "A Relational Model of Data for Large Shared Data Banks" (PDF). Communications of the ACM. 13 (6): 377–387. doi:10.1145/362384.362685. S2CID 207549016. Archived (PDF) from the original on 2004-09-08. Retrieved 2020-04-29.
^"Relation definition – Math Insight". mathinsight.org. Retrieved 2019-12-11.
^Ernst Schröder (1895) Algebra und Logic der Relative, via Internet Archive
^C. I. Lewis (1918) A Survey of Symbolic Logic, pages 269–279, via internet Archive
^Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7, Chapt. 5
^Jacobson, Nathan (2009), Basic Algebra II (2nd ed.) § 2.1.
mathematics, a binaryrelation associates elements of one set, called the domain, with elements of another set, called the codomain. A binaryrelation over sets...
In mathematics, a homogeneous relation (also called endorelation) on a set X is a binaryrelation between X and itself, i.e. it is a subset of the Cartesian...
In mathematics, a binaryrelation R {\displaystyle R} on a set X {\displaystyle X} is reflexive if it relates every element of X {\displaystyle X} to...
relation is a type of binaryrelation. An example is the relation "is equal to", because if a = b is true then b = a is also true. Formally, a binary...
In mathematics, a binaryrelation R on a set X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates...
In mathematics, a binaryrelation R {\displaystyle R} on a set X {\displaystyle X} is antisymmetric if there is no pair of distinct elements of X {\displaystyle...
two arguments Binary operation, a mathematical operation that takes two arguments Binaryrelation, a relation involving two elements Binary-coded decimal...
Rx1⋯xn and using postfix notation by x1⋯xnR. In the case where R is a binaryrelation, those statements are also denoted using infix notation by x1Rx2. The...
mathematics, an equivalence relation is a binaryrelation that is reflexive, symmetric and transitive. The equipollence relation between line segments in...
In mathematics, an asymmetric relation is a binaryrelation R {\displaystyle R} on a set X {\displaystyle X} where for all a , b ∈ X , {\displaystyle...
term, as in binary code. For instance, 'hot' gains meaning because of its relation to 'cold,' and vice versa. It is not a contradictory relation but a structural...
canonically identified with the quotient topology under the equivalence relation defined by f. Dually, for a function f from a set S to a topological space...
a binaryrelation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of'...
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a...
equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) is a homogeneous binaryrelation that is...
mathematics, the transitive closure R+ of a homogeneous binaryrelation R on a set X is the smallest relation on X that contains R and is transitive. For finite...
case of a logical matrix representing a binaryrelation R, the transpose corresponds to the converse relation RT. The transpose of a matrix A, denoted...
mathematics, especially in order theory, a preorder or quasiorder is a binaryrelation that is reflexive and transitive. The name preorder is meant to suggest...
axiomatization of a calculus of relations. Roughly, a relation algebra is to a system of binary relations on a set containing the empty (0), universal...
In mathematics, a binaryrelation R ⊆ X×Y between two sets X and Y is total (or left total) if the source set X equals the domain {x : there is a y with...
partial order without incomparable pairs Total relation, which may also mean connected relation (a binaryrelation in which any two elements are comparable)...
single binary operation, satisfying certain axioms. If G {\displaystyle G} is a group with operation ∗ {\displaystyle \ast } , a congruence relation on G...
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols:...