Equivalence relation: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Richard Pinch
m (→‎Examples: fix link)
imported>Peter Schmitt
m (fixing quickly some problems; but needs major editing)
Line 1: Line 1:
{{subpages}}
{{subpages}}
In [[mathematics]], an '''equivalence relation''' is a [[relation (mathematics)|relation]] between that formalises the intuitive notion that related objects have some property in common.  Examples include [[equality]] between numbers or other quantities; [[geometry|geometrical]] relations such as [[parallel]], [[congruence]], [[similarity]] or between-ness; abstract algebraic concepts such as [[isomorphism]] or [[homeomorphism]].  The equivalence may be expressed by [[formula]]e, geometric concepts or [[algorithm]]s, but in keeping with the modern definition of [[function (mathematics)|mathematics]], it is most convenient to identify an equvialence relation with the sets of objects for which it holds true.   
In [[mathematics]], an '''equivalence relation''' is a (binary) [[relation (mathematics)|relation]] between object that formalises the intuitive notion that related objects have some specific property in common.  Examples include [[equality]] between numbers or other quantities; [[geometry|geometrical]] relations such as [[parallel]], [[congruence]], [[similarity]]; abstract algebraic concepts such as [[isomorphism]].  The equivalence may be expressed by [[formula]]e, geometric concepts or [[algorithm]]s, but in keeping with the modern definition of [[function (mathematics)|mathematics]], it is most convenient to identify an equvialence relation with the sets of objects for which it holds true.   


A relation <math>\sim\,</math> on a set ''X'' is a equivalence relation if it satisfies the following three properties
A relation <math>\sim\,</math> on a set ''X'' is an equivalence relation if it satisfies the following three properties
* <math>\sim\,</math> is ''reflexive'':  <math>x \sim x\,</math> for all <math>x \in X</math>.
* <math>\sim\,</math> is ''reflexive'':  <math>x \sim x\,</math> for all <math>x \in X</math>.
* <math>\sim\,</math> is ''symmetric'':  <math>x\sim y \Leftrightarrow y \sim x</math>.
* <math>\sim\,</math> is ''symmetric'':  <math>x\sim y \Leftrightarrow y \sim x</math>.
Line 9: Line 9:
An '''equivalence class''' for <math>\sim\,</math> is the set of elements of ''X'' all related to some particular element
An '''equivalence class''' for <math>\sim\,</math> is the set of elements of ''X'' all related to some particular element
:<math>[x]_\sim = \{ y \in x : x \sim y \} . \,</math>
:<math>[x]_\sim = \{ y \in x : x \sim y \} . \,</math>
The equivalence classes for a [[partition]] of the set ''X'', that is, two classes <math>[x]_\sim</math> and <math>[y]_\sim</math> are either equal (have the same members), which is the case when <math>x \sim y\,</math>, or are [[disjoint sets|disjoint]] (have no members in common), which is the case when <math>x \not\sim y</math>.
The equivalence classes form a [[partition]] of the set ''X'', that is, two classes <math>[x]_\sim</math> and <math>[y]_\sim</math> are either equal (have the same members), which is the case when <math>x \sim y\,</math>, or are [[disjoint sets|disjoint]] (have no members in common), which is the case when <math>x \not\sim y</math>.


==Examples==
==Examples==

Revision as of 16:43, 14 October 2009

This article is developed but not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable, developed Main Article is subject to a disclaimer.

In mathematics, an equivalence relation is a (binary) relation between object that formalises the intuitive notion that related objects have some specific property in common. Examples include equality between numbers or other quantities; geometrical relations such as parallel, congruence, similarity; abstract algebraic concepts such as isomorphism. The equivalence may be expressed by formulae, geometric concepts or algorithms, but in keeping with the modern definition of mathematics, it is most convenient to identify an equvialence relation with the sets of objects for which it holds true.

A relation on a set X is an equivalence relation if it satisfies the following three properties

  • is reflexive: for all .
  • is symmetric: .
  • is transitive: .

An equivalence class for is the set of elements of X all related to some particular element

The equivalence classes form a partition of the set X, that is, two classes and are either equal (have the same members), which is the case when , or are disjoint (have no members in common), which is the case when .

Examples

  • On any set X, the identity relation . The equivalence classes are the singleton sets .
  • On any set X, the universal relation for all x,y. There is one equivalence class, X itself.
  • On the integers, parity: iff m,n have the same remainder on division by 2. There are two equivalence classes, "even" and "odd".
  • On the integers more generally, modular arithmetic operates on the equivalence classes defined by remainder on division by a fixed modulus M.
  • On lines in the plane, being parallel. The equivalence classes are the directions.
  • On triangles in the plane, being congruent.
  • On triangles in the plane, being similar.

Quotient classes

It will be seen in the examples that a common way of defining an equivalence relation is to state that elements have some common property. We can formalise this by saying that if f is a function defined on the set X, we define the relation by

This is an equivalence relation, the kernel of f. Every equivalence relation can be defined in this way for a suitable function f.