5 Connections to Logic In this chapter, 1 we want to connect concepts of computability with concepts of defin- ability. The idea of definability comes from logic. Roughly speaking, one can specify a language and then study what sets or relations might have exact definitions that can be formulated in that language. In our case, we will take a language for the arithmetic of natural numbers (that is, number theory). One goal will be to show that every computable set is definable in this language. This connection between computability and definability has some interesting con- sequences. For one, it will show that the set of true sentences of arithmetic is very far from being a computable set. And for another, we will come to G odel's (first) incom- ¨ pleteness theorem. This theorem says that starting from any computable set of true axioms, one cannot possibly hope to derive all the true sentences of arithmetic. Historically, G odel's incompleteness theorem (1931) preceded by five years the ¨ beginnings of computability theory. But there is an advantage to running history back- wards and looking at G odel's theorem from the point of view of computability theory. ¨ First, however, we want to build on our characterization of recursively enumerable sets as being the 1 sets. The notation " 1 " already suggests that there ought be a