Reflexive relation

Let ${\displaystyle R}$ be a binary relation over 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 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 \,<.}$

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 (${\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 (i.e., 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.

The number of reflexive relations on an n-element set is 2ⁿ²⁻ⁿ.[5]

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

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

• "Reflexivity", Encyclopedia of Mathematics, EMS Press, 2001 [1994]