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.