Sunday, 14 July 2013

Theorem 1

In the previous century, I wrote a paper
Ketland 1999: "Deflationism and Tarski's Paradise" (Mind). 
The main point of this paper was to argue that deflationary truth theories should (and indeed do, usually) satisfy a conservation condition, but adequate theories should satisfy a reflection condition. This reflection condition is Leitgeb's adequacy condition (b) in
Leitgeb 2007: "What Theories of Truth Should be Like (but Cannot be)" (Phil Compass: available here). 
These two conditions are incompatible, in some scenarios, because of Gödel's incompleteness theorems: hence, deflationary truth theories are inadequate.

Just before that, but unbeknownst to either of us, Stewart Shapiro published a paper,
Shapiro 1998, "Proof and Truth - Through Thick and Thin" (J. Phil, 1998),
giving a similar argument against deflationism, based on conservation and reflection. And a few years before that (the similarities were unbeknownst to any of the three of us), Leon Horsten had given some similar arguments in a 1995 article,
Horsten 1995, "The Semantic Paradoxes, The Neutrality of Truth and the Neutrality of the Minimalist Theory of Truth".
But in the 1999 paper, I'd given a "theorem", labelled "Theorem 1". This "theorem" is wrong. Somewhat fortunately, this theorem can be "fixed" by adding certain side conditions (see below). But, as stated, it's wrong. How I ended up with a wrong theorem is moderately interesting.

Still, the wrong "theorem" itself comes from a theorem which is not wrong, which is what I'd started with (I vividly remember guessing it and working out the proof), and which is important in the sense that it's connected to the ensuing debate about the conservativeness/non-conservativeness of truth theories. That theorem is:
$PA$ + the Tarski biconditionals for $L$-sentences is a conservative extension of $PA$.
This can be established in a number of ways: e.g., model-theoretically and proof-theoretically. It's clear that the theorem should generalize, because very little of the apparatus of $PA$ is needed for this to hold. In fact, it is sufficient that the base theory $T$ prove the distinctness of distinct expressions. That is,
if $\epsilon_1 \neq \epsilon_2$, then $T \vdash \ulcorner \epsilon_1 \urcorner \neq \ulcorner \epsilon_2 \urcorner$.
Unfortunately, I generalized too much! In my 1999 paper, I say that the set of Tarski-biconditionals
$\Delta_{TB} := \{\mathbf{True}(\ulcorner \phi \urcorner) \leftrightarrow \phi \mid \phi \in Sent(L)\}$
conservatively extends any theory $T$, and this isn't so. $T$ must satisfy certain conditions. And the proof I give, by model expansion, is somewhat muddled, as it assumes that one can extend the domain of the starting model $\mathcal{M}$ by adding infinitely many (codes of) sentences, and this is not correct.

I noticed the theorem was wrong, when the article appeared in January 1999. For in the same issue of Mind, Volker Halbach published
Halbach 1999, "Disquotationalism and Infinite Conjunctions" (Mind),
and reading his paper carefully made me notice that my result needed side conditions. Halbach's paper included reference to a wealth of other recent work on axiomatic truth theories of which I'd been completely unaware when I wrote my paper. (I knew only Tarski's original 1936 paper Der Wahrheitsbegriff and worked from there. I didn't know the subsequent work by, e.g., Wang, Mostowksi, Feferman, Friedman & Sheard, Cantini, Halbach et al.)

