7
$\begingroup$

I'm reading Enderton's logic book and have arrived to his deductive calculus for first order logic. After defining it, he presents the following theorem:

$\Gamma\vdash \varphi$ iff $\Gamma\cup \Lambda$ tautologically implies $\varphi$.

Here (if I understand correctly):

  1. $\Gamma$ is simply a set of sentences.
  2. $\Lambda$ is the set of axioms for a calculus.
  3. $\vdash$ is the usual notion of formal deduction - there is a finite sequence of sentences such that every sentence is either in $\Gamma\cup\Lambda$ or is obtained from previous sentences using some deduction rule (Enderton only uses MP: $\alpha\to\beta$ and $\alpha$ imply $\beta$).
  4. "tautologically implies" means that if we treat what he calls "prime formulas" (atomic formulas and those of the form $\forall x\alpha$) as variables, every assignment that satisfies $\Gamma \cup \Lambda$ also satisfies $\varphi$.

I agree with Enderton's proof, but I don't understand how this doesn't contradict the completeness theorem, which states (if I understand correctly) that if $\Gamma$ logically implies $\varphi$ (i.e. every model of $\Gamma$ is a model of $\varphi$) then $\Gamma\vdash\varphi$. But this means that if $\Gamma$ logically implies $\varphi$ then it tautologically implies $\varphi$ which is obviously false. Enderton himself gives the example of $\forall x\psi(x)$ and $\psi(c)$ (where c is some term).

What am I missing here? I'm sure its basic and embarrassing.

2 Answers 2

4

As someone pointed out to me somewhere else, my mistake is not noting the difference between "$\Gamma$ tautologically implies $\varphi$" and "$\Gamma\cup\Lambda$ tautologically implies $\varphi$". It is indeed the case that if $\varphi$ is logically implied by $\Gamma$ then $\Gamma\cup\Lambda$ tautologically imply $\varphi$; it does not mean that $\Gamma$ alone tautologically implies $\varphi$.

1

To find the "trick", is necessary to reflect on the fact that NOT all the formulae in the set $\Lambda$ of logical axioms are tautologies (see Enderton, pag.115). Obviously, $\forall x (x=x)$ is not.

In the proof of Th.24B, Enderton exploits the fact that his only rule of inference is MP and that MP tracks Tautological Implication, i.e. {$\alpha, \alpha \rightarrow \beta$} $\vDash_{TAUT} \beta$.

But this does not means that $\alpha$ and $\beta$ are Tautologies !

In the original derivation of $\varphi$ from $\Gamma$ you certainly will use logical axioms from $\Lambda$. In the proof of the metatheorem he supposes that $v$ is a truth assignment (i.e.a boolean valuation) that satisfy all formulae in $\Gamma$ and $\Lambda$.

Becuase in derivations only MP is used and MP has the above property, we have that in each step of the above deduction where you apply MP, if $v$ satisfy the premisses, then $v$ satisfy also the conclusion: and this is enough.