# Reflexive relation

In mathematics, a binary relation ${\displaystyle R}$ on a set ${\displaystyle X}$ is reflexive if it relates every element of ${\displaystyle 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 xRy}$  means that ${\displaystyle (x,y)\in R}$  while "not ${\displaystyle xRy}$ " means that ${\displaystyle (x,y)\not \in R.}$

The relation ${\displaystyle R}$  is called reflexive if ${\displaystyle xRx}$  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 reflexive reduction 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 <}$  on the reals ${\displaystyle \mathbb {R} }$  is the usual non-strict inequality ${\displaystyle \leq }$  whereas the reflexive reduction of ${\displaystyle \leq }$  is ${\displaystyle <.}$

### 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 ${\displaystyle xRx}$  holds for no ${\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 xRy,}$  then necessarily ${\displaystyle xRx.}$ [4]
right quasi-reflexive
if whenever ${\displaystyle x,y\in X}$  are such that ${\displaystyle xRy,}$  then necessarily ${\displaystyle yRy.}$
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 xRy,}$  then necessarily ${\displaystyle xRx}$  and ${\displaystyle yRy.}$  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 xRy{\text{ and }}yRx,}$  then necessarily ${\displaystyle x=y.}$
coreflexive
if whenever ${\displaystyle x,y\in X}$  are such that ${\displaystyle xRy,}$  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 xRy}$  implies not ${\displaystyle yRx}$ ), nor antitransitive (${\displaystyle R}$  is antitransitive if ${\displaystyle xRy{\text{ and }}yRz}$  implies not ${\displaystyle xRz}$ ).

## 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>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 Symmetric Preorder Partial order Total preorder Total order Equivalence relation
0 1 1 1 1 1 1 1 1 1
1 2 2 1 2 1 1 1 1 1
2 16 13 4 8 4 3 3 2 2
3 512 171 64 64 29 19 13 6 5
4 65,536 3,994 4,096 1,024 355 219 75 24 15
n 2n2 2n(n−1) 2n(n+1)/2 n
k=0
k!S(n, k)
n! n
k=0
S(n, k)
OEIS A002416 A006905 A053763 A006125 A000798 A001035 A000670 A000142 A000110

Note that S(n, k) refers to Stirling numbers of the second kind.

## 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, p. 74
2. ^ Schmidt 2010
3. ^ This term is due to C S Peirce; see Russell 1920, p. 32. Russell also introduces two equivalent terms to be contained in or imply diversity.
4. ^ The Encyclopedia Britannica calls this property quasi-reflexivity.
5. ^
6. ^ On-Line Encyclopedia of Integer Sequences A053763
7. ^ Hausman, Kahane & Tidman 2013, pp. 327–328
8. ^ Clarke & Behling 1998, p. 187

## References

• Clarke, D.S.; Behling, Richard (1998). Deductive Logic – An Introduction to Evaluation Techniques and Logical Theory. University Press of America. ISBN 0-7618-0922-8.
• Fonseca de Oliveira, José Nuno; Pereira Cunha Rodrigues, César de Jesus (2004), "Transposing relations: from Maybe functions to hash tables", Mathematics of Program Construction, Springer: 334–356
• Hausman, Alan; Kahane, Howard; Tidman, Paul (2013). Logic and Philosophy – A Modern Introduction. Wadsworth. ISBN 1-133-05000-X.
• Levy, A. (1979), Basic Set Theory, Perspectives in Mathematical Logic, Dover, ISBN 0-486-42079-5
• Lidl, R.; 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
• Russell, Bertrand (1920). Introduction to Mathematical Philosophy (PDF) (2nd ed.). London: George Allen & Unwin, Ltd. (Online corrected edition, Feb 2010)
• Schmidt, Gunther (2010), Relational Mathematics, Cambridge University Press, ISBN 978-0-521-76268-7