IE: bounded to
Not quite, this would make a->a false.
Include a definition of <-> in the table, which a quote refers to later?
The definition of <-> in terms of previous can't be right, that's always 1 regardless of a and b. Also you missed the s in the formula for <->.
(Also it's kinda iffy that weak disjunction is a stronger statement than strong disjunction...)
The definition of <-> in terms of previous can't be right, that's always 1 regardless of a and b. Also you missed the vs in the formula for <->.
I don't think so? If we substitute things it ends up being (restricted to [0, 1]) which is a perfectly cromulent formula.
It was previously strong_disjunction(a->b,b->a) instead of weak_conjunction(a->b,b->a) :P.
(I wonder how one decides whether to use weak or strong conjunction there...)
(Also it's kinda iffy that weak disjunction is a stronger statement than strong disjunction...)
Yeah! I'm just going with what Wikipedia said there (unless I've made an error), but I had the same thought.
supremum: the least value which is greater than all the values in the set
Should be "greater than or equal to all the values in the set" or a closed interval like [0,1] has no supremum.
The story of 1/2, 1/4, ... could be continued immediately to the infinite case, right? (And all the way up the ordinal ladder.)
Instead of saying "This sentence doesn't have truth value 1, nor 1/2, nor 1/4, ..." (which, even if infinitely long, would only work for countably many truth values), you could simply say "This sentence has truth value 0", which is just as paradoxical, but the paradox also works for real-valued or hyperreal truth values.
Yeah, the logic still can't handle arbitrary truth-functions; it only works for continuous truth-functions. To accept this theory, one must accept this limitation. A zealous proponent of the theory might argue that it isn't a real loss, perhaps arguing that there isn't really a true precise zero, that's just a model we use to understand the semantics of the logic. What I'll say is that this is a real compromise, just a lesser compromise than many other theories require. We can construct truth-functions arbitrarily close to a zero detector, and their corresponding Strengthened Liar will be arbitrarily close to false.
Not sure exactly what you're getting at? I suppose you're imagining extending the sequence to ordinal values? We can do this, sure, and still can have the same issue with sup/inf not being well-defined.
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, here represents the Gödel code for sentence .
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.
Footnotes 3 and 4 do not refer to anything in the text.
Do 'transfinite natural number' and 'hyperfinite natural number' mean the same thing in this context?
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 ω-inconsistent.
We consider this abandonment too hasty. The success of Łukasiewicz logic lies in postulating "between values" of truth, starting at 12-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 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 ¬T is definable (not-true). This means a sentence λ exists such that:
λ⟺¬T(‘‘λ")
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 λ: 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 12. The Liar sentence, λ, is neither true (1) nor false (0), but instead gets the intermediate value, 12. Ł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. 14) 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 Ł∞ by defining the connectives as real-valued functions. Here, v(s) is the truth-value of a sentence s.
⊥
(falsehood)
a→b
(implication)
max(0,min(1,1−v(a)+v(b)))
IE: 1−(v(a)−v(b)) bounded to [0,1]
a∨b
(weak disjunction)
a∧b
(weak conjunction)
a⊕b
(strong disjunction)
¬a→b
a⊗b
(strong conjunction)
∀x.ϕ[x]
(universal quantification)
∃x.ϕ[x]
(existential quantification)
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 Ł∞, notice that a→b is 1 if and only if va≥vb. 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(s)
Does Ł∞ 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 γ, 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 12 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, an, starting with a0 defined as follows:
a0:=¬∀(n>0).T(an)
In words: a0 says that there exists some an that is false, for n>0.
For the rest, we define an:=an−1⊗a0. That is, the sentence an is the strong-conjunction a0 with itself, a total of n times.
What is the truth value of a0? 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 a0, we get that v(a0)=v[¬∀(n>0).T(an)]=1−infn>0v(an). Now, we branch into two possible paths, and derive contradiction from each.
Suppose v(a0)=1. Then because of the definition of strong conjunction, v(an)=max(0,v(an−1)+v(a0)−1)=max(0,v(an−1)+1−1)=v(an−1). This implies that the value of all the an is v(an)=1, which means its infimum is also 1. In conjunction with the semantics from the previous paragraph, we get that v(a0)=1−infn>0v(an)=1−1=0, which shows that a0 must be false and is different from the v(a0)=1 we started with!
Now assume the other branch, v(a0) is not completely true, that is v(a0)=1−δ for some δ>0. Then v(an)=max(0,v(an−1)+(1−δ)−1)=max(0,v(an−1)−δ). Applying this repeatedly we see that v(an)=max(0,1−n⋅δ), and so the infimum over all the sentences is 0. Next we substitute this into v(a0)=1−infn>0v(an)=1−0=1. This is also different from v(a0)=1−δ!
Clearly, all branches lead to the truth-value v(a0) 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 Ł∞-Peano arithmetic plus truth is inconsistent.[2]
But Ł∞-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:
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 a0 can get the value 1−ϵ. This seems promising: perhaps ϵ can be small enough that the sequence v(an) is never less than 1 by a positive real number, even though v(an+1) is always smaller than v(an).
The most direct route hits some difficulties. Infimum and supremum are not well-defined once we add infinitesimals. For example, consider the sequence 1,12,14,18... 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:
∫baxdx=limn→∞∑ni=1a+ib−an
Instead, an integral is defined directly as a sum:
∫baxdx=∑Ni=1a+ib−aN
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 ∀ and ∃ as minimum and maximum over a transfinite number ω of sentences. That's not much of a restriction compared to previously: ω 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 ω of sentences an, the previous attempt at proof no longer ends in a contradiction. The truth value of a0 used to be v(a0)=1−infn>0v(an), but with the new definition of ∀, it is v(a0)=1−min0<n≤ωv(an).
Consider now the second branch of the proof, where we guess that v(a0)=1−ϵ for some ϵ>0, and let's take an infinitesimal ϵ. Recall that v(an)=1−n⋅ϵ, so the minimum truth value of the an is obtained for v(aω)=1−ω⋅ϵ. Plugging this into the value for a0 we obtain that v(a0)=1−ϵ=1−(1−ω⋅ϵ). Solving for ϵ gives us the infinitesimal ϵ=1ω+1. So the truth value of a0 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 ω of elements only. This would limit the number of entities in the theory (i.e., the number of numbers) to at most ω. Or, it could be provable that there at most ω−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:
Because we have just restricted ∀ statements to be over transfinite amounts of elements, for example at most ω, this means that the sum can be defined for at most ω 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 ω, because the 'forall' statement that defines numbers can only be over at most ω 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 ω−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.
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.)
Restall's paper proves ω-inconsistency, which is a weaker flaw. However, ω-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.
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.
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.