#jsDisabledContent { display:none; } My Account |  Register |  Help

# Reflexive relation

Article Id: WHEBN0000200458
Reproduction Date:

 Title: Reflexive relation Author: World Heritage Encyclopedia Language: English Subject: Collection: Mathematical Relations Publisher: World Heritage Encyclopedia Publication Date:

### Reflexive relation

In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself. In other words, a relation ~ on a set S is reflexive when x ~ x holds true for every x in S, formally: when ∀xS: x~x holds.[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.

## Contents

• Related terms 1
• Examples 2
• Number of reflexive relations 3
• Philosophical logic 4
• Notes 6
• References 7

## Related terms

A relation that is irreflexive, or anti-reflexive, is a binary relation on a set where no element is related to itself. An example is the "greater than" relation (x>y) on the real numbers. 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 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.

A relation ~ on a set S is called quasi-reflexive if every element that is related to some element is also related to itself, formally: if ∀x,yS: x~yx~xy~y. An example is the relation "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.

The reflexive closure ≃ of a binary relation ~ on a set S is the smallest reflexive relation on S that is a superset of ~. Equivalently, it is the union of ~ and the identity relation on S, formally: (≃) = (~) ∪ (=). For example, the reflexive closure of x<y is xy.

The reflexive reduction, or irreflexive kernel, of a binary relation ~ on a set S is the smallest relation ≆ such that ≆ shares the same reflexive closure as ~. 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 ~, formally: (≆) = (~) \ (=). That is, it is equivalent to ~ except for where x~x is true. For example, the reflexive reduction of xy is x<y.

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

## Number of reflexive relations

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

Number of n-element binary relations of different types
n all 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 65536 3994 4096 355 219 75 24 15
OEIS A002416 A006905 A053763 A000798 A001035 A000670 A000142 A000110

## Philosophical logic

Authors in philosophical logic often use deviating designations. A reflexive and a quasi-reflexive relation in the mathematical sense is called a totally reflexive and a reflexive relation in philosophical logic sense, respectively.[4][5]

## Notes

1. ^ Levy 1979:74
2. ^ Relational Mathematics, 2010
3. ^ On-Line Encyclopedia of Integer Sequences A053763
4. ^ Alan Hausman, Howard Kahane, Paul Tidman (2013). Logic and Philosophy — A Modern Introduction. Wadsworth. Here: p.327-328
5. ^ D.S. Clarke, Richard Behling (1998). Deductive Logic — An Introduction to Evaluation Techniques and Logical Theory. University Press of America. Here: p.187

## 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
• Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7.