0440949 Andreas van Cranenburgh. Basic Logic homework 3.

Exercise 11.

Step f) At step n+1 I^ is applied. In this case there are

steps i <= n and j <= n, such that:

i) At step i a sentence ψ has been introduced. At step j a

sentence χ has been introduced. Sentence φ = ψ ^ χ.

ii) the union of Gamma_i and Gamma_j is a proper subset of

Gamma_n+1

Following the induction hypothesis we may assume that:

the union of Delta and Gamma_i entails ψ

the union of Delta and Gamma_j entails χ

from this it follows, using the semantic definition of

conjunction, that the union of Delta and Gamma_n+1 entails φ.

Step g) At step n+1 E^ is applied. In this case there is

step i <= n, such that:

i) At step i a sentence ψ has been introduced, of the form

ψ = φ ^ χ

or ψ = χ ^ φ.

ii) Gamma_i is a proper subset of Gamma_n+1

Following the induction hypothesis we may assume that:

the union of Delta and Gamma_i entails ψ

from this it follows, using the semantic definition of

conjunction, that the union of Delta and Gamma_n+1 entails φ.

Step h) At step n+1 Iv is applied. In this case there is

step i <= n, such that:

i) At step i a sentence ψ has been introduced. There is an

arbitrary sentence χ. Sentence φ = ψ v χ.

ii) Gamma_i is a proper subset of Gamma_n+1

Following the induction hypothesis we may assume that:

the union of Delta and Gamma_i entails ψ

from this it follows, using the semantic definition of

disjunction, that the union of Delta and Gamma_n+1 entails φ.

Step j) Application of E->

Step k) Application of I->

Step l) Application of E~~

Exercise 12

Suppose ~~φ is derivable from Delta in intuitionistic logic, then

there is a simple derivation in classical logic to obtain φ:

.

.

.

n ~~φ

n+1 φ E~~

Converse:

Suppose there is a derivation of φ from Delta in classical logic.

base case: At step 1 we have the following possibilities:

- a premise is introduced

- an assumption is made

Both of these steps can be made in intuitionistic logic as well.

induction step:

induction hypothesis: if φ_n can be derived in classical logic, then

~~φ_n can be derived in intuitionistic logic.

Suppose the induction hypothesis holds, then at the next step the

following possibilities can occur:

a) a premise is introduced

b) an assumption is made

c) ⊥ is introduced

d) Negation introduction

these four can be made in intuitionistic logic as well so they don't

contradict the induction hypothesis.

e) EFSQ

At some step i <= n we have ⊥, under the same assumptions as step n.

we assume ~φ_n+1

repeat ⊥

withdraw assumption, introduce negation. No we have ~~φ_n+1.

f) Conjunction introduction, see lemma (ii)

g) conjuction elimination, see lemma (iii)

h) disjunction introduction, see lemma (iv)

i) disjunction elimination, see lemma (v)

j) Application of E->

For some i and j >= n, φ_i = ~~φ and φ_j = ~~(φ -> ψ). By

lemma (vii) ~~ψ can be derived.

k) Application of I->, at step n some φ is in Gamma and some formula

~~ψ has been derived. Then by lemma (vi), ~~(φ -> ψ) can be derived.

Alternatively, the formula ψ has been derived from φ. In this case

φ -> ψ can simply be derived.

l) Application of E~~

If φ_n has an even number of negations greater than 2, then lemma

(viii) is applied. Otherwise this step is skipped.

Lemma:

(iii)

1. ~~(φ ^ ψ) pr.

2. +-- ~φ A

3. | - φ ^ ψ A

4. | | φ E^3

5. | | ⊥ E~2,4

6. | | ~(φ ^ ψ) I~

| +--------------------

7. | ⊥ E~1,6

+----------------------

8. ~~φ I~

(vi)

still looking for this one...

(vii)

1. ~~φ pr.

2. ~~(φ -> ψ) pr.

3. +---- ~ψ A

4. | +-- φ -> ψ A

5. | | - φ A

6. | | | ψ E->4,5

7. | | | ⊥ E~3,6

| | +-------------------

8. | | ~φ I~

9. | | ⊥ E~1,8

| +---------------------

10.| ~(φ->ψ) I~

11.| ⊥ E~10,2

+------------------------

12. ~~ψ I~

Exercise 13

1. p -> q prem.

2. q -> r prem.

3. (q -> r) -> (p -> (q ->r )) Axiom i

4. p -> (q -> r) 2,3 mp

5. (p -> (q -> r)) -> ((p -> q) -> (p -> r)) Axiom ii

6. (p -> q) -> (p -> r) 4,5 mp

