## Description

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