Can truth be defined by a 'same-level' language according to Tarski's undefinability theorem?

Question

I have been learning about Tarski's undefinability theorem. My current understanding is that you need a 'meta-language' to define truth in a language (let's call this language 'A'). But could the same definition of truth be achieved by using another language (B) of the same level as (A)? Or is a meta-language that 'talks about A' required?

Answer 1

The answer is arguably yes (to the title question). In the next two sections I'll give this positive argument; in the following section I'll give a rebuttal. Then I'll end with a rebuttal rebuttal, mostly because that sounds funny.

The problem here is that questions of this type are really hard to phrase precisely (indeed that's tightly bound up with why they're so interesting!), so I dont think there will be a totally satisfying answer one way or the other. But hopefully what I write below clarifies the situation sufficiently.

---

Let's first re-phrase Tarski's theorem to try to make it less mysterious. For simplicity, let's assume I'm working in the language of arithmetic: $\{0,1,+,\times, exp,<\}$, and looking at $\mathbb{N}$ (as a structure in this language in the obvious way).

Now one of the two pieces of philosophical meat in Godel's incompleteness theorem was his coding apparatus: a function $\ulcorner$$\cdot$$\urcorner$ from sentences in the language of arithmetic to natural numbers.

Tarski's theorem then says:

The set $$Truth_{arithmetic}:=\{\ulcorner \varphi\urcorner: \varphi\mbox{ is a sentence in the language of arithmetic which is true in $\mathbb{N}$}\}$$ is not a definable set in $\mathbb{N}$.

Note that I've said "not a definable set" instead of "not definable;" I want to shift attention from language to structure. A subset $X$ of some structure $\mathcal{A}$ is definable in $\mathcal{A}$ if there is some unary formula $\psi$ in the language of $\mathcal{A}$ such that $X=\{a\in \mathcal{A}: \mathcal{A}\models\psi(a)\}$.

Technically, what I've described above is "definability without parameters" - but this isn't an issue in our context, since every element of $\mathbb{N}$ is definable without parameters, so parameters are never useful in $\mathbb{N}$. See this old answer of mine for more details.

---

OK, so what?

Well, consider the language $\Sigma$ gotten by taking the language of arithmetic and adding a new unary predicate symbol $T$; and consider the $\Sigma$-structure $\mathbb{N}^*$, which is the same as $\mathbb{N}$ with the additional stipulation that we interpret $T$ as follows: $$T^{\mathbb{N}^*}=\{\ulcorner\varphi\urcorner: \mathbb{N}\models\varphi\}.$$

Now here's the key point: the set $True_{arithmetic}$ is definable in $\mathbb{N}^*$, namely by the formula $T(x)$. On the other hand, we also have the set of $\Sigma$-truths: $$Truth_\Sigma=\{\langle \theta\rangle: \theta\mbox{ is a sentence in the language $\Sigma$ which is true in $\mathbb{N}^*$}\}.$$ And the proof of Tarski's theorem for arithmetic translates immediately to this context, and shows:

The set $Truth_\Sigma$ is not a definable set in $\mathbb{N}^*$.

---

Note that the way we interpreted the new predicate was crucial: we could also consider the $\Sigma$-structure $\mathbb{N}^\circ$, gotten by "expanding" $\mathbb{N}$ to stipulate that $T$ holds of everything, and then we would not gain any additional expressive strength: $Truth_{arithmetic}$ is not definable in $\mathbb{N}^\circ$, and indeed every set definable in $\mathbb{N}^\circ$ is already definable in $\mathbb{N}$.

The point is that I've performed a bit of sleight-of-hand here: where did my new structure come from? In building $\mathbb{N}^+$ I made reference to $Truth_{arith}$, so I already had to have a definition of truth in order to produce this "low-level truth definer." That is, there is no obvious way to justify the existence of $\mathbb{N}^+$ without at some point falling back on the usual "higher-order" definition of arithmetic truth.

It's hard to argue whether this is an essential obstacle, but here is an important point: the structure $\mathbb{N}^*$ is meaningfully complicated in a precise logical sense. Specifically:

• While $\mathbb{N}$ has a computable copy (= an isomorphic structure with domain $\subseteq\mathbb{N}$ such that the set of true atomic sentences with parameters is computable) - namely, itself! - the structure $\mathbb{N}^+$ has no computable copy.

• In fact, it's worse than that: as long as $S$ is a computably axiomatizable theory (e.g. PA, ZFC, ...), then $S$ has a model which is low - that is, "close to computable" in a precise sense. By contrast, no copy of $\mathbb{N}^*$, or anything elementarily equivalent to it (= satisfying the same sentences), is low.

• Nor does $\mathbb{N}^*$ (or anything elementarily equivalent to it) have a copy computable from the halting problem, or the halting problem's halting problem, or any finite iterate of the halting problem.

Indeed, no structure which "defines arithmetic truth" can have a copy computable from any finite number of iterates of the Turing jump; there is a tight connection between definability in the language of arithmetic and the Turing jump. So there is a really big gulf here, and my cavalier definition of $\mathbb{N}^*$ seems, well, just plain rude.

---

OK, now let me rebut the rebuttal.

The issue isn't complexity of the set but complexity of the language; we don't need to care about computability theory today (much as it pains me). And when we set this aside, we see that there is a difference between "topical order" and "logical order;" the latter is both more fundamental and avoidable here.

Specifically:

• "Logical order" refers to order in the logical-language sense: there's first-order logic, second-order logic, third-order logic, …, "$\omega$th-order logic," … I'll also extend it to cover general increases in the fundamental strength of the underlying logic: e.g. infinitary first-order logic is of a "higher order" in a broad sense than usual first-order logic, even though it's definitely not second-order.

• "Topical order," by contrast, refers to the intention behind a theory in an arbitrary logical system. E.g. if I write down a list of axioms in a certain language and I'm trying to describe natural numbers and sets of natural numbers, that has "topical order" $2$; it's meant to be talking about second-order things. However, the ambient logic might still be first-order logic; so the theory has "high" topical order but "low" logical order. (Such theories are studied in reverse mathematics, including the very-confusingly-named theory Z$_2$="second order arithmetic," which despite the name is a theory in first-order logic.)

Now the point is that we can "provably define" arithmetic truth in a low-logical-order theory. Namely, ZFC is a first-order theory in the logical sense, but in a reasonable sense it proves that $\mathbb{N}$ and the set of all arithmetic truths exist (and it proves that they are defined by specific formulas). So we've defined arithmetic truth, in a sense, by increasing the topical order and not increasing the logical order.

What's wonderful here is that ZFC is still computably axiomatizable! We've dodged the obstacle above. This apparent paradox is resolved by noting that ZFC has many models whose notion of "arithmetic truth" is incorrect (e.g. in some models of ZFC, the sentence "ZFC is inconsistent" is thought to be an arithmetic truth!). So what we're doing here is really separating defining from computing, as well as logical order from topical order.