7. p -> r 1,6 mp

Exercise 14

By the deduction theorem it is sufficient to show that

p -> (q -> r), q |- p -> r

1. p -> (q -> r) prem.

2. q prem.

3. q -> (p -> q) Axiom i

4. p -> q 2,3 mp

5. (p -> (q -> r)) -> ((p -> q) -> (p -> r)) Axiom ii

6. (p -> q) -> (p -> r) 4,5 mp

7. p -> r 4,6 mp

Exercise 15

Lemma:

Axioms derived using natural deduction:

(i)

1. +-- φ A

2. | - ψ A

3. | | φ rep 1

| +-----------------------

4. | ψ -> φ I->

+-------------------------

5. φ -> (ψ -> φ) I->

(ii)

1. +--- φ -> (ψ -> χ) A

2. |+-- φ -> ψ A

3. || - φ A

4. || | ψ -> χ E->1,3

5. || | ψ E->2,3

6. || | χ E->4,5

|| +-----------------------

7. || φ -> χ I->

|+-------------------------

8. | (φ -> ψ) -> (φ -> χ) I->

+--------------------------

9. (φ -> (ψ -> χ)) -> (φ -> ψ) -> (φ -> χ) I->

(iii)

1. +-- ~φ A

2. | - φ A

3. | | ⊥ E~1,2

| +------------

4. | φ -> ⊥ I->

+----------------

5. ~φ -> (φ -> ⊥) I->

(iv)

1. +-- φ -> ⊥ A

2. | - φ A

3. | | ⊥ E->1,2

| +-------------------

4. | ~φ I~

+----------------------

5. (φ -> ⊥) -> ~φ I->

(v)

1. +-- ⊥ A

2. | - ~φ A

3. | | ⊥ rep. 1

| +--------------------------

4. | ~~φ I~

5. | φ E~~

+-----------------------

6. ⊥ -> φ I->

(vi)

1. - ~~φ A

2. | φ E~~

+-----------------------

3. ~~φ -> φ I->

Suppose there is an axiomatic deduction of φ from Delta, then there is

also a natural deduction. Let φ_k be the sentence derived at step k.

We prove by induction on k that φ_k is derivable using natural

deduction:

base case:

a) φ_1 is an element of Delta

b) φ_1 is an axiom

discussed in step case

step case: n = k + 1.

induction hypothesis: Assume there is a natural deduction up till k.

At step n the sentence φ_n is derived in one of the following ways:

a) φ_n is an element of Delta: introduce premise.

b) φ_n is an axiom: introduce derivation of axiom, see lemma.

c) φ_n is obtained using modus ponens, using θ -> φ_n and θ at

previous steps. Apply implication elimination.

Suppose there is a natural deduction of φ from Delta, then there is

also an axiomatic deduction. Let φ_k be the sentence derived at

step k. We prove by induction on k that φ_k is derivable using

axiomatic deduction:

base case:

Gamma_0 = {}

a) a premise is introduced

b) an assumption is made

discussed in step case

step case:

induction hypothesis: n = k + 1. Assume there is an axiomatic

deduction up till k, with Gamma_k = Gamma_k-1 unless otherwise specified.

At step n the following can happen:

a) a premise is introduced: same in axiomatic deduction

b) an assumption is made: add φ_n to Gamma_n.

c) ⊥ is introduced:

For some i and j >= n, φ_i = ~φ and φ_j = φ. Derive ψ using modus

ponens on axiom (iii) with i and then j.

1. ~φ -> (φ -> ⊥) axiom (iii)

2. φ -> ⊥ mp 1,i

3. ⊥ mp 2,j

d) Negation introduction: use axiom (v)

e) EFSQ: use axiom (v)

f) Application of E~~, use axiom (vi)

g) Application of E->

For some i and j >= n, φ_i = φ and φ_j = φ -> ψ. Derive ψ using

modus ponens on i and j.

h) Application of I->, at step n-1 some ψ is in Gamma_n-1 and some

formula χ derived at step j <= n. Deduction theorem shows that ψ -> χ

can be obtained if Delta and ψ entail χ. ψ is removed from Gamma_n

Exercise 16

Conjunction introduction

Aiom: ψ -> (φ -> (φ ^ ψ))

Conjuction elimination:

Axiom: (φ ^ ψ) -> φ

Axiom: (φ ^ ψ) -> ψ

Disjunction introduction:

Axiom: (φ v ψ) -> φ

Axiom: (φ v ψ) -> ψ

Disjunction elimination:

Axiom: (φ v ψ) -> ((φ -> χ) -> ((φ -> χ) -> χ))