Reflexive relation - Citizendia

In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. In Mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of

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

If a relation is reflexive, all elements in the set are related to themselves. For example, the relations "is not greater than" and "is equal to" are reflexive over the set of all real numbers. Since no real number is greater than itself, if you compare any number to itself, you will find "is not greater than" to be true. Since every real number is equal to itself, if you compare any number to itself, you will find "is equal to" to be true.

A reflexive relation is ON set X. This means that all elements in a set are related to themselves by the relation. There are relations which are reflexive on certain sets but not reflexive on the set of real numbers. Say the relation is:

a is related to b if (a - b/2) is a whole number.

This relation is reflexive on the set of EVEN numbers but not reflexive on the set of real numbers. Because. . .

2 - 2/2 = 2 - 1 = 1 is a whole number 4 - 4/2 = 4 - 2 = 2 is a whole number

BUT

3 - 3/2 = 3 - 1. 5 = 1. 5 is NOT a whole number.

Formally:

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:

$\forall a \in X,\ a R a$ . See also Table of mathematical symbols Mathematical notation is used in Mathematics, and throughout the Physical sciences, Engineering

An irreflexive (or aliorelative) relation R is one where for all a in X, a is never R-related to itself.

An irreflexive relation is a relationship for which no element of a set is related to itself.

Formally:

$\forall a \in X,\ \lnot (a R a)$ .

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 and 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. In Mathematics, an inequality is a statement about the relative size or order of two objects or about whether they are the same or not (See also equality 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. ↔

An irreflexive relation is a relationship for which NO element of a set is related to itself.

With the example above, the relationship is irreflexive for the set of odd numbers (no odd number is related to itself that way), reflexive for the set of even numbers (all even numbers are related to themselves that way), and neither reflexive or irreflexive for the set of all integers.

A transitive irreflexive relation is an asymmetric relation and a strict partial order, while a transitive reflexive relation is only a preorder. In Mathematics, a Binary relation R over a set X is transitive if whenever an element a is related to an element b Asymmetric often means simply not symmetric In this sense an asymmetric relation is a Binary relation which is not a Symmetric relation. In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Mathematics, especially in Order theory, preorders are Binary relations that satisfy certain conditions 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

$\forall a ( \exists b (aRb \lor bRa) \to aRa).$

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. In Mathematics, especially in Order theory, preorders are Binary relations that satisfy certain conditions In Mathematics, a Binary relation R over a set X is transitive if whenever an element a is related to an element b Special cases of preorders such as partial orders and equivalence relations are, therefore, also reflexive. In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent"

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"
"is greater than":

Number of reflexive relations

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

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

References

Lidl, R. Equality is the paradigmatic example of the more general concept of Equivalence relations on a set those binary relations which are reflexive, symmetric In Mathematics, a divisor of an Integer n, also called a factor of n, is an integer which evenly divides n without In Mathematics, the Integers a and b are said to be coprime or relatively prime if they have no common factor other than In Mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of In Mathematics, a Binary relation R over a set X is transitive if whenever an element a is related to an element b In Mathematics, especially in Order theory, preorders are Binary relations that satisfy certain conditions In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Mathematics, especially Order theory, a strict weak ordering is a Binary relation S that is a strict partial order In Mathematics and Set theory, a total order, linear order, simple order, or (non-strict ordering is a Binary relation In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent" The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences 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-5

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Properties containing the reflexive property

Examples

Number of reflexive relations

References