# Reflexive relation

Short description: Binary relation that relates every element to itself

In mathematics, a binary relation R on a set X is reflexive if it relates every element of X to itself.[1][2]

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.

## Definitions

Let $\displaystyle{ R }$ be a binary relation on a set $\displaystyle{ X, }$ which by definition is just a subset of $\displaystyle{ X \times X. }$ For any $\displaystyle{ x, y \in X, }$ the notation $\displaystyle{ x R y }$ means that $\displaystyle{ (x, y) \in R }$ while "not $\displaystyle{ x R y }$" means that $\displaystyle{ (x, y) \not\in R. }$

The relation $\displaystyle{ R }$ is called reflexive if $\displaystyle{ x R x }$ for every $\displaystyle{ x \in X }$ or equivalently, if $\displaystyle{ \operatorname{I}_X \subseteq R }$ where $\displaystyle{ \operatorname{I}_X := \{ (x, x) ~:~ x \in X \} }$ denotes the identity relation on $\displaystyle{ X. }$ The reflexive closure of $\displaystyle{ R }$ is the union $\displaystyle{ R \cup \operatorname{I}_X, }$ which can equivalently be defined as the smallest (with respect to $\displaystyle{ \subseteq }$) reflexive relation on $\displaystyle{ X }$ that is a superset of $\displaystyle{ R. }$ A relation $\displaystyle{ R }$ is reflexive if and only if it is equal to its reflexive closure.

The reflexive reduction or irreflexive kernel of $\displaystyle{ R }$ is the smallest (with respect to $\displaystyle{ \subseteq }$) relation on $\displaystyle{ X }$ that has the same reflexive closure as $\displaystyle{ R. }$ It is equal to $\displaystyle{ R \setminus \operatorname{I}_X = \{ (x, y) \in R ~:~ x \neq y \}. }$ The irreflexive kernel of $\displaystyle{ R }$ can, in a sense, be seen as a construction that is the "opposite" of the reflexive closure of $\displaystyle{ R. }$ For example, the reflexive closure of the canonical strict inequality $\displaystyle{ \lt }$ on the reals $\displaystyle{ \mathbb{R} }$ is the usual non-strict inequality $\displaystyle{ \leq }$ whereas the reflexive reduction of $\displaystyle{ \leq }$ is $\displaystyle{ \lt . }$

### Related definitions

There are several definitions related to the reflexive property. The relation $\displaystyle{ R }$ is called:

Irreflexive, Anti-reflexive or Aliorelative[3]
If it does not relate any element to itself; that is, if not $\displaystyle{ x R x }$ for every $\displaystyle{ x \in X. }$ A relation is irreflexive if and only if its complement in $\displaystyle{ X \times X }$ is reflexive. An asymmetric relation is necessarily irreflexive. A transitive and irreflexive relation is necessarily asymmetric.
Left quasi-reflexive
If whenever $\displaystyle{ x, y \in X }$ are such that $\displaystyle{ x R y, }$ then necessarily $\displaystyle{ x R x. }$[4]
Right quasi-reflexive
If whenever $\displaystyle{ x, y \in X }$ are such that $\displaystyle{ x R y, }$ then necessarily $\displaystyle{ y R y. }$
Quasi-reflexive
If every element that is part of some relation is related to itself. Explicitly, this means that whenever $\displaystyle{ x, y \in X }$ are such that $\displaystyle{ x R y, }$ then necessarily $\displaystyle{ x R x }$ and $\displaystyle{ y R y. }$ Equivalently, a binary relation is quasi-reflexive if and only if it is both left quasi-reflexive and right quasi-reflexive. A relation $\displaystyle{ R }$ is quasi-reflexive if and only if its symmetric closure $\displaystyle{ R \cup R^{\operatorname{T}} }$ is left (or right) quasi-reflexive.
Antisymmetric
If whenever $\displaystyle{ x, y \in X }$ are such that $\displaystyle{ x R y \text{ and } y R x, }$ then necessarily $\displaystyle{ x = y. }$
Coreflexive
If whenever $\displaystyle{ x, y \in X }$ are such that $\displaystyle{ x R y, }$ then necessarily $\displaystyle{ x = y. }$[5] A relation $\displaystyle{ R }$ is coreflexive if and only if its symmetric closure is anti-symmetric.

