2

I've been reading Peter Smith's Intro to Godel's theorem but I cannot understand how diagonalization works in Tarski's theorem of inexpressibility of truth.

The mentioned Carnap's equivalence is of the form γ⟺φ(⌜γ⌝), where φ(x) is any wff of the language with one free variable. One common interpretation I've seen regarding this equivalence is that γ is saying about itself having certain property.

Smith's explanation uses this equivalence, but instead it is applying to a negated truth predicate.

  1. How come Smith could apply the equivalence to a negated truth predicate? As far as I understand the equivalence can only be applied to a predicate with no additional logical operator.

  2. Isn't this theorem just a variant of the Liar paradox? But as far as I understand no one talks about this theorem being related to the Liar, so what's the difference?

enter image description here

Constantly confused
  • 834
  • 5
  • 15
  • Negation is not an "operator", it is just a connective that can be used to form wff along with all other connectives and quantifiers. And undefinability of truth is routinely linked to the Liar paradox, see e.g. [IEP, Tarski’s Undefinability Theorem](https://iep.utm.edu/par-liar/#SH1c). – Conifold Oct 09 '21 at 23:49

2 Answers2

3

1. You wrote yourself:

γ⟺φ(⌜γ⌝), where φ(x) is any wff of the language with one free variable.

¬TA(x) is a wff of the language with one free variable. φ(x) doesn't have to be an atomic formula.

2. In a sense, yes. What Tarski shows here is that, because of the liar paradox, a formal language cannot have a truth predicate that applies to sentences of that language. Here is what the SEP entry on self-reference says on this:

Tarski showed that the liar paradox is formalisable in any formal theory containing his schema T, and thus any such theory must be inconsistent. This result is often referred to as Tarski’s theorem on the undefinability of truth. The result is basically a formalisation of the liar paradox within first-order arithmetic extended with the T-schema.

E...
  • 6,436
  • 4
  • 20
  • 39
  • -1: Wasn't it Goedel that said he translated the liar's paradox into formal logic and not Tarski? – Mozibur Ullah Oct 10 '21 at 01:24
  • 1
    @MoziburUllah Yes, Goedel also makes use of the liar's paradox, but that has nothing to do with my answer. I didn't say Tarski was the only one who did it. There are several other connections, by the way, between Tarski's and Goedel's theorems. Also, my answer quotes the Stanford Encyclopedia of Philosophy on this. I don't know if you are suggesting that they are wrong, or what. But there's really nothing else I can add here. – E... Oct 10 '21 at 03:27
  • No, but it does have a great deal with the relationship between Goedel & Tarski. According to Wikipedia entry on Tarski's Undefiniability Theorem on the undefinability of arithemetical truth, Goedel actually proved the undefinability theorem the year before actually proving his incompleteness theorems in 1931 and "well before" Tarski proved the same in 1933. This coupled with his use of the Liar's paradox is, I put it, kindof suspicious. There are examples of independent discoveries ... but it looks as though Tarski was led to it already by Goedel's work. – Mozibur Ullah Oct 10 '21 at 03:58
  • @Eliran Thank you for your reply; but if φ(x) doesn't have to be an atomic formula, then wouldn't we be able to prove some weird results? The diagonization lemma says that 'If a theory T is consistent, p.r. axiomatized and extends Q, then there is a sentence γ st T proves γ⟺φ(⌜γ⌝)'. If we take φ(x) to be an arbitrary predicate (doesn't have to be the truth predicate), then it seems that T will prove both γ⟺φ(⌜γ⌝) and γ⟺¬φ(⌜γ⌝). Obviously this goes against the assumption that T is consistent, but this seems to just follow from the lemma. What am I doing wrong? – Constantly confused Oct 10 '21 at 04:15
  • 1
    @Constantlyconfused For every formula φ there is a γ such that T proves γ⟺φ(⌜γ⌝), yes, but it doesn't have to be the same γ for every φ, which is what you are assuming. – E... Oct 10 '21 at 04:21
  • @Eliran Ah yes of course, stupid me! Thank you so much – Constantly confused Oct 10 '21 at 04:23
  • 1
    If one ponders deeper, it's really the *fixed point* property linking Tarski's undefinability of truth within first order theories of arithmetic to liar paradox, *self-reference* itself is moot. For example, "This sentence is true." is ungrounded thus its truth value is undecidable but unparadoxical (no logical antimony) at all per Kripke. And this sentence is clearly consistent as it can only be expressed as L⟺T_A(⌜L⌝) from OP's above section. – Double Knot Oct 11 '21 at 02:30
2

You might find it worth looking through Yanofsky's A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points which is available on the arxiv and is an exposition of Lawvere's 1969 paper where he used the language of category theory:

to describe many of the classical paradoxes and incompleteness theorem's in a categorical fashion.

Including:

  1. Cantor's theorem
  1. Russell's Paradox
  1. The non-definability of satisfiability
  1. Tarski's non-definability of truth
  1. Goedel's First Incompleteness Theorem

Note, that the firsrlt ecample, Cantor's Theorem, is the well-known classical theorem that use's diagonalisation argument which the cardinality of the integers is strictly less than the cardinality of the continuum. Moreover, although Tarski is conventionally given credit for the theorem of the non-definability of (arithmetical) truth, it was Goedel that discovered it, three years before Tarski did and actially before he proced his incompleteness theorems.

Mozibur Ullah
  • 1
  • 14
  • 88
  • 234
  • Gosh I really do not like category theory haha, that course was one of the stressful experiences I've had. But from the looks of it, is this paper about an underlying structure about all these? Incidentally, Graham Priest also discussed this and called the underlying structure Qualified Russell's Schema/Inclosure Schema, which as the name suggests, originates from Bertrand Russell – Constantly confused Oct 10 '21 at 04:25
  • @Constantly confused: Yes, it is about the underlying structure to the theorem's listed. This is useful as whilst many authors have spotted the resemblence between them, this was not made explicit until Lawvere's work. Yanofsky's paper is an exposition and so it's written to be understood by a wide audience that is mathematically mature whereas Lawvere's original paper is written for specialist's in category theory. I don't understand why you have brought up Graham Priest's work in this context. His work has nothing to do with what I'm talking about - and furthermore ... – Mozibur Ullah Oct 10 '21 at 04:32
  • @constantly confused: ... nothing to do with what you were originally asking. It's a non-sequiter which is confusing the issues under discussion here. – Mozibur Ullah Oct 10 '21 at 04:34
  • @constantly confused: Can you explain why you did so? I mean, what relevance it has? – Mozibur Ullah Oct 10 '21 at 04:35
  • If this is about the resemblance between all of them, then this has probably already been discussed by Russell before Lawvere, as suggested by Priest. – Constantly confused Oct 10 '21 at 04:39
  • 1
    @Constantly confused: I've already mentioned that "many authors have spotted the resemblence between them" without bothering to list them. The difficult work was turning this into a theorem and this required the invention of a new language - category theory - although it was not invented expressly for this purpose. That it is able to do so demonstrates it's flexibility. As you are interested in Priest's attempts to also turn this resemblence into rigorous mathematics, you might be interested in [this](https://www.tandfonline.com/doi/abs/10.1080/01445340802337783) paper by Landini where he ... – Mozibur Ullah Oct 10 '21 at 04:56
  • @constantly confused: ... demonstates that "Russell's Theorem is not Priest's schema and questions the application of Priest's Inclosure Schema to the paradoxes of 'definability'". It's behind a paywall though. – Mozibur Ullah Oct 10 '21 at 04:59