<<

. 101
( 107 .)



>>

Exercises


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-

<<

. 101
( 107 .)



>>