A reflexive relation on a nonempty set $\displaystyle{ X }$ can neither be irreflexive, nor asymmetric ($\displaystyle{ R }$ is called asymmetric if $\displaystyle{ x R y }$ implies not $\displaystyle{ y R x }$), nor antitransitive ($\displaystyle{ R }$ is antitransitive if $\displaystyle{ x R y \text{ and } y R z }$ implies not $\displaystyle{ x R z }$).

## Examples

Examples of reflexive relations include:

• "is equal to" (equality)
• "is a subset of" (set inclusion)
• "divides" (divisibility)
• "is greater than or equal to"
• "is less than or equal to"

Examples of irreflexive relations include:

• "is not equal to"
• "is coprime to" on the integers larger than 1
• "is a proper subset of"
• "is greater than"
• "is less than"

An example of an irreflexive relation, which means that it does not relate any element to itself, is the "greater than" relation ($\displaystyle{ x \gt 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 (that is, neither all nor none are). For example, the binary relation "the product of $\displaystyle{ x }$ and $\displaystyle{ 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.

An example of a quasi-reflexive relation $\displaystyle{ R }$ is "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. An example of a left quasi-reflexive relation is a left Euclidean relation, which is always left quasi-reflexive but not necessarily right quasi-reflexive, and thus not necessarily quasi-reflexive.

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 relation and a transitive relation on the same set is always transitive.

## Number of reflexive relations

The number of reflexive relations on an $\displaystyle{ n }$-element set is $\displaystyle{ 2^{n^2-n}. }$[6]

Number of n-element binary relations of different types
Elem­ents 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 65,536 3,994 4,096 355 219 75 24 15
n 2n2 2n2n n
k=0

k! S(n, k)
n! n
k=0

S(n, k)
OEIS A002416 A006905 A053763 A000798 A001035 A000670 A000142 A000110

## Philosophical logic

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.[7][8]

## Notes

1. Levy 1979:74
2. Relational Mathematics, 2010
3. This term is due to C S Peirce, see Bertrand Russell (Apr 1920). Introduction to Mathematical Philosophy (2nd ed.). London: George Allen & Unwin, Ltd..  (Online corrected edition, Feb 2010). Here: p. 32. Russel also introduces two equivalent terms to be contained in or imply diversity.
4. The Encyclopedia Britannica calls this property quasi-reflexivity.
5. Fonseca de Oliveira, J. N., & Pereira Cunha Rodrigues, C. D. J. (2004). Transposing Relations: From Maybe Functions to Hash Tables. In Mathematics of Program Construction (p. 337).
6. On-Line Encyclopedia of Integer Sequences A053763
7. Alan Hausman; Howard Kahane; Paul Tidman (2013). Logic and Philosophy — A Modern Introduction. Wadsworth. ISBN 1-133-05000-X.  Here: p.327-328
8. D.S. Clarke; Richard Behling (1998). Deductive Logic — An Introduction to Evaluation Techniques and Logical Theory. University Press of America. ISBN 0-7618-0922-8.  Here: p.187

## References

• Levy, A. (1979) Basic Set Theory, Perspectives in Mathematical Logic, Springer-Verlag. Reprinted 2002, Dover. ISBN 0-486-42079-5
• Lidl, R. and Pilz, G. (1998). Applied abstract algebra, Undergraduate Texts in Mathematics, Springer-Verlag. ISBN 0-387-98290-6
• Quine, W. V. (1951). Mathematical Logic, Revised Edition. Reprinted 2003, Harvard University Press. ISBN 0-674-55451-5
• Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7.