Goedel's Fixed Point Theorem

Question

Let's consider an arithmetic theory such as Peano Arithmetic. Suppose the Gödel codes of all the true sentences are even and all the false sentences are odd. Then, how can there be a fixed point for the predicate, $\phi(x)=$"x is odd."?

Answer 1

Turning my comments into an answer, the issue is that when you write

Suppose the Gödel codes of all the true sentences are even and all the false sentences are odd

you're making a very false assumption: that that situation can in fact occur with respect to a Godel coding system. In fact, the rest of your question is more-or-less the proof that this can't happen! Keep in mind that the diagonal lemma is not trivial; it doesn't apply to all functions from formulas to numbers, only to some. So the fact that this places restrictions on the possible behaviors shouldn't be a surprise.

---

Specifically, we have the following result:

(Tarski's undefinability theorem) Suppose $\mathscr{F}$ is an injective function from formulas to numbers such that the "substitution relation" $$\mathfrak{S}:=\{(l,m,n)\in\mathbb{N}^3: l\in ran(\mathscr{F})\wedge \mathscr{F}(\mathscr{F}^{-1}(l)[\underline{m}/x])=n\}$$ is definable in $\mathcal{N}$. Then $\mathscr{F}[Th(\mathcal{N})]$ is not definable in $\mathcal{N}$.

That's a lot of notation! Here's what it means:

• "Formula" means "first-order formula in the language of arithmetic," and "number" means "natural number."

• $\underline{n}$ is the numeral corresponding to $n$, e.g. $\underline{3}=(1+1)+1$.

• $\varphi[t/x]$ is the formula gotten from $\varphi$ by replacing all free occurrences of the variable $x$ with the term $t$.

So intuitively, $\mathfrak{S}(l,m,n)$ means "If we take the formula with code $l$ and substitute $m$ for the variable $x$, the resulting formula has code $n$." And it's not hard to see that we really lean on the definability of $\mathfrak{S}$ in proving the diagonal lemma for $\mathscr{F}$, when in fact $\mathscr{F}$ is a "reasonable coding system," so this matters.

Continuing on:

• "Definable" means what it usually does in model theory.

• $\mathcal{N}$ is the structure $(\mathbb{N};+,\times,0,1)$ (or anything "morally equivalent" to that).

• $\mathscr{F}[Th(\mathcal{N})]$ is the image under $\mathscr{F}$ of the theory of $\mathcal{N}$; or, more intuitively, the set of $\mathscr{F}$-codes of true sentences.