let $D$ be an inference system where the axioms are all the propositions that are not Tautology and the rule of inference is $\frac{\alpha \vee \beta}{\alpha \wedge \beta}$.

I need to show with induction on the proof sequence that $$\vdash \alpha \Longrightarrow \nvDash \alpha$$ i.e if $\alpha$ can be proven from the system, and A is the axioms set then $A \vDash \alpha$

I know that if $\vdash \alpha$ then $\alpha$ is either an axiom or inferred. If $\alpha$ is an axiom then isn't $\models \alpha$? as if all the axioms are true so is $\alpha$. And if $\alpha$ is inferred then there are propositions $\varphi$ and $\psi$ such that $\alpha = \varphi \wedge \psi$ and $\vdash \varphi \vee \psi$ wouldn't $\nvDash \varphi \vee \psi \Longrightarrow \nvDash \varphi \wedge \psi$ also be correct?

I'm not sure how am I supposed to show it with induction and as I wrote above I have a problem understanding how it works when $\alpha$ is an axiom

  • $\begingroup$ "if α can be proven from the system, it isn't derived from the system" is wrong. "Proven from the system" and "derived from the system" are the same thing. $\endgroup$ Apr 22 at 11:31
  • $\begingroup$ @MauroALLEGRANZA I'm not sure how to write it, but I meant that if all the axioms are true then $\alpha$ isn't necessarily true $\endgroup$ Apr 22 at 11:46
  • $\begingroup$ The symbol $\nvDash$ reads: it is not valid that in propositional logic amounts to: it is not a tautology. $\endgroup$ Apr 22 at 11:54
  • $\begingroup$ @MauroALLEGRANZA after talking to my professor, he explained that if A is the axioms set then $\nvDash \alpha $ means $A \nvDash \alpha$ which begs the question what if $\alpha$ is an axiom, in that case $ A \vDash \alpha$ because $\alpha \in A$ $\endgroup$ Apr 22 at 18:48
  • $\begingroup$ It may be worth noting that the inference rule in this inference system is redundant: if $\alpha \lor \beta$ is not a tautology, then a fortiori, $\alpha \land \beta$ is not a tautology, so the theorems in this inference system coincide with the axioms. $\endgroup$
    – Rob Arthan
    Apr 22 at 20:57


The proof is by induction; thus, there are two cases:

(i) base case: $\alpha$ is an axiom and thus (by your choice of axioms) it is not a tautology, i.e. $\nvDash \alpha$.

(ii) induction step: $\alpha$ is inferred by a previous formula. You have only one rule with only one premise; thus, the inferential step will be $\alpha_i \vdash \alpha_{i+1}$.

By induction hypotheses you have $\nvDash \alpha_i$. What can you conclude about $\alpha_{i+1}$?


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.