Limits of Logic #5: Truth Is Undefinable

26 Jul, 2024

I think Limits of Logic is an excellent presentation of important results in logic, and at minimum, it is possible to work through it as an undergraduate Philosophy student.

But the results presented in the text are far too beautiful and fascinating to only be accessible via a formal university education in Philosophy.

I would really like to make these results accessible, in a reasonably rigorous manner, for the reader who may know of Godel's Incompleteness Theorem from a YouTube video, or may have only heard some nerd claim how "Math is Incomplete!" back in school. At best, I'd like to create a presentation that makes even the math/numbers/symbols care.

I believe that the intuition for these results can be communicated simply.

This is a big task for someone like myself; it has been a few years since I've dealt with these ideas in an academic setting. But after diving back into the pool with a first reading of Limits of Logic, my gut says that I can do it.

In fact, I think this is the only way that I will truly absorb the intuition behind these results.

I think a good proof of concept would be to explain Tarski's theorem about the undefinability of truth -- that there is no single "formula" that can churn out true sentences.

Here, I begin this proof of concept project by giving the proof of Tarski's theorem, but without background, in order to trace back from this proof and figure out what one really needs to know in order to grasp this proof.

Exercise 6.7.2 (Tarski's Theorem)

Show that the set of sentences that are true in the standard string structure $𝕊$ is not definable in $𝕊$ .

Proof:

"Diagonlisation" or "self-application" is a syntactic operation that is definable in $𝕊$ .

Therefore, we can consider $𝕊_{d i a g}$ which is the definitional expansion of $𝕊$ with a function symbol diag $(x)$ such that: $[$ diag $(A (x)]_{𝕊} = A < A (x) >$ .

Let $F (x)$ be any formula in the language of strings $𝕊$ . So, $F ($ diag $(x))$ is a formula in the expanded language $𝕊_{d i a g}$ .

Let the formula $H (x)$ in $𝕊$ be the translation of the formula $F ($ diag $(x))$ in $𝕊_{d i a g}$ .

Consider the sentence $G$ (in the language $𝕊$ ) which is the self-application of $H (x)$ such that $G = H < H (x) >$ .

Since $H (x)$ in $𝕊$ is the translation of $F ($ diag $(x))$ from the expanded language $𝕊_{d i a g}$ we know that $G = H < H (x) >$ has the same truth values as $F ($ diag $< H (x) >)$ .

That is, $G$ is true iff $F ($ diag $< H (x) >)$ is true in $𝕊_{d i a g}$ .

But $[$ diag $< H (x) >]_{𝕊_{d i a g}} = H < H (x) >$ .

Therefore, we have that $G$ is true iff $F (G)$ is true in $𝕊_{d i a g}$ for any formula $F (x)$ .

Now assume for contradiction that truth is definable. That is, there is a formula $T r u e (x)$ in $𝕊$ that picks out the set of all and only those sentences which are true. Now if $T r u e (x)$ is a formula, then so is $\neg T r u e (x)$ .

But then, $G$ is true iff $\neg T r u e (G)$ is true, which is a contradiction.

Therefore, there cannot be any such formula $T r u e (x)$ in $𝕊$ that picks out the set of all and only those sentences which are true.

And hence, the set of sentences that are true in the standard string structure $𝕊$ is not definable in $𝕊$ . $∎$

Here's what comes to mind in terms of what needs to be explained to someone to let them grasp this proof:

What is a structure? Why think in terms of structures?
What is the string structure $𝕊$ ?
Why use the string structure to reason about truth?
What is sentence and formula?
What is self-application? Prove that it is a definable operation in the string structure.
What is a definitional expansion of a structure?
You can translate a formula in an expanded structure to an equivalent formula in the original structure.
What is truth in structure? Is this a good representation of truth as we understand it?
What is definability in a structure? Why should one care about this notion?

I'm sure the list is longer, but this is a good place to start.