Sale!

ve203 Assignment 3

$30.00

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)

Category:

Description

5/5 - (4 votes)

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