Soundness and Completeness of a limited language
Posted: Wed May 13, 2015 4:29 pm
I was challenged with completing this task.
"Consider languages whose logical vocabulary is restricted to just negation and contradiction/absurdity/bottom. Thus, conjunction, disjunction, implication etc. do not occur in sentences of these languages. We can still conduct proofs for such languages using the following natural deduction rules:
(negation-introduction, negation-elimination, double negation-elimination). With regard to languages restricted in this way, complete the
following tasks:
(1) Show that the fragment of the natural deduction system is sound.
(2) Show that the fragment of the natural deduction system is complete (massage the
statement, get a special set, define a model and show it has the desired properties).
(3) Now imagine that we do not allow double negation-elimination as a rule. Do we still have soundness?
Do we still have completeness? If not, identify where the attempted proof of that
fact would break down."
Any insights would be appreciated
"Consider languages whose logical vocabulary is restricted to just negation and contradiction/absurdity/bottom. Thus, conjunction, disjunction, implication etc. do not occur in sentences of these languages. We can still conduct proofs for such languages using the following natural deduction rules:
(negation-introduction, negation-elimination, double negation-elimination). With regard to languages restricted in this way, complete the
following tasks:
(1) Show that the fragment of the natural deduction system is sound.
(2) Show that the fragment of the natural deduction system is complete (massage the
statement, get a special set, define a model and show it has the desired properties).
(3) Now imagine that we do not allow double negation-elimination as a rule. Do we still have soundness?
Do we still have completeness? If not, identify where the attempted proof of that
fact would break down."
Any insights would be appreciated