Insights into Curry’s Paradox?
Hi,
I am trying to more precisely understand some ideas in mathematical logic and find myself drowning a bit in self referential formal logic and theorems by Lob, Tarski, Kripke, Godel…
Looking at Curry’s Paradox:
1) Let F be: “if this sentence is true then Santa exists”
2) Assume F is true.
3) Since F says “if F is true then Santa exists” and we have assumed F is true, Santa exists.
4) This proves F implies Santa exists; precisely F. So Santa exists by step 3.
It is obvious to me that the pathology is self reference (roughly the truth value of the sentence is a different kind of thing then the truth value within the sentence) but how would you be more precise?
I’m also interested in being more precise about self reference, godel, strange loops, systems trying to “escape” systems. They too often blend together as concepts in my mind when I think about, e.g., LLMs interpreting their own sparse autoencoders.
The problem is not self-reference: Quine’s paradox and Yablo’s paradox do not involve self-reference. The problem is undefinability of truth.
I think the first thing you need to learn properly is how arithmetization (Gödel numbering) works, and why it can encode sentences talking about provability of other sentences by their Gödel number, but not sentences talking about truth of other sentences by their Gödel number. Then the rest will be easy.
Hi.
Yablo’s paradox: beautiful, thanks for sharing that. Though, I want to argue that there is self reference there.
It plays on the classic “this is not true” self-reference paradox where T ⇒ F ⇒ T ⇒ F ⇒ (absurd)… and yet from what I see Yablo’s paradox has the same oscillating truth value form but instead of the direct circular dependency of “this is not true,” its chain of dependency is rolled out to infinity (by referencing all m>n for each iteration n). I know I am not using the most precise language and I may be misinterpreting some parts of mathematical logic, but does my argument track there?
No, the issue really is what I said. Because self-reference can also be legitimate: e.g. the proof of Gödel’s theorem involves a self-referential sentence saying “this sentence is not provable”. It can be encoded just fine by the diagonal lemma and causes no paradoxes. So in summary you see, self-reference but without trying to arithmetize truth → works fine. Trying to arithmetize truth, even without self reference → fails.
I’d repeat my advice to learn the nitty gritty (how a sentence about axioms and inferences can be encoded into a sentence about integers and prime factors etc) and get an intuition why some things work there and others don’t. It’s super valuable.
I usually revisit Gödel’s theorem every few years to get a better understanding, and thank you, the combination Gödel numbering + Tarski’s undefinability theorem made it quite intuitive.
Now I am wondering if there is a simple way to spot the sentences that are “arithmetizing” the truth within a formal system? So that one can spot that they are outside of the scope of this system and “non-legit”.
I will second that it’s best to learn the actual underlying mathematics.
However, self-referential truth predicates can also be legitimate: the sigma_n/pi_n truth predicates are respectively sigma_n/pi_n definable, for example, and can refer to themselves. The sigma_n/pi_n truth predicates seem to avoid paradox by being unable to refer to their own negations.
I also want to say that I think what Yablo’s paradox shows is that it’s possible to “hide” the self-reference by having the sentence refer not directly to itself, but instead to a logically equivalent sentence which is encoded slightly differently.
Edited to add:
I think the general form of Tarski’s undefinability of truth gives a pretty good list of conditions. It seems to be the combination of self-reference, negation, and truth predicate which gives paradox. But any two on their own are fine.
To explain what I mean with respect to Yablo’s paradox. Take a sentence defined so that (P <-> ~P). This is clearly a self-referential sentence. Suppose I instead defined a sentence (P <-> ~P’), where P’ is just P with a bunch of double negations randomly inserted into it. P doesn’t directly appear anywhere on the right-hand side in this case, but P is still contradictory, and it seems fair to say it is still self-referential.
In Yablo’s paradox, the only notable differences between each sentence in the sequence are the starting indices they use. However, the choice of indices in each sentence has no effect on its truth, and if we renumber all the sequences to start at 0, we are left with an equivalent set of sentences to the original. But renumbering them this way makes the self-reference very clear, because now each sentence in the sequence is identical!
Edited to add more, because I’m thinking too much about this:
I should maybe explicitly spell out the following argument. Whatever definition of self-reference we choose, it cannot rely on the sentence referring directly to its unmodified self, because that would rule out most practical cases of self-reference. For example, if n is the godel number of P, and (P <-> ~Provable_in_PA(n)), then P is the standard self-referential sentence from the incompleteness theorem, but it does not directly refer to itself (only indirectly using an encoding). Even if we accepted the encoded version as “the same” as the original, the proof of incompleteness would still work if n was modified to be the godel number of any other sentence P’, so long as P’ was provably (in PA) logically equivalent to P.
Given that, it seems to me that if we can show that the truth of a sentence depends on the falsity of another logically equivalent sentence, that should count as a self-referential paradox.
Finally, here is a perhaps a more rigorous approach to show the self-reference in Yablo’s paradox, since it’s not immediately clear that the renumbering to zero in my original argument is valid. Let S be Yablo’s sequence starting at 1, and Z be Yablo’s sequence starting at 2. There is a clear bijection between both of these sequences, simply by mapping S1 to Z1, S2 to Z2, etc. And by examining the logical structure of Yablo’s sequence, we can see that the choice of initial index has no effect on the truth of the first sentence in the sequence, so (S1 <-> Z1). But since Z1 is the same sentence as S2, we have (S1 <-> S2). We can apply this procedure to get that (S1 <-> Sn) for all n. Since (S1 <-> forall i>1 ~Si), we get (S1 <-> ~S1), which is a self-referential contradiction.
Got it thank you.
Arguably Yablo’s paradox requires a self-referential function.
No proof is actually allowed to use infinite statements. If you just defined the statements using individual axioms, there would be no contradiction since any finite subset of the theory is consistent.
To get a contradiction, you need a function S(n) = “forall i>n. not true(S(i))”.
Quine’s paradox doesn’t require self-reference tho, which is why like you said the truth predicate is the real problem!
Yablo’s clearly has flavors of self reference, but would you grant that Quine’s does too:
F: “yield falsehood when preceded by quotation” yields falsehood when preceded by quotation
I actually looked it up and it seems that Hofstadter argues exactly this: that Quine’s paradox involves “indirect self-reference” pathology in GEB. I can try to find the page.
Well, this is controversial. See e.g., Priest (1997) and Beall (2001).
https://www.jstor.org/stable/3328081
https://www.jstor.org/stable/3329231
Yeah, ok, I’m happy to split the difference and agree that the question is a philosophical one, to which no final answer shall ever be determined ;-)
Note that the liar’s paradox is just a special case of this, since “not A” is equivalent to “A implies ⊥”.
Here is a form of Curry’s paradox without self-reference (like Quine’s paradox).
Let C(“X”) = “X(‘X’) implies Y” is true
Lemma: C(“C”) implies Y
Proof: Assume C(“C”). By the definition of true, C(“C”) implies Y. Thus Y.
Theorem: Y
Proof: By the lemma, C(“C”) implies Y. By the definition of true, C(“C”). Thus Y.
I’ve drawn out my understanding of these below, in the hope that some thoughts that may be helpful. (Fwiw tracking in this level of detail is not yet easy for me! But I think I have made a good attempt.)
I think the basic thing to say is that self-reference is (generally) not a provided primitive! So anything anyone does that looks like self-reference is actually a construction that has to ground out in a finite and fully-unrolled sentence.
Here are my full thoughts though, others will hopefully correct me if anything I’m saying is misleading:
As you’ve sketched, you can prove that for any
That does mean that if you are working in a logical framework that lets you construct a sentence with this property, you would be in trouble!
In almost-python, the “proof” looks like:
def go[F, R](up: F → (F → R), down: (F → R) → F) → R:half: F → R = lambda f: up(f)(f)return half(down(half))(You may recognize this as a Y-combinator-y construction! If you invent some type
Fthat’s equal toF → R, you can then pass in the identity functionlambda f: fforupanddown. Thengowill build the resulting “R” by *checks notes* looping forever and never actually returning anything. Anyway.)But why can’t you generally say
We could see the definition
There are ways you can get (working) self-reference within this constraint. One way is that you can think of
T=>F=>T=>F…if you set R to something false, so there’s no fixed point to be had here.A different way you can build in self-reference (of sorts) is using quining. Quining lets you refer to the source code of
(I’m weakest on this part, someone may correct me:) Tarski’s undefinability of truth result says that consistent logical systems must not contain a general evaluator
Looking on from outside the system, we pick a “model” that is some way to assign true/false to every sentence that is consistent with what the system can prove to be true and false. Call this our truth function
There can be no general
This means our model of the truth value of the sentence
The reason Tarski’s result holds is exactly that it lets you build the self-reference chain. Because
This doesn’t rule out an
For instance a common use of
This means you can build sentences like
This means there are partial models of truth
As maybe a callback to
(Relatedly you can write things like “there exists some length of proof
I hope that’s helpful!
My main goal is to be more precise about mathematical logic and computability in general.
Llm recommended Spencer-Brown representational calculus for similar problems though I haven’t gotten around to looking into it yet.
As far as I understand, the current solution is to have the axiom set ensure that the sentence F is meaningless. For example, if we consider the naive set theory, then the set
To get a better understanding of the details of self-reference in mathematical logic, if you know how to code, I’d recommend looking at quines, and programming one yourself in your favorite language.
When made rigorous, sentences like “this sentence is unprovable” essentially translate to the sentence S = “the sentence output by the program P is unprovable”, where P happens to be a quine which outputs S. So if you understand quines, then you already understand the basic idea behind self-referential statements in logic.
It will probably help at first to simply take for granted that peano arithmetic is capable of talking about computer programs and their outputs. The specific details of how peano arithmetic can do this will sometimes be important, but you can get pretty far without knowing them.
I also don’t think it’s actually important to learn godel numbering specifically. If you understand how sentences can be encoded as ASCII which can be encoded as numbers, then you already understand the important part. Nonetheless, I will still refer to numeric encoding of a sentence as its “godel number”, because that is the standard word for it.
A truth predicate for PA would be any sentence T(x) in PA with one free variable x which, when x is substituted for the godel number of some other sentence S, is true if and only if S is true. In other words, for any sentence S, if n is its godel number, then (T(n) <-> S).
The paradoxes of self-reference come from combining self-reference, negation, and truth predicates. Tarski’s proof of the undefinability of truth makes essential use of all three. But any two of these on their own are fine: self-reference with negation are combined just fine in PA, and self-reference with truth predicates (but without negation) can also be combined just fine in PA, using sigma_n or pi_n formulas in the arithmetical hierarchy (where n>0).
Going back to Curry’s paradox, let’s assume we have a truth predicate T. Then curry’s sentence is the sentence S = (T(p) → Santa), where p is a quine which outputs the godel number of S. Note that (T(p) → Santa) is the same as (~T(p) OR Santa), so we can see that Curry’s paradox combines self-reference, negation, and a truth predicate.