3
$\begingroup$

Prove that all formulas of the following form are true in all structures: $ (\forall x (\varphi \rightarrow \psi)) \rightarrow (\forall x \varphi \rightarrow \forall x \psi)$

Can someone give me a hint? I have thought about showing that this formula is a tautology in propositional logic which would give me the statement. Or using the substition axiom but I don't know how to proceed. (I also had to prove that the other direction of implication is not true in all structures where for which I constructed a structure as a counterexample.)

$\endgroup$
4
$\begingroup$

It is not a tautology of propositional logic since it is of the form $A\to (B\to C).$ You can either prove it formally and use soundness, or just argue informally about structures. I’ll opt for the latter since I don’t know what proof systems you use.

We need to show in an arbitrary structure, if we have $\forall x (\varphi\to\psi)$ and $\forall x \varphi,$ then we have $\forall x\psi,$ which means if $a$ is any element of the domain, $\psi(a)$ holds. Well, by our assumptions, we have $\varphi(a)\to \psi(a)$ and $\varphi(a),$ so it follows that $\psi(a)$ holds.

$\endgroup$
  • $\begingroup$ Thanks for your hint! I think I managed to prove it now. I have posted another similar question here: math.stackexchange.com/questions/2981871/… If you could take a look I would be grateful, since you helped with this exercise so much. $\endgroup$ – thehardyreader Nov 2 '18 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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