Sale!

ve203 Assignment 4

$30.00

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.

Category:

Description

5/5 - (4 votes)

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