A reflexive relation is a binary relation on a set in which every element is related to itself. Formally, a relation is reflexive on if
Reflexivity is one of the defining properties of equivalence relations and partial orders. It imposes a requirement only on pairs whose two entries are equal; it places no restriction on whether distinct elements are related.
Definition and underlying set
Writing for , the defining condition becomes
The relation is a subset of the Cartesian product .
The identity relation, or diagonal relation, on is
Thus reflexivity can equivalently be expressed as
The identity relation is the smallest reflexive relation on , while the universal relation is the largest.
Reflexivity depends on the specified underlying set. For example,
is reflexive on , but not on , because .
On the empty set, the empty relation is reflexive: there is no element for which the requirement could fail. This is an instance of a universally quantified statement being true when its domain is empty.
Examples and nonexamples
Common reflexive relations include:
- Equality: for every element of any set.
- Non-strict numerical order: for every real number .
- Set inclusion: for every set , so inclusion is reflexive on any specified collection of sets.
- Divisibility: Every positive integer divides itself.
- Congruence modulo a positive integer: , since divides . This relation is central to modular arithmetic.
In contrast, strict order is not reflexive on a nonempty set of numbers, because never holds. Inequality likewise never relates an element to itself.
Reflexivity does not require every pair to belong to the relation. On , the relation
is reflexive even though .
Distinction from other relation properties
A relation is irreflexive if no element is related to itself:
Being not reflexive is different from being irreflexive. Failure of reflexivity requires only one missing diagonal pair:
For example, on is neither reflexive nor irreflexive. On a nonempty set, a relation cannot be both reflexive and irreflexive; on the empty set, the empty relation has both properties.
Reflexivity is also distinct from:
- Symmetry: implies .
- Antisymmetry: and together imply .
- Transitivity: and together imply .
None of these three properties follows from reflexivity alone. Their combinations define important classes of relations:
| Class | Required properties |
|---|---|
| Equivalence relation | Reflexive, symmetric, transitive |
| [[preorder | Preorder]] |
| Partial order | Reflexive, antisymmetric, transitive |
For example, reflexivity in an equivalence relation ensures that every element belongs to its own equivalence class.
Graph and matrix representations
A relation on a set can be represented by a directed graph, with an edge from to exactly when . Under this representation, reflexivity means that every vertex has a self-loop. This representation requires a graph convention that permits loops.
For a finite set , define the Boolean adjacency matrix by
The relation is reflexive exactly when every diagonal entry is :
Off-diagonal entries are unrestricted. Consequently, the number of reflexive relations on a fixed -element set is
because the diagonal entries are fixed and the remaining entries can be chosen independently.
Reflexive closure and preservation
The reflexive closure of a relation on is
It is the smallest reflexive relation on containing . It adds precisely the missing self-pairs and leaves all pairs of distinct elements unchanged. In graph terms, it adds missing self-loops; in matrix terms, it sets every diagonal entry to .
Several operations preserve reflexivity:
- The intersection of reflexive relations on the same set is reflexive.
- The union of any nonempty family of reflexive relations on the same set is reflexive.
- The inverse relation is reflexive whenever is.
- If , the restriction is reflexive on whenever is reflexive on .
- The composition of two reflexive relations on the same set is reflexive, since each element can serve as its own intermediate element.
In graph reachability, the reflexive transitive closure allows paths of length zero, so every vertex is reachable from itself. A transitive closure defined using only paths of positive length need not be reflexive: an isolated vertex, for example, has no positive-length path back to itself.