MATH 209/509 - FALL 2022
PROBLEM SET # 4
Below Z denotes the set of integers and N denotes the set of non-negative integers.
(1) For the following relations R decide which of them is a function:
• X = {1, 2, 3, 4}, Y = {2, 3, 4}, R = {(1, 2), (2, 3), (3, 4)} ⊂ X × Y ;
• X = Z, Y = N, R = {(x, y) ∈ X × Y | |x| = |y|};
• X = Z = Y , R = {(x, y) ∈ X × Y | x = |y|}.
(2) Let X = {1, 2, 3, 4} and consider a function f : X → X defined in the following way:
f(1) = 4, f(2) = 1, f(3) = 4, f(4) = 2. Find
• f−1({1, 4})
• f(f−1({1, 4}))
• f({1, 4})
• f−1(f({1, 4}))
(3) For X = {1, 2, 3, 4} and Y = {1, 2, 3} write down an example of a function f : X → Y
which is
• surjective but not injective;
• injective but not surjective;
• neither injective nor surjective.
(4) Consider a function f : {1, 2} × {2, 3, 4} → {2, 3, 4} which is the projection onto the second
coordinate, i.e., f((x, y)) = y.
• Find f({(1, 2), (2, 3)});
• Find f({(1, 2), (2, 2)});
• Find f−1({2});
• Find f−1({3, 4}).
(5) Consider a function f : Z→ Z given by f(x) = x2 − 1. Find f(N) and f−1(N).
(6) For an integer x write x+4Z for the equivlaence class of x for the relation that is congruence
mod 4. Consider a fuction f : {1, 2, 3, 4, 5, 6} → Z/4Z defined by f(x) = x + 4Z. Is f
injective? Surjective? Find
• f({1, 5})
• f−1({3 + 4Z})
• f−1({1 + 4Z, 2 + 4Z})
Can you find a subset A of Y such that f(f−1(A)) 6= A?
1
2 MATH 209/509 - FALL 2022 PROBLEM SET # 4
(7) Let f : X → Y be a function. Prove that for any subsets A and B of Y one has f−1(A∪B) =
f−1(A) ∪ f−1(B).
MATH 509 - FALL 2022
PROBLEM SET # 5
Below N denotes the set of all natural numbers (including zero) and Q+ denotes the set of
positive rationals.
(1) Let X = {1, 2, 3, 4} with a partial order denoted by �. For the different � below decide
which statements are true:
(a) x � y if x ≥ y. Is it true that:
(i) 2 � 2?
(ii) 3 � 4?
(iii) 4 � 1?
(iv) 3 ≺ 4?
(v) 2 is an immediate predecessor of 3?
(b) x � y if x divides y, Is it true that
(i) 1 � 2?
(ii) 1 � 3?
(iii) 2 � 3?
(iv) 2 ≺ 3?
(v) 2 ≺ 4?
(vi) 2 is an immediate predecessor of 3?
(2) Let X = P({0, 1, 2, 3, 4, 5})−{0, 1, 2, 3, 4, 5} with the partial order given by A � B if A ⊂ B.
• Find all the immediate successors of {1, 2}.
• Find all the immediate predecessors of {1, 2}.
• Find all the immediate predecessors of {4}
• Find all the immediate successors of {4}.
• Find the largest and the smallest element of X if they exist.
• Find all the minimal and all the maximal elements of X.
(3) For the following relations R on X×X decide which of them are a partial orde
total order.
If R is a partial order, determine the least element, the greatest element (if they exist),
minimal and maximal elements.
• X = {1, 2, 3, 4}, R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
• X = {1, 2, 3}, R = {(1, 1), (1, 3), (2, 2), (3, 3)},
• X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, R = {(x, y) ∈ X ×X | x divides y},
• X = {1, 3, 5, 15}, R = {(x, y) ∈ X ×X | x divides y},
• X = P({1, 2, 3, 4})− {∅, {1}, {2}, {3}, {4}}, R = {(x, y) ∈ X ×X | x ⊂ y}.
1
2 MATH 509 - FALL 2022 PROBLEM SET # 5
(4) Consider X = N with the partial order given by the ‘less than or equal’ relation ≤. For the
following sets E find the set E∗ of all upper bounds, the set E∗ of all lower bounds, supE
and inf E.
• E = {3, 5, 6}
• E = the set of even natural numbers including 0
• E = the set of all divisors of 100.
(5) Let X = Q+ denote the set of positive rationals with the partial order given by the “less
than or equal” relation ≤. For the following sets E find the set E∗ of all upper bounds, the
set E∗ of all lower bounds, supE and inf E, if they exist.
• E = {3, 5, 6}
• E = {a ∈ Q+ | a ≥ 1}
• E = {a ∈ Q+ | a > 1}
• E = {a ∈ Q+ | 2 ≤ a < 3}
• {2−n ∈ Q+ | n ∈ N}
• {a ∈ Q+ | a2 < 2}
(6) Consider the set Y = {1, 2, 3, 4}. We equip its power set X = P(Y ) with partial order �
given by inclusion, i.e., A � B if A ⊂ B.
• Find all the strict predecessors and all the strict successors of {1, 2} as well as all the
immediate predecessors and all the immediate successors of {1, 2}.
• Let E = {{1, 2}, {1}} ⊂ P(Y ). Find the set E∗ of all upper bounds, the set E∗ of all
lower bounds, supE and inf E if they exist.
• Let E = {{1, 2}, {1}, {2, 3}} ⊂ P(Y ). Find the set E∗ of all upper bounds, the set E∗
of all lower bounds, supE and inf E if they exist.
• Let E be the subset of P(Y ) consisting of all singletons, i.e., E = {{1}, {2}, {3}, {4}}.
Find the set E∗ of all upper bounds, the set E∗ of all lower bounds, supE and inf E if
they exist.
(7) Consider the set A = {1, 2, 3, 4} and order A×A by the lexicographical order, i.e., (x, y) �
(x′, y′) if eithe
• x < x′ o
• x = x′ and y ≤ y′.
Let E = {(2, 2), (2, 3), (3, 4)} ⊂ A × A. Find the set E∗ of all upper bounds, the set E∗ of
all lower bounds, supE and inf E if they exist.