The number of completions of a finite, consistent set of propositional logic formulas

35 Views Asked by At

The following definitions and claims appear on p. 31 of Fred Kröger's Temporal Logic of Programs (Springer, 1987). The formulas under discussions are those of propositional temporal logic, but I think it is safe for the purpose of my question to assume regular propositional logic.


Definition 1 A finite set $\mathcal{F} = \{A_1, \dots, A_n\}$ of formulas is called inconsistent if $\vdash\neg(A_1\wedge\dots\wedge A_n)$, otherwise it is called consistent.

Definition 2 Let $F$ be a formula. We define $\tau(F)$ to be the set of subformulas of $F$. If $\mathcal{F}$ is a set of formulas, then we let $\tau(\mathcal{F})=\{A|A\in\tau(F), F\in\mathcal{F}\}$.

Definition 3 A set $\mathcal{F}$ of formulas is called complete if for every formula $A\in\tau(\mathcal{F})$ either $A\in\mathcal{F}$ or $\neg A\in\mathcal{F}$ (but not both).

Lemma 4 Let $\mathcal{F}$ be a finite, consistent set of formulas. There is a finite, consistent and complete set $\mathcal{F}^*$ of formulas with $\mathcal{F}\subseteq\mathcal{F}^*$.

Definition 5 Let us call a set $\mathcal{F}^*$ according to Lemma 4 a completion of $\mathcal{F}$.

Claim 6 In general, there may exist different completions of $\mathcal{F}$, but obviously only finitely many.


Question

Re claim 6: why are there only finitely many completions of $\mathcal{F}$?