Partial equivalence relation
- Partial equivalence relation
In mathematics, a partial equivalence relation (often abbreviated as PER) "R" on a set "X" is a relation which is "symmetric" and "transitive". In other words, it holds for all a, b and c in X that:
# (Symmetry) if a R b then b R a
# (Transitivity) if a R b and b R c then a R c
If "R" is reflexive, then R is an equivalence relation. On the other hand, "R" could be taken as the empty relation, so that there are PERs that are not equivalence relations.
There is in fact a simple structure to the general PER "R" on "X": it is an equivalence relation on some subset "Y" of "X", such that in the complement of "Y" no element is related by "R" to any other. Concretely, let . By construction, is reflexive on and therefore an equivalence relation on . But if , then there is no for which "z R w"; if there were, then by symmetry we would have "w R z", which implies "z R z" by transitivity, contradicting .
Example
For an example of a PER, consider a set and a partial function that is defined on some elements of but not all. Then the relation defined by : "if and only if is defined at both and , and "is a partial equivalence relation but not an equivalence relation. It possesses the symmetry and transitivity properties, but it is not reflexive since if is not defined then -- in fact, for such an there is no such that . It follows immediately that the subset of for which is an equivalence relation is precisely the subset on which is defined.
Uses
PER's are used mainly in computer science, in type theory. It is also used in constructive mathematics to define setoids, sometimes called partial setoids. The action of forming one from a type and a PER is an analogue to the operations of subset and quotient in classical set-theoretic mathematics.
ee also
*Equivalence relation
*Binary relation
Wikimedia Foundation.
2010.
Look at other dictionaries:
Equivalence relation — In mathematics, an equivalence relation is a binary relation between two elements of a set which groups them together as being equivalent in some way. Let a , b , and c be arbitrary elements of some set X . Then a b or a ≡ b denotes that a is… … Wikipedia
Relation algebra — is different from relational algebra, a framework developed by Edgar Codd in 1970 for relational databases. In mathematics, a relation algebra is a residuated Boolean algebra supporting an involutary unary operation called converse. The… … Wikipedia
Relation (mathematics) — This article sets out the set theoretic notion of relation. For a more elementary point of view, see binary relations and triadic relations. : For a more combinatorial viewpoint, see theory of relations. In mathematics, especially set theory, and … Wikipedia
Partial isometry — In functional analysis a partial isometry is a linear map W between Hilbert spaces H and K such that the restriction of W to the orthogonal complement of its kernel is an isometry. We call the orthogonal complement of the kernel of W the initial… … Wikipedia
Binary relation — Relation (mathematics) redirects here. For a more general notion of relation, see Finitary relation. For a more combinatorial viewpoint, see Theory of relations. In mathematics, a binary relation on a set A is a collection of ordered pairs of… … Wikipedia
Equivalence of categories — In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are essentially the same . There are numerous examples of categorical equivalences… … Wikipedia
Partial differential equation — A visualisation of a solution to the heat equation on a two dimensional plane In mathematics, partial differential equations (PDE) are a type of differential equation, i.e., a relation involving an unknown function (or functions) of several… … Wikipedia
Transitive relation — In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b , and b is in turn related to an element c , then a is also related to c . Transitivity is a key property of both partial order… … Wikipedia
Inverse relation — In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation child of is the relation parent of . In formal… … Wikipedia
Reflexive relation — In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation on S where x x holds true for every x in S.[1] For example, could be is equal to . Contents 1 Related terms 2… … Wikipedia
