On a Theory of Truth and on the Regress Problem S. Heikkilä Department of Mathematical Sciences, University of Oulu BOX 3000, FIN-90014, Oulu, Finland E-mail: sheikki@cc.oulu.fi October 1, 2013 Abstract A theory of truth is introduced for the first–order language L of set theory. Fully interpreted metalanguages which contain their truth predicates are constructed for L. The presented theory is free from infinite regress, whence it provides a proper framework to study the regress problem. In proofs only ZF set theory, concepts definable in L and classical two-valued logic are used. Similar truth theory can be presented also for each consistent theory of every countable first–order formal language. MSC: 00A30, 03A05, 03B10, 03C62, 03E04, 03F50, 06A07, 47H04, 47H10 Keywords: Set theory, Zermelo-Fraenkel, model, first–order, theory, formal language, metalanguage, truth, provability, fixed point chain, transfinite sequence, regress problem. 1 1 Introduction In this paper we construct for the first–order formal language L = {∈} of set theory logically consistent metalanguages which contain their truth predicates. Valuations of metalanguages conform to that of L determined by the model M for Zermelo Fraenkel (ZF) set theory constructed in [2]. Classical two-valued logic is used in reasoning. The regress problem is studied within the framework of such a metalanguage. Examples of infinite regresses are presented. The paper is organized as follows. In Section 2 we construct metalanguages for L. They are included in the expansion L = {∈, T} of L, where T is a monadic predicate. Considerations are influenced by the derivation of Kripke's theory of truth for arithmetics presented in [5]. Denote by X the set of numerals of Gödel numbers of sentences of L in its fixed Gödel numbering. X is a subset of M because M contains finite ordinals. Let dAe denote the numeral of the Gödel number of a sentence A of L. Corresponding to each subset U of X we construct a metalanguage LU of L. U is called consistent if for no sentence A of L both dAe and d¬Ae are in U . In Section 3 we first valuate the sentences of constructed metalanguages. Standard truth tables of two-valued logic hold for logical connectives of sentences of LU if U is consistent. We call T a truth predicate for LU if T -biconditionality: A ↔ T (dAe) is true for all sentences A of LU . To every formula θ(x) of L there is such a sentence A in L that the sentence A ↔ ¬θ(dAe) is true in M (cf., e.g., [11, Lemma IV.5.30]). Thus the language L does not contain its own truth predicate with respect to the valuation determined by M . Denote by G(U) the set of numerals of Gödel numbers of true sentences of LU . We shall show that if U is consistent, and is a fixed point of G, i.e., U = G(U), then T is a truth predicate for LU . Moreover, the truth in M , as defined, e.g., in [11] and the truth in the metalanguage LU are shown to be connected as follows: For each sentence A of L, either (a) A is true in M , equivalently, A is true in LU , equivalently, T (dAe) is true in LU , or (b) ¬A is true in M , equivalently, ¬A is true in LU , equivalently, ¬T (dAe) is true in LU . In Section 4 we prove that G has consistent fixed points including the smallest one. Denoting it by U , the sentences of LU are called grounded. In proofs only ZF set theory, concepts definable in L, sets of M and classical logic are used. Section 5 is devoted to the study of the regress problem within the language of grounded sentences. In the study we question the following conclusion stated in [16]: "it is logically impossible for there to be an infinite parade of justifications". Notwithstanding this conclusion we present examples of infinite parades (regresses) of justifications that satisfy the conditions imposed on them in [15]. Examples are inconsistent with the above quoted conclusion that is used in [15, 16] as a basic argument to refute Principles of Sufficient Reasons. An example of a transfinite regress is also presented. Tarski's theory of truth is not a suitable framework because of infinite regress of metalanguages. Three-valued inner logic in Kripke's theory of truth makes the use of it problematic. Relations of the constructed theory to these two truth theories and to the norms presented for such theories in [12] are studied in Section 6. 2 2 Construction of metalanguages First we shall construct a family of metalanguages for the language L = {∈} of set theory. As for the used terminology, cf. e.g., [6, 11]. Let Th(M) be comprised by all those sentences of L which are true in the model M of ZF set theory constructed in [2] in the sense that M |=A (cf. [11, Subsection II.2.7 and p. 237]). Th(M) is by [11, Lemma II.2.8.22] complete with respect to L, i.e., for each sentence A of L either A or its negation ¬A is true in M . Given a subset U of the set X of numerals of Gödel numbers of sentences of L = {∈, T}, define subsets G(U) and F (U) of X by following rules (iff abbreviates if and only if): (r1) If A is a sentence of L, then dAe is in G(U) iff M |=A. (r2) If A is a sentence of L, then dT (dAe)e is in G(U) iff dAe is in U . (r3) If A is a sentence of L, then dT (dAe)e is in F (U) iff d¬Ae is in U . Sentences determined by rules (r1)–(r3), i.e., sentences A of L for which M |=A and sentences T (dAe) of L for which dAe or d¬Ae is in U , are called atomic sentences. Next rules deal with sentences containing logical constants. Let A and B be sentences of L. (r4) Negation rule: d¬Ae is in G(U) iff dAe is in F (U), and in F (U) iff dAe is in G(U). (r5) Disjunction rule: dA ∨Be is in G(U) iff dAe or dBe is in G(U), and in F (U) iff dAe and dBe are in F (U). (r6) Conjunction rule: dA ∧Be is in G(U) iff d(¬A) ∨ (¬B)e is in F (U) iff (by (r4) and (r5)) both dAe and dBe are in G(U). Similarly, dA ∧Be is in F (U) iff d(¬A) ∨ (¬B)e is in G(U) iff dAe or dBe is in F (U). (r7) Implication rule: dA→ Be is in G(U) iff d¬A ∨Be is in G(U) iff (by (r4) and (r5)) dAe is in F (U) or dBe is in G(U). dA→ Be is in F (U) iff d¬A ∨Be is in F (U) iff dAe is in G(U) and dBe is in F (U). (r8) Biconditionality rule: dA↔ Be is in G(U) iff dAe and dBe are both in G(U) or both in F (U), and in F (U) iff dAe is in G(U) and dBe is in F (U) or dAe is in F (U) and dBe is in G(U). When A(x) is a formula in L, then quantifications ∃xA(x) and ∀xA(x) are sentences of L. Rules (r1)–(r8) are applicable to them and their logical connectives with sentences of L. Remaining formulas A(x) in L form its subset, denoted by F . Assume that X is their domain of discursion, and that (r9) d∃xA(x)e is in G(U) iff dA(n)e is in G(U) for some n ∈ X, and in F (U) iff dA(n)e is in F (U) for every n ∈ X. (r10) d∀xA(x)e) is in G(U) iff dA(n)e is in G(U) for every n ∈ X, and in F (U) iff dA(n)e is in F (U) at least for one n ∈ X. 3 Rules (r1)–(r10) and induction on the complexity of formulas determine uniquely subsets G(U) and F (U) of X whenever U is a subset of X. Languages LU formed by those sentences A of L for which dAe is in G(U) or in F (U) are metalanguages for L. We say that a subset U of X is consistent iff both dAe and d¬Ae are not in U for any sentence A of L. For instance, the empty set ∅ is consistent. The following two lemmas have counterparts in [5], and proofs are similar. Lemma 2.1. Let U be a consistent subset of X. Then G(U) ∩ F (U) = ∅. Proof. Consider first atomic sentences. Rule (r1) puts no member to F (U). By rules (r2) and (r3) dT (dAe)e is in G(U) iff dAe is in U , and in F (U) iff d¬Ae is in U . Thus dT (dAe)e cannot be both in G(U) and in F (U) because U is consistent. Make an induction hypothesis: (h0) A and B are such sentences of L that neither dAe nor dBe is in G(U) ∩ F (U). As shown above, (h0) holds if A and B are atomic sentences. If d¬Ae is in G(U) ∩ F (U), then dAe is in F (U) ∩G(U). Hence, if (h0) holds, then d¬Ae is not in G(U) ∩ F (U). If dA ∨Be is in G(U) ∩ F (U), then dAe or dBe is in G(U), and both dAe and dBe are in F (U) by (r5), so that dAe or dBe is in G(U) ∩ F (U). Hence, if (h0) holds, then dA ∨Be is not in G(U) ∩ F (U). dA ∧Be cannot be in G(U) ∩ F (U), for otherwise both dAe and dBe are in G(U), and at least one of dAe and dBe is in F (U), contradicting with (h0). If d¬Ae is in G(U) ∩ F (U), then dAe is in F (U) ∩G(U), and (h0) is not valid. Thus, under the hypothesis (h0) neither d¬Ae nor dBe is in G(U) ∩ F (U). This result and the above result for disjunction imply that d¬A ∨Be, or equivalently, dA→ Be, is not in G(U)∩F (U). Similarly, dA↔ Be is not in G(U) ∩ F (U), for otherwise, both dAe and dBe would be in G(U) ∩ F (U) by rule (r8), contradicting with (h0). It remains to show that if A(x) is a formula in F , then d∃xA(x)e and d∀xA(x)e are not in G(U) ∩ F (U). If A(n) is an atomic sentence for every n ∈ X, the above proof implies that the following induction hypothesis holds: (h1) dA(n)e is not in G(U) ∩ F (U) for any n ∈ X. Then neither d∃xA(x)e nor d∀xA(x)e is in G(U)∩F (U), for otherwise, it would follow from (r9) and (r10) that dA(n)e is in G(U) ∩ F (U) for some n ∈ X, contradicting with (h1). The above results and induction on the complexity of formulas imply that dAe is not in G(U) ∩ F (U) for any sentence A of L. Lemma 2.2. If a subset U of X is consistent, then G(U) is consistent. Proof. If G(U) is not consistent, then there is such a sentence A of L, that dAe and d¬Ae are in G(U). Because d¬Ae is in G(U), then dAe is also in F (U) by rule (r4), and hence in G(U)∩F (U). But then, by Lemma 2.1, U is not consistent. Consequently, if U is consistent, then G(U) is consistent. 4 3 A theory of truth We shall first define valuations and a concept of truth predicate for metalanguages LU formed by those sentences A of L for which dAe is in one of the subsets G(U) and F (U) of X constructed in Section 2. Definition 3.1. Let U be a consistent subset of X. We say that a sentence A of LU is true iff dAe is in G(U), and false iff dAe is in F (U). T is called a truth predicate for the language LU iff T -biconditionality: A↔ T (dAe) is true for every sentence A of LU . In view of the given valuation 'dAe is in G(U)' can be replaced by 'A is true' and 'dAe is in F (U)' by 'A is false' in (r4)–(r10). Standard truth tables of classical two-valued logic hold for logical connectives of sentences of LU when 'true' is replaced by '1' and 'false' by '0'. In the study whether T is a truth predicate for LU , the consistent subsets U of X which are fixed points of the set mapping G := U 7→ G(U), i.e., U = G(U), play the crucial role. Lemma 3.1. If U ⊂ X is a consistent fixed point of G, then T is a truth predicate for LU . Proof. Assume that U ⊂ X is consistent, and let A be a sentence of LU . Applying rules (r2), (r3) and (r4), it follows that if U = G(U), then (i) dAe is in G(U) iff dAe is in U iff dT (dAe)e is in G(U); (ii) dAe is in F (U) iff d¬Ae is in G(U) iff d¬Ae is in U iff dT (dAe)e is in F (U). (i) and (ii) imply that dAe and dT (dAe)e are either both in G(U) or both in F (U). Thus dA↔ T (dAe)e is by rule (r8) in G(U), so that A ↔ T (dAe) is true by Definition 3.1. This holds for every sentence A of LU , whence T is a truth predicate for LU by Definition 3.1. Our main result on the connection between valuations in L determined by M and those determined by Definition 3.1 reads as follows: Theorem 3.1. Let U be a consistent fixed point of G. If A is a sentence of L, then either (a) M |=A (A is true in M), equivalently, A is true, equivalently, T (dAe) is true, or (b) M |=¬A (A is false in M), equivalently, A is false, equivalently, T (dAe) is false. Proof. Assume that A is a sentence of L. Because theory Th(M) is complete with respect to L by [11, Lemma II.8.22], then either M |=A or M |=¬A. (a) M |=A iff dAe is in G(U), by rule (r1), iff A is true, by Definition 3.1, iff T (dAe) is true, by Lemma 3.1. (b) M |=¬A iff d¬Ae is in G(U), by rule (r1), iff dAe is in F (U), by rule (r4), iff A is false, by Definition 3.1, iff T (dAe) is false, by Lemma 3.1. It remains to show that G has consistent fixed points. Denote by P the family of consistent subsets of X. In the formulation and the proof of our main fixed point theorem we use transfinite sequences of P indexed by von Neumann ordinals. Such a sequence (Uλ)λ∈α of P is said to be strictly increasing if Uμ ⊂ Uν whenever μ ∈ ν ∈ α, and strictly decreasing if Uν ⊂ Uμ whenever μ ∈ ν ∈ α. A set V of P is called sound iff V ⊆ G(V ). The following fixed point theorem is proved in Section 4. 5 Theorem 3.2. If V is a sound subset of P, then there exists the smallest of those consistent fixed points of G which contain V . This fixed point is obtained as the last member of the union of those transfinite sequences (Uλ)λ∈α of P which satisfy (C) (Uλ)λ∈α is strictly increasing, U0 = V , and if 0 ∈ μ ∈ α, then Uμ = ⋃ λ∈μ G(Uλ). The following Theorem shows that every consistent subset C of X has the greatest sound and consistent subset. The proof is presented in Section 4. Theorem 3.3. The equation V = C ∩ G(V ) has for each consistent subset C of X the greatest solution V in P. It is the greatest sound subset of P that is contained in C. V is the last member of the union of those transfinite sequences (Vλ)λ∈α of P which satisfy (D) (Vλ)λ∈α is strictly decreasing, V0 = C, and if 0 ∈ μ ∈ α, then Vμ = C ∩ ( ⋂ λ∈μ G(Vλ)). The next result is a special case of Theorem 3.2. Theorem 3.4. G has the smallest consistent fixed point. Proof. The empty set ∅ is both sound and consistent. Thus, by Theorem 3.2, there is the smallest consistent fixed point of G that contains ∅. It is the smallest consistent fixed point of G, since every fixed point of G contains ∅. Sentences of the language LU , where U is the smallest consistent fixed point of G, are in every other fixed point language. These sentences are called grounded, as in [5, 10]. A result for formalists: Replace M |=A in rule (r1) by ZF |−A (A is provable in ZF set theory). Interpreting in the so obtained language of grounded sentences a sentence A as true if dAe is in G(U), then T recognizes a sentence of L as true if it is provable in ZF. Remarks 3.1. The smallest members of (Uλ)λ∈α satisfying (C) are n-fold iterations Un = Gn(V ), n ∈ N = {0, 1, . . . }. If they form a strictly increasing sequence, the next member Uω is their union, Uω+n = G n(Uω), n ∈ N, and so on. Let V be a set of numerals of Gödel numbers of those sentences of L which are true in M . Then V ⊂ G(∅) ⊂ G(V ), whence V is sound. Moreover, V is also consistent. If U is a fixed point of G, then V ⊂ G(∅) ⊂ G(U) = U . In particular, the smallest consistent fixed point of G contains V . If the set C is finite, then the longest sequence (Vλ)λ∈α satisfying (D) is finite. Its members are determined by the finite algorithm: (A) V0 = C. For n from 0 while Vn 6= C ∩G(Vn) do: Vn+1 = C ∩G(Vn). The above results hold also when M is replaced by any other countable model of ZF set theory, including "the basic Cohen model" and "the second Cohen model" described, e.g., in [8, p. 10]. Similar truth theory can be presented also for each consistent theory of every countable first–order formal language, M being a countable model of the theory in question. Such a model exist by Downward Löwenheim-Skolem Theorem. For instance, the language of set theory can be replaced by the language of arithmetic, and M by a standard model of arithmetic. Models for other set theories, for arithmetic and for other important theories of contemporary mathematics are presented in [11]. As for axiomatic theories of truth, see, e.g., [4] and the references therein. 6 4 The proofs of Theorems 3.2 and 3.3 Let P denote the family of all consistent subsets of the set X. Before the proofs of Theorems 3.2 and 3.3 we prove some auxiliary results. Lemma 4.1. Let U and V be sets of P, and assume that U ⊆ V . If A is a sentence of L, then dAe is in G(V ) whenever it is in G(U), and dAe is in F (V ) whenever it is in F (U). Proof. Assume that U ⊆ V . Consider first atomic sentences. Let A be a sentence of L. By rule (r1) dAe is in G(U) and also in G(V ) iff M |=A. Rule (r1) leaves both F (U) and F (V ) empty. Let A be a sentence of L. If dT (dAe)e is in G(U), then dAe is in U by rule (r2). Because U ⊆ V , then dAe belongs to V , whence dT (dAe)e is in G(V ) by rule (r2). If dT (dAe)e is in F (U), then d¬Ae is in U by rule (r3). Since U ⊆ V , then d¬Ae belongs to V , so that dT (dAe)e is in F (V ) by rule (r3). Thus all atomic sentences satisfy the lemma. Assume that A is a sentence of L. If d¬Ae is in G(U) but not in G(V ), then dAe is in F (U) but not in F (V ) by rule (r4). If d¬Ae is in F (U) but not in F (V ), then dAe is in G(U) but not in G(V ) by rule (r4). Hence, if A satisfies the lemma, then also ¬A satisfies it. Make an induction hypothesis: (h2) A and B are such sentences of L that dAe is in G(V ) if it is in G(U), dAe is in F (V ) if it is in F (U), dBe is in G(V ) if it is in G(U), and dBe is in F (V ) if it is in F (U). If dA ∨Be is in G(U), then dAe or dBe is in G(U) by rule (r5). By (h2) dAe or dBe is in G(V ), so that dA ∨Be is in G(V ). If dA ∨Be is in F (U), then dAe and dBe are in F (U) by rule (r5), and hence also in F (V ), by (h2), so that dA ∨Be is in F (V ). Thus A∨B satisfies the lemma if (h2) holds. If dA ∧Be is in G(U), then both dAe and dBe are in G(U) by rule (r6), and hence also in G(V ), by (h2). Thus dA ∧Be is in G(V ). If dA ∧Be is in F (U), then dAe or dBe is in F (U) by rule (r6), and hence also in F (V ), by (h2), whence dA ∧Be is in F (V ). Thus A ∧ B satisfies the lemma if (h2) holds. If dA→ Be is in G(U), then d¬Ae or dBe is in G(U), i.e., dAe is in F (U) or dBe is in G(U). Then, by (h2), dAe is in F (V ) or dBe is in G(V ), i.e., d¬Ae or dBe is in G(V ). Thus dA→ Be is in G(V ). If dA→ Be is in F (U), then dAe is in G(U) and dBe is in F (U). This implies by (h2) that dAe is in G(V ) and dBe is in F (V ), so that dA→ Be is in F (V ). Thus A → B satisfies the lemma if (h2) holds. Similarly, it can be shown that B → A satisfies the lemma, so that also A↔ B satisfies the lemma if (h2) holds. When A(x) is a formula in F , make an induction hypothesis: (h3) For every n ∈ X, dA(n)e is in G(V ) whenever it is in G(U), and in F (V ) whenever it is in F (U). If d∃xA(x)e is in G(U), then (r9) implies that at least one dA(n)e belongs to G(U). This dA(n)e is by (h3) also in G(V ), whence d∃xA(x)e is in G(V ), by (r9). If d∃xA(x)e is in F (U), it follows from (r9) that dA(n)e is in F (U), and hence, by (h3), also in F (V ), for every n ∈ X, whence d∃xA(x)e is in F (V ), by (r9). 7 If d∀xA(x)e is in G(U), then every dA(n)e is in G(U), by (r10). Thus, by (h3), every dA(n)e is in G(V ), so that d∀xA(x)e is in G(V ), by (r10). If d∀xA(x)e is in F (U), then, by (r10), some dA(n)e is in F (U), and hence also in F (V ), by (h3). This implies by (r10) that d∀xA(x)e is in F (V ). Consequently, if (h3) holds, then both d∃xA(x)e and d∀xA(x)e are in G(V ) whenever they are in G(U), and in F (V ) whenever they are in F (U). Because (h2) and (h3) hold for atomic sentences, the above results and induction on the complexity of expressions imply the conclusion of the lemma. According to Lemma 2.2 the mapping G := U 7→ G(U) maps P into P . Assuming that P is ordered by inclusion, the above lemma implies the following result. Lemma 4.2. G is order preserving in P, i.e., G(U) ⊆ G(V ) whenever U and V are sets of P and U ⊆ V . Lemma 4.3. (a) If W is a chain in P, then the union ∪W = ∪{U | U ∈ W} is consistent. (b) The intersection ∩W = ∩{U | U ∈ W} of every nonempty subfamily W of P is a consistent subset of X. Proof. (a) Assume on the contrary that ∪W is not consistent. Then there is a such a sentence A of L that both dAe and d¬Ae are in ∪W . Thus W has a member, say U , which contains dAe, and a member, say V , which contains d¬Ae. If W is a chain, then U ⊆ V or V ⊆ U . In former case V and in latter case U contains both dAe and d¬Ae. But this is impossible because W is a subfamily of P . This proves (a). (b) ∩W is a subset of X, and is contained in every member of W . Hence ∩W is consistent, for otherwise there is such a sentence A in L that both dAe and d¬Ae are in ∩W . Then every member of W would also contain both dAe and d¬Ae. But this is impossible because every member of W is consistent. This proves (b). As an application of Lemmas 2.2, 4.2 and 4.3 we shall prove our main fixed point theorem. Proof of Theorem 3.2. Let V ∈ P be sound, i.e., V ⊆ G(V ). Transfinite sequences of P having properties (C) of Theorem 3.2 are called G-sequences. We shall first show that G-sequences are nested: (1) Assume that (Uλ)λ∈α and (Vλ)λ∈β are G-sequences, and that {Uλ}λ∈α 6⊆ {Vλ}λ∈β. Then (Vλ)λ∈β = (Uλ)λ∈β. By the assumption of (1) μ = min{λ ∈ α | Uλ 6∈ {Vλ}λ∈β} exists, and {Uλ}λ∈μ ⊆ {Vλ}λ∈β. Properties (C) imply by transfinite induction that Uλ = Vλ for each λ ∈ μ. To prove that μ = β, make a counter-hypothesis: μ ∈ β. Since μ ∈ α and Uλ = Vλ for each λ ∈ μ, it follows from properties (C) that Uμ = ⋃ λ∈μ G(Uλ) = ⋃ λ∈μ G(Vλ) = Vμ, which is impossible, since Vμ ∈ {Vλ}λ∈β, but Uμ 6∈ {Vλ}λ∈β. Consequently, μ = β and Uλ = Vλ for each λ ∈ β, whence (Vλ)λ∈β = (Uλ)λ∈β. By definition, every G-sequence (Uλ)λ∈α is a function λ 7→ Uλ from α into P . Property (1) implies that these functions are compatible. Thus their union is by [7, Theorem 2.3.12] 8 a function with values in P , the domain being the union of all index sets of G-sequences. Because these index sets are ordinals, then their union is also an ordinal. Denote it by γ. The union function can be represented as a sequence (Uλ)λ∈γ of P . It is strictly increasing as an union of strictly increasing nested sequences. To show that γ is a successor, assume on the contrary that γ is a limit ordinal. Given ν ∈ γ, then μ = ν ∪ {ν} and α = μ ∪ {μ} are in γ, and (Uλ)λ∈α is a G-sequence. Denote Uγ = ⋃ λ∈γ G(Uλ). G is order preserving by Lemma 4.2, and (Uλ)λ∈γ is a strictly increasing sequence of P . Thus {G(Uλ)}λ∈γ is a chain in P , whence Uγ is consistent by Lemma 4.3(a). Moreover, Uν ⊂ Uμ = ⋃ λ∈μ G(Uλ) ⊆ Uγ. This holds for each ν ∈ γ, whence (Uλ)λ∈γ∪{γ} is a G-sequence. This is impossible, since (Uλ)λ∈γ is the union of all G-sequences. Consequently, γ is a successor, say γ = α∪{α}. Thus Uα is the last member of (Uλ)λ∈γ, Uα = max{Uλ}λ∈γ, and G(Uα) = max{G(Uλ)}λ∈γ. Moreover, (Uλ)λ∈γ is a G-sequence, for otherwise (Uλ)λ∈α would be the union of all G-sequences. In particular, Uα = ⋃ λ∈α G(Uλ) ⊆ ⋃ λ∈γ G(Uλ) = G(Uα), so that Uα ⊆ G(Uα). Equality holds, since otherwise the longest G-sequence (Uλ)λ∈γ could be extended by Uγ = ⋃ λ∈γ G(Uλ). Thus Uα is a fixed point of G in P . Assume that W ∈ P is a fixed point of G, and that V ⊆ W . Then U0 = V ⊆ W . If 0 ∈ μ ∈ γ, and Uλ ⊆ W for each λ ∈ μ, then G(Uλ) ⊆ G(W ) for each λ ∈ μ, whence Uμ = ⋃ λ∈μ G(Uλ) ⊆ G(W ) = W . Thus, by transfinite induction, Uμ ⊆ W for each μ ∈ γ. In particular, Uα = max{Uλ}λ∈γ ⊆ W . This proves that Uα is the smallest consistent fixed point of G that contains V . Proof of Theorem 3.3. Assume that C is a consistent subset of X. Like the proof that the union of all G-sequences is a G-sequence one can prove that the union of all transfinite sequences which have properties (D) given in Theorem 3.3 has property (D). Let (Vλ)λ∈γ be that sequence, i.e., (Dγ) (Vλ)λ∈γ is strictly decreasing, V0 = C, and if 0 ∈ μ ∈ γ, then Vμ = C ∩ ( ⋂ λ∈μ G(Vλ)). Denote V = C ∩ ( ⋂ λ∈γ G(Vλ)). Because C and the sets Vλ, λ ∈ γ, are consistent, it follows from Lemma 2.2 and Lemma 4.3(b) that V is consistent. Moreover, V ⊆ Vλ for each λ ∈ γ. If V ⊂ Vλ for each λ ∈ γ, then the choice Vλ = V implies that (Vλ)λ∈γ∪{γ} satisfies (D) when α = γ ∪{γ}. But this is impossible because of the choice of (Vλ)λ∈γ. Thus V = min{Vλ}λ∈γ, and V is the last member of (Vλ)λ∈γ because this sequence is strictly decreasing. Since G is order preserving, then G(V ) = min{G(Vλ)}λ∈γ = ⋂ λ∈γ G(Vλ). Thus V = C ∩ G(V ), so that V ⊆ G(V ), i.e., V is sound and is contained in C. Assume that W is consistent, that W ⊆ G(W ), and that W ⊆ C. Since V0 = C by (Dγ), then W ⊆ V0. If 0 ∈ μ ∈ γ and W ⊆ Vλ for each λ ∈ μ, then G(W ) ⊆ G(Vλ) for each λ ∈ μ, whence W ⊆ C ∩ G(W ) ⊆ C ∩ ( ⋂ λ∈μ G(Vλ)) = Vμ. Thus, by transfinite induction, W ⊆ Vλ for each λ ∈ γ, so that W ⊆ min{Vλ}λ∈γ = V . Consequently, V is the greatest sound and consistent subset of X that is contained in C. 9 5 On the Regress Problem First of ten theses presented in [1, p. 6] is: "The Regress Problem is a real problem for epistemology." We shall first adjust our terminology to that used in [15] in the study of the Regress Problem. By statements we mean grounded sentences, i.e., the sentences of LU , where U is the smallest fixed point of G. A statement A is said to entail B, if it is not possible that A is true and B is false simultaneously. For instance, if A → B is true, then A entails B. We say that a statement A justifies a statement B if A confirms the truth of B. For instance, if A↔ ¬B is true, then A justifies B iff A is false. If A→ B is true, then A justifies B iff A is true (Modus Ponens). A statement A is called contingent if the truth value of A is unknown. Consider an infinite regress . . . Fi, . . . , F1, F0 (5.1) of statements Fi, i ≥ 0, where the statement F0 is contingent. We shall impose the following conditions on statements Fi, i > 0 (cf. [15]): (i) Fi entails Fi−1; (ii) F0 ∨ * * * ∨ Fi−1 does not entail Fi; (iii) F0 ∨ * * * ∨ Fi−1 does not justify Fi. Regress (5.1) is called justification-saturated if the following condition holds: (iv) . . . what justifies Fi−1 is Fi, . . . , what justifies F1 is F2, what justifies F0 is F1. Lemma 5.1. Assume that in regress (5.1) the statement F0 is contingent, and that the statements Fi, i > 0, satisfy conditions (i)–(iii). (a) If F1 is false, then Fi is false for each i > 0. F0 is justified iff F0 ↔ ¬F1 is true. (b) If Fn is true for some n > 0, then Fi is true when 0 ≤ i ≤ n. (c) The regress (5.1) is justification saturated iff Fi is true for all i > 0, in which case F0 is justified. Proof. (a) Assume that F1 is false. If Fi would be true for some i > 1, there would be the smallest such an i. Then Fi−1 would be true by (i). Replacing i by i − 1, and so on, this reasoning would imply after i− 1 steps that F1 is true; a contradiction. Thus all statements Fi, i > 0, are false. Because F1 is false, it confirms the truth of F0 iff F0 and ¬F1 have same truth values iff F0 ↔ ¬F1 is true. (b) Assume that Fn is true for some n > 0. Since Fi entails Fi−1, i = n, n− 1, . . . , 1, then Fi is true for every i = n− 1, . . . , 0. (c) If Fn is false for some n > 0, then Fn+1 is false by property (i), and it does not justify Fn, so that condition (iv) is not valid. On the other hand, condition (i) ensures that condition (iv) is valid if Fi is true for all i > 0. In this case F1 justifies F0, i.e., F0 is true. 10 The following examples show that there exist infinite regresses of statements Fi, i = 0, 1, . . . , that satisfy assumptions of Lemma 5.1. Exactly one instance in both examples yields an infinite justification-saturated regress. Example 5.1. Let Q+ denote the set nonnegative rational numbers, let Y denote a nonempty subset of Q+, and let Fi, i = 0, 1, 2, . . . , be the following statements: Fi : Every number of Y is less than 1 2i , i = 0, 1, 2, . . . . (5.2) Show that the following conclusions are valid. (a) F0 is contingent. (b) Conditions (i)–(iii) are valid for the infinite regress (5.1). (c) If 1 ≤ p ∈ Y , then statement Fi is false for every i > 0. (d) If 0 < p < 1 for some p ∈ Y , there is an n ≥ 0 such that Fn is true and Fn+1 is false. (e) Regress (5.1),(5.2) is justification-saturated if and only if Y = {0}. Solution. (a) Statement F0 is neither logically necessary (Y can contain numbers ≥ 1) nor logically impossible (all numbers of Y can be < 1). Thus F0 is contingent, i.e., (a) is valid. (b) If p < 1 2i , then p < 1 2j when i > j ≥ 0, but not conversely. Thus, for every i > 0, Fi entails Fi−1, i.e., (i) holds, and Fi is not entailed by F0 ∨ * * * ∨ Fi−1, so that (ii) holds. If 1 ≤ i and p = 1 2i ∈ Y , then the statement Fj is true when 0 ≤ j < i, but the statement Fi is false. Thus Fi is not justified by F0 ∨ * * * ∨ Fi−1, whence (iii) is valid. The above results imply that conditions (i)–(iii) are valid, which proves (b). (c) If 1 ≤ p ∈ Y , then p 6< 1 2i for every i > 0, which proves (c). (d) If 0 < p < 1 for some p ∈ Y , there exists an n ≥ 0 such that 1 2n+1 ≤ p < 1 2n . Then Fn is true and Fn+1 is false. This proves (d). (e) It follows from (c) and (d) that condition: Y = {0} is necessary for Fi to be true for all i > 0. If Y = {0}, then Fi is true for all i > 0. Thus (e) holds by Lemma 5.1. Example 5.2. Let β be an element of the 'universe' S(ω) formed by all natural numbers 0, 1, . . . (finite ordinals), plus the smallest infinite ordinal ω. Equip S(ω) with the natural ordering < of natural numbers plus n < ω for every natural number n. If Z denotes a nonempty subset of S(ω), it is easy to verify that the infinite regress (5.1) of statements Fi : i < β, for every β ∈ Z, i = 0, 1, . . . , (5.3) satisfy conditions (i)–(iii), and that F0 is contingent. Moreover, condition (iv) is valid by Lemma 5.1 if and only if Fi is true for all i > 0. This holds if and only if Z = {ω}. Comments. Examples 5.1 and 5.2 are inconsistent with the conclusion of [16] cited in the Introduction. In these examples the property that regress (5.1) is justification-saturated both implies and is implied by truth of a 'foundational' statements Fb : Y = {0} and Z = {ω}, respectively. Thus they don't support the form of infinitism presented in [9]: "infinitism holds that there are no ultimate, foundational reasons". On the other hand, they support "impure" infinitism and the form of foundationalism presented in [1, 18]. Examples 5.1 and 5.2 imply that the proofs in [15, 16] to the assertion that "any version of Principle of Sufficient Reason is false" are based on the questionable premise that infinite 11 regresses of justifications don't exist. In fact, these examples give some support to Principles of Sufficient Reason, as well as to many other arguments whose validity is questioned in [15, 16]. For instance, in the 'universe' S(ω) of Example 5.2, • {ω} provides a sufficient reason for F0; • {ω} affords an ultimate and foundational reason that justifies F0; • {ω} is the final explainer of F0; • {ω} gives the first cause that makes regress (5.1),(5.3) justification-saturated; • ω explains the existence of the 'universe' N of natural numbers (N = ω by [7]); • ω and {ω} explain the existence of the 'universe' S(ω) (S(ω) = ω ∪ {ω} by [7]); • ω is something beyond natural numbers; • ω is infinite and greatest in the 'universe' S(ω); • ω is 'self-justified' (The Axiom of Infinity). Belief that ω exists is a matter of faith. The basis in the construction of the model M used here is the set ω ∪ {ω}, i.e., the set formed by natural numbers and their set (cf. [2, 8]). Notice that this set does not belong to the standard model of arithmetic. Thus a theory of truth for the language of arithmetic is not sufficient framework to Example 5.2 and the next example. Example 5.3. Let {Yi}i∈S(ω) be a family of nonempty subsets of M such that Yi ⊂ Yi+1 for every i ∈ ω. Let Z denote a nonempty subfamily of {Yi}i∈S(ω). Consider an infinite regress (5.1) of statements Fi, i ∈ ω, given by Fi : Yi ⊂ Y for every Y ∈ Z. (5.4) It is easy to verify that F0 is contingent, and that the conditions (i)–(iii) are valid Moreover, the following condition: (iv) is valid iff Z = {YS(ω)}, in which case F0 is true. 6 Final Remarks A purpose of the truth theory presented in this paper is to establish a proper framework to study the regress problem. Tarski's theory of truth (cf. [17]) does not offer it because that theory itself is not free from infinite regress. According to [14, p.189]: "the most important problem with a Tarskian truth predicate is its demand for a hierarchy of languages. ... within that hierarchy of languages, we cannot seem to have any valid method of ending the regression to introduce the "basic" metalanguage." Pure infinite regress is even refused in ([3, p.13]): "Thus, since there can be no infinite regress, from the point of view of logic mathematics must rest ultimately on some sort of axiomatic foundations." 12 Kripke's theory of truth is also a problematic framework because of three-valued inner logic. As stated in [12, p.283]: "Classical first-order logic is certainly the default choice for any selection among logical systems. It is presupposed by standard mathematics, by (at least) huge parts of science, and by much of philosophical reasoning." Moreover, T -biconditionality rule does not hold in Kripke's theory of truth because of paradoxical sentences. Paradoxes led Zermelo to axiomatize set theory. To avoid paradoxes Tarski "excluded all Liar-like sentences from being well-formed", as noticed in [12]. Construction of fixed point languages LU serves the same purpose. They are logically consistent and semantically closed, i.e., they contain their truth predicates and codes of all their sequences, violating 'Tarski's Commandment' (cf. [13], p. 531). The presented theory of truth has the following properties corresponding to the eight norms (a)–(h) formulated in [12] for truth theories: (a) Truth is expressed by a predicate T . Syntax is comprised by logical symbols of firstorder predicate logic, nonlogical symbols ∈ and T , and variables ranging in M . (b) A theory of truth is added to the theory Th(M), and it proves the latter true, by Theorem 3.1. (c) Truth predicate is not subject to any restrictions within fixed point languages LU . (d) T -biconditionals are derivable unrestrictedly within fixed point languages LU , by the proof of Lemma 3.1. (e) Truth is compositional, by Definition 3.1 and rules (r4)–(r10). (f) The theory allows for standard interpretations. M is a standard model of set theory. (g) The outer logic and the inner logic coincide. Both are classical. In particular: (h) The outer logic is classical. According to [12], "In the best of all (epistemically) possible worlds, some theory of truth would satisfy all of these norms (i.e., norms (a)–(h) formulated in [12]) at the same time. Unfortunately, we do not inhabit such a world." As for mathematical theories of truth the above properties (a)–(h) of the theory presented in this paper indicate that we don't live far away from such a world. Only the following mathematically acceptable additional norm is needed: (i) Metalanguages for which theories of truth are formulated should be free from contradictions. Acknowledgments: The author is greatly indebted to Ph.D. Tapani Hyttinen for valuable discussions on the subject. 13 References [1] Aikin, Scott F. (2011) Epistemology and the Regress Problem, Routledge. [2] Cohen, Paul (1963) A minimal model for set theory, Bulletin of the American Mathematical Society, 69, 537–540. [3] Feferman, Solomon (2009) For Philosophy of Mathematics: 5 Questions, philpapers.org/rec/FEFPOM. [4] Halbach, Volker (2011) Axiomatic Theories of Truth, Cambridge University Press. [5] Heck, Richard G. , Kripke's theory of truth, http:/www.frege.brown.edu /heck/philosophy/pdf/notes /KripkesTheoryOfTruth.pdf. [6] Heck, Richard G. Formal background for theories of truth, http:/www. frege.brown.edu/heck /philosophy /pdf /notes/FormalBackground.pdf. [7] Hrbacek, Karel & Jech, Thomas (1999) Introduction to Set Theory, Marcel Dekker, Inc, New York Basel. [8] Kanamori, Akihiro (2008) Cohen and Set Theory, The Bulletin of Symbolic Logic, 14,3, 351–377. [9] Klein, Peter D. (1999) Human Knowledge and the Infinite Regress of Reasons, Philosophical Perspectives, 13 297–325. [10] Kripke, Saul (1975) Outline of a Theory of Truth, Journal of Philosophy, 72, 690–716. [11] Kunen, Kenneth (2009) The Foundations of Mathematics, Mathematical Logic and Foundations, 19. [12] Leitgeb, Hannes (2007) What Theories of Truth Should be Like (but Cannot be), Philosophy Compass, 2/2, 276–290. [13] McGee, Vann (1989) Applying Kripke's Theory of Truth, The Journal of Philosophy, 86,10, 530–539. [14] Pantsar, Markus (2009) Truth, Proof and Gödelian arguments, Philosophical Studies from the University of Helsinki 23, 310 pp. [15] Post, John F. (1987) The Faces of Existence: An Essay in Nonreductive Metaphysics, Cornell University Press. [16] Post, John F. (2011) How to Refute Principles of Sufficient Reason, Preprint, Cogprints.org/390/. [17] Tarski, Alfred (1983) The concept of Truth in Formalized Languages, In A. Tarski, Logic, Semantics, Metamathematics (trans. J. H. Woodger) Hackett Publishing Company Indianapolis. [18] Turri, John (2009) On the regress argument for infinitism, Synthese 166,1.