Question

1. diagonalization. cantors proof is often referred to as \cantors diagonalization argument.\ explain why this is a reasonable name.
2. digging through diagonals. first, consider the following infinite collection of real numbers. describe in your own words how these numbers are constructed (that is, describe the procedure for generating this list of numbers). then, using cantors diagonalization argument, find a number not on the list. justify your answer.

0.123456789101112131415161718...
0.2468101214161820222426283032...
0.369121518212427303336394245...
0.4812162024283236404448525660...
0.510152025303540455055606570...

1. coloring revisited (exh). in mindscape 35 of the previous section we considered the following infinite collection of circles and all the different ways of coloring the circles with either red or blue markers. show that the set of all possible circle colorings has a greater cardinality than the set of all natural numbers.
2. a penny for their thoughts. suppose you had infinitely many people, each one wearing a uniquely numbered button: 1, 2, 3, 4, 5, ... (you can use all the people in the hotel cardinality if you dont know enough people yourself). you also have lots of pennies (infinitely many, so youre really rich; but dont try to carry them all around at once). now you give each person a penny, then ask everyone to flip his or her penny at the same time. then ask them to shout out in order what they flipped (h for heads and t for tails). so you might hear: hhththtthththththhhth... or you might hear thttththhtththttttthhhththth..., and so forth. consider the set of all possible outcomes of their flipping (all possible sequences of hs and ts). does the set of possible outcomes have the same cardinality as the natural numbers? justify your answer.

Explanation:

11.

Cantor's proof involves constructing a new element by changing the diagonal elements of a list of infinite - length elements (like real - numbers in decimal form). This diagonal - manipulation is the key operation, so the name "diagonalization argument" is reasonable as it highlights this central step.

Step1: Analyze number construction

The first digit of the first number is 0, the first digit of the second number is 0, the first digit of the third number is 0, etc. The \(n\)th digit of the \(m\)th number is \(n\times m\bmod{10}\).

Step2: Apply Cantor's diagonalization

Let the list of numbers be \(x_1,x_2,x_3,\cdots\). Consider the diagonal digits \(d_1,d_2,d_3,\cdots\) where \(d_i\) is the \(i\)th digit of \(x_i\). Construct a new number \(y\) such that the \(i\)th digit of \(y\) is \(d_i + 1\bmod{10}\) if \(d_i
eq9\) and 0 if \(d_i = 9\). This number \(y\) is not on the list. Suppose it was the \(k\)th number on the list. But the \(k\)th digit of \(y\) is different from the \(k\)th digit of the \(k\)th number on the list by construction.

Step1: Represent colorings as binary sequences

Each coloring of the circles can be thought of as an infinite binary sequence, where 0 represents blue and 1 represents red.

Step2: Apply Cantor's diagonalization

Assume that the set of all colorings (binary sequences) has the same cardinality as the set of natural numbers. Then we can list all the binary sequences \(s_1,s_2,s_3,\cdots\). Construct a new binary sequence \(s\) such that the \(i\)th digit of \(s\) is the opposite of the \(i\)th digit of \(s_i\). This new sequence \(s\) is not on the list, so the set of all possible circle colorings has a greater cardinality than the set of natural numbers.

Answer:

The name is reasonable because the proof's key step involves manipulating the diagonal elements of a given list of infinite - length objects (such as real numbers in decimal representation).

12.