If we take `φ`

and `ψ`

to range over the set of
propositional
formulas,
then the set H of propositional formulas
is called a propositional Hintikka set if and only if

- For every variable
`X`

it is not the case that both`X`

∈ H and`¬X`

∈ H; - neither
`f`

∈ H nor`¬t`

∈ H; - if
`¬¬φ`

∈ H then`φ`

∈ H; - if
`φ∧ψ`

∈ H then`φ`

∈ H and`ψ`

∈ H; - if
`φ∨ψ`

∈ H then`φ`

∈ H or`ψ`

∈ H; - if
`φ⇒ψ`

∈ H then`¬φ`

∈ H or`ψ`

∈ H; - if
`φ⇔ψ`

∈ H then both`φ⇒ψ`

∈ H, and,`ψ⇒φ`

∈ H.

Hintikka's lemma states that every Hintikka set is satisfiable.
The proof involves constructing a truth assignment, `γ`

,
where for each occurrence of the propositional variable `X`

in the set we assign
`γ`

(`X`

) = `t`

,
and for each occurrence of `¬X`

in the set, we assign `γ`

(`X`

) = `f`

.
It is easy to demonstrate that such an assignment can be constructed and that it satisfies the Hantikka set.

Fitting, Melvin. *First-Order Logic and Automated Theorem Proving.* Springer, 1990.

Copyright © 2014 Barry Watson. All rights reserved.