Abstract Algebra/Equivalence relations and congruence classes

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

We often wish to describe how two mathematical entities within a set are related. For example, if we were to look at the set of all people on Earth, we could define "is a child of" as a relationship. Similarly, the \ge operator defines a relation on the set of integers. Formally speaking, a relation is a binary proposition defined on two elements of a set, and is generally written with an infix operator. We will write a \sim b for some a,b\in G and for some relation \sim.

However, there are very many types of relations. Indeed, further inspection of our earlier examples reveals that the two relations are quite different. In the case of the "is a child of" relationship, we observe that there are some people A,B where neither A is a child of B, nor B is a child of A. In the case of the \ge operator, we know that for any two integers m,n\in Z exactly one of m\ge n or n > m is true. In order to learn anything about relations, we must look at a smaller class of relations.

In particular, we care about the following properties of relations:

  • Reflexivity: a \sim a for all a\in G.
  • Symmetry: {a \sim b} \implies {b \sim a} for all a,b \in G.
  • Transitivity: { {a \sim b} \wedge {b \sim c} } \implies { a \sim c } for all a,b,c \in G.

One should note that in all three of these properties, we quantify across _all_ elements of the set.

A total order relation which exhibits the properties of reflexivity, symmetry and transitivity is called an equivalence relation. Two elements related under an equivalence relation are called equivalent.


Example: For a fixed integer p, we define a relation \sim_p on the set of integers such that a \sim_p b if and only if a − b = kp for some k \in Z. Prove that this defines an equivalence relation on the set of integers.

Proof:

  • Reflexivity: For any a\in G, it follows immediately that a − a = 0 = 0p, and thus a \sim_p a for all a\in G.
  • Symmetry: For any a,b \in G, assume that a \sim_p b. It must then be the case that a − b = kp for some integer k, and b − a = ( − k)p. Since k is an integer, − k must also be an integer. Thus, {a \sim_p b }\implies {b \sim_p a} for all a,b\in G.
  • Transivity: For any a,b,c\in G, assume that a \sim_p b and b \sim_p c. Then a − b = k1p and b − c = k2p for some integers k1,k2. By adding these two equalities togeter, we get {(a-b)+(b-c)=(k_1 p) + (k_2 p)} \Leftrightarrow {a-c = (k_1 + k_2) p}, and thus a \sim_p c

Q.E.D.

Remark. In elementary number theory we denote this relation a \equiv b (\text{mod } p) and say a is equivalent to b modulo p.


Congruence classes (sometimes called equivalence classes) are partitionings of a set according to an equivalence relation. In other words, for any element a\in G we define a subset \left[ a \right]\subseteq G as:

\left[ a \right] = \left \{ b \in G | a \sim b \right \}

Theorem: b \in \left[ a \right] \implies \left[ b \right] = \left[ a \right]

Proof: Assume b \in \left[ a \right]. Then, by construction a \sim b.

  • [\subseteq]: Let p be an arbitrary element of \left[ b \right]. Then p\sim b by construction of the equivalence class, and p\sim a by transitivity of equivalence relations. Thus, {p\in\left[b\right]}\implies {p\in\left[a\right]}, or that \left[b\right] \subseteq \left[a\right].
  • [\supseteq]: Let q be an arbitrary element of \left[ a \right]. Then, by construction q\sim a. By transitivity, q\sim b, so q\in\left[ b\right]. Thus, {q\in\left[a\right]}\implies {q\in\left[b\right]}, or that \left[a\right] \subseteq \left[b\right].

As \left[a\right] \subseteq \left[b\right] and as \left[b\right] \subseteq \left[a\right], it must be the case that \left[ b \right] = \left[ a \right].

Q.E.D. The text in its current form is incomplete.

Retrieved from "http://en.wikibooks.org/wiki/Abstract_Algebra/Equivalence_relations_and_congruence_classes"