4
$\begingroup$

A set $\Gamma$ of propositional formulas is closed under derivations if, for any $\varphi$, we have $\Gamma \vdash \varphi \Rightarrow \varphi \in \Gamma$.

A set is maximally consistent if it is consistent and for any $\Gamma'$ s.t. $\Gamma \subseteq \Gamma'$ and $\Gamma'$ consistent, then $\Gamma ' = \Gamma$ (i.e. there is no larger set of propositions that is consistent.)

Every maximally consistent set is closed under derivations (or closed under consequence). I am trying to determine if the reverse is true. My intuition is that it is not; i.e., that there are sets cloesd under derivations that are not maximally consistent. However, I haven't been able to find an example of such set.

A particular problem is that the counterexample I'm looking for must be infinite. Any finite set $\{\varphi_1, \ldots, \varphi_n \}$ of arbitrary size $n$ is not closed under derivation. (It is easy to imagine infinite combinations, using the connectives $\land, \lor,$ etc, of the elements of the set, which a finite set could never contain).

Any guidance is appreciated.

$\endgroup$

3 Answers 3

6
$\begingroup$

HINT: Let the set of sentence symbols be a singleton set $S=\{p\}$, and let $\Gamma$ be the set of tautologies, i.e. the "closure under derivations" of the empty set.

  1. Can you see why $\Gamma$ is closed under derivations?
  2. Can you see why the sentence $\varphi = p$ is not in $\Gamma$?
  3. Can you see why the sentence $\varphi = p$ is consistent with $\Gamma$?
$\endgroup$
3
  • 3
    $\begingroup$ The answer given above is very good. Another obvious counterexample (the dual, if you will) that comes to mind is the set of all formulas. It is closed under consequence, albeit trivially since the consequent (of he definition of closure under derivation) is always satisfied, but it is not consistent, so a fortiori not maximally consistent. $\endgroup$ Jul 10, 2023 at 19:20
  • $\begingroup$ Thanks again Franklin $\endgroup$
    – lafinur
    Jul 12, 2023 at 15:46
  • $\begingroup$ @lafinur Sure thing ;-) $\endgroup$ Jul 13, 2023 at 15:39
6
$\begingroup$

The answer given by Franklin Pezzuti Dyer is very good. Another obvious counterexample (the dual, if you will) that comes to mind is the set of all formulas. It is closed under consequence, albeit trivially since the consequent (of the definition of closure under derivation) is always satisfied, but it is not consistent, so a fortiori not maximally consistent.

$\endgroup$
3
$\begingroup$

Others have already provided nice examples. Let me add a few more. Assume $p,q$ are two distinct propositional symbols, and define $$ \begin{align} \Gamma_0 &= \{ \varphi :\ \vdash \varphi\} \\ \Gamma_1 &= \{ \varphi :\ p\lor q\vdash \varphi\} \\ \Gamma_2 &= \{ \varphi :\ p\vdash \varphi\} \\ \Gamma_3 &= \{ \varphi :\ p\land q\vdash \varphi\} \\ \end{align} $$

All the sets above are closed under consequence, by construction.

It is easy to verify that we have the strict inclusions $\Gamma_0\subset\Gamma_1 \subset \Gamma_2 \subset \Gamma_3$, so this proves that all of these sets (except the last $\Gamma_3$) are not maximal.

Following the same idea, whenever you have a sequence of stronger and stronger formulas, you can make a chain of strictly increasing closed under consequence sets.

You can even find families of sets not forming a chain. Above you can also add $\Gamma_2' = \{ \varphi :\ q\vdash \varphi\}$ which is incomparable to $\Gamma_2$ but in the same order relationship to other sets $\Gamma_i$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .