Chapter I
A Weak Post’s Theorem and the Deduction Theorem Retold
This note is about the Soundness and Completeness (“Post’s Theorem”) in Boolean logic.
1. Soundness of Boolean Logic
Soundness is the Property expressed by the statement of the metatheory below:
IfΓ⊢A,thenΓ|=taut A (1)
1.1 Definition. The statement “Boolean logic is Sound”
means that Boolean logic satisfies (1).
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
2 I. A Weak Post’s Theorem and the Deduction Theorem Retold
To prove soundness is an easy induction on the length
of Γ-proofs:
We prove that proofs preserve truth.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
1. Soundness of Boolean Logic 3 1.2 Lemma. Eqn and Leib preserve truth, that is,
A, A ≡ B |=taut B (2) A≡B|=taut C[p:=A]≡C[p:=B] (3)
and
Proof. We proved (2) in Assignment #1. We prove (2)
now:
So, let a state s make A ≡ B true (t). We will show that
C[p := A] ≡ C[p := B] is t in state s (4) If p is not in C then (4) is C ≡ C, a tautology, so is
true under s in particular.
Let then the distinct p,q,r,r′,r′′,… all occur in C.
Now in the lhs of (4) p gets the value s(A), while q, r, r′, r′′, . . . get their values DIRECTLY from s.
Now, in the RHS of (4) p gets the value s(B), while q, r, r′, r′′, . . . STILL get their values DIRECTLY from s.
But s(A) = s(B).
So both the lhs and rhs of (4) end up with the same
truth value after the indicated substitutions.
In short, the equivalence is true.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
4 I. A Weak Post’s Theorem and the Deduction Theorem Retold We can now prove:
1.3 Metatheorem. Boolean logic is Sound, that is, (1) on p.1 holds.
Proof. By induction on the length of proof, n, needed to
obtain Γ ⊢ A we prove
Γ |=taut A (†) So pick a state s that satisfies Γ. (‡)
1. Basis. n = 1. Then we have just A in the proof.
If A ∈ Λ, then it is a tautology, so in particular is
true under s. We have (†).
If A ∈ Γ, then s satisfies A. Again we have (†).
I.H. Assume for all proofs of length ≤ n.
I.S. Prove the theorem in the case (†) needed a proof of length n + 1:
length =n
… ,A
length =n+1
Now if A is in Λ∪Γ we are back to the Basis. Done.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
1. Soundness of Boolean Logic 5 If not
• Case where A is the result of EQN on X and X ≡ Y that are in the “…-area”.
By the I.H. s satisfies X and X ≡ Y hence, by the Lemma, satisfies A.
• Case where A is the result of LEIB on X ≡ Y that are is the “. . .-area”.
By the I.H. s satisfies X ≡ Y hence, by the Lemma, satisfies A.
1.4 Corollary. If ⊢ A then |=taut A. A is a tautology. Proof. Γ = ∅ here. BUT, EVERY state s satisfies THIS
Γ, vacuously:
Indeed, to prove that some state v does NOT you
NEED an X ∈ ∅ such that v(X) = f; IMPOSSIBLE. Hence every state satisfies A. Thus a |=taut A.
1.5
las: To show they are NOT theorems.
Example. Soundness allows us to disprove formu- • ⊢ p is false. If this were true, then p would be a
tautology!
• ⊢ ⊥ is false! Because ⊥ is not a tautology!
• p ⊢ p∧q is false. Because if it were true I’d have to have p |=taut p ∧ q.
Not so: Take a state s such that s(p) = t and s(q) =
f.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
6 I. A Weak Post’s Theorem and the Deduction Theorem Retold 2. Completeness of Boolean logic
(“Post’s Theorem”)
We prove here
(1) A weak form of Post’s theorem: If Γ is finite and
Γ|=taut A,thenΓ⊢A
and derive as a corollary the Deduction Theorem:
(2) If Γ, A ⊢ B, then Γ ⊢ A → B.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
2. Completeness of Boolean logic (“Post’s Theorem”) 7 2.1. Some tools
We will employ the TWO results from class/text below:
2.1 Theorem. ⊢ ¬(C∨D)∨E ≡ (¬C∨E)∧(¬D∨E). 2.2 Theorem. ¬C ∨ E, ¬D ∨ E ⊢ ¬(C ∨ D) ∨ E.
2.3 Main Lemma. Suppose that A contains none of the symbols ⊤, ⊥, →, ∧, ≡. If |=taut A, then ⊢ A.
Proof. The proof is long but easy!
Under the assumption, A is an ∨-chain, that is, it has the form
A1 ∨A2 ∨A3 ∨…∨Ai ∨…∨An (1) wherenoneoftheAi hastheformB∨C.
In (1) we assume without loss of generality that n > 1,
due to the axiom X ∨ X ≡ X —that is, in the contrary case we can use A ∨ A instead, which is a tautology as well.
Moreover, (1), that is A, is written in least parenthesised
notation.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
8 I. A Weak Post’s Theorem and the Deduction Theorem Retold
Let us call an Ai reducible iff it has the form ¬(C ∨ D)
or ¬(¬C).
“Reducible”, since Ai is not alone in the ∨-chain, will be
synonymous to simplifiable. Otherwise Ai is irreducible. Not simplifiable.
Thus, the only possible irreducible Ai have the form p or ¬p (where p is a variable).
We say that p “occurs positively in . . .∨p∨. . .”, while it “occurs negatively in …∨¬p∨…”.
In, for example, p ∨ ¬p it occurs both positively and negatively.
By definition we will say that A is irreducible iff all its Ai are.
We define the reducibility degree, of EACH Ai —in sym- bols, rd(Ai)— to be the total number, counting repetitions of the ¬ and ∨ connectives in it, not counting a pos- sible leading ¬.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
2. Completeness of Boolean logic (“Post’s Theorem”) 9 The reducibility degree of the entire A is the sum of the
reducibility degrees of all its Ai.
For example, rd(p) = 0, rd(¬p) = 0, rd(¬(¬p ∨ q)) =
2, rd(¬(¬p ∨ ¬q)) = 3, rd(¬p ∨ q) = 0.
By induction on rd(A) we now prove the main lemma,
that ⊢ A on the stated hypothesis that |=taut A.
For the Basis, let A be an irreducible tautology —so,
rd(A) = 0.
It must be that A is a string of the form “···∨p∨···¬p∨···”
for some p, otherwise,
if no p appears both “positively” and “negatively”,
then we can find a truth-assignment that makes A false (f) —a contradiction to its tautologyhood.
To see that we can do this, just assign f to p’s that occur positively only, and t to those that occur neg- atively only.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
10 I. A Weak Post’s Theorem and the Deduction Theorem Retold Now
A
⇔ commuting the terms of an ∨-chain p∨¬p∨B (what is “B”?)
⇔ Leib + axiom + Red. ⊤ META; Denom: r ∨ B; fresh r ⊤ ∨ B bingo!
Thus ⊢ A, which settles the Basis-case: rd(A) = 0.
We now argue the case where rd(A) = m+1, on the I.H. that for any formula Q with rd(Q) ≤ m, we have that |=taut Q implies ⊢ Q.
By commutativity (symmetry) of “∨”, let us assume without restricting generality that rd(A1) > 0.
We have two cases:
(1) A1 is the string ¬¬C, hence A has the form
¬¬C ∨ D.
Clearly |=taut C ∨ D as well.
Moreover, rd(C ∨ D) < rd(¬¬C ∨ D), hence (by I.H.) ⊢C∨D (†)
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
2. Completeness of Boolean logic (“Post’s Theorem”) 11 But,
¬¬C ∨ D
⇔Leib + ⊢ ¬¬X ≡ X; Denom: r ∨ D; fresh r
C ∨ D (†) above is “bingo”!
Hence, ⊢ ¬¬C ∨ D, that is, ⊢ A in this case.
Lecture #12, Oct. 23
One more case to go:
(2) A1 is the string ¬(C ∨ D), hence A has the form ¬(C ∨ D) ∨ E.
Wewant: ⊢¬(C∨D)∨E (i)
By 2.1 and from |=taut ¬(C ∨ D) ∨ E —this says |=taut A— we immediately get that
and
from the ≡ and ∧ truth tables.
|=taut ¬C ∨ E (ii) |=taut ¬D ∨ E (iii)
Since the rd of each of (ii) and (iii) is < rd(A), the I.H. yields ⊢ ¬C ∨ E AND ⊢ ¬D ∨ E.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
12 I. A Weak Post’s Theorem and the Deduction Theorem Retold
Apply the RULE 2.2 to the above two theorems to get
(i).
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
2. Completeness of Boolean logic (“Post’s Theorem”) 13 We are done, except for one small detail:
If we had changed the “original” A into A ∨ A (cf. the “without loss of generality” remark just below (1) on p.7), then all we proved above is ⊢ A ∨ A.
The contraction rule from (e-)Class, Notes, and Text
then yield ⊢ A.
But ALL this only proves “|=taut A implies ⊢ A” when A does not contain ∧, →, ≡, ⊥, ⊤.
WHAT IF IT DOES?
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
14 I. A Weak Post’s Theorem and the Deduction Theorem Retold
We are now removing the restriction on A regarding
its connectives and constants:
2.4 Metatheorem. (Post’s Theorem) If |=taut A, then ⊢ A.
Proof. First,wenotethefollowingtheoremsstatingequiv- alences, where p is fresh for A.
The proof of the last one is in the notes and text but it was too long (but easy) to cover in class.
⊢ ⊤ ≡ ¬p ∨ p
⊢ ⊥ ≡ ¬(¬p ∨ p)
⊢ C → D ≡ ¬C ∨ D (2)
⊢ C ∧ D ≡ ¬(¬C ∨ ¬D)
⊢ (C ≡ D) ≡ ((C → D) ∧ (D → C))
Using (2) above, we eliminate, in order, all the ≡, then all the ∧, then all the → and finally all the ⊥ and all the ⊤.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
2. Completeness of Boolean logic (“Post’s Theorem”) 15 Let us assume that our process eliminates one unwanted
symbol at a time.
This leads to the Equational Proof below.
Starting from A we will generate a sequence of formu-
lae
whereFn containsno⊤,⊥,∧,→,≡.
I am using here F1 as an alias for A. We will also give to Fn an alias A′.
A
⇔ Leib from (2) F2
⇔ Leib from (2) F3
⇔ Leib from (2) F4
.
⇔ Leib from (2)
A′
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
F1,F2,F3,...,Fn
16 I. A Weak Post’s Theorem and the Deduction Theorem Retold
Thus,⊢A′ ≡A (∗)
By soundness, we also have |=taut A′ ≡ A (∗∗) So, say |=taut A. By (∗∗) we have |=taut A′ as well, and
by the Main Lemma 2.3 we obtain ⊢ A′. By (∗) and Eqn we get ⊢ A.
Post’s theorem is the “Completeness Theorem”† of Boolean Logic.
It shows that the syntactic manipulation apparatus — proofs— DOES certify the “whole truth” (tautologyhood)
in the Boolean case.
†Which is really a Metatheorem, right?
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
2. Completeness of Boolean logic (“Post’s Theorem”) 17 2.5 Corollary. If A1, . . . , An |=taut B, then A1, . . . , An ⊢
B.
Proof. It is an easy semantic exercise to see (see the spe-
cial case in Problem Set #1, Fall 2020) that |=taut A1 →...→An →B
By 2.4,
⊢A1 →...→An →B hence (hypothesis strengthening)
A1,A2...,An ⊢A1 →A2 →...→An →B (1) Applying modus ponens n times to (1) we get
A1,...,An ⊢B
The above corollary is very convenient.
It says that every (correct) schema A1, . . . , An |=taut B
leads to a derived rule of inference, A1, . . . , An ⊢ B. In particular, combining with the transitivity of ⊢
metatheorem, we get
2.6 Corollary. If Γ ⊢ Ai, for i = 1,...,n, and if A1,...,An |=taut
B, then Γ⊢B.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
18 I. A Weak Post’s Theorem and the Deduction Theorem Retold
Thus —unless otherwise requested!— we can, from now on, rigorously mix syntactic with semantic justifications of our proof steps.
For example, we have at once A ∧ B ⊢ A, because (trivially) A∧B |=taut A (compare with our earlier, much longer, proof given in class).
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
3. Deduction Theorem, Proof by Contradiction 19 3. Deduction Theorem,
Proof by Contradiction
3.1 Metatheorem. (The Deduction Theorem) If Γ, A ⊢ B, then Γ ⊢ A → B, where “Γ,A” means “all the as- sumptions in Γ, plus the assumption A” (in set notation this would be Γ ∪ {A}).
Proof. Let G1,...,Gn ⊆ Γ be a finite set of formulae used in a Γ, A-proof of B.
Thus we also have G1,...,Gn,A ⊢ B. By soundness, G1, . . . , Gn, A |=taut B.
But then,
G1,...,Gn |=taut A → B By2.5,G1,...,Gn ⊢A→BandhenceΓ⊢A→Bby
hypothesis strengthening.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
20 I. A Weak Post’s Theorem and the Deduction Theorem Retold
The mathematician, or indeed the mathematics practi- tioner, uses the Deduction theorem all the time, with- out stopping to think about it. Metatheorem 3.1 above makes an honest person of such a mathematician or prac- titioner.
The everyday “style” of applying the Metatheorem goes like this:
Say we have all sorts of assumptions and we want, un- der these assumptions, to “prove” that “if A, then B” (verbose form of “A → B”).
We start by adding A to our assumptions, often with the words, “Assume A”. We then proceed and prove just B (not A → B), and at that point we rest our case.
Thus, we may view an application of the Deduction theorem as a simplification of the proof-task. It allows
us to “split” an implication A → B that we want to prove, moving its premise to join our other assumptions.
We now have to prove a simpler formula, B, with the help of stronger assumptions (that is, all we knew so far, plus A). That often makes our task so much easier!
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
3. Deduction Theorem, Proof by Contradiction 21
An Example. Prove
⊢ (A → B) → A ∨ C → B ∨ C
By DThm, suffices to prove
A→B⊢A∨C→B∨C
instead.
Again By DThm, suffices to prove
instead.
Let’s do it:
1. A→B
2. A∨C
3. A→B≡¬A∨B 4. ¬A∨B
5. B∨C
⟨hyp⟩
⟨hyp⟩ ⟨¬∨thm⟩ ⟨1+3+Eqn⟩ ⟨2+4+Cut⟩
A → B, A ∨ C ⊢ B ∨ C
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
22 I. A Weak Post’s Theorem and the Deduction Theorem Retold
3.2 Definition. A set of formulas Γ is inconsistent or
contradictory iff Γ proves every A in WFF.
Why “contradictory”? For if Γ proves everything, then
it also proves p ∧ ¬p. 3.3 Lemma. Γ is inconsistent iff Γ ⊢ ⊥
Proof. only if-part. If Γ is as in 3.2, then, in particular, it proves ⊥ since the latter is a well formed formula.
if-part. Say, conversely, that we have
Γ⊢⊥ (9)
Let now A be any formula in WFF whatsoever. We have ⊥ |=taut A (10)
Pause. Do you believe (10)?
By Corollary 3.4, Γ ⊢ A follows from (9) and (10).
3.4 Metatheorem. (Proof by contradiction) Γ ⊢ A iff Γ ∪ {¬A} is inconsistent.
Proof. if-part. So let (by 3.3) Γ, ¬A ⊢ ⊥
Hence
by the Deduction theorem. However ¬A → ⊥ |=taut A,
Γ ⊢ ¬A → ⊥ (1) hence, by Corollary 2.6 and (1) above, Γ ⊢ A.
only if-part. So let
Γ⊢A
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis
3. Deduction Theorem, Proof by Contradiction 23 By hypothesis strengthening,
Γ, ¬A ⊢ A (2)
Moreover, trivially,
Γ, ¬A ⊢ ¬A (3) Since A,¬A |=taut ⊥, (2) and (3) yield Γ,¬A ⊢ ⊥ via
Corollary 2.6, and we are done by 3.3.
3.4 legitimises the tool of “proof by contradiction” that goes all the way back to the ancient Greek mathemati- cians: To prove A assume instead the “opposite”, ¬A. Proceed then to obtain a contradiction. This being ac- complished, it is as good as having proved A.
A “Weak” Post’s Theorem and the Deduction Theorem© by George Tourlakis