# 1. A mean statistics problem

You are asked to find the typical temperature for a particular time of year centered around day 0. Suppose you have collected daily high temperatures x

_{-n}...x_{n}for 2n+1 days in a row (with x_{0}, the day 0 temperature, in the middle), but you are only allowed to report one "typical" temperature y. You will be punished for deviation from the typical temperature according to the formula p = ∑_{i}(x_{i}-y)². Given an explicit formula for the value of y that minimizes p.Now suppose you are allowed to include a predicted daily increment z, so that the guess for day i is now y+iz. Give an explicit formula for the values of y and z that between them minimize p = ∑

_{i}(x_{i}- (y+iz))².

## 1.1. Solution

We'll recast this as an orthogonal projection problem. Treat the x

_{i}as a vector x over a (2n+1)-dimensional space. We want to find the point in the 1-dimensional subspace where all coordinates are equal that is closest to x, i.e. to find the multiple of b = (1, 1, ..., 1) that is the orthogonal projection of x. From the orthogonal projection formula we get y = b(x⋅b)/(b⋅b) = b ∑x_{i}/(2n+1). Or in terms of a single typical temperature y, we have y = ∑x_{i}/(2n+1), the average temperature.Again we will do orthogonal projection, but now we are projecting onto a 2-dimensional subspace of all vectors of the form v

_{i}= y1 + zi. A basis for this space is given by b_{1}= (1, 1, 1, ..., 1) and b_{2}= (-n, ..., n). These happen to be orthogonal since b_{1}⋅b_{2}= ∑[i=-n to n] i = 0. So we can project by taking y = x⋅b_{1}/b_{1}⋅b_{1}= ∑x_{i}/(2n+1) as before and z = x⋅b_{2}/b_{2}⋅b_{2}= ∑ ix_{i}/ ∑ i². (The denominator for z can be converted to closed form if one really wants to.)

Also works: Take partial derivatives wrt y and z and set the result to zero; this gives the same answer if one is careful enough.

# 2. Equivalence relations and functions

Let f:A→B be some function.

Show that the relation ~

_{f}, given by the rule x~_{f}y if and only if f(x) = f(y), is an equivalence relation.- Show the converse: if ~ is an equivalence relation on A, there exists a set B and a function f:A→B such that x~y if and only if f(x) = f(y).

## 2.1. Solution

Recall that ~ is an equivalence relation if it is (a) reflexive (x~x), (b) symmetric (x~y ⇒ y~x) and (c) transitive (x~y ∧ y~z ⇒ x~z).

For the relation ~

_{f}, we have (a) f(x) = f(x), so x~_{f}x; (b) x~_{f}y ⇒ f(x)=f(y) ⇒ f(y)=f(x) ⇒ y~_{f}x; and (c) x~_{f}y ∧ y~_{f}z ⇒ f(x) = f(y) ∧ f(y) = f(z) ⇒ f(x) = f(z) ⇒ x~_{f}z. So ~_{f}is reflexive, symmetric, and transitive.- Given an equivalence relation ~ on A, let B = A/~ be the set of equivalence classes of ~, and let f:A→B be given by f(x) = [x] = {y|x~y}. Then f(x)=f(y) if and only if x and y are in the same equivalence class, i.e., if x~y.

# 3. Partial orders

Let A = ℕ^{k} be the set of all sequences of natural numbers of length k. Given two elements x and y of A, let x≤y if and only if x_{i}≤y_{i} for all i.

Prove (by showing reflexivity, antisymmetry, and trasitivity) that ≤ as defined above is a partial order on ℕ

^{k}.- Give examples of choices of k for which ≤ is/is not a total order.
Prove that (ℕ

^{k}, ≤) contains no infinite descending chain, i.e. there is no infinite sequence a_{0}, a_{1}, a_{2}, ..., where a_{i+1}< a_{i}for all i.Now consider the set ℕ

^{ℕ}of all*infinite*sequences of natural numbers, where x ≤ y is defined to mean x_{i}≤ y_{i}for all i∈ℕ. Prove or disprove: (ℕ^{ℕ}, ≤) contains no infinite descending chain.

## 3.1. Solution

Reflexivity: if x = y, then x

_{i}= y_{i}⇒ x_{i}≤ y_{i}for all i, giving x ≤ y. Antisymmetry: if x ≤ y and y ≤ x, then for each i we also have x_{i}≤ y_{i}and y_{i}≤ x_{i}; it follows that x_{i}=y_{i}for all i and thus x = y. Transitivity: If x ≤ y and y ≤ z, then for each i, x_{i}≤ y_{i}and y_{i}≤ z_{i}, giving x ≤ z.Let k = 0, then N

^{0}has exactly one element (the empty sequence), which is ≤ itself. It follows that any two elements of N^{0}are comparable and that (N^{0}, ≤) is a totally ordered set. (The case k=1 also works, and is slightly more interesting). For a non-totally-ordered set, take k=2; then (0,1) and (1,0) (for example) are incomparable.Suppose we have an infinite descending chain a

_{0}> a_{1}> ... . Write a_{i}[0]...a_{i}[k-1] for the k elements of a_{i}; then we have a_{i+1}[j] ≤ a_{i}[j] for all i, j, and a_{i+1}[j] < a_{i}[j] for at least one j. It follows that ∑_{j}a_{i+1}[j] < ∑_{j}a_{i}[j] ≤ ∑_{j}a_{i}[j] - 1. An easy induction on i gives ∑_{j}a_{i}[j] ≤ ∑_{j}a_{0}[j] - i. But then for i > ∑_{j}a_{0}[j], we have ∑_{j}a_{i}[j] < 0, an impossibility. It follows that there is no infinite descending chain.Disproof by counterexample: Let a

_{i}[j] = 1 if i > j and 0 otherwise. Then a_{i+1}[j] = a_{i}[j] = 0 if j < i, a_{i+1}[i] = 0 < a_{i}[i] = 1, and a_{i+1}[j] = a_{i}[j] = 1 if j ≥ i+1. It follows that a_{i+1}< a_{i}for all i, and the a_{i}form an infinite descending chain.

# 4. Lattices

- Prove or disprove: In any lattice, x∨(y∧z) = (x∨y)∧(x∨z).
- Prove or disprove: In any lattice, x≥y ⇒ x∧(y∨z) = (x∧z)∨y.

## 4.1. Solution

These properties are known as the **distributive law** and the **modular law**, respectively. Both are false in general (although both hold in a lot of common lattices). The simplest counterexample to the modular law is the *pentagon lattice* N_{5}, whose Hasse diagram looks like this:

1 / \ / \ p \ | r q / \ / \ / 0

Here p≥q, but p∧(q∨r) = p∧1 = p while (p∧r)∨q = 0∨q = q ≠ p.

The distributive law also fails in N_{5}: r∨(p∧q) = r∨p = 1, but (r∧p)∨(r∧q) = 0∨0 = 0 ≠ 1.