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

1.1. Solution

1. Proof: We'll show how to assign a unique element of ℕ to each function in S2. Given a non-decreasing function f from ℕ to {0,1}, let c(f) = 0 if f(x) = 0 for all x in ℕ. Otherwise, there is some least value mf such that f(mf) = 1; let c(f) = mf+1. If f and g are distinct non-decreasing functions, then there is some x such that f(x) != g(x). Suppose that f(x) = 1 and g(x) = 0. Then either g is the constant zero function, and c(f) = mf + 1 > 0 = c(g), or mg > x (because if g(y) = 1 for some y < x, g(x) would have to be 1 as well) and mf ≤ x; again this implies mf > mg. So we have shown that c is an injection from S2 to ℕ, implying that S2 is countable.1

2. Disproof: There are a lot of ways to show S is uncountable. Here's a particularly slick way, by constructing an explicit bijection between S and ℕ, the set of all functions (monotone or not) from ℕ to ℕ. Given f in ℕ, let mf be the function given by mf(x) = ∑z≤x f(z). Then mf is non-decreasing (if x ≤ y, then mf(y) = mf(x) + ∑x<z≤y f(z) ≥ mf(x)). The map f↦mf is a bijection because it's invertible: given mf, we can compute f by letting f(x) = mf(x) - mf(x-1) (with f(0) = mf(0) as a special case). Since ℕ is uncountable, this implies S is also uncountable.

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

2.1. Solution

Proof: Suppose (a,b) ≤× (a',b') in the product order. Then a' ≤ a and b ≤ b'. If a < a', then (a,b) ≤L (a',b'); if a = a', then b ≤ b' implies again (a,b) ≤L (a',b'). By symmetry, the same argument works for ≤C. If follows that (a,b) ≤× (a',b') implies (a,b) ≤L (a',b') and (a,b) ≤C (a',b'), or that (≤×) ⊆ (≤L) ∩ (≤C).

For the other direction, suppose (a,b) ≤L (a',b') and (a,b) ≤C (a',b'). From (a,b) ≤L (a',b'), we have a ≤ a'. From (a,b) ≤C (a',b'), we have b ≤ b'. It follows that (a,b) ≤× (a',b'). In set-theoretic terms, we thus have (≤×) ⊇ (≤L) ∩ (≤C).

Since we've proved subset in both directions, the two sets are equal.

(Note: This doesn't work for the product of three or more sets. Consider (0,1,0) and (1,0,1).)

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

3.1. Solution

1. Reflexive: (x,y) ~ (x,y), since x+y = x+y. Symmetric: Suppose (x,y) ~ (x',y'). Then x+y' = x'+y. Using symmetry of equality gives x'+y = x+y', or (x',y') ~ (x,y). Transitive: Let (r,s) ~ (t,u) and (t,u) ~ (v,w). Then r+u = t+s and t+w = v+u. Add these two equations together to get r+u+t+w = t+s+v+u. Rewrite as r+w+(t+u) = v+s+(t+u) and cancel out the (t+u) terms to get r+w = v+s. Use the definition of ~ to get (r,s) ~ (v,w).
2. Let (x,y) ~ (z,z); then x+z = z+y, which we can rewrite as x+z = y+z, which implies x = y by cancellation. Expand (x,y) + (x',y') as (x+x', y+y'). Observe that (x+x', y+y') ~ (x',y') if and only if x+x'+y' = x'+y+y', which we can rewrite as (x'+y')+x = (x'+y')+y. This follows from x=y.
3. Compute (x',y') + -(x',y') = (x',y') + (y',x') = (x'+y',x'+y') = (z,z) where z = x'+y'. But then (x,y) + (x',y') + -(x',y') = (x,y) + (z,z) ~ (x,y) by the previous case.

Some examples of this construction in action: If S = ℕ and + is the usual addition operation, then (ℕ×ℕ)/~ represents ℤ, with + and - having their usual meanings. If S = ℤ - {0} and + is multiplication, then (S×S)/~ represents ℚ-{0} with + acting as multiplication and - acting as inverse.

1. It's actually a bijection. (1)

2014-06-17 11:57