Prove that the set of formulas derivable from a complete set is maximal consistent

55 Views Asked by At

I was introduced to an alternate definition of a complete set for this problem: a set $\Gamma$ is complete if, for each formula $\phi$, it holds that $\Gamma \vdash \phi$ or $\Gamma \vdash \neg\phi$ but not both.

Let $Der(\Gamma) = \{\phi\;|\;\Gamma \vdash \phi\}$ be the set of formulas derivable from $\Gamma$. Show that if $\Gamma$ is complete then $Der(\Gamma)$ is maximally consistent.

Proof: we prove that $Der(\Gamma)$ is maximally consistent by proving it is consistent, and that for every set $\Gamma'$ such that $Der(\Gamma) \subset \Gamma'$ it holds that $\Gamma'$ is not consistent.

(i) Assume that $\Gamma$ is complete, by the provided definition we know that $\Gamma \vdash \phi$ or $\Gamma \vdash \neg\phi$ but not both. By the definition of $Der(\Gamma)$ this would mean that either $\phi \in Der(\Gamma)$ or $\neg\phi \in Der(\Gamma)$ but not both. Now suppose that $Der(\Gamma)$ is not consistent i.e. By the definition of $\vdash$ it holds that either $Der(\Gamma) \vdash \phi$ or $Der(\Gamma) \vdash \neg\phi$ but not both i. e. $Der(\Gamma) \nvdash \phi \land \neg\phi$. From this we can conclude that $Der(\Gamma)$ is consistent.

(ii) Consider $\Gamma'$ such that $Der(\Gamma) \subset \Gamma'$. Assume that $\Gamma$ is complete, once again by the provided definition we have that $\Gamma \vdash \phi$ or $\Gamma \vdash \neg\phi$ but not both. Once again, by the definition of $Der(\Gamma)$ this would mean that either $\phi \in Der(\Gamma)$ or $\neg\phi \in Der(\Gamma)$ but not both. Now suppose that $\phi \in \Gamma$ and $\neg\phi \notin Der(\Gamma)$ (this choice is arbitrary and the remainder of the proof is analogous whether we choose otherwise). It then must follow that $\neg\phi \in \Gamma'$, and given that $Der(\Gamma) \subset \Gamma'$ it then follows that $\neg\phi, \phi \in \Gamma'$. As such, $\Gamma' \vdash \phi \land \neg\phi$. From this we may conclude that $\Gamma'$ is not consistent. $\square$

Is this proof correct? I was not entirely sure as it seems a bit shaky and rash. Thanks in advance!