Sale!

ve203 Assignment 2

$30.00

ve203 Assignment 2

Q1. Draw diagrams representing every possible partial order (up to isomorphism) with
exactly 4 elements. Note that it is probably helpful for you to use a notation that allows
you to omit relationships that are forced by the axioms of reflexivity and transitivity.
Which of these posets are chain complete? Which of these posets are linear orders?
Which of these posets are well-orders? Which of these posets are lattices? Which of
these posets are complete lattices?
(3 marks)

Category:

Description

5/5 - (2 votes)

ve203 Assignment 2

Q1. Draw diagrams representing every possible partial order (up to isomorphism) with
exactly 4 elements. Note that it is probably helpful for you to use a notation that allows
you to omit relationships that are forced by the axioms of reflexivity and transitivity.
Which of these posets are chain complete? Which of these posets are linear orders?
Which of these posets are well-orders? Which of these posets are lattices? Which of
these posets are complete lattices?
(3 marks)
Q2.
(i) Prove that every complete lattice has a unique maximal element.
(ii) Give an example of an infinite chain complete poset with no unique maximal
element.
(iii) Prove that any closed interval on R ([a, b]) with the usual order (≤) is a complete
lattice (you may assume the properties of R that you assume in Calculus class).
(iv) Say that a poset is almost chain complete if every nonempty chain has an l.u.b.
Give an example of an almost chain complete poset with no minimal element.
(4 marks)
Q3. Give an example of a partial order in which every pair of elements has an upper
bound, but not every pair of elements has a l.u.b.
(2 marks)
Q4. Define a relation  on N × N (so ⊆ (N × N) × (N × N)) by
(x, y)  (z, w) if and only if x < z or (x = z and y ≤ w)
where < and ≤ are the usual “less than (or equals)” relations on N. Prove that (N×N, )
is a linear order. Is it a well-order? Either prove your answer (you may assume that
(N, ≤) is a well-order) or provide a counterexample.
(3 marks)
Q5. Define a relation  on N × N by
(x, y)  (z, w) if and only if x ≤ z and y ≤ w
where ≤ is the usual “less than or equals” relation on N. Prove that (N × N, ) is a
poset. Is it a linear order? Is it a lattice? Prove your answers.
(3 marks)
Q6. Define a relation  on Q × Q × Q by
(x, y, p)  (z, w, q) if and only if x ≤ z or (y ≤ w and p ≤ q)
where ≤ is the usual “less than or equals” relation on Q. Is (Q × Q × Q, ) a poset?
Prove your answer.
(1 marks)
1
Q7. Let A and be B be sets and let f : A −→ B be a function. Define ∼⊆ A × A by
x ∼ y if and only if f(x) = f(y).
Prove that ∼ is an equivalence relation on A. Let X be the set of ∼-equivalence classes
of A. I.e.
X = {[x]∼ | x ∈ A}.
Define g : X −→ B by
g([x]∼) = f(x).
Prove that g is a function. Prove that g is injective. Since g is injective, g
−1
: ran f −→
X is a function. For the function f : R −→ R defined by f(x) = x
3 − 4x
2 − 15x + 18,
find all the elements of g
−1
(0).
(4 marks)
Q8. Show that the following sentences are not tautologies.
(i) (∃xP(x) ∧ ∃yQ(y)) ⇒ ∃z(P(z) ∧ Q(z))
(ii)*
(∀z(Q(z) ∨ P(z))) ⇒ ((∀xQ(x)) ∨ (∀yP(y)))
(iii) ((∀xP(x)) ⇒ (∃yQ(y))) ⇒ ∀z(P(z) ⇒ ∃wQ(w))
(3 marks)
Q9. Use the primitive rules of inference for predicate logic to show that
∀x(P(x) ∨ Q(x))
∀x(R(x) ⇒ ¬P(x))
∃x(¬Q(x))
∴ ∃x(¬R(x))
is a valid argument.
(3 marks)
Q10. A. and B. find themselves trapped in a dark and cold dungeon. After a quick
search they find three doors; the first one red, the second one blue, and the third one
green. Behind one of the doors is a path to freedom. Behind the other two doors,
however, is almost certain death. On each door there is an inscription: the red door
says “freedom is behind this door”, the blue door says “freedom is not behind this door”
and the green door says “freedom is not behind the blue door”. Given the fact that at
LEAST ONE of the three statements on the three doors is true and at LEAST ONE of
them is false, which door would lead A. and B. to safety?
(3 marks)
2