Hello I have been struggeling with the following questions:
We here introduce a notion of completeness slightly different from the one discussed in the lecture. A set of formulas $\Gamma$ is complete if, for each formula $\phi$, it holds that either $\Gamma \vdash \phi$ or $\Gamma \vdash \neg \phi$, but not both (that is, exactly one between $\Gamma \vdash \phi$ and $\Gamma \vdash \neg \phi$ holds).
- Give some examples of sets which are not complete.
Let $\operatorname{Der}(\Gamma)=\{\psi \mid \Gamma \vdash \psi\}$ be the set of formulas derivable from $\Gamma$.
Show that if $\Gamma$ is complete then $\operatorname{Der}(\Gamma)$ is maximally consistent, that is:
A. Prove that, if $\Gamma$ is complete, then $\operatorname{Der}(\Gamma)$ is consistent.
B. Prove that, if $\Gamma$ is complete, then for all $\Gamma^{\prime}$ such that $\operatorname{Der}(\Gamma) \subsetneq \Gamma^{\prime}$ it holds that $\Gamma^{\prime}$ is not consistent.
I have this now:
- We say that a formula is not complete when for each formula $\phi$, it holds that not $\Gamma \vdash \phi$ and not $\Gamma \vdash \neg \phi$. Examples are:
- Let $S=\{R\}$. Let $x$ and $y$ be distinct variables. Suppose we have the set $\phi= \{R x \lor R y\}$.\
- If $\Gamma$ contains insufficient formulas. For example $\Gamma$ could be empty and $\phi$ is such that neither $\phi$ nor $\neg \phi$ is universally valid (valid for every interpretation).\
- In group theory: Consider as $\phi$ the formula $\forall x \forall y (xy = yx)$. This formula holds for some groups (called commutative or "Abelian" groups), but not all. So we don't expect to be able to prove it just from the axioms of group theory. But neither do we expect to prove its negation from those axioms. Thus this formula is independent of the group theory axioms.
A set of formulas $\Gamma$ is consistent if $\Gamma \nvdash \perp$.To prove that $\operatorname{Der}(\Gamma)$ is consistent if $\Gamma$ is complete, we need to show that there is no formula $\phi$ such that both $\phi$ and $\neg \phi$ belong to $\operatorname{Der}(\Gamma)$. Assume for contradiction that $\operatorname{Der}(\Gamma)$ is inconsistent, which gives that $\Gamma \vdash \perp$. There exists a formula $\phi$ such that both $\phi$ and $\neg \phi$ are derivable from $\Gamma$, i.e., $\Gamma \vdash \phi$ and $\Gamma \vdash \neg \phi$. Since $\Gamma$ is complete, we know that exactly one of the following holds: $\Gamma \vdash \phi$ or $\Gamma \vdash \neg \phi$. We distinguish two cases.
Case 1: $\Gamma \vdash \phi$.
If $\Gamma \vdash \phi$, and we also have $\Gamma \vdash \neg \phi$, then we have a contradiction because both $\phi$ and $\neg \phi$ cannot be derivable from $\Gamma$ simultaneously. Therefore, this case cannot occur.
Case 2: $\Gamma \vdash \neg \phi$.
If $\Gamma \vdash \neg \phi$, and we also have $\Gamma \vdash \phi$, then we again have a contradiction because both $\phi$ and $\neg \phi$ cannot be derivable from $\Gamma$ simultaneously. Therefore, this case cannot occur either.
Since both cases lead to contradictions, the assumption that $\operatorname{Der}(\Gamma)$ is inconsistent must be false. Hence, $\operatorname{Der}(\Gamma)$ is consistent when $\Gamma$ is complete.I dont know how to prove this I only know that: Since $\operatorname{Der}(\Gamma) \subsetneq \Gamma'$, there exists a formula $\phi$ such that $\phi \in \Gamma'$ but $\phi \notin \operatorname{Der}(\Gamma)$. This means that $\phi$ is not derivable from $\Gamma$. Since $\Gamma$ is complete, we know that either $\Gamma \vdash \phi$ or $\Gamma \vdash \neg \phi$ holds.