Proof of Proposition 4 for the Completeness Theorem

Press the right key for the next slide (or swipe left)

also ...

Press the left key to go backwards (or swipe right)

Press n to toggle whether notes are shown (no equivalent if you don't have a keyboard)

Press m or double tap to see a menu of slides

This is a proof of Proposition 4 in §17.2 of the textbook LPL.

Define a structure, h, so that:

h(P)=T when P is in A*

h(P)=F when ¬P is in A*

Claim: h(X)=T for every X such that A* ⊢ X

We want to provide this slightly stronger claim (because we're going to do induction)

Proposition: for every X, h(X)=T iff A* ⊢ X

Suppose not. Then take the shortest sentence, Y, such that the Proposition is false.

Either: h(Y)=T and A* ⊬ Y

Or: h(Y)=F and A* ⊢ Y

We know that Y cannot be a sentence letter or its negation from the assumption about how h() was defined

Also, Y has the form (A→B) or (A∧B) or ...

Let's consider a case.

h(Y)=T

So h(A∧B)=T

So h(A)=T and h(B)=T

But A and B are shorter than Y

So, by assumption, A* ⊢ A and A* ⊢ B

Then A* ⊢ A∧B

i.e A* ⊢ Y

This contradicts our assumption

A* ⊢ Y i.e. A* ⊢ A→B

h(Y)=F i.e. h(A→B)=F

So h(A)=T and h(B)=F

But A and B are shorter than Y.

So, by assumption, A* ⊢ A and A* ⊬ B

But for all X, A* ⊢ X or A* ⊢ ¬X

So A* ⊢ ¬B

So A* ⊢ ¬(A→B) (proofs about proofs)

So A* ⊢ ⊥ (proofs about proofs), which contradicts our assumption.