Abstract:^[1] 

Tarski's Undefinability Theorem showed (under some plausible assumptions) that no language can contain its own notion of truth. This deeply counterintuitive result launched several generations of research attempting to get around the theorem, by carefully discarding some of Tarski's assumptions.

In Hartry Field's Saving Truth from Paradox, he considers and discards a theory of truth based on Łukasiewicz logic, calling it the "most successful theory so far" (out of very very many considered by that point in the book) and enumerating its many virtues. The theory is discarded due to a negative result due to Greg Restall, which shows that a version of the theory with quantifiers must be $\omega$-inconsistent.

We consider this abandonment too hasty. The success of Łukasiewicz logic lies in postulating "between values" of truth, starting at $\frac{1}{2}$-valued sentences positioned precisely between true and false, and ending in the whole continuum of real values $[0,1]$. Why stop there? We propose a variant of the theory based on nonstandard analysis, which avoids Greg Restall's paradox by introducing truth values between the real numbers, such as $\frac{1}{ϵ}$.

Tarski's Theorem

Tarski investigated the subject of truth predicates. The idea is to have a $T(‘‘s")$ which is true if $s$ is a true sentence, and false otherwise. ($T$ is a function that acts on numbers, and  $‘‘s"$ is the Gödel encoding of $s$, a number which encodes the symbol string of $s$.)  This is formalized as Tarski's T-Schema. For each sentence $s$, we add this axiom to the formal system: 

