Reflexive relation
From Wikipedia, the free encyclopedia
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]
Contents |
[edit] 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.
[edit] 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":
[edit] Number of reflexive relations
The number of reflexive relations on an n-element set is 2n2-n.[2]
| 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 |
[edit] Notes
[edit] See also
[edit] 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
