CSE 526
Spring 2005 Stony Brook |
Principles of Programming Languages
Annie Liu Homework 4 |
Handout H4
Feb. 15, 2005 Due Feb. 22 |

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.

i.e., given any set

i.e., if an operator is monotone (only, but not increasing), then given any set