$T(‘‘s")⟺s$

Working in classical logic, Tarski shows that T-Schema is incompatible with a technical assumption called the diagonal lemma. The diagonal lemma says that for any predicate $P(.)$ which is definable, we can construct a sentence $s$ such that the following holds:

$s⟺P(‘‘s")$

That is: $s$ says precisely "$P$ is true of $‘‘s"$". (This is equation is different from the previous schema, because it applies to any predicate $P$ instead of just $T$, but only some special $s$ rather than all sentences).

This sort of self-referential sentence might sound illegal, but a major part of Gödel's contribution in the proofs of his incompleteness theorems was to show that it is actually quite difficult to rule out: the diagonal lemma can be proven for most axiomatic systems of interest.

If the diagonal lemma is true, and if a predicate $T$ is definable which satisfies the T-schema, then it follows that $\neg T$ is definable (not-true). This means a sentence $\lambda$ exists such that:

$\lambda ⟺\neg T(‘‘\lambda ")$

This sentence is called the Liar. Informally, it says of itself "This sentence is not true."

Making use of the T-schema and classical logic, we can derive a contradiction from the existence of $\lambda$: if it were true, then it must be false; if it were false, then it must be true. Thus, Tarski formalized the classic Liar paradox.

We've reached a contradiction. The assumptions we made are not compatible. Which should we throw out?

Tarski concludes that $T$ must not be definable in the language. This is fine: there is no unitary notion of "truth" but only truth-for-a-language. Tarski's theorem shows that no language can contain its own truth predicate; instead, languages form a hierarchy. To talk about the truth of statements in one language, you must ascend to a "higher" language. For example, to talk about the truth predicate for Peano Arithmetic, we can work in Zermelo-Fraenkel set theory.

Not everyone was satisfied with this solution. The complaint is that this doesn't fit very well with the way we use "true" in natural language. At least naively, in English, we can ask "Is it true?" for any English sentence. Tarski's theory says that we shouldn't do that; we're mistaken. The argument for the Liar paradox just works, so we need to abandon our naive theory of truth.

This set off a line of research attempting to save the naive theory of truth. Typically, the hope is to keep the T-schema and the diagonal lemma, by abandoning classical logic.

We will focus on one particular logic that has been proposed.

Łukasiewicz Logic

A common response to the Liar paradox is to add a third truth-value to the language, which for the sake of foreshadowing we will call $\frac{1}{2}$. The Liar sentence, $\lambda$, is neither true (1) nor false (0), but instead gets the intermediate value, $\frac{1}{2}$. Łukasiewicz logic $Ł$ is one way (of many) to add extra truth-values. ${Ł}_2$ is regular classical logic, whereas ${Ł}_3$ has a third value intermediate between true and false.

Unfortunately, although this resolves the Liar paradox, ${Ł}_3$ is subject to another paradox, in which we construct a sentence which says of itself that it is neither true nor half-true. Again we are stuck with no consistent option: if the sentence is true or half-true, then it is completely false; but if it were completely false, it would be true.

We can add a fourth value (e.g. $\frac{1}{4}$) to try and solve this problem, but again we can apply the same general strategy (make a sentence which claims it is neither true, nor half-true, nor quarter-true). In general, this strategy for producing paradoxes is called the Strengthened Liar. ${Ł}_n$ is subject to a Strengthened Liar paradox so long as $n$ is a natural number greater than 1.

Fortunately, we can solve all Strengthened Liars by adding infinitely many truth values between 0 and 1.

Continuum-Valued Łukasiewicz Logic

I will describe the semantics of ${Ł}_{\infty }$ by defining the connectives as real-valued functions. Here, $v\left(s\right)$ is the truth-value of a sentence $s$.

In case you're not familiar, "inf" takes the infimum of a set of values: the greatest value which is less than or equal to all the values in the set. Similarly, "sup" takes the supremum: the least value which is greater than or equal to all the values in the set. When working with the real numbers, infima and suprema are guaranteed to exist. (This is why it makes sense to use the real numbers here, rather than, say, the rational numbers.)

You'll notice that disjunction and conjunction have split into weak and strong versions. It turns out that Łukasiewicz logic is a special case of Linear Logic, if you're familiar with that. I recommend reading Affine Logic for Constructive Mathematics by Michael Schulman if you want to get some intuitions for what a logic like this might be useful for (aside from a theory of truth).

Łukasiewicz logic is also a fuzzy logic. Indeed, "fuzzy logic" just means that we take truth-values to be real numbers in the range $[0,1]$ and define the values of connectives through real-valued functions such as those above.

Fuzzy logic is typically applied in cases where statements have "degrees of truth", but in a way that is not readily interpreted as probability. You might be asking: but what does it mean for something to be partially true?? One natural interpretation is vague statements, such as "that box is small". In the context of ${Ł}_{\infty }$, notice that $a\to b$ is 1 if and only if $v_a\ge v_b$. I imagine this as "Oh, if box A is small, box B is definitely small!". In other words, the standards of truth are vague, but (where Łukasiawicz logic applies well) those standards are always comparable. We might not be able to say whether a box is objectively small (given all the facts), but there is a fact of whether one box is smaller than another.

To all the operators above, we want to add a $T$ which obeys the T-schema. We define this very simply:

$v(T(‘‘s"))=v\left(s\right)$

Does ${Ł}_{\infty }$ solve all paradoxes? That is: is it actually consistent with a self-referential truth-predicate obeying the T-schema?

We do get the following positive result. So long as we have a finite collection of sentences, we can apply Brouwer's fixed point theorem to find a consistent assignment of truth-values for those sentences. I'll illustrate the idea with some examples.

Here's the Liar paradox:

And a Strengthened Liar $\gamma$, which can be defined by "adding to itself" (strong disjunction) before negating:

No matter how you draw the blue line, so long as it is continuous, you can't escape intersecting with the red dotted line at some point. Thus, we can always find a consistent solution. A similar observation applies to finite sets of sentences.

However, it does turn out that we can run into some trouble when infinitely many sentences are involved.

Restall's Theorem

We introduced Łukasiewicz logic to be able to assign a truth value of $\frac{1}{2}$ to the Liar sentence, and avoid paradox. As it turns out, Łukasiewicz logic plus the Peano axioms can contain Peano arithmetic without contradictions. Perhaps we can define a Truth predicate for Łukasiewicz logic? 

Unfortunately, no. It turns out that adding a version of Tarski's T-schema to Łukasiewicz-Peano also results in a paradox, as Greg Restall showed in 1994. 

Restall constructs an infinite sequence of sentences, $a_n$, starting with $a_0$ defined as follows:

$a_0:=\neg \forall (n>0).T\left(a_n\right)$

In words: $a_0$ says that there exists some $a_n$ that is false, for $n>0$.

For the rest, we define $a_n:=a_{n-1}\otimes a_0$. That is, the sentence $a_n$ is the strong-conjunction $a_0$ with itself, a total of $n$ times.

What is the truth value of $a_0$? We will show there is no value that is consistent with this construction, by contradiction.

Proof: We start by applying the recursive definition of the truth-value $v$ to the straightforward formula of $a_0$, we get that $v\left(a_0\right)=v\left[\neg \forall \right(n>0).T(a_n\left)\right]=1-{inf}_{n>0}v\left(a_n\right)$.  Now, we branch into two possible paths, and derive contradiction from each.

Suppose $v\left(a_0\right)=1$. Then because of the definition of strong conjunction, $v\left(a_n\right)=max(0,v(a_{n-1})+v(a_0)-1)=max(0,v(a_{n-1})+1-1)=v\left(a_{n-1}\right)$. This implies that the value of all the $a_n$ is $v\left(a_n\right)=1$, which means its infimum is also 1. In conjunction with the semantics from the previous paragraph, we get that $v\left(a_0\right)=1-{inf}_{n>0}v\left(a_n\right)=1-1=0$, which shows that $a_0$ must be false and is different from the $v\left(a_0\right)=1$ we started with!

Now assume the other branch, $v\left(a_0\right)$ is not completely true, that is $v\left(a_0\right)=1-\delta$ for some $\delta >0$. Then $v\left(a_n\right)=max(0,v(a_{n-1})+(1-\delta )-1)=max(0,v(a_{n-1})-\delta )$. Applying this repeatedly we see that $v\left(a_n\right)=max(0,1-n\cdot \delta )$, and so the infimum over all the sentences is 0. Next we substitute this into $v\left(a_0\right)=1-{inf}_{n>0}v\left(a_n\right)=1-0=1$. This is also different from $v\left(a_0\right)=1-\delta$!

Clearly, all branches lead to the truth-value $v\left(a_0\right)$ being something different than which it started. Thus, even in a world of fuzzy logic, there cannot be a well-defined truth-value $v$: the theory of ${Ł}_{\infty }$-Peano arithmetic plus truth is inconsistent.^[2]

But ${Ł}_{\infty }$-truth is very nice

In his book Saving Truth from Paradox, after an extensive review of many different theories of self-referential truth, Hartry Field suggests that the theory based on Łukasiewicz was the most successful considered:

In some ways the most successful theory we've considered so far is the Lukasiewicz continuum-valued logic for the quantifier-free fragment of the language (but with self-reference allowed by non-quantificational means). Like the Kripkean theory KFS in Kleene logic, but unlike all the broadly classical theories, it allows the full Intersubstitutivity Principle: $\text{True}(⟨A⟩)$ is everywhere intersubstitutable with $A$ (and the analogous principle for 'true of' holds as well). But unlike KFS, it has a reasonable conditional; in particular, this allows it to contain all instances of the Tarski schema 

(T) $\text{True}(⟨A⟩)\leftrightarrow A$

(and the analogous schema for 'true of'). The logic comes with a pleasing model-theoretic semantics, in which all connectives including the '$\to$' are treated "value-functionally"—that is, sentences are assigned values merely on the basis of the values of their immediate components. $\text{True}(⟨A⟩)$ always gets assigned the same value as $A$, which explains why the two sentences are intersubstitutable. Also, the values are ordered, with a conditional getting value 1 if and only if the value of the antecedent is less than or equal to that of the consequent; this together with the fact that $|\text{True}(⟨A⟩)|=|A|$ explains why all instances of Schema (T) hold. I've been speaking of 'true', but the point extends to 'true of' and related notions. In short, the naive theory of truth, truth-of, etc. in a sentential logic based on continuum-valued semantics would be a very nice theory, if only it could be generalized to apply to the full quantificational language without generating inconsistencies, or $\omega$-inconsistencies, or non-conservativeness (in the same sense of conservativeness employed in Section 3.3), or anything similarly unpleasant.

Hartry Field proceeds to construct his own theory, inspired by the virtues of Łukasiewicz logic, but unfortunately much more complex. Our contention in this essay is that Field gave up too soon. The go-to strategy, when it comes to Łukasiewicz logic, should be to respond to paradoxes by adding even more truth values!

Infinitesimal Truth

In particular, we have in mind adding an infinitesimal value $ϵ$, so that Restall's paradoxical sentence $a_0$ can get the value $1-ϵ$. This seems promising: perhaps $ϵ$ can be small enough that the sequence $v\left(a_n\right)$ is never less than 1 by a positive real number, even though $v\left(a_{n+1}\right)$ is always smaller than $v\left(a_n\right)$.

The most direct route hits some difficulties. Infimum and supremum are not well-defined once we add infinitesimals. For example, consider the sequence $1,\frac{1}{2},\frac{1}{4},\frac{1}{8}...$ What is the infimum of this sequence? Within the reals, the infimum would have been 0, as it is the largest number that lower-bounds the sequence. But the infinitesimal $ϵ$ is greater than 0 and less than all the numbers in the sequence, so it has a better claim. This doesn't work either, however: $2ϵ$ is even greater, and still less than all the listed numbers. We can keep going higher forever without exceeding any number in the sequence, so there's no infimum.

To resolve this problem, we will utilize the notion of infinitesimal from nonstandard analysis.

Nonstandard Analysis

Newton and Leibniz originally formulated calculus with infinitesimals. Modern calculus textbooks instead reformulate everything by building up from the concept of limits. Nonstandard analysis resurrects infinitesimals using model theory.

The standard model of the real numbers can only be pinned down with second-order logic. However (due to Gödel's incompleteness results!) there is no complete and consistent inference system for second-order logic. Any axiom system we use to reason about real numbers is equivalent to a first-order axiom system (which has a complete inference system, but which does not uniquely pin down the standard model of the real numbers).

Nonstandard analysis exploits this fact to treat infinitesimals as nonstandard reals, which satisfy all the first-order facts about real numbers, while being simultaneously above zero and less than all positive (standard) reals. This yields the hyperreal numbers.

Nonstandard analysis also takes advantage of nonstandard natural numbers called hyperfinite numbers. For example, we don't define an integral in the usual way as a limit of finer and finer sums:

${\int }_a^{b}xdx={\text{lim}}_{n\to \infty }{\sum }_{i=1}^{n}a+i\frac{b-a}{n}$

Instead, an integral is defined directly as a sum:

${\int }_a^{b}xdx={\sum }_{i=1}^{N}a+i\frac{b-a}{N}$

Here, $N$ is a hyperfinite number: a nonstandard number which is larger than all the standard natural numbers, but obeys all the first-order properties of natural numbers.

This provides the inspiration for our approach to quantifiers.

Hyperfinite Quantification

As we argued earlier, if we are going to use hyperreal numbers, we can't keep our definition of quantification as inf and sup because those operations aren't well-defined for hyperreals.

For this reason, we need to redefine $\forall$ and $\exists$ as minimum and maximum over a transfinite number $\omega$ of sentences. That's not much of a restriction compared to previously: $\omega$ is larger than all the natural numbers, so we can have an unbounded number $N$ of sentences, we just cannot have infinitely many of them.

With a transfinite number $\omega$ of sentences $a_n$, the previous attempt at proof no longer ends in a contradiction. The truth value of $a_0$ used to be $v\left(a_0\right)=1-{inf}_{n>0}v\left(a_n\right)$, but with the new definition of $\forall$, it is $v\left(a_0\right)=1-{min}_{0<n\le \omega }v\left(a_n\right)$. 

Consider now the second branch of the proof, where we guess that $v\left(a_0\right)=1-ϵ$ for some $ϵ>0$, and let's take an infinitesimal $ϵ$. Recall that $v\left(a_n\right)=1-n\cdot ϵ$, so the minimum truth value of the $a_n$ is obtained for $v\left(a_{\omega }\right)=1-\omega \cdot ϵ$. Plugging this into the value for $a_0$ we obtain that $v\left(a_0\right)=1-ϵ=1-(1-\omega \cdot ϵ)$. Solving for $ϵ$ gives us the infinitesimal $ϵ=\frac{1}{\omega +1}$. So the truth value of $a_0$ is infinitesimally close to, but distinct from 1!

Discussion. Is truth actually inside the theory?

We have shown that the previous way of proving the inconsistency of a Truth predicate with Peano Arithmetic, does not go through in nonstandard-valued Łukasiewicz logic. On the surface, it looks like we have provided an example of a theory that can contain a Truth predicate without contradictions!

This might well be the case. But it could also be the case that we have just provided a recipe for an ordered infinite set of Ł-PA theories, each of which can only express the truth predicate of those smaller than itself–but not itself.

This is not a proof or a rigorous argument, we're just gesturing at the problem. The problem is that, in this new theory, quantifiers are over a transfinite number $\omega$ of elements only. This would limit the number of entities in the theory (i.e., the number of numbers) to at most $\omega$. Or, it could be provable that there at most $\omega -1$ numbers, in which case the theories would shrink.

Consider the two axioms of PA which are essential to defining addition, from Restall's paper:

1. $\forall x.(x+0=x)$ (the number zero is the neutral element of addition)
2. $\forall x.\forall y.(x+Sy=S(x+y\left)\right)$ (define addition in terms of Succession of numbers)

Because we have just restricted $\forall$ statements to be over transfinite amounts of elements, for example at most $\omega$, this means that the sum can be defined for at most $\omega$ total numbers. The resulting theory is therefore different than Peano Arithmetic, it has fewer numbers. In Peano Arithmetic, there can be infinitely many number lines of "nonstandard numbers", all larger than the standard numbers which start at 0; but now there can be at most $\omega$, because the 'forall' statement that defines numbers can only be over at most $\omega$ elements.

Even if this is true, it would still be the case that the theory can express the number of elements that can be in its 'forall' statements. However, it is possible that something about how numbers are derived makes it so that there are at most $\omega -1$ (or fewer) numbers. In that case, the number to express the maximum amount of entities that can be inside a quantifier does not even exist in the theory itself, which is ironic.

1. ^{^}

   Why care about formal theories of truth?

   This article is mostly for fun, but I (Abram) do see a potential application for AI safety. One sub-problem of AI safety is interpretability: figuring out what an AI is thinking about. In order to thoroughly address this question, it may be necessary to adopt a theory of meaning/semantics/referentiality: how do we reason in general about what something is "about"?

   The concern is that attempts to formulate a theory of semantics robust enough to inform interpretability efforts could run head-first into Tarski's Undefinability Theorem, which shows (under some assumptions) that it is impossible for any theory $S$ of semantics to work for $S$ itself. Naively, what this suggests is that humans can only interpret what an AI is thinking about if the AI is (in a semantic sense) less capable than the humans.

   Tarski's Undefinability Theorem launched a literature on trying to get around the theorem, which is what we are engaging with here. A successful theory of this sort could be relevant to a theory of interpretability which applies to AI systems which are as capable as humans. (We don't claim that the current proposal is necessarily the right one for such an application, although we do think it has some nice features.)

2. ^{^}

   Restall's paper proves $\omega$-inconsistency, which is a weaker flaw. However, $\omega$-inconsistency contradicts the semantics we gave for quantifiers, based on infimum and supremum. So, we can accurately say that the assumptions we've made are inconsistent.

3. ^{^}

   These theories are typically developed within the domain of arithmetic, which means that in order to talk about sentences, we need to choose a way to encode sentences as numbers. This is now standard practice in computer science (where everything is encoded as binary numbers), but Gödel introduced the idea in this context, so we call the practice Gödel encoding. The current essay uses regular quotes to represent this, for familiarity. Hence, $‘‘s"$ here represents the Gödel code for sentence $s$.

4. ^{^}

   Though slightly weaker systems that prove their own consistency exist: self-verifying theories. These might still have a lot of the theorems that we know and love.