Abstract Algebra/Equivalence relations and congruence classes

From Wikibooks, open books for an open world
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. A binary relation, hereafter referred to simply as a relation, is a binary proposition defined on any selection of the elements of two sets.

Formally, a relation is any arbitrary subset of the Cartesian product between two sets X and Y so that, for a relation R, R \subseteq X \times Y. In this case, X is referred to as the domain of the relation and Y is referred to as its codomain. If an ordered pair (x, y) is an element of R (where, by the definition of R, x \in X and y \in Y), then we say that x is related to y by R. We will use R(x) to denote the set

\{y \in Y:(x, y) \in R\}.

In other words, R(x) is used to denote the set of all elements in the codomain of R to which some x in the domain in related.

Equivalence relations[edit]

To denote that two elements x and y are related for a relation R which is a subset of some Cartesian product X \times X, we will use an infix operator. We write x \sim y for some x,y\in X and (x, y) \in R.

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 about relations, we must look at a smaller class of relations.

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

  • Reflexivity: A relation R \subseteq X \times X is reflexive if a \sim a for all a\in X.
  • Symmetry: A relation R \subseteq X \times X is symmetric if {a \sim b} \implies {b \sim a} for all a,b \in X.
  • Transitivity: A relation R \subseteq X \times X is transitive if { {a \sim b} \wedge {b \sim c} } \implies { a \sim c } for all a,b,c \in X.

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

Any relation R \subseteq X \times X which exhibits the properties of reflexivity, symmetry and transitivity is called an equivalence relation on X. Two elements related by an equivalence relation are called equivalent under the equivalence relation. We write a \sim_R b to denote that a and b are equivalent under R. If only one equivalence relation is under consideration, we can instead write simply a \sim b. As a notational convenience, we can simply say that \sim is an equivalence relation on a set X and let the rest be implied.


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 = k p for some k \in Z. Prove that this defines an equivalence relation on the set of integers.

Proof:

  • Reflexivity: For any a\in X, it follows immediately that a-a=0=0 p, and thus a \sim_p a for all a\in G.
  • Symmetry: For any a,b \in X, assume that a \sim_p b. It must then be the case that a-b=k p 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.
  • Transitivity: For any a,b,c\in X, assume that a \sim_p b and b \sim_p c. Then a-b=k_1 p and b-c=k_2 p for some integers k_1,k_2. By adding these two equalities together, 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.

Equivalence classes[edit]

Let \sim be an equivalence relation on X. Then, for any element a\in X we define the equivalence class of a as the subset \left[ a \right]\subseteq X given by

\left[ a \right] = \left \{ b \in X | 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 definition, a \sim b.

  • We first prove that \left[b\right] \subseteq \left[a\right]. Let p be an arbitrary element of \left[ b \right]. Then p\sim b by definition 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]} and \left[b\right] \subseteq \left[a\right].
  • We now prove that \left[a\right] \subseteq \left[b\right] Let q be an arbitrary element of \left[ a \right]. Then, by definition 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]} and \left[a\right] \subseteq \left[b\right].

As \left[a\right] \subseteq \left[b\right] and as \left[b\right] \subseteq \left[a\right], we have \left[ b \right] = \left[ a \right].

Q.E.D.

Partitions of a set[edit]

A partition of a set X is a disjoint family of sets X_i, i\in I, such that \bigcup_{i\in I} X_i = X.

Theorem: An equivalence relation \sim on X induces a unique partition of X, and likewise, a partition induces a unique equivalence relation on X, such that these are equivalent.

Proof: (Equivalence relation induces Partition): Let P be the set of equivalence classes of \sim. Then, since a\in [a] for each a\in X, \cup P = X. Furthermore, by the above theorem, this union is disjoint. Thus the set of equivalence relations of \sim is a partition of X.

(Partition induces Equivalence relation): Let X_i\,,\,i\in I be a partition of X. Then, define \sim on X such that a\sim b if and only if both a and b are elements of the same X_i for some i\in I. Reflexivity and symmetry of \sim is immediate. For transitivity, if a,b\in X_i and b,c\in X_i for the same i\in I, we neccesarily have a,c\in X_i, and transitivity follows. Thus, \sim is an equivalence relation with X_i\,,\, i\in I as the equivalence classes.

Lastly obtaining a partition P from \sim on X and then obtaining an equivalence equation from P obviously returns \sim again, so \sim and P are equivalent structures.

Q.E.D.

Quotients[edit]

Let \sim be an equivalence relation on a set X. Then, define the set X/\sim as the set of all equivalence classes of X. In order to say anything interesting about this construction we need more theory yet to be developed. However, this is one of the most important constructions we have, and one that will be given the much attention throughout the book.