Description

The world is a hierarchy
Definitions/Important Concepts
Partition and Equivalence Classes
Equivalent: If R is an equivalence relation, a is equivalent to b if aRb.
Partition: A partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union Equivalence Class of a w.r.t R ([a]R): The set of all elements of A that are equivalent to a.
Ordering
Poset: A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S,R). Members of S are called elements of the poset.
Comparable: The elements a and b of a poset (S,⪯) are called comparable if either a ⪯ b or b ⪯ a.
Total Order: If (S,⪯) is a poset and every two elements of S are comparable, S is called a totally ordered or linearly ordered set, and ⪯ is called a total order or a linear order.
Maximal Element: An element of a poset that is not less than any other element of the poset.
Alternate: a is maximal in the poset (S,⪯) if ∄b ∈ S : a ≺ b.
Minimal Element: An element of a poset that is not greater than any other element of the poset.
Alternate: a is minimal in the poset (S,⪯) if ∄b ∈ S : b ≺ a.
Greatest Element: An element of a poset greater than all other elements in this set.
Alternate: a is the greatest element if ∀b ∈ A : b ⪯ a
Least Element: An element of a poset less than all other elements in this set.
Alternate:a is the least element if ∀b ∈ A : a ⪯ b
Upper Bound of a set: An element in a poset greater than all other elements in the set.
Alternate: Assume A ⊆ (S,⪯).u ∈ S is an upper bound of A if ∀a ∈ A : a ⪯ u
Lower Bound of a set: An element in a poset less than all other elements in the set.
Alternate: Assume A ⊆ (S,⪯).l ∈ S is a lower bound of A if ∀a ∈ A : l ⪯ u
Least Upper Bound of a set: An upper bound of the set that is less than all other upper bounds.
Greatest Lower Bound of a set: A lower bound of the set that is greater than all other lower bounds.
1
Questions
1. Justify that for an equivalence relation R for an equivalence class [c] ∀a,b ∈ [c](a,b) ∈ R, or every element in the equivalence class has relation with every element in the equivalence class
2. Determine the number of different equivalence relations on a set with three elements a,b,c by listing them.
3. Let us assume that F is a relation on the set R real numbers defined by xFy if and only if x − y is an integer. Prove that F is an equivalence relation on R.
(a) What is the equivalence class of 1 for this equivalence relation?
(b) What is the equivalence class of 1/2 for this equivalence relation?
4. Can you draw the Hasse diagram for the relation {(a,b) | a > b} on {1,2,3,4,6,8,12}? If not, then why?
5. Which of these relations(R) on {0,1,2,3} are partial orderings? Determine the properties of a partial ordering that the others lack.
1. {(0,0),(2,2),(3,3)}
b) {(0,0),(1,1),(2,0),(2,2),(2,3),(3,3)}
c) {(0,0),(1,1),(1,2),(2,2),(3,1),(3,3)}
d) {(0,0),(1,1),(1,2),(1,3),(2,0),(2,2),(2,3), (3,0),(3,3)}
e) {(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2), (1,3),(2,0),(2,2),(3,3)}
6. Is (S,R) a poset if S is the set of all people in the world and (a,b) ∈ R, where a and b are people, if a) a is no shorter than b ?
b) a weighs more than b ?
c) a = b or a is a descendant of b ?
d) a and b do not have a common friend?
7. Which of these are posets?
1. (Z,=) 2. (Z,∤)
8. Determine whether the relations represented by these zero-one matrices are partial orders. a.
 
1 0 0
0 1 0
 
1 0 1 b.
 
1 0 1 0
0 1 1 0
 
0 0 1 1
 
1 1 0 1
9. Determine whether relations with the following directed graph is a partial order.
(a)
(b)
(c)
(d)
10. EXAMPLE: Draw the Hasse diagram representing the partial ordering {(a,b) | a divides b} on {1,2,3,4,6,8,12}.
11. Prove that the greatest element is unique when it exists.
12. Prove the least element is unique when it exists.
13. Draw a Hasse Diagram for the following cases.
(a) Divisibility on the set {1,2,3,5,7,11,13}
(b) less than or equal to relation on {0,2,5,10,11,15}.
14. Answer these questions for the poset ({{1},{2},{4},{1,2},{1,4},{2,4},{3,4},{1,3,4},{2,3,4}},⊆).
(a) Draw a Hasse Diagram representing this poset.
(b) Find the maximal elements.
(c) Find the minimal elements.
(d) Is there a greatest element?
(e) Is there a least element?
(f) Find all upper bounds of {{2},{4}}.
(g) Find the least upper bound of {{2},{4}}, if it exists.
(h) Find all lower bounds of {{1,3,4},{2,3,4}}.
(i) Find the greatest lower bound of {{1,3,4},{2,3,4}}, if it exists
15. Let R be the relation on the set of all colorings of the 2 × 2 checkerboard where each of the four squares is colored either red or blue so that (C1 , C2 ), where C1 and C2 are 2 × 2 checkerboards with each of their four squares colored blue or red, belongs to R if and only if C2 can be obtained from C1 either by rotating the checkerboard or by rotating it and then reflecting it.
(a) Show that R is an equivalence relation.
(b) What are the equivalence classes of R?
16. Show that the partition of the set of bit strings of length 16 formed by equivalence classes of bit strings that agree on the last eight bits is a refinement of the partition formed from the equivalence classes of bit strings that agree on the last four bits.
Definition: A partition P1 is called a refinement of the partition P2 if every set in P1 is a subset of one of the sets in P2.