To give a corrected version, first here's a lemma---one that is useful in thinking about truth predicates (it shows that given a finite set of sentences, then defining truth for these is not difficult, given just a bit of syntax):
Lemma: Let $L$ be the usual language of arithmetic and let $L^+$ be the result of adding a new unary predicate symbol $\mathsf{True}$. Let $T$ in $L$ be a theory such that, for any distinct sentences $\phi, \theta$ in $L$,
$T \vdash\ulcorner \phi \urcorner \neq \ulcorner \theta \urcorner$.
Let $\Psi$ be a finite set of $L$-sentences. Then there is an $L$-formula $\mathsf{True}^{\circ}(x)$ such that,
$T \vdash \mathsf{True}^{\circ}(\ulcorner \psi \urcorner) \leftrightarrow \psi$,
for each $\psi \in \Psi$.
Proof: Let the assumptions be as stated, and let $\Psi = \{\psi_1, \dots, \psi_n\}$ be given. Define the following $L$-formula:
$\mathsf{True}^{\circ}(x) := \bigvee \{x = \ulcorner \psi \urcorner \wedge \psi \mid \psi \in \Psi\}$
Let $\psi_i \in \Psi$ and consider $\mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner)$. That is,
$(\ulcorner \psi_i \urcorner = \ulcorner \psi_1 \urcorner \wedge \psi_1) \vee \dots  \vee (\ulcorner \psi_i \urcorner = \ulcorner \psi_n \urcorner \wedge \psi_n)$
Note that, if $i \neq j$, then
$T \vdash \ulcorner \psi_i \urcorner \neq \ulcorner \psi_j \urcorner$
So, if $i \neq j$,
$T \vdash \neg(\ulcorner \psi_i \urcorner = \ulcorner \psi_j \urcorner \wedge \psi_j)$
So,
$T \vdash \bigwedge \{\neg(\ulcorner \psi_i \urcorner = \ulcorner \psi_j \urcorner \wedge \psi_j) \mid j \neq i\}$
But, by the definition of $\mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner)$, we have:
$T, \mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner) \vdash (\ulcorner \psi_i \urcorner = \ulcorner \psi_1 \urcorner \wedge \psi_1) \vee \dots  \vee (\ulcorner \psi_i \urcorner = \ulcorner \psi_n \urcorner \wedge \psi_n)$
So, then
$T, \mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner) \vdash
(\ulcorner \psi_i \urcorner = \ulcorner \psi_i \urcorner \wedge \psi_i)$
and so,
$T, \mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner) \vdash \psi_i$
By similar reasoning,
$T, \psi_i \vdash \mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner)$ 
So,
$T \vdash \mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner) \leftrightarrow \psi_i$ 
QED.

Here then is one modification of "Theorem 1" which is ok:
Theorem: Let $L$ be the usual language of arithmetic and let $L^+$ be the result of adding a new unary predicate symbol $\mathsf{True}$. Let $T$ in $L$ be a theory such that, for any distinct sentences $\phi, \theta$ in $L$,
$T \vdash \ulcorner \phi \urcorner \neq \ulcorner \theta \urcorner$.
Then $T \cup \Delta_{TB}$ conservatively extends $T$ (for $L$-sentences).
Proof. We will suppose that $T \cup \Delta_{TB}$ proves some $L$-sentence $\phi$, and then "convert" the proof into a proof in $T$ of $\phi$.

So, suppose that
$T \cup \Delta_{TB} \vdash \phi$, 
with $\phi \in Sent(L)$. Let
$P = (\theta_0, \dots, \theta_k)$
be such a proof. If no axioms from $ \Delta_{TB}$ occur in $P$, then $P$ is a proof in $T$ of $\phi$ and we are done.

So suppose that the following are axioms of  $\Delta_{TB}$ occurring in $P$
$\mathsf{True}(\ulcorner \psi_1 \urcorner) \leftrightarrow \psi_1$
$\dots$
$\mathsf{True}(\ulcorner \psi_n \urcorner) \leftrightarrow \psi_n$
(I.e., these are T-sentences occurring in the proof $P$.)

Next let $\Psi = \{\psi_1, \dots, \psi_n\}$. By the above Lemma, we may define $\mathsf{True}^{\circ}(x)$, and then we have, by the Lemma above, that
$T \vdash \mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner) \leftrightarrow \psi_i$ 
for each $\psi_i \in \Psi$.

Next, given any $\theta_i$ in the proof $P$, we define $(\theta_i)^{\circ}$ to be the result of replacing each occurrence of a subformula $\mathsf{True}(t)$ in $\theta_i$ by $\mathsf{True}^{\circ}(t)$. We obtain the sequence:
$P^{\circ} = ((\theta_0)^{\circ}, \dots, (\theta_k)^{\circ})$
Substitution preserves deducibility, and so this sequence is a proof using the translations of $T$-sentences as axioms. However, each $T$-sentence
$\mathsf{True}(\ulcorner \psi_i \urcorner) \leftrightarrow \psi_i$
occurring in the proof $P$ is translated to a theorem of $T$, namely,
$\mathsf{True}^{\circ}(\ulcorner \psi_i \urcorner) \leftrightarrow \psi_i$
So, if we extend $P^{\circ}$ by inserting the missing subproofs (in $T$) of these theorems, we obtain then a new sequence $P^{\ast}$. This is then a proof of $\phi$ in $T$, as required. QED.

No comments:

Post a Comment