HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
''R'' on a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
''X'' is reflexive if it relates every element of ''X'' to itself. An example of a reflexive relation is the relation " is equal to" on the set of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, since every real number is equal to itself. A reflexive relation is said to have the reflexive property or is said to possess reflexivity. Along with
symmetry Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
and transitivity, reflexivity is one of three properties defining
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relation ...
s.


Definitions

Let R be a binary relation on a set X, which by definition is just a subset of X \times X. For any x, y \in X, the notation x R y means that (x, y) \in R while "not x R y" means that (x, y) \not\in R. The relation R is called if x R x for every x \in X or equivalently, if \operatorname_X \subseteq R where \operatorname_X := \ denotes the
identity relation In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
on X. The of R is the union R \cup \operatorname_X, which can equivalently be defined as the smallest (with respect to \subseteq) reflexive relation on X that is a
superset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of R. A relation R is reflexive if and only if it is equal to its reflexive closure. The or of R is the smallest (with respect to \subseteq) relation on X that has the same reflexive closure as R. It is equal to R \setminus \operatorname_X = \. The irreflexive kernel of R can, in a sense, be seen as a construction that is the "opposite" of the reflexive closure of R. For example, the reflexive closure of the canonical strict inequality < on the reals \mathbb is the usual non-strict inequality \leq whereas the reflexive reduction of \leq is <.


Related definitions

There are several definitions related to the reflexive property. The relation R is called: ;, or : If it does not relate any element to itself; that is, if not x R x for every x \in X. A relation is irreflexive
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
its
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
in X \times X is reflexive. An
asymmetric relation In mathematics, an asymmetric relation is a binary relation R on a set X where for all a, b \in X, if a is related to b then b is ''not'' related to a. Formal definition A binary relation on X is any subset R of X \times X. Given a, b \in X, ...
is necessarily irreflexive. A transitive and irreflexive relation is necessarily asymmetric. ;: If whenever x, y \in X are such that x R y, then necessarily x R x.Th
Encyclopedia Britannica
calls this property quasi-reflexivity.
;: If whenever x, y \in X are such that x R y, then necessarily y R y. ;: If every element that is part of some relation is related to itself. Explicitly, this means that whenever x, y \in X are such that x R y, then necessarily x R x y R y. Equivalently, a binary relation is quasi-reflexive if and only if it is both left quasi-reflexive and right quasi-reflexive. A relation R is quasi-reflexive if and only if its
symmetric closure In mathematics, the symmetric closure of a binary relation R on a set X is the smallest symmetric relation on X that contains R. For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the ...
R \cup R^ is left (or right) quasi-reflexive. ; Antisymmetric: If whenever x, y \in X are such that x R y \text y R x, then necessarily x = y. ;: If whenever x, y \in X are such that x R y, then necessarily x = y. A relation R is coreflexive if and only if its symmetric closure is anti-symmetric. A reflexive relation on a nonempty set X can neither be irreflexive, nor asymmetric (R is called if x R y implies not y R x), nor
antitransitive In mathematics, intransitivity (sometimes called nontransitivity) is a property of binary relations that are not transitive relations. This may include any relation that is not transitive, or the stronger property of antitransitivity, which descri ...
(R is if x R y \text y R z implies not x R z).


Examples

Examples of reflexive relations include: * "is equal to" (
equality Equality may refer to: Society * Political equality, in which all members of a society are of equal standing ** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elite ...
) * "is a
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of" (set inclusion) * "divides" (
divisibility In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
) * "is greater than or equal to" * "is less than or equal to" Examples of irreflexive relations include: * "is not equal to" * "is
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to" on the integers larger than 1 * "is a proper subset of" * "is greater than" * "is less than" An example of an irreflexive relation, which means that it does not relate any element to itself, is the "greater than" relation (x > y) on the
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s. 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 (that is, 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 number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because \begin -2 \cdot 2 &= -4 \\ 0 \cdot 2 &= 0 \\ 41 ...
s, irreflexive on the set of odd numbers, and neither reflexive nor irreflexive on the set of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s. An example of a quasi-reflexive relation R is "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. An example of a left quasi-reflexive relation is a left
Euclidean relation In mathematics, Euclidean relations are a class of binary relations that formalize " Axiom 1" in Euclid's ''Elements'': "Magnitudes which are equal to the same are equal to each other." Definition A binary relation ''R'' on a set ''X'' is Eucl ...
, which is always left quasi-reflexive but not necessarily right quasi-reflexive, and thus not necessarily quasi-reflexive. An example of a coreflexive relation is the relation on
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s in which each odd number is related to itself and there are no other relations. The equality relation is the only example of a both reflexive and coreflexive relation, and any coreflexive relation is a subset of the identity relation. The union of a coreflexive relation and a transitive relation on the same set is always transitive.


Number of reflexive relations

The number of reflexive relations on an n-element set is 2^.


Philosophical logic

Authors in
philosophical logic Understood in a narrow sense, philosophical logic is the area of logic that studies the application of logical methods to philosophical problems, often in the form of extended logical systems like modal logic. Some theorists conceive philosophical ...
often use different terminology. Reflexive relations in the mathematical sense are called totally reflexive in philosophical logic, and quasi-reflexive relations are called reflexive. Here: p.187


Notes


References

* Levy, A. (1979) ''Basic Set Theory'', Perspectives in Mathematical Logic, Springer-Verlag. Reprinted 2002, Dover. * Lidl, R. and Pilz, G. (1998). ''Applied abstract algebra'',
Undergraduate Texts in Mathematics Undergraduate Texts in Mathematics (UTM) (ISSN 0172-6056) is a series of undergraduate-level textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are small yellow boo ...
, Springer-Verlag. * Quine, W. V. (1951). ''Mathematical Logic'', Revised Edition. Reprinted 2003, Harvard University Press. * Gunther Schmidt, 2010. ''Relational Mathematics''. Cambridge University Press, .


External links

* {{springer, title=Reflexivity, id=p/r080590 Binary relations