Andreas van Cranenburgh 0440949

Basic Logic first exam

Thu Oct 22 13:27:50 CEST 2009

I worked alone.

Exercise 1

Δ_1 is complete

Δ_2 is not complete

Δ_3 is inconsistent

That Δ_3 is inconsistent can be shown thusly:

1. ¬(p -> q) pr.

2. ¬p pr.

3. +- p A

4. | ⊥ E¬2,3

5. | q EFSQ

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

6. p -> q I->

7. ⊥ E¬1,6

Δ_1 is consistent and complete. We can derive ¬q

1. ¬(p -> q) pr.

2. ¬q pr.

3. ¬q rep. 2

And we can derive p:

1. ¬(p -> q) pr.

2. ¬q pr.

3. +-- ¬p A

4. | +- p A

5. | | ⊥ E¬3,4

6. | | q EFSQ

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

7. | p -> q I->

8. | ⊥ E¬1,7

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

9. ¬¬p I¬

10. p E¬¬

So we can derive each atomic formula or its negation from this set. Now any

complex formula made of these atomic formulas can be derived, or its

negation, using these building blocks, thus the set is complete.

Lastly Δ_2 is consistent but not complete. Namely, neither Δ_2 ⊦ q nor

Δ_2 ⊦ ¬q. This can be seen by observing that both Δ_2' and Δ_2''

are consistent:

Δ_2' = { p -> q, ¬p, ¬q}

Δ_2'' = { p -> q, ¬p, q}

Since the antecedent p is false, the consequent can have any value. This

causes the incompleteness of Δ_2.

Exercise 2

Proposition: consider an arbitrary derivation Δ ⊦raa φ

Then it also holds that Δ ⊦ φ.

Base case:

a) a premise is introduced

b) an assumption is made

The proposition holds because these steps are equivalent in ⊦ and

⊦raa.

Inductive step: Assume the proposition holds for all steps k <= n (induction

hypothesis).

Consider step n + 1:

a) raa is applied. At some step j some sentence ¬ψ was in

Γ_j.

Γ_n = {¬ψ} U Γ_n+1.

At step n ⊥ is derived.

In ⊦raa we have:

j. +- ¬ψ A

| :

| :

n. | ⊥

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

n+1 ψ raa

Now in ⊦ we do:

j. +- ¬ψ A

| :

| :

n. | ⊥

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

¬¬ψ I¬

ψ E¬¬

b) All other cases: equivalent in ⊦ and ⊦raa.

Conclusion: A derivation in ⊦raa can be reformulated in ⊦, so Δ ⊦ φ

if Δ ⊦raa φ.

Proposition: consider an arbitrary derivation Δ ⊦ φ

Then it also holds that Δ ⊦raa φ.

Base case:

a) a premise is introduced

b) an assumption is made

The proposition holds because these steps are equivalent in ⊦ and

⊦raa.

Inductive step: Assume the proposition holds for all steps k <= n (induction

hypothesis).

Consider step n + 1:

a) E¬¬ is applied. At step n we have ¬¬ψ

in ⊦ we have:

n. ¬¬ψ

o. ψ E¬¬n

Now in ⊦raa we do:

n. ¬¬ψ

o. +- ¬ψ A

p. | ⊥ E¬n,o

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

q. ψ raa

b) I¬ is applied. At step n we have ⊥. At some step j < n we have

an assumption ψ. Γ_n = { ψ } U Γ_n+1.

In ⊦ we have:

j. +- ψ A

| :

| :

n. | ⊥

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

n+1 ¬ψ I¬

In ⊦raa we have to go back to step j and modify the assumption

by adding a double negation:

j. +-- ¬¬ψ A

j+1| + ¬ψ A

j+2| | ⊥ E¬j,j+1

j+3| +--------------

j+4| ψ raa

| :

| :

n | ⊥

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

n+1 ¬ψ raa

Going back to change the assumption does not affect the induction

hypothesis, because only new steps are inserted and no formulas are taken away, since at step j+4 we arrive at ψ, so that ⊥

can be derived just as it was in ⊦. At step n the same assumptions

are active in ⊦ and ⊦raa, except for ψ being ¬¬ψ in ⊦raa.

c) All other cases: equivalent in ⊦ and ⊦raa.

Conclusion: A derivation in ⊦ can be reformulated in ⊦raa,

so Δ ⊦raa φ if Δ ⊦ φ.

Exercise 3

a) Consider an I such that I(p) = 1/2. Then VI(¬¬p) = 1.

