Abstract Algebra/Equivalence relations and congruence classes

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 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 and so that, for a relation , . In this case, is referred to as the domain of the relation and is referred to as its codomain. If an ordered pair is an element of (where, by the definition of , and ), then we say that is related to by . We will use to denote the set

.

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

Equivalence relations

edit

To denote that two elements   and   are related for a relation   which is a subset of some Cartesian product  , we will use an infix operator. We write   for some   and  .

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   operator, we know that for any two integers   exactly one of   or   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   is reflexive if   for all  .
  • Symmetry: A relation   is symmetric if   for all  .
  • Transitivity: A relation   is transitive if   for all  .

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

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

Example: For a fixed integer  , we define a relation   on the set of integers such that   if and only if   for some  . Prove that this defines an equivalence relation on the set of integers.

Proof:

  • Reflexivity: For any  , it follows immediately that  , and thus   for all  .
  • Symmetry: For any  , assume that  . It must then be the case that   for some integer  , and  . Since   is an integer,   must also be an integer. Thus,   for all  .
  • Transitivity: For any  , assume that   and  . Then   and   for some integers  . By adding these two equalities together, we get  , and thus  .

Q.E.D.

Remark. In elementary number theory we denote this relation   and say a is equivalent to b modulo p.

Equivalence classes

edit

Let   be an equivalence relation on  . Then, for any element   we define the equivalence class of   as the subset   given by

 

Theorem:  

Proof: Assume  . Then by definition,  .

  • We first prove that  . Let   be an arbitrary element of  . Then   by definition of the equivalence class, and   by transitivity of equivalence relations. Thus,   and  .
  • We now prove that   Let   be an arbitrary element of  . Then, by definition  . By transitivity,  , so  . Thus,   and  .

As   and as  , we have  .

Q.E.D.

Partitions of a set

edit

A partition of a set   is a disjoint family of sets  ,  , such that  .

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

Proof: (Equivalence relation induces Partition): Let   be the set of equivalence classes of  . Then, since   for each  ,  . Furthermore, by the above theorem, this union is disjoint. Thus the set of equivalence relations of   is a partition of  .

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

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

Q.E.D.

Quotients

edit

Let   be an equivalence relation on a set  . Then, define the set   as the set of all equivalence classes of  . 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 much attention throughout the book.