## Description

ve203 Assignment 4

Q1. Let (L, ) be a complete lattice and let f : L −→ L be an order-preserving function.

(i) Let a, b ∈ L with a b. Define

[a, b] = {x ∈ L | a x b}

Show that ([a, b], ) is a complete lattice.

(ii) Consider X = {x ∈ L | f(x) = x}. The Tarski-Knaster Theorem shows that there

exists a ∈ X such that for all x ∈ X, a x. Let S ⊆ X. Since (L, ) is a complete

lattice, S has a g.l.b.

s =

^

S

in L. Show that a s.

(iii) By considering f restricted to [a, s], for s and a defined in (ii), show that S has a

g.l.b. in X. Note that it is not necessarily the case that the g.l.b. of S in X is the

same as the g.l.b. of S in L.

(iv) Show that (X, ) is a complete lattice.

(v) Define an order-preserving function f : [0, 1] −→ [0, 1] such that the set of fixed

points of f endowed with the usual order (≤) on R is a linear order with exactly

4 elements.

(8 marks)

Q2. Define G : N × N −→ N × N by: for all (n, m) ∈ N × N,

G((n, m)) = (n + 1, 2

m)

Let X = {R ∈ P(N × N) | (0, 0) ∈ R}. Define F : X −→ X by: for all R ∈ X,

F(R) = R ∪ G“R.

(i) Show that (X, ⊆) is a complete lattice.

(ii) Prove that F is an order preserving function on (X, ⊆).

By the Tarski-Knaster Theorem, we know that F must have a least fixed point in (X, ⊆).

Let f be the least fixed point of F.

(iii) Prove that f is a function with dom(f) = N.

(iv) Prove that for all n ∈ N with n ≥ 2, f(n) is even.

(v) Prove that f is injective.

(7 marks)

Q3. Prove that

n

k

=

n!

(n − k)!k!

(2 marks)

1

Q4. Prove that for all n ≥ 1,

Xn

k=0

(−1)k

n

k

= 0

(1 mark)

Q5. Prove that for all m ≥ 0 and for all n ≥ 1,

Xn

k=0

m + k

m

=

m + n + 1

m + 1

(2 marks)

Q6. What is coefficient of x

31y

4

in the expansion of ((x + y)

8 + y)

7

?

(2 mark)

Q7. Find the greatest term in the expansion of (1 + 4x)

9 when x =

1

3

.

(2 marks)

Q8. Find the number solutions to the equation x1+x2+x3+x4 ≤ 6 with x1, x2, x3, x4 ∈ N.

(2 mark)

Q9*

. Use the binomial theorem to evaluate (1.2)5

.

(1 marks)

Q10. This question refers to Ndef discussed in lectures.

(i) Prove that if n ∈ Ndef with n 6= ∅, then there exists m ∈ Ndef such that

n = S(m)

For (ii) you may assume the definition of + on Ndef given in lectures ensures that ≤

(defined in the first lecture) is a linear ordering of Ndef.

(ii) Prove that the usual ≤ order on Ndef is a well order.

(6 marks)

2