Because the antecedent has a higher value than the consequent,

VI(¬¬p -> p) = VI(p), which is I(p) = 1/2. So I(p) = 1/2 is a

counterexample for ⊧3 ¬¬p -> p, because there is a an interpretation

where its value is not 1.

b)

Lemma:

i) Δ ⊧3 ψ and Δ ⊧3 ¬ψ then Δ ⊧3 ⊥

From the definition of negation it can be seen that either

VI(ψ) = 0 or VI(¬ψ) = 0, so we can conclude that the lowest truth

value must be 0. By the definition of entailment in n-valued logic

we see that ⊥ is entailed, since any formula with a truth value equal

to or greater than the lowest truth value in the premises is entailed.

ii)

If Δ ⊧3 ψ and Δ ⊧3 ψ -> χ then Δ ⊧3 χ

In all interpretations the value of ψ is at least as high as the

lowest truth value in Δ, and in all interpretations either the

implication is true because ψ has a lower value or because ψ has a

higher value. In both cases we must conclude that χ is the case.

a) in the first because χ simply has a higher truth value than ψ, a

formula which was established to be valid

b) in the second because the implication receives as truth value the

valuation of χ, and the implication is valid, so χ on its own

must also be valid.

iii)

if Δ ⊧3 ψ and Δ ⊧3 χ then Δ ⊧3 ψ ^ χ

Conjunction is defined as the minimal truth value among both

conjuncts. Whichever of the two has this minimal truth value, it is

entailed so the conjunction must hold as well.

iv)

if Δ ⊧3 ψ then Δ ⊧3 ψ v χ and Δ ⊧3 χ v ψ

Disjunction is defined as the maximum of the truth value of the two

disjuncts. Thus, if ψ is entailed then both Δ ⊧3 ψ v χ and Δ ⊧3 χ v ψ

as well, regardless of the truth value of the newly introduced

disjunct.

Suppose there is an intuitionistic derivation of φ from Δ.

Then Δ ⊧n φ for say n = 3.

Proposition: consider an arbitrary derivation. For each step n in this

derivation, the sentence introduced at step n, follows logically from

the premises used in the derivation plus the assumptions that are active

at step n.

Base case: At the first step in a derivation there are two cases:

a) a premise is introduced

b) an assumption is made

Let φ_1 be the sentence entered. In both cases it follows immediately

that Δ, Γ_1 ⊧3 φ_1, because φ_1 is an element of Δ U Γ_1.

Inductive step:

Assume the proposition holds for all stepts k <= n

(induction hypothesis).

Consider step n + 1. The following cases can be discerned:

a) a premise is introduced

b) an assumption is made

These follow immediately, like in the base case.

c) at step n + 1 the sentence ⊥ is introduced by an application of

E¬. In this case there are j <= n and k <= n such that

i) at step j some sentence ψ and at step k the sentence ¬ψ is

introduced

ii) all assumptions active at j and k are also active at step n+1.

Otherwise it would not have been allowed to apply E¬.

So we find that Γ_j is a subset of Γ_n+1 and Γ_k is a subset of

Γ_n+1. The induction hypothesis tells us that Δ U Γ_j ⊧3 ψ

and Δ U Γ_k ⊧3 ¬ψ. Given the fact that Γ_j U Γ_k is a subset of Γ_n+1,

and lemma i), Δ U Γ_k ⊧3 ⊥.

d) At step n+1 a sentence of the form χ is introduced by an application

of E->. In this case we have the following:

i) At step j <= n we have ψ -> χ.

ii) At step k <= n we have ψ.

Γ_j U Γ_k ⊆ Γ_n+1, because E-> may only be applied to steps whose

assumptions have not been withdrawn.

The induction hypothesis tells us that

Δ U Γ_n ⊧3 ψ -> χ and Δ U Γ_n ⊧3 ψ.

Using lemma ii) we can conclude that

Δ U Γ_n+1 ⊧3 χ

e) 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) We know that Γ_i is a subset of Γ_n+1 and

Γ_j is a subset of Γ_n+1.

Following the induction hypothesis we may assume that:

Δ U Γ_i ⊧3 ψ

Δ U Γ_j ⊧3 χ

from this it follows, using lemma iii),

that Δ U Γ_n+1 ⊧3 φ.

f) 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 χ, or φ = χ v ψ

ii) Γ_i is a subset of Γ_n+1

Following the induction hypothesis we may assume that:

