## Archive for the ‘Models of Arithmetic’ Category

### Assumptions On Definability Over The Standard Model Ω, Part 2

September 11, 2010

So we set out the basic assumptions about definability over $\Omega$ that factor into the proof of Tarski’s theorem.  Let’s go over each one to get clear on all the definitions.

(i) Every effectively computable function $\textup{F}: \omega \rightarrow \omega$ is definable over $\Omega$.

A function $\textup{F}: \textup{X} \rightarrow \textup{Z}$ is effectively computable if, and only if, there is an effective procedure such that, for any $x \in \textup{X}$ the procedure calculates the value $\textup{F}(x)$.  The claim is that every such function defined on the natural numbers is definable in the standard model.

(ii) Every decidable set $\textup{X} \subseteq \omega$ is definable over $\Omega$.

A subset $\textup{A} \subseteq \textup{X}$ is decidable if, and only if, the property $\mathcal{P}$ defined as $(\mathcal{P}(x): \Longleftrightarrow x \in \textup{A})$ is decidable in $\textup{X}$.  And a property $\mathcal{P}$ defined over a set $\textup{X}$ is decidable in $\textup{X}$ if, and only if, there is an effective (or decision) procedure for deciding, for any $x \in \textup{X}$ whether or not $\mathcal{P}(x)$ holds.  Here the claim is straightforward, every such set of natural numbers is definable in the standard model.

(iii) Every effectively countable set $\textup{X} \subseteq \omega$ is definable over $\Omega$

Finally, a set $\textup{X}$ is effectively countable if, and only if, $\textup{X}$ is empty or there is an effectively computable function $\textup{F}: \omega \rightarrow \textup{X}$ that counts $\textup{X}$ (i.e., $\textup{X}$ is the image of $\textup{F}$, $\textup{X} = \mathsf{Im}(\textup{F}) := \{\textup{F}(n): n \in \omega\}$). So, what’s being assumed here is that the effectively countable subsets of the natural numbers are definable in the standard model.

Just a few more definitions and we can get into Tarski’s theorem.  In the next update I’ll define the set of indices for the theorems of $\Omega$ as well as a diagonalization function that will play a role in the proof.

### Assumptions On Definability Over The Standard Model Ω, Part 1

September 10, 2010

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 $\textup{F}: \omega \rightarrow \omega$ is definable over $\Omega$.

(ii) Every decidable set $\textup{X} \subseteq \omega$ is definable over $\Omega$.

(iii) Every effectively countable set $\textup{X} \subseteq \omega$ is definable over $\Omega$.

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.