0
$\begingroup$

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

$\endgroup$
5
  • $\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$
    – Mauro ALLEGRANZA
    Apr 22, 2021 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$
    – CforLinux
    Apr 22, 2021 at 11:46
  • $\begingroup$ The symbol $\nvDash$ reads: it is not valid that in propositional logic amounts to: it is not a tautology. $\endgroup$
    – Mauro ALLEGRANZA
    Apr 22, 2021 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$
    – CforLinux
    Apr 22, 2021 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, 2021 at 20:57

1 Answer 1

Reset to default
2
$\begingroup$

Hint

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}$?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .