Home Philosophy Advances in ProofTheoretic Semantics


The Liar ParadoxIn this section we shall study the liar paradox as an example of a selfcontradictory argument. The liar paradox is the following. Let P be the sentence “This sentence is false.” That is, P is the sentence “ P is false.” Assume P. Hence, by the definition of P, P is false. This contradicts the assumption P, and hence P is false. Since P is false, P follows from the definition of P. This is a contradiction. This argument is very similar to Russell's paradox. Below we present the formal system FP, specially designed for a formal presentation of the liar paradox. The language of FP is the set of formulas, where ⊥ and P are formulas, and if A and B are formulas, then A ⊃ B is a formula; ¬ A is defined to be A ⊃ ⊥. The inference schemata of FP are the following. D ¬ P PI P [ A] D B A ⊃ B ⊃I D P PE ¬ P D E A ⊃ B A B ⊃ The liar paradox is formally represented by the following deduction G , F ⎫ ⎧ [ P ] PE F ¬ P PI ⎪⎬ G where F ⎪⎨ ¬ P [ P] ¬ P P ⊃E⎪⎭ ⊥ ⎪ ⊥ I ¬ P The set of formal meanings to be assigned to formulas in deductions in the formal system FP is inductively defined as follows. The meaning variable x is a meaning, and if m and n are meanings, then pm and m ⇒ n are meanings. We may interpret the meanings as follows: m ⇒ n means “m implies that n,” and pm means “This sentence is false,” where “This” refers to the sentence expressed by m. The meaning conditions associated with the formal system FP are the following. D m :¬P PI pm : P [m : A] D n : B I m ⇒ n : A ⊃ B D pm : P PE m : ¬ P D E m ⇒ n : A ⊃ B m : A n : B ⊃ Now assume that there is an assignment of formal meanings to the formulas in the deduction F above such that this assignment satisfies the meaning conditions. Assume that m is the meaning of the minor premise P of the ⊃E inference and that n is the meaning of the conclusion ⊥ of the ⊃E inference. Then, by the conditions above we conclude that the meaning of the premise P of the PE inference must be p(m ⇒ n). [ p (m ⇒ n ) : P ] PE m ⇒ n :¬P [m : P ] n : ⊥ ⎫ ⎬⎪ ⊃E F ? : ¬ P ⊃I ⎪⎭ The condition given for the ⊃I inference schema requires both of the formulas cancelled at the ⊃I inference in F to have the same meaning. However, no matter how we choose m and n the meanings m and p(m ⇒ n) are not the same. Hence, there is no assignment of formal meanings to the formulas in F such that this assignment satisfies the meaning conditions. Hence, F is selfcontradictory. Selfcontradictory Reasoning in N−∀∃=Let N−∀∃= be the fragment of N obtained by removing the symbols ∀, ∃ and = and the inference schemata corresponding to these symbols from N. In this section we shall study the notion of selfcontradictory deductions in the formal system N−∀∃=. We shall also prove the following theorem. Theorem 1 Every nonselfcontradictory deduction in N−∀∃= is normalizable. In this section and the two succeeding ones we shall use the terminology of Ekman (1994) [2, Sect. 3.1], see Appendix below. Hence, by “normalizable” in Theorem 1 we mean normalizable as defined in Ekman (1994) [2, Sect. 3.1], see Appendix below. As in the formal system FP, m and n denote meanings. Assume that A is a formula such that there is no normal proof of A in N−∀∃=. Then, by Proposition 3.1.4 in Ekman (1994) [2] there is no normalizable proof of A in N−∀∃=. Hence by Theorem 1 every proof of A is selfcontradictory. Since there is no normal proof of ⊥ in N−∀∃= it follows that every paradox in N−∀∃= is self contradictory, if by paradox we mean a proof of ⊥. In Ekman (1994) [2, Sect. 2.1] it is shown that there is no normal proof of the formula t ∈/ u, where t is the term defined by Hence, every proof of t t ≡ {x  x ∈ u & x ∈/ x } ∈/ u in N−∀∃= is selfcontradictory. In Ekman (1994) [2, Sect. 2.1] also a proof, named Crabbe's counterexample (see Crabbé (1974) [1]), of the formula t ∈/ u is presented. This proof is a proof in N−∀∃= and hence Crabbe's counterexample is a selfcontradictory proof. It is also argued in Ekman (1994) [2, Sect. 2.1] that Crabbe's counterexample expresses a correct argument in ZF. Hence the formula t ∈/ u, or the proposition that informally corresponds to t ∈/ u, serves as an example of a proposition provable in ZF, but only by selfcontradictory proofs, unless we use proof principles not expressible in N−∀∃=. The variables of the language of N−∀∃= will also be used to denote meaning variables. The set of formal meanings to be assigned to formulas in deductions in the formal system N−∀∃= is inductively defined as follows. The meaning variable x and false are meanings, and if m and n are meanings, then Em, m ⇒ n, m ∧ n and m + n are meanings. The meaning conditions associated with the formal system N−∀∃= are the following. D m : A [t /x ] Em : t ∈ {x  A} ∈I [m : A] D D false : ⊥ m : A ⊥E D E m : t ∈{x  A } m : A[t /x ] ∈E D E n : B m ⇒ n : A ⊃ B ⊃ m ⇒ n : A ⊃ B m : A n : B ⊃ D E D D m : A n : B &I m ∧ n : A & B m ∧ n : A & B &E1 m : A m ∧ n : A & B &E2 n : B D D D [m1 : A1] E1 [m2 : A2] E2 m : A m + n : A ∨ B ∨ n : B m + n : A ∨ B ∨ m 1 + m 2 : A 1 ∨ A 2 n : C n : C n : C ∨E Let D and E be two deductions in N−∀∃= such that D is nonselfcontradictory, θ is an assignment of formal meanings to the formula occurrences in D such that this assignment satisfies the meaning conditions and D =⇒ E (i.e., D reduces to E ; see Appendix for the definition of reductions of deductions). Then we let a(θ, E , D ) denote the assignment of formal meanings to the formula occurrences in E given by considering every formula occurrence in E to correspond to a formula occurrence in D and assigning the same meaning to the formula occurrence in E as the meaning assigned to the corresponding formula occurrence in D . If D reduces to E via an epsilon reduction, then the deduction D , with its formula occurrences decorated by θ has the form F m : A [t /x ] E m : t ∈{x  A } m : A[t /x ] G C ⎫ ⎪ ⎪⎪ ∈E⎬ D ⎪ ⎪ ⎭ In this case E , with its formula occurrences decorated by a(θ, E , D ), is the following deduction F ⎫ m : A[t /x ] ⎪⎬ E G ⎪ C If D reduces to E via an imply reduction, then D , with its formula occurrences decorated by θ , has the form [m : A] ⎫ ⎪ ⎪ n : B ⊃I G ⎬ m ⇒ n : A ⊃ B m : A D n : B ⊃ ⎪ H ⎪ C ⎭ In this case E , with its formula occurrences decorated by a(θ, E , D ), is the deduction G ⎫ m A ⎪ ⎪ F ⎬⎪ n : B E H ⎪ C ⎭ For all other cases of the kind of reduction that takes D to E , a(θ, E , D ) is defined similarly. Lemma 1 If a deduction D is nonselfcontradictory and D reduces to E , then also the deduction E is nonselfcontradictory. Proof Let θ be an assignment of formal meanings to the formula occurrences in D such that this assignment satisfies the meaning conditions. Then a(θ, E , D ) is an assignment of formal meanings to the formula occurrences in E such that this assignment satisfies the meaning conditions. D Let the formal system P of propositional logic be given as in the Appendix below. We assume that there is at least one propositional variable P in the language of P. Let ∗ be the function from the set of meanings to be assigned to formulas in deductions in the formal system N−∀∃= onto the set of formulas of P, defined as follows. x ∗ ≡ P false ≡ ⊥ (Em)∗ ≡ (⊥⊃ ⊥) ⊃ m∗ (m ⇒ n)∗ ≡ m∗ ⊃ n∗ (m ∧ n)∗ ≡ m∗ & n∗ (m + n)∗ ≡ m∗ ∨ n∗ We extend ∗ to a function from the set of sets of meanings to be assigned to formulas in deductions in the formal system N−∀∃= onto the set of sets of formulas of P by letting Γ ∗ denote the set of formulas A∗ such that A belongs to Γ , for all sets of meanings to be assigned to formulas in deductions in the formal system N−∀∃=. We extend ∗ once more, to a function from the set of nonselfcontradictory deductions in N−∀∃= to the set of deductions in P. If D is a deduction in N−∀∃= consisting of the open assumption m : A, then D ∗ is the open assumption m∗: ⎛ D ⎞∗ ⎝ m : A[t /x ] ⎠ ≡ Em : t ∈ {x  A} ∈ D ∗ m∗ (⊥⊃ ⊥) ⊃ m∗ ⊃I Observe that there is no open assumption of the form ⊥⊃⊥ in D ∗, cancelled at the ⊃I inference, in the deduction to the right above. ⎛ D ⎞∗ D ∗ [⊥] ⎝ E m : t ∈{x  A } m : A[t /x ] ∈E⎠ ≡ (⊥⊃ ⊥) ⊃ m∗ m∗ ⊥⊃⊥ ⊃I ⊃E For all other cases of the end inference of a deduction D , the definition of D ∗ commutes with the definition of deduction. For instance, for the case that an ⊃I is the last inference of a deduction, we have the following clause defining the image under ∗ of this deduction: ⎛ [m : A] ⎜ D ⎞∗ [m∗] ⎟ ≡ D ∗ ⎝ n : B I⎠ m ⇒ n : A ⊃ B n∗ m∗ ⊃ n∗ ⊃I Proposition 1 Assume that D is a nonselfcontradictory deduction, θ is an assignment of formal meanings to the formula occurrences in D such that this assignment satisfies the meaning conditions and D =⇒ E . Let D also denote the deduction obtained from D by decorating the formula occurrences in D with θ . Let E also denote the deduction obtained from E by decorating the formula occurrences in E with a(θ, E , D ). Then D ∗ =⇒ E ∗. Since P is strongly normalizable (see Prawitz (1965) [6]), we have Theorem 1 as a consequence of Proposition 1. 
< Prev  CONTENTS  Next > 

Related topics 