Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 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.

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

2. 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).

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.

1. Show that ~ is an equivalence relation.
2. 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').
3. Define -(x,y) = (y,x). Show that (x,y) + (x',y') + -(x',y') ~ (x,y).

2014-06-17 11:57