Δ U Γ_i ⊧3 ψ

from this it follows, using lemma iv),

that Δ U Γ_n+1 ⊧3 φ.

g) [...]

:

:

Conclusion: whenever there exists a derivation ⊦i φ, the formula

φ is valid in ⊧3.

This result generalizes for higher values of n, because we haven't

needed to refer to truth values except for the extreme values 0 and 1

which are always there.

c) Suppose we take ⊧3, then we can take the contrapositive of b)

if Δ ⊭3 φ then Δ ⊬i φ

Now we take φ = p v ¬p, and we take Δ as the empty set.

We establish ⊭3 p v ¬p using a truth table:

p ¬p p v ¬p

0 1 1

1/2 0 1/2 <-- counterexample for ⊧3 p v ¬p

1 0 1

With this counterexample we can conclude from the contrapositive that

⊬i p v ¬p

d)

⊭k θ_k, because there can be such an interpretation, where each value

is assigned only once, that each atomic sentence p_i is paired with an

atomic sentence p_j with a lower value, ie., in a descending order:

p_i -> p_j

The disjunct will then have the value of the consequent because p_i is

greater than p_j.

In the case of θ_3 the following reading would occur, where we write

the truth values instead of the symbols:

(1 -> 1/2) v (1/2 -> 0)

The first disjunct will have the value of 1/2, and this will be the

maximum of all disjuncts. Since there is no disjunct with the truth

value 1, this formula is not a tautology in ⊧3, because of this

counterexample.

The same holds for any higher k: the first disjunct will be the maximum,

but its value will be (k-2)/(k-1) instead of 1 which is the value of the

atomic sentence with the highest truth value.

On the other hand, ⊧k-1 θ_k. Because in a system with k-1 truth values,

any interpretation of a θ sentence with k proposition symbols will always

have at least two occurences of at least one truth value. Because of this

there cannot be an interpretation where the truth values appear in

descending and monotonically decreasing order in the θ sentence, as was

used in the counterexample before.

So there must be a disjunct:

p_i -> p_j

where I(p_i) <= I(p_j). This disjunct will receive the truth value 1,

and the formula will be valid.

e)

Sentences of the form θ_k are valid in ⊧k-1, however, they are not valid

in intuitionistic logic. To see this consider the interpretation where

the symbols p1 till p_k-1 receive the truth value 1, whereas p_k receives

the truth value 0.

Now, if we write truth values instead of proposition symbols,

the θ-formula reads:

(1 -> 1) v (1 -> 1) v ... v (1 -> 0)

It is easy to see that in this case all disjuncts except the last one

will have the truth value 1, whereas the last one will have the truth

value 0 (ie., the negation of the others, in terms of truth values).

Now we can apply the replacement theorem repeatedly to reduce the first

k-1 disjuncts to one, because in this interpretation for every disjunct φ except the last one, VI(φ) = 1, and φ v φ <-> φ. Then we apply the

replacement theorem to replace the last disjunct with the negation of the

first, and we end up with a formula of the form:

φ v ¬φ

However, because p v ¬p is not a tautology in intuitionistic logic, and

because we can use the substitution theorem to substitute these disjuncts

with p and ¬p, we can see that these sentences are not valid in

intuitionistic logic.

We have to conclude that that there are valid formulas in all n-valued

logics which are not derivable in intuitionistic logic.

Exercise 4

a)

If ⊭ φ, then φ is not a tautology. So there is an interpretation I

where the valuation VI(φ) = 0.

Given this interpretation, we can substitute the propositional symbols.

For every symbol p_i, if I(p_i) = 1, substitute ¬⊥ for it. Otherwise,

substitute ⊥ for it.

The effect of this is that every line of the truth table of *φ will look

like the interpretation that we used, thus for every interpretation I,

VI(¬φ*) will be true.

b)

Suppose we have a system ⊧s which is stronger than classical logic.

If it is stronger there must be some φ such that:

⊧s φ, but not ⊧ φ

Ie., in ⊧s φ is a tautology, but not in ⊧. However, given a) we know that

if ⊭ φ, we can substitute in such a way as to obtain *φ such that

⊧ ¬φ*.

But given the substitution theorem, we can substitute any part of a

tautology with any formula, so also the substition instance φ* should

still be a tautology in ⊧s.

Now we have a contradiction, because ⊧s φ*, yet ⊧ ¬φ* according to

classical logic. So we have to retract our assumption that there can be a

stronger system than classical logic.