Reflexive relation

In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation R on S where xRx holds true for every x in S.^[1]

Related terms

An irreflexive, or anti-reflexive, relation is the opposite of a reflexive relation. It is a binary relation on a set where no element is related to itself. An example is x<y. Note that not every relation which is not reflexive is irreflexive; it is possible to define relations where some elements are related to themselves but not others. 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 on the set of natural numbers.

The reflexive closure of a binary relation R on a set S is the smallest relation R′ such that R′ is a superset of R and R′ is reflexive on S. This is equivalent to the union of R and the identity relation on S. For example, the reflexive closure of x<y is x≤y.

The reflexive reduction of a binary relation R on a set S is the smallest relation R′ such that R′ shares the same reflexive closure as R. It can be seen in a way as the opposite of the reflexive closure. It is equivalent to the complement of the identity relation on S with regard to R. That is, it is equivalent to R except for where xRx is true. For example, the reflexive reduction of x≤y is x<y.

Examples

Examples of reflexive relations include:

• "is equal to" (equality)
• "is a subset of" (set inclusion)
• "divides" (divisibility)
• "is greater/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":

Number of reflexive relations

The number of reflexive relations on an n-element set is 2^n2-n.^[2]

Notes

References

• 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