19.32 G¨del™s Incompleteness Theorem was inspired by the famous Liar™s Paradox, the sentence This

o

sentence is not true.

1. Let us assume that this sentence makes an unambiguous claim. Show that the claim

is true if and only if it is not true.

2. Conclude that the sentence must not be making an unambiguous claim.

3. One possibility for locating the ambiguity is in a shift in the domain of discourse as

the argument proceeds. Discuss this suggestion.

Section 19.8

556 / Completeness and Incompleteness

19.33 (Unde¬nability of Truth) Show that the following predicate cannot be expressed in the language

of arithmetic:

n is the code of a true sentence.

This is a theorem due to Alfred Tarski. [Hint: Assume it were expressible. Apply the Diagonal

Lemma to obtain a sentence which says of itself that it is not true.]

19.34 (L¨b™s Paradox) Consider the sentence If this conditional is true, then logic is the most fasci-

o

nating subject in the world. Assume that the sentence makes an unambiguous claim.

1. Use the method of conditional proof (and modus ponens) to establish the claim.

2. Use modus ponens to conclude that logic is the most fascinating subject in the world.

Surely a good way to end a logic course.

Chapter 19

Summary of Rules

Propositional rules (FT)

Conjunction Introduction Conjunction Elimination

(§ Intro) (§ Elim)

P1 P1 § . . . § Pi § . . . § Pn

.

.

“ .

Pn Pi

.

.

.

P1 § . . . § Pn

Disjunction Introduction Disjunction Elimination

(∨ Intro) (∨ Elim)

Pi P1 ∨ . . . ∨ Pn

. .

. .

. .

P1 ∨ . . . ∨ Pi ∨ . . . ∨ Pn P1

.

.

.

S

“

Pn

.

.

.

S

.

.

.

S

557

558 / Summary of Rules

Negation Introduction Negation Elimination

(¬ Intro) (¬ Elim)

¬¬P

P

.

.

.

.

.

. P

⊥

¬P

⊥ Introduction ⊥ Elimination

(⊥ Intro) (⊥ Elim)

P ⊥

. .

. .

. .

¬P P

.

.

.

⊥

Conditional Introduction Conditional Elimination

(’ Intro) (’ Elim)

P’Q

P .

.

.

.

.

. P

.

.

Q .

Q

P’Q

Summary of Rules

First-order rules (F ) / 559

Biconditional Introduction Biconditional Elimination

(” Intro) (” Elim)

P ” Q (or Q ” P)

P

.

.

.

.

.

. P

.

.

Q .

Q

Q

.

.

.

P

P”Q

Reiteration

(Reit)

P

.

.

.

P

First-order rules (F)

Identity Introduction Identity Elimination

(= Intro) (= Elim)

n=n P(n)

.

.

.

n=m

.

.

.

P(m)

First-order rules (F )

560 / Summary of Rules

General Conditional Proof Universal Elimination

(∀ Intro) (∀ Elim)

∀x S(x)

c P(c) .

.

.

. S(c)

.

.

Q(c)

∀x (P(x) ’ Q(x))

Universal Introduction

(∀ Intro)

c

.

.

.

P(c)

∀x P(x)

where c does not occur out-

side the subproof where it is

introduced.

Existential Introduction Existential Elimination

(∃ Intro) (∃ Elim)

S(c) ∃x S(x)

. .

. .

. .

∃x S(x) c S(c)

.

.

.

Q

Q

where c does not occur out-

side the subproof where it is

introduced.

Summary of Rules

Inference Procedures (Con Rules) / 561

Inference Procedures (Con Rules)

Fitch also contains three, increasingly powerful inference procedures. They

are not technically inference rules.

Tautological Consequence

(Taut Con)

Taut Con allows you to infer any sentence that follows from the cited sen-