Begin a deduction from a tautology, also make a tautology?

47 Views Asked by At

I'm doing a course in first-order logic in mathematics and I've stumpled upon a question while preparing for the exam:
Assume you have two formulas (well-formed) $\varphi, \psi$ and you have proved that $\psi \vdash \varphi$, i.e. there is a deduction from $\psi$ to $\varphi$. Now you get asked whether or not it also holds that $\psi \models_t \varphi$ (if $\psi$ tautologically implies $\varphi$).
Can one argue by, since $\varphi$ is a deduction from $\psi$, then by proving $\psi$ is a tautology, then $\varphi$ must also be a tautology? I can't really find anything in my notes about a similar argument, so I'm a bit unsure how to argue for the tautology...
(For your own information, we have used, or more followed Enderton's book in the course, if that helps...)

1

There are 1 best solutions below

1
On

See Enderton's Logic, page 115: in general $\varphi \vdash \psi$ does not imply $\varphi \vDash_t \psi$.

The counter-example is in the text: we have $∀xPx⊢Pc$ but the second is not tautologically implied by the first one.

Why so? because in order to use tautological implication we have to "model" the predicate logic case in terms of propositional logic. But $\forall x Px$ and $Pc$ are two different atomic formulas: $Q$ and $R$ say, and $Q \nvDash_t R$.

We have to apply THEOREM 24B $\Gamma \vdash \varphi$ iff $\Gamma \cup \Lambda$ tautologically implies $\varphi$.

As suggested by the proof of the theorem, you can easily verify that: $\forall x Px, \forall x Px \to Pc \vDash_t Pc$.

Note: wrt to the title, if $\varphi$ is a tautology and $\varphi \vdash \psi$, due to soundness we have $\varphi \vDash \psi$ and thus also $\psi$ is a tautology. But this is consistent with the discussion above: $\forall xPx$ is not a tautology.