Jump to content

Equivalence class: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
top: linking "congruence" and unlinking "equivalence relation" (linked in the text)
m Fixed punctuation
Line 26: Line 26:


==Examples==
==Examples==
* If {{mvar|X}} is the set of all cars, and {{math|~}} is the equivalence relation "has the same color as." then one particular equivalence class consists of all green cars. {{math|''X''/~}} could be naturally identified with the set of all car colors ([[cardinality]] of {{math|''X''/~}} would be the number of all car colors).
* If {{mvar|X}} is the set of all cars, and {{math|~}} is the equivalence relation "has the same color as", then one particular equivalence class consists of all green cars. {{math|''X''/~}} could be naturally identified with the set of all car colors ([[cardinality]] of {{math|''X''/~}} would be the number of all car colors).
* Let {{mvar|X}} be the set of all rectangles in a plane, and {{math|~}} the equivalence relation "has the same area as". For each positive real number ''A'' there will be an equivalence class of all the rectangles that have area ''A''.<ref>{{harvnb|Avelsgaard|1989|loc=p. 127}}</ref>
* Let {{mvar|X}} be the set of all rectangles in a plane, and {{math|~}} the equivalence relation "has the same area as". For each positive real number ''A'' there will be an equivalence class of all the rectangles that have area ''A''.<ref>{{harvnb|Avelsgaard|1989|loc=p. 127}}</ref>
* Consider the [[modular arithmetic|modulo]] 2 equivalence relation on the set {{math|'''Z'''}} of [[integer]]s: {{math|''x'' ~ ''y''}} if and only if their difference {{math|''x'' &minus; ''y''}} is an [[even number]]. This relation gives rise to exactly two equivalence classes: one class consisting of all even numbers, and the other consisting of all odd numbers. Under this relation {{math|[7]}}, {{math|[9]}}, and {{math|[1]}} all represent the same element of {{math|'''Z'''/~}}.<ref>{{harvnb|Devlin|2004|loc=p. 123}}</ref>
* Consider the [[modular arithmetic|modulo]] 2 equivalence relation on the set {{math|'''Z'''}} of [[integer]]s: {{math|''x'' ~ ''y''}} if and only if their difference {{math|''x'' &minus; ''y''}} is an [[even number]]. This relation gives rise to exactly two equivalence classes: one class consisting of all even numbers, and the other consisting of all odd numbers. Under this relation {{math|[7]}}, {{math|[9]}}, and {{math|[1]}} all represent the same element of {{math|'''Z'''/~}}.<ref>{{harvnb|Devlin|2004|loc=p. 123}}</ref>

Revision as of 10:36, 16 December 2015

Congruence is an example of an equivalence relation. The two triangles on the left are congruent triangles, while the third and fourth triangles are not congruent to any other triangle. Thus, the first two triangles are in the same equivalence class, while the third and fourth triangles are each in their own equivalence class.

In mathematics, when a set has an equivalence relation defined on its elements, there is a natural grouping of elements that are related to one another, forming what are called equivalence classes. Notationally, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a. It follows from the definition of the equivalence relations that the equivalence classes form a partition of X. The set of equivalence classes is sometimes called the quotient set or the quotient space of X by ~ and is denoted by X / ~.

When X has some structure, and the equivalence relation is defined with some connection to this structure, the quotient set often inherits some related structure. Examples include quotient spaces in linear algebra, quotient spaces in topology, quotient groups, homogeneous spaces, quotient rings, quotient monoids, and quotient categories.

Notation and formal definition

An equivalence relation is a binary relation ~ satisfying three properties:[1]

  • For every element a in X, a ~ a (reflexivity),
  • For every two elements a and b in X, if a ~ b, then b ~ a (symmetry)
  • For every three elements a, b, and c in X, if a ~ b and b ~ c, then a ~ c (transitivity).

The equivalence class of an element a is denoted [a] and is defined as the set

of elements that are related to a by ~. An alternative notation [a]R can be used to denote the equivalence class of the element a, specifically with respect to the equivalence relation R. This is said to be the R-equivalence class of a.

