0.1 Discrete structures relation

Example 3: Taking this discrete structures course together this semester is another equivalence relation.

Equivalence relations can also be represented by a digraph since they are a binary relation on a set. For example the digraph of the equivalence relation congruent mod 3 on {0, 1, 2, 3, 4, 5 , 6} is as shown in Figure 9. It consists of three connected components.

Definition (equivalence class): For an equivalence relation R on a set A, the set of the elements of A that are related to an element, say a, of A is called the equivalence class of element a and it is denoted by [a].

Example 4: For the equivalence relation of hours on a clock, equivalence classes are

[1] = {1, 13, 25, ... } = {1+ 12n: n ∈N} ,

[2] = {2, 14, 26, ... } = {2+ 12n: n ∈N} ,

........,

where N is the set of natural numbers. There are altogether twelve of them.

For an equivalence relation R on a set A, every element of A is in an equivalence class. For if an element, say b, does not belong to the equivalence class of any other element in A, then the set consisting of the element b itself is an equivalence class. Thus the set A is in a sense covered by the equivalence classes. Another property of equivalence class is that equivalence classes of two elements of a set A are either disjoint or identical, that is either [a] = [b]or [a] ∩ [b]= ∅ for arbitrary elements a and b of A. Thus the set A is partitioned into equivalence classes by an equivalence relation on A. This is formally stated as a theorem below after the definition of partition.

Definition (partition): Let A be a set and let A1, A2, ..., An be subsets of A. Then {A1, A2, ..., An} is a partition of A, if and only if

(1) ${}_{i=1}^n$ Ai = A, and

(2) Ai ∩Aj = ∅, if Ai ≠ Aj , 1 ≤ i, j ≤ n .

(3) Example 5: Let A = {1, 2, 3, 4, 5}, A1 = {1, 5}, A2 = {3}, and A3 = {2, 4}. Then {A1, A2, A3} is a partition of A. However, B1 = {1, 2, 5}, B2 = {2, 3}, and B3 = {4} do not form a partition for A because B1 ∩B2 ≠∅, though B1 ≠B2.

Theorem 1: The set of equivalence classes of an equivalence relation on a set A is a partition of A.

Conversely, a partition of a set A determines an equivalence relation on A.

Theorem 2: Let {A1, ..., An} be a partition of a set A. Define a binary relation R on A as follows:<a, b>∈R if and only if a ∈Ai and b ∈Ai for some i, 1 ≤i ≤n . Then R is an equivalence relation.

Theorem 3: Let R1 and R2 be equivalence relations. Then R1 ∩R2 is an equivalence relation, but R1 ∪R2 is not necessarily an equivalence relation.

Order relation

Shoppers in a grocery store are served at a cashier on the first-come-first-served basis. When there are many people at cashiers, lines are formed. People in these lines are ordered for service: Those at the head of a line are served sooner than those at the end. Cars waiting for the signal to change at an intersection are also ordered similarly. Natural numbers can also be ordered in the increasing order of their magnitude. Those are just a few examples of order we encounter in our daily lives. The order relations we are going to study here are an abstraction of those relations. The properties common to orders we see in our daily lives have been extracted and are used to characterize the concepts of order. Here we are going to learn three types of order: partial order, total order, and quasi order.