# 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.[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 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 <}$  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 not ${\displaystyle xRx}$  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 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 2n2n 2n(n+1)/2 ${\textstyle \sum _{k=0}^{n}k!S(n,k)}$  n! ${\textstyle \sum _{k=0}^{n}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:74
2. ^ Relational Mathematics, 2010
3. ^ This term is due to C S Peirce, see Bertrand Russell (Apr 1920). Introduction to Mathematical Philosophy (PDF) (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