Advanced Mathematics

3.3Equivalence Relations

Purpose of Section

To introduce the concept of an equivalence relation and show how it partitions a set into disjoint subsets. We also introduce the idea of the congruence of integers and modular arithmetic.

3.3.1 Introduction

As you well know every fraction has many equivalent forms. For example

are different ways to represent the same number. They may appear different and are called different names, but they are all equal. The idea of grouping things together that appear different, but from a certain perspective are the same which is the fundamental idea behind equivalence relations.

An equivalence relation is a relation that holds between two elements that relaxes the sometimes over‐restrictive “equals relation” and replaces it by “equals from a certain point of view.” This allows one to partition sets into groups called equivalence classes which share common properties. For example, we might say two integers as the same if they have the same remainder when divided by a certain number. For example, from some points of view, we may consider the integers … −5, −2, 1, 4, 7, … “equal” since they all have a remainder of +1 when divided by 3.

Definition

An equivalence relation on a set A, denoted by “≡” (or sometimes by “~”) is a relation on A such that for all x, y, z in A, it is reflexive, symmetric, and transitive. That is

• Reflexive: x