Name: ___________________________________
Exercises for Uncountability and Transcendence 
Last modified: September 16, 2004
Please hand these in, on this sheet of paper, at the class after the last minilecture on the topic is presented.
1. You know the quadratic formula, and you may have heard of the cubic formula and the quartic formula.  Galois and Abel proved around 1800 that there is no "quintic formula."  There are solutions to equations like x5 + 13 x2 + 2x - 7 = 0 that cannot be calculated by means of addition, subtraction, multiplication, division, and extraction of nth roots.
GIve a direct proof that the set S of all solutions to quintic equations with integer coefficients (positive, negative, or zero) is countably infinite.  That is, describe a procedure to list all such numbers.  There is no obligation to exclude duplicates from the list, since you know that S has an uncountable subset, the integers.

2. Prove that any set of disjoint intervals on the real line is countable. An example would be 
{(0,1/3), (e, p], [, ]} , which is not merely countable but finite.  You may assume without proof that between any two real numbers there lies at least one rational number and that the rational numbers are countable.  Hint: proof by contradiction. 
3. A computer science concentrator who is competing for the Crimson claims to have written a program that will generate a list of all possible sequences of future Harvard football results.  For example, if you ask for item 27, it might say:
27: 2003, Game 1 W Game 2 L, ... 2004 Game 1 L  Game 2 L
and go on until you stop it.
Use Cantor's argument to show that no such program can function as advertised.