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

## 1.1. Solution

Proof: We'll show how to assign a unique element of ℕ to each function in S

_{2}. 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 m_{f}such that f(m_{f}) = 1; let c(f) = m_{f}+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) = m_{f}+ 1 > 0 = c(g), or m_{g}> x (because if g(y) = 1 for some y < x, g(x) would have to be 1 as well) and m_{f}≤ x; again this implies m_{f}> m_{g}. So we have shown that c is an injection from S_{2}to ℕ, implying that S_{2}is countable.^{1}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 m_{f}be the function given by m_{f}(x) = ∑_{z≤x}f(z). Then m_{f}is non-decreasing (if x ≤ y, then m_{f}(y) = m_{f}(x) + ∑_{x<z≤y}f(z) ≥ m_{f}(x)). The map f↦m_{f}is a bijection because it's invertible: given m_{f}, we can compute f by letting f(x) = m_{f}(x) - m_{f}(x-1) (with f(0) = m_{f}(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).)

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

## 3.1. Solution

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

It's actually a bijection. (1)