This assignment has two problems, each worth 50% of the grade, respectively. There is a bonus problem at the end, worth an additional 30% of the grade (Note: it is not harder than other problems; it is only meant to give you extra points if you do it). The assignment is due before class on Tuesday Feb. 22.

Problem 1. Complete partial orders.

Which ones below are partial orders? and which ones are not? For those that are not, say why.

a. (Pow(S),subset), where Pow(S) is the power set of S, and subset is the subset relation.

b. (int,<=), where int is the set of integers, and <= is the standard comparison relation.

c. (int,<), where int is the set of integers, and < is the standard comparison relation.

d. (nat,|), where nat is the set of natural numbers, and a|b iff a divides b iff b=ka for some natural number k.

e. (S,=), where S is any set, and = is the identity relation.

f. (S,]), where S is any set, and ] is such that a ] b iff b [ a, and if (S,[) is a partial order.

Which ones below are complete partial orders? and which ones are not? For those that are not, say why.

a, b, e above.

g. (int U {infinity}, <=)

h. ([0,1], <=), where [0,1] is the closed continuum between 0 and 1.

i. ([0,1), <=).

Problem 2. Continuous functions.

Winskel's book Exercise 5.12 (ii) on page 73.

Winskel's book Exercise 4.13 on page 54. In particular, its last sentence is clarified as follows.