6 CHAPTER 1. SOME PREREQUISITE TOPICS

1.3 Equivalence RelationsThere are many ways to compare elements of a set other than to say two elements are equalor the same. For example, in the set of people let two people be equivalent if they have thesame weight. This would not be saying they were the same person, just that they weighthe same. Often such relations involve considering one characteristic of the elements of aset and then saying the two elements are equivalent if they are the same as far as the givencharacteristic is concerned.

Definition 1.3.1 Let S be a set. ∼ is an equivalence relation on S if it satisfies the followingaxioms.

1. x∼ x for all x ∈ S. (Reflexive)

2. If x∼ y then y∼ x. (Symmetric)

3. If x∼ y and y∼ z, then x∼ z. (Transitive)

Definition 1.3.2 [x] denotes the set of all elements of S which are equivalent to x and [x] iscalled the equivalence class determined by x or just the equivalence class of x.

With the above definition one can prove the following simple theorem.

Theorem 1.3.3 Let ∼ be an equivalence relation defined on a set, S and let H denote theset of equivalence classes. Then if [x] and [y] are two of these equivalence classes, eitherx∼ y and [x] = [y] or it is not true that x∼ y and [x]∩ [y] = /0.

Proof: If x ∼ y, then if z ∈ [y] , you have x ∼ y and y ∼ z so x ∼ z which shows that[y]⊆ [x]. Similarly, [x]⊆ [y]. If it is not the case that x∼ y, then there can be no intersectionof [x] and [y] because if z were in this intersection, then x∼ z,z∼ y so x∼ y. ■

1.4 Well Ordering and InductionMathematical induction and well ordering are two extremely important principles in math.They are often used to prove significant things which would be hard to prove otherwise.

Definition 1.4.1 A set is well ordered if every nonempty subset S, contains a smallest ele-ment z having the property that z≤ x for all x ∈ S.

Axiom 1.4.2 Any set of integers larger than a given number is well ordered.

In particular, the natural numbers defined as N≡{1,2, · · ·} is well ordered.The above axiom implies the principle of mathematical induction. The symbol Z de-

notes the set of all integers. Note that if a is an integer, then there are no integers betweena and a+1.

Theorem 1.4.3 (Mathematical induction) A set S ⊆ Z, having the property that a ∈ S andn+1 ∈ S whenever n ∈ S contains all integers x ∈ Z such that x≥ a.