Proving that $\{P_1,P_2, \dots, P_n\}$ is complete but not maximally consistent

logicproof-theorypropositional-calculus

Prove that $\{P_0,P_1, \dots, P_n\}$ is complete but not maximally consistent

So I need to prove that this is complete, consistent, but not maximally consistent. But I have a few confusions about this question:

1) How do we prove that it is complete (for every formula $\phi$, either $\Gamma \vdash \phi$ or $\Gamma \not\vdash\phi$)? Do we simply say that since all atomic formulas are included, we can prove any formula or its negations from this set? Do we need to do structural induction for this?

2) Is my attempt at proving consistency OK? Assume it is inconsistent, thus $\Gamma \vdash \phi$ and $\Gamma \vdash\lnot\phi$ for some formula $\phi$. By soundness $\Gamma \vDash \phi$ and $\Gamma \vDash\lnot\phi$. But we know that PL is truth functional, so the truth value of these formula depend on their constituting atomic formula. But this must mean at least one atomic formula $v(\psi)=T$ and $v(\psi)=F$ meaning $v(\lnot\psi)=T$. But this is impossible given this is just a set of negation free atomic formula.

PS: I know it is not maximally consistent because $P_0\land P_1$is consistent and derivable, but not included in this set so that has been taken care of.

Best Answer

Your question is slightly ambiguous. In my opinion, there are two possible interpretations of your question:

  1. Let $V$ be the set of all propositional variables (they are countably infinitely many). Then, $V$ is consistent and complete but not maximally consistent.

    Proof.

    • Consistency: Clearly, there is a model $v$ of $V$, the one such that $v(P) = \top$ for all $P \in V$. By soundness theorem, $V$ is consistent i.e. there is no formula $\varphi$ such that $V \vdash \varphi$ and $V \vdash \lnot \varphi$.

    • No maximal consistency: As you correctly said, for any $P, Q \in V$, one has $V \vdash P \land Q$ since $V \vdash P$ and $V \vdash Q$, but the formula $P \land Q \notin V$.

    • Completeness: Let $\varphi$ be a formula. There is only one truth assignment $v$ that is a model of $V$: it is the truth assignment $v$ such that $v(P) = \top$ for all $P \in V$. As any truth assignment, either $v \vDash \varphi$ or $v \vDash \lnot \varphi$. Hence, either $V \vDash \varphi$ or $V \vDash \lnot \varphi$, i.e. either all the models of $V$ are a model of $\varphi$ or all the models of $V$ are a model of $\lnot \varphi$. By completeness theorem, $V \vdash \varphi$ or $V \vdash \lnot \varphi$. $\quad\square$

  2. Let $V$ be a proper subset of the set of all propositional variables (in particular, this is the case if $V$ is a finite set of propositional variables). Then, $V$ is consistent but neither complete nor maximal consistent.

    Proof.

    • Consistency: As above.

    • No maximal consistency: given a propositional variable $P \notin V$ (it exists by hypothesis), $V \cup \{P\}$ is consistent (see consistency in Point 1), but $V \subsetneq V \cup \{P\}$.

    • No completeness: As correctly suggested by Asaf Kasaglia's comment, given a propositional variable $P \notin V$ (it exists by hypothesis), from the consistency of $V \cup \{P\}$ it follows that $V \not\vdash \lnot P$. But $V \cup \{\lnot P\}$ is consistent as well (take the truth assignment $v$ such that $v(Q) = \top$ for all $Q \in V$, and $v(P) = \bot$, then use soundness theorem to conclude), hence $V \not \vdash P$. $\qquad \square$