I am trying to study Mathematical Logic by Chiswell and Hodges.

They prove that for every syntactically consistent set Γ of formulas, there is a Hintikka set Δ s.t. Γ ⊆ Δ.

They describe an algorithm to construct the Hintikka set. The algorithm needs to check whether the addition of the new formula preserves the syntactical consistency of the set. But how is the algorithm able to tell whether that's the case?


The aim of the proof (often called *"Model existence lemma") is to show that a consistent set of formulae has a model.

Chiswell & Hodges [page 91-92] split the proof into :

Lemma 3.10.5 Every Hintikka set has a model.

Lemma 3.10.6 If Γ is a syntactically consistent set of formulas of LP(σ), then there is a Hintikka set Δ of formulas of LP(σ) with Γ ⊆ Δ.

Please, note that the statement of the second Lemma says : "there is"; this does not mean that the Lemma will provide an algorithm (a "recipe") to build up "effectively" the set Δ.

The gist of this completeness theorem is that it is not constructive.

| improve this answer | |

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.