I am learning about the completeness and soundness of the sentential logic natural deduction system. I am having trouble understanding what defines the completeness of a system.
For example this is a question given in the lecture notes,
- Suppose the rule ->I (conditional introduction) is revised to the following: "If you have derived wff "a" and you have derived wff "b", then you can write a->b depending on everything b depends on. The system is not complete.
However, if the rule is changed to "If you have derived wff "a" and you have derived wff "b", then you can write a->b depending on everything "a" depends on", the system is still complete.
I do not understand why changing the dependency would make the system complete/incomplete.
The rules as stated are a bit confusing, but I think the following is meant:
Suppose you change the conditional introduction rule so that if you can derive $b$ on the basis of assumptions $\Gamma$, then within those very same assumptions, you can derive $a \rightarrow b$. Or, as a sequent rule: if $\Gamma \vdash b$, then $\Gamma \vdash a \rightarrow b$
Now, this is different from the 'normal' conditional introduction rule in that you typically say that if $a$ is one of the assumptions in $\Gamma$, then you can 'discharge' assumption $a$ when getting $a \rightarrow b$. As a sequent rule: if $\Gamma \vdash b$ and $a \in \Gamma$, then $\Gamma \setminus \{ a \} \vdash a \rightarrow b$
With the modified rule, the proof system will indeed be incomplete, since you can no longer prove something like $p \rightarrow p$, i.e. that $p \rightarrow p$ is a tautology, i.e $\{ \} \vdash p \rightarrow p$, since you can't discharge any assumptions. That is, you can show $\{ p \} \vdash p$, but from that you can only infer $\{ p \} \vdash p \rightarrow p$, rather than $\{ \} \vdash p \rightarrow p$