For the Compactness Theorem for Propositional Logic, show that the extension is not unique.

Question

During the proof of the compactness theorem, from an arbitrary finitely satisfiable set $\Sigma$ of WFFs, we construct a finitely satisfiable set $\Delta\supseteq \sigma$ such that for every WFF $\alpha$, either $\alpha\in\Delta$ or $\lnot\alpha \in\Delta$. Show that $\Delta$ need not be unique by describing an infinite, finitely satisable set $\Sigma$ of WFFs such that there is more than one possible extension $\Delta$.

Could someone please give me some guidance in answering this question? Much appreciated. Thanks.

If $\beta\notin \Sigma$ then $\Sigma\cup{\beta}$ and $\Sigma\cup{\lnot\beta}$ can be extended maximal finitely satisfiable set and they are not same. — Hanul Jeon, Oct 06 '13 at 01:08
@tetori: Not so fast. How about $\Sigma={\alpha, \alpha\to\beta}$? Then $\Sigma\cup{\neg\beta}$ will not be satisfiable. — hmakholm left over Monica, Oct 06 '13 at 02:12

score 1 · Answer 1 · answered Oct 05 '13 at 19:58

1

Hint. Suppose the language contains some unary predicate that is not mentioned in $\Sigma$ at all ...

answered Oct 05 '13 at 19:58

hmakholm left over Monica

286,031

For the Compactness Theorem for Propositional Logic, show that the extension is not unique.

1 Answers1