Andreas van Cranenburgh 0440949 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 hypthesis). 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 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. Because the highest atomic sentence has the 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. 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.