Reflexive relation
In mathematics, a binary relation R over a set X is reflexive if every element of X is related to itself.[1][2]
In mathematical notation, this is:
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.
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,y∈S: x~y ⇒ x~x ∧ y~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 x≤y.
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 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 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 2n2−n.[3]
| Elements | 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 | 2n(n−1) | 2n(n+1)/2 | ∑n k=0 k!S(n, k) |
n! | ∑n k=0 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 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]
See also
Notes
- ^ Levy 1979:74
- ^ Relational Mathematics, 2010
- ^ On-Line Encyclopedia of Integer Sequences A053763
- ^ Alan Hausman; Howard Kahane; Paul Tidman (2013). Logic and Philosophy — A Modern Introduction. Wadsworth. ISBN 1-133-05000-X. Here: p.327-328
- ^ 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
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.
External links
- "Reflexivity", Encyclopedia of Mathematics, EMS Press, 2001 [1994]