1. (An alternate characterization of infinite sets) In this problem, X is an infinite set (recall that this means that there exists a non-surjective injection f : X ,→ X). We will show that X is infinite if and only if X is bijective to X ` X. (a) Let f : X ,→ X be a non-surjective injection. Set Ai = f i (X) − f i+1(X). Show that f|Ai : Ai → Ai+1 is a bijection. (b) Show that the construction in (a) produces a partition of X; i.e. show {Ai : i ∈ Z≥0} is a partition of X indexed by i ∈ Z≥0. [By convention, we set f 0 (X) := X.] (c) Set Y := S i even Ai and Z := S i odd Ai . Show that f|Y : Y → Z is a bijection. (d) Show that Y is bijective to X. [Hint: for each i, find a bijection Ai ∼−→ A2i .] Explain how this shows that if X is infinite, then X is bijective to X ` X. (e) If X is bijective to X ` X, why is it infinite? 2. (Permutations and cardinality) Suppose X is a set. A bijection g : X → X is sometimes called a permutation of X. We denote by Perm(X) the set of permutations of X. (a) Recall that the factorial n! of a natural number n is defined inductively by setting 0! = 1, and letting (n+ 1)! = (n+ 1)n!. Describe the set A := {n ∈ N : n! ≥ 2 n}. Use induction to prove your answer is correct. (b) Suppose that X is finite, with |X| = n. Show that |Perm(X)| = n!. Deduce that for n ∈ A, there is an injection P(X) ,→ Perm(X). (c) Suppose now that X is infinite. Use the result of problem 1 to construct an injection ϕ : P(X) ,→ Perm(X). 1 Show that the map you defined is an injection. [Hint: to define ϕ, you need to attach to every subset A ⊆ X a different permutation of X. If you split X into two copies of itself, i.e. fix a bijection X ∼−→ X ` X, then you can find a set that looks like A ` A inside of X. Try to think of an interesting permutation you could do on this set . . . ] (d) Show that, for any set X with 3 or more elements, |Perm(X)| ≥ |X| but that |Perm(X)| 6= |X|. 3. (More on permutations) (a) Suppose g, h are permutations of a set X. Show that the composition g ◦ h is also a permutation of X. We write simply gh for g ◦ h. (b) Find two permutations g, h ∈ Perm({1, 2, 3}) so that gh 6= hg. (c) For any set X, show that the set Perm(X), together with the operation of composition, has the following properties: i. For any g, h, k ∈ Perm(X), we have g(hk) = (gh)k. ii. There is an element e ∈ Perm(X) which has the property that ge = eg = g for all g ∈ Perm(X). iii. Given any element g ∈ Perm(X), there exists an element g 0 so that gg0 = g 0 g = e. [These three axioms are called the group axioms; by checking them, you have verified that Perm(X) equipped with composition is a group. We will discuss groups in more detail later in the semester.] 4. (The Frobenius map) Let p ∈ N be a prime number. Consider the map F : Z/pZ → Z/pZ x 7→ x p . This is called the Frobenius map. (a) (Easy) Show that for all x, y ∈ Z/pZ, F(xy) = F(x)F(y). (b) Show that for all x, y ∈ Z/pZ, F(x + y) = F(x) + F(y). [This fact is sometimes given the funny but somewhat insulting name of the “Freshman’s dream:” modulo p, (x+y) p = x p+y p .] Remark: You may not use (c) to show this–rather, you will use this fact to show (c)! (c) In fact, for Z/pZ, something even stronger is true: F = Id. Show this. Remark: You may not simply cite Theorem 6.35/6.36 1 in the book to get credit for this problem; rather, you must prove this theorem! The margin of the book offers a suggestion. (d) Find 17478863 mod 691. Explain how you found your answer. You cannot use a computer. [Hint: 691 is a prime number and 478863 = 6912 + 2 ∗ 691. You will have to do some computation, but not much.]