23. PL Proofs: Theorems

Question 1

From Tautologies to Theorems

Answer 1

A) Tautologies have a syntactic counterpart: a theorem
B) conclusion syntactically valid argument with no premises

Question 2

Peirce’s law ⊢((P → Q) → P) → P

Answer 2

1.1 SUPP ((P → Q) → P)
2.1 SUPP NOT P
3.1 SUPP P
3.2 FALSUM
3.3 EFQ Q
2.2 If P the Q (3.1-3.3)
2.3. P
2.4. FALSUM
1.2. NOT NOT P
1.3 P
If ((P → Q) → P) then P (1.1-1.3)

Question 3

The law of excluded middle (LEM)

Answer 3

1) LEM is interchangeable form DN
2) Given DN we can derive LEM and Vice-Versa
3) LEM is not part of our system, it is redundant
A) … α ∨ ¬α

Question 4

SOUND AND COMPLETE

Answer 4

Since our semantic (⊨) and syntactic (⊢) notions of validity perfectly match each other, then we can say:
A) SOUND if Γ⊢α then also Γ⊨α
B) COMPLETE if Γ⊨α then also Γ ⊢α
C) SUMMARY Γ⊢α if and only if Γ⊨α
D) SPECIAL CASE ⊢α if and only if ⊨α

Question 5

Complete-1

Answer 5

if Γ⊨α then also Γ ⊢α

Question 6

Complete-2

Answer 6

For all wff’s α: Γ ⊢α or Γ ⊢¬α

Question 7

Incompleteness Theorem:

Answer 7

In any reasonable mathematical system there will always be true statements that cannot be proved:
If a theory Γ meets certain simple criteria,
then there exists a wff α such that Γ ⊬α and Γ⊬ ¬α
in other words, then Γ is incomplete-2