Reflexive relation

You don't need to be Editor-In-Chief to add or edit content to WikiDoc. You can begin to add to or edit text on this WikiDoc page by clicking on the edit button at the top of this page. Next enter or edit the information that you would like to appear here. Once you are done editing, scroll down and click the Save page button at the bottom of the page.

In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity.

At least in this context, (binary) relation (on X) always means a relation on X×X, or in other words from a set X into itself.

• A reflexive relation R on set X is one where for all a in X, a is R-related to itself. In mathematical notation, this is:

.

• An irreflexive (or aliorelative) relation R is one where for all a in X, a is never R-related to itself. In mathematical notation, this is:

.

The reflexive closure R ⁼ is defined as R ⁼ = {(x, x) | x ∈ X} ∪ R, i.e., the smallest reflexive relation over X containing R. This can be seen to be equal to the intersection of all reflexive relations containing R.

The reflexive reduction of a binary relation R on a set is the irreflexive relation R' with xR'y iff xRy for all x≠y.

Note: A common misconception is that a relationship is always either reflexive or irreflexive. Irreflexivity is a stronger condition than failure of reflexivity, so a binary relation may be reflexive, irreflexive, or neither. The strict inequalities "less than" and "greater than" are irreflexive relations whereas the inequalities "less than or equal to" and "greater than or equal to" are reflexive. However, if we define a relation R on the integers such that a R b iff a = -b, then it is neither reflexive nor irreflexive, because 0 is related to itself.

A transitive irreflexive relation is an asymmetric relation and a strict partial order, while a transitive reflexive relation is only a preorder. Thus on a finite set there are more of the latter than of the former.

Some authors, such as Quine (1951), use the term totally reflexive for this property, and use the term relexive for the weaker property

Contents 1 Properties containing the reflexive property 2 Examples 3 Number of reflexive relations 4 References

Properties containing the reflexive property

Preorder - A reflexive relation that is also transitive. Special cases of preorders such as partial orders and equivalence relations are, therefore, also reflexive.

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

Image:GreaterThanOrEqualTo.png

Examples of irreflexive relations include:

• "is not equal to"
• "is coprime to"
• "is greater than":

Image:GreaterThan.png

Number of reflexive relations

Template:Number of relations

The formula for the number of reflexive relations is 2^n2-n

References

• Lidl, R. and Pilz, G. (1998). Applied abstract algebra, Undergraduate Texts in Mathematics, Springer-Verlag. ISBN 0-387-98290-6
• Levy, A. (1979) Basic Set Theory, Perspectives in Mathematical Logic, Springer-Verlag. Reprinted 2002, Dover. ISBN 0-486-42079-5
• Quine, W. V. (1951). Mathematical Logic, Revised Edition. Reprinted 2003, Harvard University Press. ISBN 0-674-55451-5cs:Ireflexivní relace

de:Reflexive Relationko:반사관계 it:Relazione riflessiva he:רפלקסיביות hu:Reflexív relációuk:Рефлексивне відношення