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: