2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are $P_1, \dots, P_n$? Propositional variables? $\endgroup$ – Taroccoesbrocco Oct 26 '18 at 15:01
  • $\begingroup$ Sorry yes, they are propositional variables $\endgroup$ – Daniel Mak Oct 26 '18 at 15:02
  • 1
    $\begingroup$ Huh? What about $P_{n+1}$ as $\phi$. Does $\Gamma$ prove $\phi$ or its negation? $\endgroup$ – Asaf Karagila Oct 26 '18 at 15:07
  • $\begingroup$ So, do you want to prove that the set of all propositional variables is complete but not maximally consistent? Or that any set of propositional variables is complete but not maximally consistent? $\endgroup$ – Taroccoesbrocco Oct 26 '18 at 15:11
1
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ Thank you! I am assuming it is probably the set of all variables as it is complete (I am afraid the info I wrote are all I am given) $\endgroup$ – Daniel Mak Oct 27 '18 at 13:24
  • $\begingroup$ I understand that there is only one model for $V$; but how does that, via soundness theorem, prove that $V$ is consistent? Also, I understand that for all truth assignments $v$, either $v\vDash\phi$ or $v\vDash\lnot\phi$, but how does that translate to $V\vDash\phi$ or $V\vDash\lnot\phi$? $\endgroup$ – Daniel Mak Oct 27 '18 at 13:27
  • 1
    $\begingroup$ @DanielMak - $V \vDash \varphi$ means that all the models of $V$ satisfy $\varphi$. Since $v$ is the only model of $V$, from $v \vDash \varphi$ it follows that $V \vDash \varphi$. $\endgroup$ – Taroccoesbrocco Oct 27 '18 at 20:21
  • 1
    $\begingroup$ @DanielMak - If $V$ is inconsistent, then there is a formula $\varphi$ such that $V \vdash \varphi$ and $V \vdash \lnot\varphi$. By soundness theorem, this means that $V \vDash \varphi$ and $V \vDash \lnot \varphi$. Therefore, there is no model of $V$, otherwise such a model would satisfy both $\varphi$ and $\lnot \varphi$, which is impossible. So, thanks to soundness theorem, we proved that if $V$ has a model, then $V$ is consistent. $\endgroup$ – Taroccoesbrocco Oct 27 '18 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.