# 1. Non-decreasing functions

Let A and B be partially-ordered sets. Recall that a function f:A→B is *non-decreasing* if x≤y implies f(x)≤f(y) for all x, y in A.

Prove or disprove: The set S

_{2}of all non-decreasing functions from ℕ to {0,1} is countable.Prove or disprove: The set S

_{ℕ}of all non-decreasing functions from ℕ to ℕ is countable.

(Assume the usual order on ℕ and {0,1}.)

# 2. Lex and colex orders

Let A and B be totally ordered sets. Here are three partial orders on A×B:

- Lexicographic order
(a,b) ≤

_{L}(a',b') iff a < a' or a = a' and b ≤ b'.- Colexicographic order
(a,b) ≤

_{C}(a',b') iff b < b' or b = b' and a ≤ a'.- Product order
(a,b) ≤

_{×}(a',b') iff a ≤ a' and b ≤ b'.

Prove or disprove: For any totally ordered sets A and B, the product order (≤_{×}) = (≤_{L}) ∩ (≤_{C}).

# 3. Addition and negation

Suppose we have an addition operation on some set S (i.e., a function +:S×S→S, written in infix form between its arguments), and we know that addition satisfies the axioms

- x+y=y+x (commutativity),
- x+(y+z) = (x+y)+z (associativity), and
- x+z = y+z ⇒ x=y (cancellation),

where x, y, z, are any elements of S.

Define the relation ~ on S×S by the rule (x,y) ~ (x',y') iff x+y' = x'+y.

- Show that ~ is an equivalence relation.
- Define the operation (x,y) + (x',y') = (x+x', y+y'). Show that if (x,y) ~ (z,z), then (x,y) + (x',y') ~ (x',y').
- Define -(x,y) = (y,x). Show that (x,y) + (x',y') + -(x',y') ~ (x,y).