MAM1019H Tutorial 7 Semester 2 2023 Solutions
1. Let (P, ≤P ), (Q, ≤Q ) and (S, ≤S ) be partially ordered sets. Suppose f : P → Q and
g : Q → S are functions.
(a) Prove or disprove: If f and g are order-preserving, then there is an order-preserving
map from P to S.
(b) Repeat (a) by replacing “order-preserving” with “order-embedding”. Then do the
same for “order isomorphism”.
(c) Prove or disprove: If f is an order-embedding, then f is injective.
(d) Prove that if f is an order isomorphism, then f −1 is an order isomorphism.
(a) Let x, y ∈ P . Suppose x ≤P y. Since f is order preserving, f (x) ≤Q f (y). Since
g is order preserving, g(f (x)) ≤S g(f (y)). Thus g◦f : P → S is and order-preserving
map.
(b) Similarly the statements are true.
(c) Suppose f : P → Q is an order-embedding. Take x, y ∈ P such that f (x) = f (y).
By reflexivity, this means f (x) ≤Q f (y) and f (y) ≤Q f (x). Since f is an order-
embedding, these statements imply x ≤P y and y ≤P f . Again, by anti-symmetry,
we have x = y. Thus f is injective.
(d) Suppose f : P → Q is an order isomorphism. Then f is bijective and so f −1
exists and is also bijective. It remains to show that f −1 is an order-embedding. Take
a, b ∈ Q. Suppose that a ≤Q b. Since f is surjective, we have x, y ∈ P such that
f (x) = a and f (b) = y. It follows from a ≤Q b that f (x) ≤Q f (y). Since f is an
order isomorphism, we have x ≤P y. But x = f −1 (a) and y = f −1 (b). So this means
f −1 (a) ≤P f −1 (b). Now take a, b ∈ Q and suppose that f −1 (a) ≤P f −1 (b). Since
f is an order isomorphism, we then have f (f −1 (a)) ≤Q f (f −1 (b)). That is, a ≤Q b.
Thus f −1 is an order isomorphism.
2. Prove that the relation of being order isomorphic is an equivalence relation.
1
Let (P, ≤P ), (Q, ≤Q ) and (S, ≤S ) be partially ordered sets.
(i) Reflexivity: The map f : P → P defined by f (x) = x is an order isomorphism.
(Work through the details yourself) Thus P ∼
= P.
(ii) Symmetry: Suppose P ∼ = Q, then there is an order isomorphism f : P → Q.
By the previous question, f −1 : Q → P is an order isomorphism. Thus Q ∼
= P.
(iii) Transitivity: Suppose P ∼
= Q and Q ∼
= S. Then there exist order isomorphisms
f : P → Q and g : Q → S. As seen in Question 1, there is then an order
isomorphism gf : P → S. Thus P ∼
= S.
Therefore ∼
= is an equivalence relation on partially ordered sets.
3. Let (P, ≤) and (Q, ⪯) be partially ordered sets with order isomorphism f : P → Q.
(a) Prove that if P has a maximum element, then does Q.
(b) Is it true that if Q has a maximum element, then so does P ?
(a) Suppose P has a maximum element m. Then for all x ∈ P , we have x ≤ m.
Since m is the maximum of P , a good candidate for the maximum of Q would be
its image under f , namely f (m). To show that f (m) is the maximum of Q, we need
to prove that y ⪯ f (m) for all y ∈ Q. Since f is bijective, for each y ∈ Q, there is
some x ∈ P such that f (x) = y. However, for all such x ∈ P , we have x ≤ m. As
f is an order isomorphism, we have f (x) ⪯ f (m). That is, y ⪯ f (m) for all y ∈ Q.
That is, Q has a maximum element, namely f (m).
(b) Yep. We can consider this same result and take f −1 : Q → P instead of
f : P → Q.
4. Prove which of the following three subsets of Q, ordered under the usual ≤, are or are
not order isomorphic:
N, A = {1 − 1
n
: n ∈ N}, B = A ∪ {1}.
2
Consider the map f : N → A defined by f (n) = 1 − n1 . Take n, m ∈ N. Note that
n ≤ m ⇐⇒ 1
m
≤ 1
n
⇐⇒ − n1 ≤ − m1
⇐⇒ 1 − 1
n
≤1− 1
m
⇐⇒ f (n) ≤ f (m).
Thus f is an order-embedding. It’s also bijective, hence it is an order isomorphism.
Thus N ∼
= A.
Notice that 1 − 1
n
≤ 1 for all n ∈ N. Thus x ≤ 1 for all x ∈ B. Since 1 ∈ B, we
can conclude that 1 is the maximum of B. On the other hand, N has no maximum
element. For any n ∈ N, we have n ̸= n + 1 and n ≤ n + 1. Similarly, A has no
maximum element. For any x = 1 − 1
n
∈ A, we have x ≤ 1 − 1
n+1
. Thus B cannot
be order isomorphic to N or A.
5. Let S be a set. Consider the partially ordered sets (P(S), ⊆) and (P(S), ⊇). Prove
that the function f : P(S) → P(S) defined by f (X) = S −X is an order isomorphism
between these two partially ordered sets.
Take X, Y ∈ P(S) such that X ⊆ Y . Then S −Y ⊆ S −X (if you’re uncomfortable
with this fact, prove it by taking some element in S − Y and showing that it must
be in S − X). That is, f (X) ⊇ f (Y ). On the other hand, if X, Y ∈ P(S) such that
f (X) ⊇ f (Y ), then we have S − X ⊇ S − Y . Thus X ⊆ Y , as desired.
It remains to show that f is bijective. If X ̸= Y , then (without loss of generality)
there is some x ∈ X such that x ∈
/ Y . Since x ∈
/ Y , we have x ∈ S − Y . However,
x∈
/ S − X. Thus S − X ̸= S − Y and so f (X) ̸= f (Y ). Thus f is injective. Now
take some A ∈ P(S). Then S − A ∈ P(S) and f (S − A) = S − (S − A) = A. Thus
f is surjective and hence bijective.
6. Prove or disprove: If (P, ≤) is linearly ordered, then (P, ≤−1 ) is linearly ordered.
3
Let x, y ∈ P . Since P is linearly ordered under ≤ we have either x ≤ y or y ≤ x.
That is, either y ≤−1 x or x ≤−1 y. Thus all elements of P are comparable under
≤−1 and so (P, ≤−1 ) is linearly ordered.
7. Let (P, ≤) be linearly ordered and (Q, ⪯) be partially ordered. Suppose f : P → Q is
a function.
(a) Prove that if f is order-preserving, then Q contains a chain.
(b) Prove that if f is an order isomorphism, then Q is linearly ordered.
(a) The set f (P ) ⊆ Q is linearly ordered. For any a, b ∈ f (P ), we have some
x, y ∈ P such that f (x) = a and f (y) = b. Since P is linearly ordered, we have
either x ≤ y or y ≤ x. This means that either f (x) ≤ f (y) or f (y) ≤ f (x). That
is, either a ≤ b or b ≤ a. So all elements of f (P ) are comparable and Q contains a
chain.
(b) Take x, y ∈ Q. We need to show that either x ⪯ y or y ⪯ x. Because f is
a bijection, we have elements f −1 (x), f −1 (y) ∈ P . Since P is linearly ordered, we
either have f −1 (x) ≤ f −1 (y) or f −1 (y) ≤ f −1 (x). Using the properties of order
isomorphisms, this means x = f (f −1 )(x) ⪯ f (f −1 (y)) = y, or y = f (f −1 )(y) ⪯
f (f −1 (x)) = x. Thus all x, y ∈ Q are comparable and so Q is linearly ordered.
Extra questions
(I) Prove that if A is a countable set, then we can define an order relation ⪯ on A such
that (A, ⪯) is a linear order.
Note: This is not saying that all countable partially ordered sets are linearly or-
dered. It is saying that if we are given a countable set, then there exists some order
relation which makes it a linearly ordered set.
4
Since A is countable, we can write its elements in a list a1 , a2 , a3 , . . .. Define a
relation ⪯ on A by a1 ⪯ a2 ⪯ a3 ⪯ · · · . Clearly all elements are now comparable,
so A is linearly ordered.