In mathematics, a binary relation R over a set X is reflexive if it relates every element of X to itself.^{[1]}^{[2]} Formally, this may be written ?x ? X : x R x, or as I ? R where I is the identity relation on X.
An example of a reflexive relation is the relation "is equal to" on the set of real numbers, since every real number is equal to itself. A reflexive relation is said to have the reflexive property or is said to possess reflexivity. Along with symmetry and transitivity, reflexivity is one of three properties defining equivalence relations.
A binary relation is called irreflexive, or anti-reflexive, if it doesn't relate any element to itself. An example is the "greater than" relation (x > y) on the real numbers. Not every relation which is not reflexive is irreflexive; it is possible to define relations where some elements are related to themselves but others are not (i.e., neither all nor none are). For example, the binary relation "the product of x and y is even" is reflexive on the set of even numbers, irreflexive on the set of odd numbers, and neither reflexive nor irreflexive on the set of natural numbers. However, a relation is irreflexive if, and only if, its complement is reflexive.
A relation ~ on a set X is called quasi-reflexive if every element that is related to some element is also related to itself, formally: ? x, y ? X : x ~ y => (x ~ x ? y ~ y). An example is the relation "has the same limit as" on the set of sequences of real numbers: not every sequence has a limit, and thus the relation is not reflexive, but if a sequence has the same limit as some sequence, then it has the same limit as itself. It does make sense to distinguish left and right quasi-reflexivity, defined by ? x, y ? X : x ~ y => x ~ x^{[3]} and ? x, y ? X : x ~ y => y ~ y, respectively. For example, a left Euclidean relation is always left, but not necessarily right, quasi-reflexive. A relation R is quasi-reflexive if, and only if, its symmetric closure R?R^{T} is left (or right) quasi-reflexive.
A relation ~ on a set X is called coreflexive if for all x and y in X it holds that if x ~ y then x = y.^{[4]} An example of a coreflexive relation is the relation on integers in which each odd number is related to itself and there are no other relations. The equality relation is the only example of a both reflexive and coreflexive relation, and any coreflexive relation is a subset of the identity relation. The union of a coreflexive and a transitive relation is always transitive. A relation R is coreflexive if, and only if, its symmetric closure is anti-symmetric.
A reflexive relation on a nonempty set X can neither be irreflexive, nor asymmetric, nor antitransitive.
The reflexive closure ? of a binary relation ~ on a set X is the smallest reflexive relation on X that is a superset of ~. Equivalently, it is the union of ~ and the identity relation on X, formally: (?) = (~) ? (=). For example, the reflexive closure of (<) is (
The reflexive reduction, or irreflexive kernel, of a binary relation ~ on a set X is the smallest relation ? such that ? shares the same reflexive closure as ~. It can be seen in a way as the opposite of the reflexive closure. It is equivalent to the complement of the identity relation on X with regard to ~, formally: (?) = (~) \ (=). That is, it is equivalent to ~ except for where x~x is true. For example, the reflexive reduction of (
Examples of reflexive relations include:
Examples of irreflexive relations include:
The number of reflexive relations on an n-element set is 2^{n2-n}.^{[5]}
Elements | Any | Transitive | Reflexive | Preorder | Partial order | Total preorder | Total order | Equivalence relation |
---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 355 | 219 | 75 | 24 | 15 | |||
n | 2^{n2} | 2^{n2-n} | ?n k=0 k! S(n, k) |
n! | ?n k=0 S(n, k) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Authors in philosophical logic often use different terminology. Reflexive relations in the mathematical sense are called totally reflexive in philosophical logic, and quasi-reflexive relations are called reflexive.^{[6]}^{[7]}