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
- 2
-
In general $\varphi \vdash \psi$ does not imply $\varphi \vDash_t \psi$; we have $\forall x Px \vdash Pc$ but the second is not tautologically implied by the first one. See page 115. – Mauro ALLEGRANZA Mar 26 '24 at 09:03
-
See also this post. – Mauro ALLEGRANZA Mar 26 '24 at 09:06
-
@MauroALLEGRANZA Sorry for the confusion with the titel, I tried to make it "less subjective"... But in relation to your soundness comment, yes it holds that $\varphi \models \psi$ by soundness but it does not necessarily mean that $\varphi \models_t \psi$... maybe I have misunderstood something? – kfx18 Mar 26 '24 at 09:21
-
No; as said before: $\forall x Px \vDash Pc$ but $\forall x \nvDash_t Pc$. – Mauro ALLEGRANZA Mar 26 '24 at 09:57
-
Counter-example: $A\lor \neg A$ is a tautology, but $(A\lor \neg A) \implies B$ is not. – Dan Christensen Mar 26 '24 at 13:00
-
Maybe the rules of the inference system used are not sound ... – Bram28 Mar 26 '24 at 20:15
1 Answers
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.
- 94,169
-
Thank you, that makes so much sense now. I'll continue with Theorem 24B in my case, and I'll see where it gets me. – kfx18 Mar 26 '24 at 11:49