Model Existence Lemma (Propositional Logic)

Let be Consistent.
Then has a Model (Propositional Logic)

Proof

We want to find a deductively closed set with
i.e. we want a set such that if and then
where is also consistent.

Countable case

Note that is countable, and hence by induction is also countable for all . Thus is countable.
We enumerate as

If is consistent and then one of or is consistent. Indeed, if not, then and
Then by Deduction Theorem, we have and and hence by (MP) which is a contradiction

Now start with the consistent .
Let
We define sets by induction:
Assume is defined and is consistent
Then let be either or ,
so that is consistent
Finally, let

Note that and either or .

Also is consistent: if then as proofs are finite, there is some such that which is a contradiction.

Uncountable case

We seek a maximal consistent set .
Let
partially ordered by .
since
Let be a nonempty Chain in .
We show is an Upper Bound:
, , it remains to show that is consistent.
If , then as proofs are finite there are some
s.t. .
Since is a chain there is some such that
Thus is consistent.
By Zorn’s Lemma, has a maximal element
Now for any , either or is consistent,
otherwise and
by the Deduction Theorem (Propositional Logic)
Then by MP.
It follows from maximality of that either or .

Finish proof

is deductively closed i.e. if and then .
Indeed, if then . So we have a proof:
First write down a proof of from and add the lines:

We now define by

Note that is a model of and hence of .

We show that is a valuation:
Firstly, since is consistent.
We now check for arbitrary

Case 1

, i.e.
need
If not, then . Write down a proof of from and add:

So and , since is deductively closed.

Case 2

i.e. .
need
Note that

So and

Case 3

i.e. and so
need: , i.e. or equivalently by Deduction Theorem
Note that: