Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

5.1 Arithmetical Hierarchy > 5.1 Arithmetical Hierarchy - Pg. 110

110 Computability Theory And so forth and so on. (This table emphasizes that for any fixed k and n, there are only countably many n k-ary relations and only countably many n k-ary relations. The last line in the table shows that each 3 relation has the form (n+2) {x | zyt T (e, x, y, z, t)} for some e. Taking the various possible values of e e = 0, e = 1, e = 2, . . . we get a complete list, with repetitions, of all the 3 k-ary relations. Moreover, because a countable union of countable sets is countable, we can go a step further and say that only countably many relations can be in the arithmetical hierarchy at all. Because PN (the power set of N ) is uncountable, there is a sense in which "most" relations fall outside the arithmetical hierarchy. See Appendix A2 for a summary of facts about countable sets.) An advantage to having such "normal form" results is that we can diagonalize out of them. Recall that when we wanted a 1 set that was not 1 , we used the set K defined by the condition x K [[x]](x) t T(x, x, t). Imitating this construction, define the 2 set S by the condition