## Description

ve203 Assignment 3

Q1. Prove that a set A is (Dedekind) infinite if an only if there exists an injective

function f : N −→ A.

(3 marks)

Q2. Let (L, ) be a lattice and let a, b ∈ L. Prove that the following are equivalent:

(i) a b

(ii) a ∨ b = b

(iii) a ∧ b = a

(3 marks)

Q3. Let (L, ) be a lattice. Prove that for all a, b, c ∈ L,

(a ∨ b) ∨ c = a ∨ (b ∨ c)

(2 marks)

Q4. Without using Cantor’s Pairing Function, prove that N × N is countable.

(2 marks)

Q5. For all n ∈ N, use [n] to denote the set of predecessors of n in the natural numbers

with the usual ordering, i.e. [0] = ∅ and for all n ≥ 1, [n] = {0, . . . , n − 1}. Define

S = {f | (∃n ∈ N)(f is a function with dom f = [n] and ran f ⊆ N)}

(i) Use the fact that every natural number has a unique factorisation into primes to

show that S is countable. Is |S| = |N|?

(ii) Define 1⊆ S × S by: f 1 g where f : [n] −→ N and g : [m] −→ N, and

A = [n] ∩ [m] if and only if

(∃i ∈ A)(f(i) < g(i)∧(∀j < i)(f(j) = g(j))) or (∀i ∈ A)(f(i) = g(i))∧([n] ⊆ [m]),

where ≤ and < are the usual orders on N. Is (S, 1) a partial order? Is (S, 1)

a linear order? Is (S, 1) chain complete? Is (S, 1) a lattice? Is (S, 1) a wellorder? Prove your answers.

(iii) Define 2⊆ S × S by: f 2 g where f : [n] −→ N and g : [m] −→ N if and only if

[n] ⊆ [m] and (∀i ∈ [n])(f(i) ≤ g(i))

Is (S, 2) a partial order? Is (S, 2) chain complete? Is (S, 2) a lattice? Is

(S, 2) a linear order? Prove your answers.

(7 marks)

Q6. Give an explicit formula that defines a bijection between N and N × N × N. You

do not have to prove that this formula works!

(1 mark)

1

Q7. Every nonzero rational number has a unique representation in the form (−1)ka

b

where k ∈ {0, 1} and a, b ∈ N with a, b 6= 0 and the greatest common divisor of a and b

is 1. Use this to show that Q is countable.

(3 marks)

Q8. Let π(x, y) be Cantor’s pairing function. Find x, y ∈ N such that π(x, y) = 223.

You may do this question however you wish.

(1 mark)

Q9*

. Prove that |P(N × N)| = |P(N)|.

(1 mark)

Q10. Prove that |N| < |R|.(Hint: Start with a bijection f : N −→ R and try to construct

a real that can not be in the range of f. There may also be a proof that uses continued

fractions and Cantor’s Theorem, but I have not thought about that too deeply.)

(3 marks)

2