Page 192

		8-20 Prove Proposition 8.24

		Hint: First consider the case i = 1. For a function f, define . Let

		.

		Show that . For i > 1, modify the definition of Sf appropriately.

		8-21 Prove Proposition 8.25

		8-22 Prove Proposition 8.26

		Hint: First consider the case j = 0. Suppose a rearrangement-independent scientist M is given. For , consider any text G that is 2i imperfect for f. For each x, y, z such that , assume without loss of generality that . Note that this implies there are at most i noisy elements in G. First show that if for some D of cardinality i and for some n1 and n2 with n1 < n2 we have

		for each with cardinality i, there is a with such that is a locking sequence for M on content(G) - D - D';

		then, either

		(i) there exists a noisy element in content(G[n2]) - content(G[n1]), or

		(ii) for some with cardinality i, , where is as above, is a program for f.

		Next, use the above facts to obtain, in the limit, a finite set of programs, one of which is a program for f.

		8-23 Prove: .

		8-24 Prove: .

		8-25 Prove Proposition 8.46.