HOMEWORK 1 — DUE SEP 26TH

MATH 25

There are three parts to this assignment (plus a fourth “optional” one which won’t be graded). Please return the three parts separately.

1. Sets and maps

1.1. Prove the following statements (here X, Y and Z are three sets):

(1) (X ∩ Y) × Z = (X × Z) ∩ (Y × Z);

(2) X \ (Y ∪ Z) = (X \ Y) ∩ (X \ Z);

(3) X \ (Y ∩ Z) = (X \ Y) ∪ (X \ Z).

1.2. Let f : A → B be a map and let Y, Z be two subsets of B. Prove the following: (1) f^{−1}(Y ∩ Z) = f^{−1}(Y) ∩ f^{−1}(Z);

(2) f^{−1}(Y \ Z) = f^{−1}(Y) \ f^{−1}(Z) if Z ⊂ Y.

1.3. Let f : A → B be a map and let Y, Z be two subsets of A. Determine whether the following are true or false (give a proof or a counterexample):

(1) f(Y ∪ Z) = f(Y) ∪ f(Z);

(2) f(Y ∩ Z) = f(Y) ∩ f(Z). If you’re looking for a counterexample, look for something simple, for example sets with only a few elements.

1.4. If A, B are two sets, let A^{B} be the set of all maps f : B → A. Construct a bijection between A^{B×C} and (A^{B})^{C}.

2. Finite sets

2.1. Show that if A and B are finite sets, then Card(A^{B}) = Card(A)^{Card(B)}.

Note that this holds even if one of A or B is empty. Here is why (the following is for your information, and will not be graded): given two non-empty sets A, B, you can attach to a map f : A → B its graph G(f) ⊂ A × B = {(a, f(a)) a ∈ A}. Show that a subset G ⊂ A × B is the graph of some map if and only if for any a ∈ A, Card(({a} × B) ∩ G) = 1.

This definition of a “map” still makes sense if A or B is empty. How many maps are there from the empty set to itself?

2.2. Let \binom{n}{k} be the number of parts of \{1, ⋯, n\} which have exactly k elements. Prove that

\binom{n}{k} = \binom{n − 1}{k} + \binom{n − 1}{k − 1},

by constructing bijections between certain sets. Show also that

\binom{n}{k} = \binom{n − 1}{k − 1} + \binom{n − 2}{k − 1} + ⋯ + \binom{k − 1}{k − 1} and that \binom{n}{k} = \frac{n!}{k!(n − k)!}.

2.3. Given n, p ≥ 1, compute Card{(x_{1}, ⋯, x_{n}) ∈ N^{n}, ∑_{i=1}^{n} x_{i} = p}.

Hint: let h(n, p) be the above cardinal. What is h(1, p)? Find a formula for h(n, p) in terms of the h(n − 1, q) with q ≤ p and use exercise 2.2.

2.4. The marriage lemma, after H. Weyl. Let W and M be two finite sets. To every m ∈ M is associated a subset W_{m} ⊂ W. Show that the following are equivalent:

(1) there exists an injective map f : M → W such that f(m) ∈ W_{m} for every m ∈ M;

(2) for every non-empty subset X ⊂ M, Card(∪_{m∈X}W_{m}) ≥ Card(X). (recall that ∪_{m∈X}W_{m} stands for the set of w ∈ W such that there exists m ∈ X with w ∈ W_{m}).

Conclusion: if there are men and women and if every man knows some of the women, it is possible to marry each man to a woman he knows if and only if for all n, any given n men know at least n women between each other.

3. Denumerable sets and cardinals

3.1. Finish the proof that if A and B are two denumerable sets then so is A × B.

3.2. Show that Q is denumerable (construct an explicit bijection between Q and Z_{≥1}).

3.3. Show that if A is any set, then Card(P (A)) = Card({0, 1}^{A}).

3.4. Let E be an infinite set and let D be a countable subset, such that E \D is still infinite. Prove that Card(E) = Card(E \ D).

HOMEWORK 1 — DUE SEP 26TH 3

3.5. Let A and B be two sets such that there exist two maps f_{i}, f_{s} : A → B with f_{i} injective and f_{s} surjective. Show that Card(A) = Card(B).

Hint: you will need to use the axiom of choice: if I is a set and {E_{i}}_{i∈I} is a collection of subsets of a set E indexed by I then there exists f : I → E such that f(i) ∈ E_{i} for all i ∈ I. Sounds obvious, doesn’t it?

4. Supplementary exercises

These exercises are harder and will not be graded. They are good practice though (especially the first one).

4.1. The purpose of this exercise is to show that Card(N) ≠ Card(R).

(1) Show that for any real number 0 ≤ α ≤ 1, there exists a sequence {x_{i}}_{i≥1} with

x_{i} ∈ {0, 1} such that α = ∑_{i=1}^{∞} x_{i}2^{−i}.

Hint: if 0 ≤ α ≤ 1, then either 0 ≤ α ≤ 1/2 or 0 ≤ α − 1/2 ≤ 1/2. Suppose that you have {x_{i}}_{1≤i≤n} such that 0 ≤ α − x_{1}2^{−1} − ⋯ − x_{n}2^{−n} ≤ 1/2^{n}. Show that there exists x_{n+1} ∈ {0, 1} such that 0 ≤ α − x_{1}/2 − ⋯ − x_{n+1}2^{−(n+1)} ≤ 1/2^{n+1}.

(2) Use this to define a surjective map {0, 1}^{N} → [0, 1];

(3) Show that the map {0, 1}^{N} → [0, 1] which sends {x_{i}}_{i≥1} to ∑_{i=1}^{∞} x_{i}3^{−i} is injective;

(4) Show that Card(P (N)) = Card({0, 1}^{N}) = Card([0, 1]) = Card(R);

(5) Show that Card(N) ≠ Card(R).

4.2. Construct a map f : R → P (N) such that:

(1) for any x ∈ R, f(x) is infinite;

(2) for any x ≠ y ∈ R, f(x) ∩ f(y) is finite.

4.3. Sperner’s lemma. Let A be a collection of elements of P ({1, ⋯, n}) such that for any X, Y ∈ A, one has X ⊄ Y.

(1) Show that ∑_{X∈A} Card(X)!(n − Card(X))! ≤ n!;

(2) prove Sperner’s lemma: Card(A) ≤ \binom{n}{⌊n/2⌋}.

4.4. A theorem of É. Borel. Let C(R, R) be the set of continuous functions from R to R. Show that Card(C(R, R)) = Card(R).