2.3. EQUIVALENCE RELATIONS 35

2.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 weighedthe 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 2.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 2.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 2.3.3 Let∼ be an equivalence class defined on a set, S and let H denote the setof equivalence classes. Then if [x] and [y] are two of these equivalence classes, either x∼ yand [x] = [y] or it is not true that x∼ y and [x]∩ [y] = /0.

2.4 Partially Ordered SetsDefinition 2.4.1 Let F be a nonempty set. F is called a partially ordered set if there is arelation, denoted here by ≤, such that

x≤ x for all x ∈F .

If x≤ y and y≤ z then x≤ z.

C ⊆F is said to be a chain if every two elements of C are related. This means that ifx,y ∈ C , then either x≤ y or y≤ x. Sometimes a chain is called a totally ordered set. C issaid to be a maximal chain if whenever D is a chain containing C , D = C .

The most common example of a partially ordered set is the power set of a given setwith ⊆ being the relation. It is also helpful to visualize partially ordered sets as trees. Twopoints on the tree are related if they are on the same branch of the tree and one is higherthan the other. Thus two points on different branches would not be related although theymight both be larger than some point on the trunk. You might think of many other thingswhich are best considered as partially ordered sets. Think of food for example. You mightfind it difficult to determine which of two favorite pies you like better although you maybe able to say very easily that you would prefer either pie to a dish of lard topped withwhipped cream and mustard. The following theorem is equivalent to the axiom of choice.For a discussion of this, see the appendix on the subject.