Page 64

		§4.2.2 Lang Compared to TxtEx

		We cannot conclude from the mere fact that there are uncomputable scientists that TxtEx is a proper subset of Lang, for there are proper subsets of the class of all scientists such that every identifiable collection of languages is identified by some member of the subset (see Exercise 4-3, below). However, does follow from the fact that the computable scientists form a countable subset of the uncountable class of all scientists.3 This is explained by the following proposition.

		4.3 Proposition Let be any countable collection of functions from SEQ to N, and let . Then

		Proof: For each and each , define . For each define a collection of languages by:

		.

		Exercise 3-12 shows that for every , . We now demonstrate:

		4.4 No scientist identifies both and for .

		To prove 4.4, let and be given, with . Suppose that scientist F identifies . Then, F identifies . By Corollary 3.25, let  s  be a locking sequence for F on Li, N. Choose finite such that . Observe that . Extend  s  to a text T for Li,D. Then, since F converges on T to an index for Li,N. Thus, F does not identify Li,D and hence does not identify . This proves 4.4.

		It is easy to see that 4.4 implies 4.3 since there are uncountably many and each identifies at most one of the classes .

		4.5 Corollary . It will facilitate later developments to exhibit a specific collection of languages that falls in Lang — TxtEx.

		4.6 Definition Let K be the r.e., nonrecursive set defined on page 25. The collection of languages is denoted .

		3 The computable scientists are countable because the collection of machines that compute them is countable. In contrast, it is easy to see that the collection of all scientists — i.e., functions from SEQ to N — has the power of the continuum.