Sketch of Solutions to Exercises

(a)

Unary alphabets

{a}, {b}, {c}

Binary alphabets

{a,b}, {b,a}, {a,c}, {c,a}, {b,c}, {c,b}

Other alphabets

{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}

(b)

Unary

t

Binary

t(t-1)

1.1.2

(a)

, a, b, ab, ba

(b)

aaa, aab, aba, abb, baa, bab, bba, bbb

1.1.3

(a)

=aab, =aba, ²=aa, ⁰² =abab, ²²=aaabab

(b)

= , =abb; =a, =bb; =ab, =b; =abb, =

1.1.4

(a)

, 0, 01, 011, 0110, 01101

(b)

, 0, 1, 11, 111, 1111, 011110

1.1.5 r^t

1.1.6

(a)

, a, a² a³, a⁴, a⁵, ..., a¹⁹

(b)

, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb, abc, aca

1.1.7

(a)

S₁ = {, a, a², a³, ..., a^t-1} hence S₁ S₂ = S₁

(b)

|S₂| = (1 string of length 0) + (3 string of length 1) + (9 string of length 2) + (27 string of length 3) + (81 string of length 4) + the following 3 strings of length 5: aaaaa, aaaab, aaaba; hence S1 S2 = , a, a², a³, a⁴, a⁵ .

1.1.8 A representation f of ^* for the i’th element in the canonically ordered set S^* can satisfy the following condition, according to the case.

(a)

f () = { the i’th element in the canonically ordered set {0,1}^* }

(b)

f () = { the i’th element in the canonically ordered set {1}^* }

1.1.9 i/j 1ⁱ01^j

1.1.10 For a given binary representation f ₁ take f ₂() = {1ⁱ0|i > 0}f ₁()

1.1.11

(a)

f () = {0}f ₁() {1}f ₂()

(b)

f () = {1^||0| in f ₁(), in f ₂()}

(c)

f () = {1^|₁|0₁1^|₂|0^₂...1^|_k|0^_k|k > 0, ₁, ..., _k in f ₁()}

1.1.12 Assume to the contrary the existence of a binary representation f. Denote by min{f ()} the binary string which appears first in the canonical ordering of f () . Assume an ordering on the real numbers ₁, ₂, ₃, ... such that _i precedes _j if and only if min{f (_i)} precedes min{f (_j)} in the canonical ordering of the binary strings. Then consider the real number whose k’th digit is different from the k’th digit of _k for all k > 1. It follows that min{f ()}, and hence f (), is not defined for .