2
$\begingroup$

let D be a deductive system. The system's axiom set, A, includes all propositions that are not tautology, and the only rule of inference is $\frac{\alpha \vee \beta}{\alpha \wedge \beta}$.

I need to answer:

  1. Show with induction on the proof that $ \vdash \alpha \Longrightarrow \nvDash \alpha $, i.e if $ \alpha $ can be proven from the empty set, then exists a model $ M $ such that for every $ \varphi \in A $, $ M(\varphi)=T $ and $ M(\alpha)=F$.
  2. Is the system strongly sound?
  3. Is $X\nvDash \alpha \Longrightarrow X\vdash \alpha$?
  4. Prove that the empty set isn't consistent in D

  1. I've already asked about this part of the question here but I still have a problem with it, because every axiom, $a\in A$, $\vdash a$ and $A \models a$, in contradiction to what I'm supposed to prove here. Moreover because the axiom set includes all what isn't tautology it also includes all that is contradiction, which means that there is no model $ M $ such that for every $ \varphi \in A $, $ M(\varphi)=T $ which means for every proposition $\psi$, $A\Longrightarrow \psi$.
  2. This one was fairly easy base on (1) the system isn't sound so it can't be strongly sound.
  3. I'm not even sure how to approach this, I don't even have an intuition whether this is correct or not. Assuming this is wrong, I need to find a set $X$ and proposition $\alpha$ such that $X\nvDash \alpha$ but $\alpha$ cannot be proven from $X$, and if it's correct I need to show that for every set, $X$, and every proposition $\alpha$ such that $X\nvDash \alpha$, $\alpha$ can be proven from $X$
  4. On the surface this looks pretty easy, both $(\varphi \wedge \psi)$ and $\neg(\varphi \wedge \psi)$ are axioms, as they aren't tautology, hence $\vdash (\varphi \wedge \psi)$ and $\vdash \neg (\varphi \wedge \psi)$ and the empty set isn't consistent but this seems too easy, like I'm missing something.

EDIT:

I might have come up with a solution for (3), if $X\nvDash \alpha$ it means that $\alpha$ isn't a tautology and if it isn't a tautology it is an axiom in D and therefore can be proven from $X$

$\endgroup$
9
  • $\begingroup$ For the "i.e." in number one, did you put that there or was it in the assignment? It seems wrong, as you say. What would make more sense - not just in terms of the problem but in terms of the plain meaning of the symbols - is if $\not\models\alpha$ means that $\alpha$ is not a tautology. (Why should $\models$ have anything to do with the deductive system, hence anything to do with $A$?) Then your task would be to show that all the axioms are not tautologies (check) and that not being a tautology is preserved by the rule of inference. $\endgroup$ Apr 25, 2021 at 4:39
  • $\begingroup$ @spaceisdarkgreen that was what I originally thought I need to show, that every proposition that can be proven in D is not a tautology, but then my professor said I need to show that if proposition a can be proven from the empty set then $A\Longrightarrow a$ where $A$ is the axiom set $\endgroup$ Apr 25, 2021 at 8:10
  • $\begingroup$ it isn't and I wrote "base on (1) the system isn't sound so it can't be strongly sound." $\endgroup$ Apr 26, 2021 at 13:23
  • $\begingroup$ As I said in a comment on an earlier question of yours, in this deductive system the only theorems are the axioms (the inference rule can't take a non-tautology to a tuatology). This is an abstract deductive system. So parts 1, 2 and 3 depend on the separate standard definition of $\models$ for propositional formulas. .... $\endgroup$
    – Rob Arthan
    Apr 26, 2021 at 20:51
  • 1
    $\begingroup$ Conclusion: what is highly unsatisfying in the problem (as stated) is the lack of details: definition of language, definition of $\vdash$, definition of $\vDash$. Without them, the only way to answer is to assume the "standard" defintions. $\endgroup$ Apr 27, 2021 at 7:31

0

Your Answer

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

Browse other questions tagged or ask your own question.