Hello, dear friend, you can consult us at any time if you have any questions, add  WeChat:  zz-x2580

Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose

should be typed, not handwritten. Use of LATEX is encouraged, but not required.

Discussion of assignment material with others is permitted, but the work submitted must be your

own in line with the University’s plagiarism policy.

Problem 1 (15 marks)

Let S be a set.

(a) Show that for any set T and any function f : S→ T, the relation R f ? S× S, defined as:

(s, s′) ∈ R f if and only if f (s) = f (s′)

is an equivalence relation. (9 marks)

(b) Show that if R ? S× S is an equivalence relation, then there exists a set T and a function fR : S → T

such that:

(s, s′) ∈ R if and only if fR(s) = fR(s′)

(6 marks)

Problem 2 (20 marks)

Let B = {0, 1} and consider the function f : N→ B given by

f (n) =

{

1 if n > 0,

0 otherwise.

(a) Show that for all a, b ∈N:

(i) f (a + b) = max{ f (a), f (b)}

(ii) f (ab) = min{ f (a), f (b)}

(6 marks)

From Problem 1, we know that R f ?N×N, the relation given by:

(m, n) ∈ R f if and only if f (m) = f (n)

is an equivalence relation. Let E ? Pow(N) be the set of equivalence classes of R f , and for n ∈ N, let

[n] ∈ E denote the equivalence class of n.

1

We would like to define binary operations, and , on E as follows:

[x] [y] := [x + y]

[x] [y] := [xy].

The difficulty is that the operands [x] and [y] can have multiple representations (e.g. if z ∈ [x] then

[x] = [z]), and so it is not clear that such a definition makes sense: if we take a different representation of

the operands, do we still end up with the same result? That is, if [x] = [x′] and [y] = [y′] is it the case that

[x + y] = [x′ + y′] and [xy] = [x′y′]? Our next step is to show that such a definition makes sense.

(b) Define relations , ? E2 ×E as follows:

((X, Y), Z) ∈ if and only if there is x ∈ X and y ∈ Y such that x + y ∈ Z

((X, Y), Z) ∈ if and only if there is x ∈ X and y ∈ Y such that xy ∈ Z

(i) Show that is a function.

(ii) Show that is a function.

(6 marks)