7.4 PARTIAL ORDERINGS 251
- (a) (i) Calculate the set of all equivalence relations on the set S = (1, 2, 3,4).
(ii) Calculate the set of all partitions of S.
Let S be any finite set and denote by ER the set of all equivalence rela-
tions on S. Define a relation 5 on ER by the rule E, I E, if and only
if El G E,, where E and E, are arbitrary elements of ER. (We often
say that El is stronger than E, in this case.) Show that I is a partial
ordering on ER and describe the strongest and weakest elements of the
poset (ER, I).
Let S be any finite set and denote by PAR the set of all partitions of S.
Define a relation I on PAR by the rule P1 I P, if and only if every cell
in PI is a subset of some cell in P,. (We often say PI is a rejinement of
P, in that case.) Show that I is a partial ordering on PAR and describe
the smallest and largest elements of the poset (PAR, I).
Find a relationship between the statements El I E, [from (i)] and
(S/E ,) I (S/E,) [from (ii)].
- Let F be the set of all real-valued functions with domain a subset of R. Define
a relation I on F by the rule, f I g if and only if dom f G dom g and f(x) I g(x)
for all x E dom f, where f and g are arbitrary elements of F. (Note: Two functions
are to be regarded as equal if and only if they have the same domain and the same
function values over their common domain.)
(a) Prove that I is a partial ordering on F.
(b) Prove that I is not a total ordering on F.
(c) Given functions f, g E F, describe the function h that serves as f v g in the
poset (F, 5 ). Describe f A g.
