# 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.

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
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. }$
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. }$ 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}. }$

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.