Show that a theory is complete if and only if (B or C is provable) implies (either B is provable or C is provable)

Question

The question: Show that a theory T is complete if and only if for any closed formulas B and C $$if \vdash_T B\ \lor C\ \Rightarrow\ \vdash_TB\ or \vdash_T C $$ Where $\vdash_T$ means that a formula P is provable in theory T.

Definition: Using definition that a theory is complete if for any formula B, either $\vdash B$ or $\vdash \lnot B$

My solution: $\Rightarrow$ If T is complete then we have either $\vdash C$ or $\vdash \lnot C$.

Now assume $\lnot (\vdash B\ or\ \vdash C)$. Then $\lnot(\vdash B)$ and $\lnot(\vdash C)$ which implies $$(\vdash \lnot B)\ \land\ (\vdash \lnot C)$$

Which means $\lnot (\vdash_T B\ \lor C)$ meaning that our hypothesis is true by modus tollens.

$\Leftarrow$ We know that $\vdash_T (B \lor \lnot B)$ because this is always true (law of excluded middle). Thus, if we have: $$\vdash_T B\ \lor C\ \Rightarrow\ \vdash_TB\ or \vdash_T C$$ for any close formula B or C, we must have that $$ \vdash_T B\ \lor \lnot B\ \Rightarrow\ \vdash_TB\ or \vdash_T \lnot B$$ And so for any B, either $\vdash B$ or $\vdash \lnot B$ meaning the theorem is complete.

Issue: I am worried as I didn't use the fact that B and C were CLOSED formula. I also would appreciate any pointers on whether my logic is correct. For example, have I used the law of excluded middle appropriately. Thanks

Answer 1

The definition of completeness of a theory is only for sentences (closed formulae) over it. To see why, I'll open up the structure of the theorem and proof below.

For part 1, your proof has a superfluous statement about $T$ proving either $C$ or $\neg C$. It's also better not to use the same logical symbols in the meta system, which you are using to analyze first-order logic! For part 2, your reasoning is right but I'll rewrite it below anyway.

---

Given any theory $T$:

  If $T$ is complete then:

    Given any sentences $B,C$ over $T$:

      If $T \vdash B \lor C$:

        If neither $T \vdash B$ nor $T \vdash C$:

          $T \nvdash B$ and $T \nvdash C$.

          Thus $T \vdash \neg B$ and $T \vdash \neg C$ [because $T$ is complete and $B,C$ are sentences over $T$].

          Thus $T \vdash \neg ( B \lor C )$ [by basic logic].

          Contradiction.

        Therefore $T \vdash B$ or $T \vdash C$.

  If:

    Given any sentences $B,C$ over $T$:

      If $T \vdash B \lor C$:

        $T \vdash B$ or $T \vdash C$.

  Then:

    Given any sentence $B$ over $T$:

      $T \vdash B \lor \neg B$.

      Thus $T \vdash B$ or $T \vdash \neg B$ [by the condition].

    Therefore $T$ is complete.

---

You may have noticed that the second half of the proof does not use the part of the condition that requires $B,C$ to be sentences over $T$, and that is true, but the condition cannot be strengthened to hold for all formulae otherwise the proof of the first part will fail.

Furthermore, not only will the proof fail if we change the condition to be for formulae instead of only sentences, the claim would also be false. For example the theory with only the equality symbol and no axioms is complete (and has quantifier elimination), but "$x = y$" is a formula that can neither be proven nor disproven over $T$. Intuitively this is because this formula concerns two unknown elements that the theory itself (knowing nothing about the elements) of course cannot fix whether it is true or not. If you pick two equal elements, then it would be true, but if you pick two unequal elements, it would be false, and hence the theory cannot possibly prove one or the other unless it is unsound.