The set of all equivalence classes in X with respect to an equivalence relation R is denoted as X/R and called X modulo R (or the quotient set of X by R).[2] The surjective map from X onto X/R, which maps each element to its equivalence class, is called the canonical surjection or the canonical projection map.

When an element is chosen (often implicitly) in each equivalence class, this defines an injective map called a section. If this section is denoted by s, one has [s(c)] = c for every equivalence class c. The element s(c) is called a representative of c. Any element of a class may be chosen as a representative of the class, by choosing the section appropriately.

Sometimes, there is a section that is more "natural" than the other ones. In this case, the representatives are called canonical representatives. For example, in modular arithmetic, consider the equivalence relation on the integers defined by a ~ b if ab is a multiple of a given integer n, called the modulus. Each class contains a unique non-negative integer smaller than n, and these integers are the canonical representatives. The class and its representative are more or less identified, as is witnessed by the fact that the notation a mod n may denote either the class or its canonical representative (which is the remainder of the division of a by n).

Examples

  • If X is the set of all cars, and ~ is the equivalence relation "has the same color as", then one particular equivalence class consists of all green cars. X/~ could be naturally identified with the set of all car colors (cardinality of X/~ would be the number of all car colors).
  • Let X be the set of all rectangles in a plane, and ~ the equivalence relation "has the same area as". For each positive real number A there will be an equivalence class of all the rectangles that have area A.[3]
  • Consider the modulo 2 equivalence relation on the set Z of integers: x ~ y if and only if their difference xy is an even number. This relation gives rise to exactly two equivalence classes: one class consisting of all even numbers, and the other consisting of all odd numbers. Under this relation [7], [9], and [1] all represent the same element of Z/~.[4]
  • Let X be the set of ordered pairs of integers (a,b) with b not zero, and define an equivalence relation ~ on X according to which (a,b) ~ (c,d) if and only if ad = bc. Then the equivalence class of the pair (a,b) can be identified with the rational number a/b, and this equivalence relation and its equivalence classes can be used to give a formal definition of the set of rational numbers.[5] The same construction can be generalized to the field of fractions of any integral domain.
  • If X consists of all the lines in, say the Euclidean plane, and L ~ M means that L and M are parallel lines, then the set of lines that are parallel to each other form an equivalence class as long as a line is considered parallel to itself. In this situation, each equivalence class determines a point at infinity.

Properties

Every element x of X is a member of the equivalence class [x]. Every two equivalence classes [x] and [y] are either equal or disjoint. Therefore, the set of all equivalence classes of X forms a partition of X: every element of X belongs to one and only one equivalence class.[6] Conversely every partition of X comes from an equivalence relation in this way, according to which x ~ y if and only if x and y belong to the same set of the partition.[7]

It follows from the properties of an equivalence relation that

x ~ y if and only if [x] = [y].

In other words, if ~ is an equivalence relation on a set X, and x and y are two elements of X, then these statements are equivalent:

Graphical representation

Any binary relation can be represented by a directed graph and symmetric ones, such as equivalence relations, by undirected graphs. If ~ is an equivalence relation on a set X, let the vertices of the graph be the elements of X and join vertices s and t if and only if s ~ t. The equivalence classes are represented in this graph by the maximal cliques forming the connected components of the graph.[8]

Invariants

If ~ is an equivalence relation on X, and P(x) is a property of elements of X such that whenever x ~ y, P(x) is true if P(y) is true, then the property P is said to be an invariant of ~, or well-defined under the relation ~.

A frequent particular case occurs when f is a function from X to another set Y; if f(x1) = f(x2) whenever x1 ~ x2, then f is said to be a morphism for ~, a class invariant under ~, or simply invariant under ~. This occurs, e.g. in the character theory of finite groups. Some authors use "compatible with ~" or just "respects ~" instead of "invariant under ~".

Any function f : XY itself defines an equivalence relation on X according to which x1 ~ x2 if and only if f(x1) = f(x2). The equivalence class of x is the set of all elements in X which get mapped to f(x), i.e. the class [x] is the inverse image of f(x). This equivalence relation is known as the kernel of f.

More generally, a function may map equivalent arguments (under an equivalence relation ~X on X) to equivalent values (under an equivalence relation ~Y on Y). Such a function is known as a morphism from ~X to ~Y.

