World Library  
Flag as Inappropriate
Email this Article

Partial equivalence relation

Article Id: WHEBN0003450320
Reproduction Date:

Title: Partial equivalence relation  
Author: World Heritage Encyclopedia
Language: English
Subject: Binary relation, Equivalence relation, Reference desk/Archives/Mathematics/2015 July 17, Mathematical relations, WikiProject Mathematics/List of mathematics articles (P)
Collection: Mathematical Relations
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Partial equivalence relation

In mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) R on a set X is a relation that is symmetric and transitive. In other words, it holds for all a, b, c \in X that:

  1. if a R b, then b R a (symmetry)
  2. if a R b and b R c, then a R c (transitivity)

If R is also reflexive, then R is an equivalence relation.

Contents

  • Properties and applications 1
  • Examples 2
    • Euclidean parallelism 2.1
    • Kernels of partial functions 2.2
    • Functions respecting equivalence relations 2.3
  • References 3
  • See also 4

Properties and applications

In a set-theoretic context, there is a simple structure to the general PER R on X: it is an equivalence relation on the subset Y = \{ x \in X | x\,R\,x\} \subseteq X. (Y is the subset of X such that in the complement of Y (X\setminus Y) no element is related by R to any other.) By construction, R is reflexive on Y and therefore an equivalence relation on Y. Notice that R is actually only true on elements of Y: if x R y, then y R x by symmetry, so x R x and y R y by transitivity. Conversely, given a subset Y of X, any equivalence relation on Y is automatically a PER on X.

PERs are therefore used mainly in computer science, type theory and constructive mathematics, particularly to define setoids, sometimes called partial setoids. The action of forming one from a type and a PER is analogous to the operations of subset and quotient in classical set-theoretic mathematics.

Every partial equivalence relation is a difunctional relation, but the converse does not hold.

The algebraic notion of congruence can also be generalized to partial equivalences, yielding the notion of subcongruence, i.e. a homomorphic relation that is symmetric and transitive, but not necessarily reflexive.[1]

Examples

A simple example of a PER that is not an equivalence relation is the empty relation R=\emptyset (unless X=\emptyset, in which case the empty relation is an equivalence relation (and is the only relation on X)).

Euclidean parallelism

In the Euclidean plane, two lines m and n are parallel lines when mn = ∅. The symmetry of this relation is obvious and the transitivity can be proven in the Euclidean plane, thus Euclidean parallelism is a partial equivalence relation. Nevertheless, mathematicians developing affine geometry prefer the facility of an equivalence relation and therefore sometimes revise the definition of parallelism to allow a line to be parallel to itself, making the new relation of "affine parallelism" that is a reflexive relation.

Kernels of partial functions

For another example of a PER, consider a set A and a partial function f that is defined on some elements of A but not all. Then the relation \approx defined by

x \approx y if and only if f is defined at x, f is defined at y, and f(x) = f(y)

is a partial equivalence relation but not an equivalence relation. It possesses the symmetry and transitivity properties, but it is not reflexive since if f(x) is not defined then x \not\approx x — in fact, for such an x there is no y \in A such that x \approx y. (It follows immediately that the subset of A for which \approx is an equivalence relation is precisely the subset on which f is defined.)

Functions respecting equivalence relations

Let X and Y be sets equipped with equivalence relations (or PERs) \approx_X, \approx_Y. For f,g : X \to Y, define f \approx g to mean:

\forall x_0 \; x_1, \quad x_0 \approx_X x_1 \Rightarrow f(x_0) \approx_Y g(x_1)

then f \approx f means that f induces a well-defined function of the quotients X / \approx_X \; \to \; Y / \approx_Y. Thus, the PER \approx captures both the idea of definedness on the quotients and of two functions inducing the same function on the quotient.

References

  1. ^ J. Lambek (1996). "The Butterfly and the Serpent". In Aldo Ursini, Paulo Agliano. Logic and Algebra. CRC Press. pp. 161–180.  
  • Mitchell, John C. Foundations of programming languages. MIT Press, 1996.
  • D.S. Scott. "Data types as lattices". SIAM Journ. Comput., 3:523-587, 1976.

See also

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.