COMP2922: Models of Computation (Adv) Tutorial 1: Mathematical Preliminaries
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP2922: Models of Computation (Adv)
Tutorial 1: Mathematical Preliminaries
August 14, 2023
Exercises
Problem 1
Prove the following statements involving unions, intersections, and set differences.
a) For any sets A, B, A ⊆ B ⇔ A ∪ B = B.
b) For any sets A, B, A ⊆ B ⇔ A ∩ B = A.
c) For any sets A, B, A \ (A \ B) = A ∩ B.
d) For any sets A, B, A ⊆ B ⇔ A \ B = ∅.
e) For any collection of sets C, A ⊆ S C for every A ∈ C. Furthermore, S C is the smallest set satisfying this property – that is, if some other set X satisfies the property A ⊆ X for every A ∈ C, then S C ⊆ X.
f) For any nonempty collection of sets C, T C ⊆ A for every A ∈ C. Furthermore, T C is the largest set satisfying this property – that is, if some other set X satisfies the property X ⊆ A for every A ∈ C, then X ⊆ T C.
Problem 2
Prove the following statements involving the empty set.
a) The empty set is unique. That is, if x /∈ A for all x, then A = ∅.
b) For any set A, ∅ ⊆ A.
Problem 3
Prove the following statements involving power sets.
a) For any sets A, B, A ⊆ B ⇒ P(A) ⊆ P(B).
b) For any sets A, B, P(A) ∈ P(B) ⇒ A ∈ B.
c) For any set A, A = S P(A).
d) For any collection of sets C, C ⊆ P( S C).
e) For any set A, T P(A) = ∅.
Problem 4
The following exercises concern the replacement set builder notation.
a) Prove that the set defined by a replacement expression is unique. That is, if B = {f(x) | x ∈ A}, and C is any set that satisfies the property
y ∈ C ⇔ there exists x ∈ A such that y = f(x),
then B = C.
b) Using the characteristic property for replacement, prove that if B = {f(x) | x ∈ A}, then B is the smallest set such that
x ∈ A ⇒ f(x) ∈ B.
That is, if for some set C we have x ∈ A ⇒ f(x) ∈ C, then B ⊆ C.
Problem 5
The following questions concern orderings.
a) For a total ordering < on a set A, prove that < is asymmetric, i.e. x < y ⇒ y < x holds for all x, y ∈ A. Does asymmetry hold if < is a partial ordering?
b) A weak partial order is a binary relation ≤ on a set A satisfying the following properties:
WO1. (Reflexivity) x ≤ x
WO2. (Antisymmetry) x ≤ y and y ≤ x ⇒ x = y
WO3. (Transitivity) x ≤ y and y ≤ z ⇒ x ≤ z
For any strict partial order <, we obtain a weak partial order by defining
x ≤ y def ⇔ x < y or x = y.
Prove that the relation ≤ defined in this way satisfies WO1, WO2, and WO3.
c) A (weak) preorder ≤ is a binary relation on a set A satisfying WO1 and WO3 above. Prove that the relation ∼ defined by
x ∼ y def ⇔ x ≤ y and y ≤ x
is an equivalence relation.
Problem 6
The following questions concern equivalence relations.
a) Let f : A → B be an arbitrary function. Prove that
x ∼ y def ⇔ f(x) = f(y)
defines an equivalence relation on A.
b) If ∼ is an equivalence relation on A, then for each x ∈ A we denote by
[x] = {y ∈ A | y ∼ x}
the equivalence class of x. Prove that for each x, y ∈ A, if x ∼ y then [x] = [y], otherwise [x]∩[y] = ∅.
Problem 7
The following questions concern functions.
a) Interpreting a function as a relation f ⊆ A × B satisfying FN1 and FN2 from the supplement, prove the extensionality property for functions holds. That is, given arbitrary f, g : A → B
f = g ⇔ for every x ∈ A, f(x) = g(x).
b) Prove that a function f : A → B is bijective if and only if there exists a function g : B → A such that g ◦ f = idA and f ◦ g = idB.
c) Prove that given functions f : A → B and g, h : B → A, if g ◦ f = idA and f ◦ h = idB, then g = h.
2023-08-24