In the late 30′s Tarski proved that arithmetical truth cannot be defined in arithmetic. In the next few updates I’m going to be discussing Tarski’s Undefinability theorem and will follows chapter 4 of Hinman’s Fundamentals. Check this earlier note if you want to get clear on the definability we’re talking about.
Below are some of the basic assumptions about definability and the standard model of arithmetic that will factor into the proof of Tarski’s theorem.
(i) Every effectively computable function is definable over .
(ii) Every decidable set is definable over .
(iii) Every effectively countable set is definable over .
In the next update I’ll break down each of these assumptions and hopefully move into the theorem itself. The point of all this is just to be able to get through Hellman’s example of determination without reduction using a corollary of the undefinability theorem.