Chapter 9 Directed graphs & Partial Orders364
Problem 9.36.
Prove that ifRis a partial order, then so isR ^1.
Problem 9.37.
Indicate which of the following relations below are equivalence relations, (E), strict
partial orders (St), weak partial orders (W). For the partial orders, also indicate
whether it islinear(L).
If a relation is none of the above, indicate whether it is
transitive(T), symmetric(Sym), asymmetric(A).
(a)The relationaDbC 1 between integers,a,b,
(b)The superset relation,on the power set of the integers.(c)The relation ExŒRç <ExŒSçbetween real-valued random variablesR;S.(d)The relation PrŒRDSçD 1 between real-valued random variablesR;S.(e)The empty relation on the set of rationals.(f)The identity relation IdZon the set of integers.(g)The divides relation on the nonnegative integers,N.(h)The divides relation on the integers,Z(i)The divides relation on the positive powers of 4.(j)The relatively prime relation on the nonnegative integers.(k)The less-than,<, relation on real-valued functions,f.x/,of the formf.x/DaxCbfor constantsa;b 2 R.
(l)The relation “has the same prime factors” on the integers.For the next parts, letf;gbe nonnegative functions from the integers to the real
numbers.
(m)The “Big Oh” relation,f DO.g/,
(n)The “Little Oh” relation,f Do.g/,(o)The “asymptotically equal” relation,fg.