9.12. Summary of Relational Properties 267
(c)What are the maximal and minimal elements? Are they maximum and mini-
mum?
(d)Answer the previous part for thepartial order on the setPf1;2;:::;6g ;.Homework Problems
Problem 9.14.
This problem asks for a proof of Lemma 9.7.2 showing that every weak partial
order can be represented by (is isomorphic to) a collection of sets partially ordered
under set inclusion (). Namely,
Lemma.Letbe a weak partial order on a set,A. For any elementa 2 A, let
L.a/WWDfb 2 Ajbag;
LWWDfL.a/ja 2 Ag:Then the function LWA!Lis an isomorphism from therelation onA, to the
subset relation onL.
(a)Prove that the function LWA!Lis a bijection.(b)Complete the proof by showing that
ab iff L.a/L.b/ (9.12)for alla;b 2 A.
Problems for Section 9.8
Practice Problems
Problem 9.15.
For each of the binary relations below, state whether it is a strict partial order, a
weak partial order, or neither. If it is not a partial order, indicate which of the
axioms for partial order it violates.
(a)The superset relation,on the power setPf1;2;3;4;5g.(b)The relation between any two nonegative integers,a,bthatab .mod8/.(c)The relation between propositional formulas,G,H, thatG IMPLIES H is
valid.
(d)The relation ’beats’ on Rock, Paper and Scissor (for those who don’t know the
game Rock, Paper, Scissors, Rock beats Scissors, Scissors beats Paper and Paper
beats Rock).