# Reflexive relation

(Redirected from Irreflexive relation)

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 $R$  be a binary relation on a set $X$ , which by definition is just a subset of $X\times X.$  For any $x,y\in X,$  the notation $xRy$  means that $(x,y)\in R$  while "not $xRy$ " means that $(x,y)\not \in R.$

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

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

### Related definitions

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

Irreflexive or Anti-reflexive
If it does not relate any element to itself; that is, if not $xRx$  for every $x\in X.$  A relation is irreflexive if and only if its complement in $X\times X$  is reflexive. An asymmetric relation is necessarily irreflexive. A transitive and irreflexive relation is necessarily asymmetric.
Left quasi-reflexive
If whenever $x,y\in X$  are such that $xRy,$  then necessarily $xRx.$ 
Right quasi-reflexive
If whenever $x,y\in X$  are such that $xRy,$  then necessarily $yRy.$
Quasi-reflexive
If every element that is related to some element is also related to itself. Explicitly, this means that whenever $x,y\in X$  are such that $xRy,$  then necessarily $xRx$  and $yRy.$  Equivalently, a binary relation is quasi-reflexive if and only if it is both left quasi-reflexive and right quasi-reflexive. A relation $R$  is quasi-reflexive if and only if its symmetric closure $R\cup R^{\operatorname {T} }$  is left (or right) quasi-reflexive.
Antisymmetric
If whenever $x,y\in X$  are such that $xRy$  and $yRx,$  then necessarily $x=y.$
Coreflexive
If whenever $x,y\in X$  are such that $xRy,$  then necessarily $x=y.$  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 ($R$  is called asymmetric if $xRy$  implies not $yRx$ ), nor antitransitive ($R$  is antitransitive if $xRy$  and $yRz$  implies not $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" (for the integers >1, since 1 is coprime to itself)
• "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 ($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.

An example of a quasi-reflexive relation $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 n-element set is 2n2n.

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.