Bridge to Abstract Mathematics: Mathematical Proof and Structures

7.4 PARTIAL ORDERINGS 245

(g) The equivalence relation - on R defined in Exercise 5(b), Article 7.2
(h) The equivalence relation z on R defined in Exercise 5(c), Article 7.2
(i) The equivalence relation - on R defined in Exercise qa), Article 7.2
*(j) The equivalence relation - on F (where F is the set of all real-valued func-
tions with domain R) defined in Exercise qb), Article 7.2
(k) The equivalence relation - on Z x (Z - (0)) defined in Exercise 7, Article 7.2

4. Let E be an equivalence relation on a set A. For each x E A, let [x] represent
   the equivalence class determined by x; that is, [x] = {y E AIx E y>. Prove:
   (a) x E [XI for all x E A
   (b) For all x, y E A, y E [XI o x E y
   *(c) For all x, y E A, [x] = [y] t> x E y


5. Prove (b) of Theorem 3: If 9 is a partition of a set A, then A/(A/9) = 9.


6. Prove that if El and E, are both equivalence relations on a set A, then El n E,
   is an equivalence relation on A. How is the partition A/(E, n E,) related to the
   partitions A/E, and A/E,? Is the union El u E, of two equivalence relations on
   A necessarily an equivalence relation on A?

7.4 Partial Orderings

The notion of partial ordering on a set A is a generalization of the rela-

tion "less than or equal to" on real numbers. You should review your

answer to Exercise 4, Article 7.1, in reference to the relation Rll = ((m, n) (

m I n) on 2. On that basis, the following definition should come as no

surprise.

DEFINITION 1

Let A be a set and R a relation on A. We say that R is a partial ordering on A if

and only if R is reflexive on A, antisymmetric, and transitive. A nonempty set A,

together with a partial ordering Ron A, is often referred to as a partially ordered

set or poset.

Clearly I is an example of a partial ordering on R. It is reflexive since

every real number is less than or equal to itself. It is antisymmetric since

the only way we can have both x I y and y 5 x is if x = y. It is transitive

since, for any real numbers x, y, and z, if x I y and y <_ z, then x 4 z.

Since _< is the prototype for a partial ordering, it is not uncommon to

denote generic partial orderings by the symbol 5 rather than by a letter.

We will often follow that convention and will sometimes use symbols I,,

I 2, and so on to denote specific examples of partial orderings.

A poset consists of two things, a nonempty set A @ a partial ordering

s on A. Often we will identify a poset by notation such as (A, s). Oc-

casionally, when there is no danger of confusion about the partial ordering,

we may refer simply to the poset A.