7.4. Does All This Really Work? 233
That is,G 0000 DG 10 Dno-1s and so strings.G 0000 /Dstrings.G 10 /D 0 . This
means that
00002 strings.G 0000 / and 10 ...strings.G 10 /:
Now we are in a position to give a precise mathematical description of an “un-
describable” set of binary strings, namely, let
Theorem.Define
UWWDfx2f0;1gjx...strings.Gx/g: (7.10)The setUis not describable.
Use reasoning similar to Cantor’s Theorem 7.1.11 to prove this Theorem.Homework Problems
Problem 7.25.
For any sets,A, andB, letŒA!Bçbe the set of total functions fromAtoB.
Prove that ifAis not empty andBhas more than one element, thenNOT.Asurj
ŒA!Bç/.
Hint:Suppose thatis a function fromAtoŒA!Bçmapping each element
a 2 Ato a functionaWA!B. Pick any two elements ofB; call them 0 and 1.
Then define
diag.a/WWD(
0 ifa.a/D1;
1 otherwise:Exam Problems
Problem 7.26.
Letf1;2;3g!be the set of infinite sequences containing only the numbers 1, 2, and
- For example, some sequences of this kind are:
.1;1;1;1:::/;
.2;2;2;2:::/;
.3;2;1;3:::/:Prove thatf1;2;3g!is uncountable.
Hint:One approach is to define a surjective function fromf1;2;3g!to the power
set pow.N/.