Quotient space in topology

In topology, a quotient space is a topological space formed on the set of equivalence classes of an equivalence relation on a topological space using the original space's topology to create the topology on the set of equivalence classes.

In abstract algebra, congruence relations on the underlying set of an algebra allow the algebra to induce an algebra on the equivalence classes of the relation, called a quotient algebra. In linear algebra, a quotient space is a vector space formed by taking a quotient group where the quotient homomorphism is a linear map. By extension, in abstract algebra, the term quotient space may be used for quotient modules, quotient rings, quotient groups, or any quotient algebra. However, the use of the term for the more general cases can as often be by analogy with the orbits of a group action.

The orbits of a group action on a set may be called the quotient space of the action on the set, particularly when the orbits of the group action are the right cosets of a subgroup of a group, which arise from the action of the subgroup on the group by left translations, or respectively the left cosets as orbits under right translation.

A normal subgroup of a topological group, acting on the group by translation action, is a quotient space in the senses of topology, abstract algebra, and group actions simultaneously.

Although the term can be used for any equivalence relation's set of equivalence classes, possibly with further structure, the intent of using the term is generally to compare that type of equivalence relation on a set X either to an equivalence relation that induces some structure on the set of equivalence classes from a structure of the same kind on X, or to the orbits of a group action. Both the sense of a structure preserved by an equivalence relation and the study of invariants under group actions lead to the definition of invariants of equivalence relations given above.

See also

Notes

  1. ^ Devlin 2004, p. 122
  2. ^ Wolf 1998, p. 178
  3. ^ Avelsgaard 1989, p. 127
  4. ^ Devlin 2004, p. 123
  5. ^ Maddox 2002, pp. 77–78
  6. ^ Maddox 2002, p.74, Thm. 2.5.15
  7. ^ Avelsgaard 1989, p.132, Thm. 3.16
  8. ^ Devlin 2004, p. 123

References

  • Avelsgaard, Carol (1989), Foundations for Advanced Mathematics, Scott Foresman, ISBN 0-673-38152-8
  • Devlin, Keith (2004), Sets, Functions, and Logic: An Introduction to Abstract Mathematics (3rd ed.), Chapman & Hall/ CRC Press, ISBN 978-1-58488-449-1
  • Maddox, Randall B. (2002), Mathematical Thinking and Writing, Harcourt/ Academic Press, ISBN 0-12-464976-9
  • Morash, Ronald P. (1987), Bridge to Abstract Mathematics, Random House, ISBN 0-394-35429-X
  • Wolf, Robert S. (1998), Proof, Logic and Conjecture: A Mathematician's Toolbox, Freeman, ISBN 978-0-7167-3050-7

Further reading

This material is basic and can be found in any text dealing with the fundamentals of proof technique, such as any of the following:

  • Sundstrom (2003), Mathematical Reasoning: Writing and Proof, Prentice-Hall
  • Smith; Eggen; St.Andre (2006), A Transition to Advanced Mathematics (6th Ed.), Thomson (Brooks/Cole)
  • Schumacher, Carol (1996), Chapter Zero: Fundamental Notions of Abstract Mathematics, Addison-Wesley, ISBN 0-201-82653-4
  • O'Leary (2003), The Structure of Proof: With Logic and Set Theory, Prentice-Hall
  • Lay (2001), Analysis with an introduction to proof, Prentice Hall
  • Gilbert; Vanstone (2005), An Introduction to Mathematical Thinking, Pearson Prentice-Hall
  • Fletcher; Patty, Foundations of Higher Mathematics, PWS-Kent
  • Iglewicz; Stoyle, An Introduction to Mathematical Reasoning, MacMillan
  • D'Angelo; West (2000), Mathematical Thinking: Problem Solving and Proofs, Prentice Hall
  • Cupillari, The Nuts and Bolts of Proofs, Wadsworth
  • Bond, Introduction to Abstract Mathematics, Brooks/Cole
  • Barnier; Feldman (2000), Introduction to Advanced Mathematics, Prentice Hall
  • Ash, A Primer of Abstract Mathematics, MAA