Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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$.

share|improve this answer

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).

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.