© LOGOS & EPISTEME, VI, 3 (2015): 313-332 CATEGORICITY, OPEN-ENDED SCHEMAS AND PEANO ARITHMETIC Adrian LUDUȘAN ABSTRACT: One of the philosophical uses of Dedekind's categoricity theorem for Peano Arithmetic is to provide support for semantic realism. To this end, the logical framework in which the proof of the theorem is conducted becomes highly significant. I examine different proposals regarding these logical frameworks and focus on the philosophical benefits of adopting open-ended schemas in contrast to second order logic as the logical medium of the proof. I investigate Pederson and Rossberg's critique of the ontological advantages of open-ended arithmetic when it comes to establishing the categoricity of Peano Arithmetic and show that the critique is highly problematic. I argue that Pederson and Rossberg's ontological criterion deliver the bizarre result that certain first order subsystems of Peano Arithmetic have a second order ontology. As a consequence, the application of the ontological criterion proposed by Pederson and Rossberg assigns a certain type of ontology to a theory, and a different, richer, ontology to one of its subtheories. KEYWORDS: Dedekind's categoricity theorem, categoricity arguments, semantic completeness, semantic realism, open-ended schemas, second order logic, Peano Arithmetic, Quine's ontological criterion Categoricity vs. Completeness Let's begin by defining the two concepts that I will investigate in this section. With respect to this goal we presuppose that a formal language L, a recursive formal system S = {A, F, Ax, R}1 with a semantic provided in the standard way have been specified. In this framework, crucial logical notions can be defined mathematically: what is a deduction of a sentence φ from a set Γ of sentences (Γ├ φ), what it means for a structure M to be a model of a sentence φ (M ⊨ φ) in which case we say that φ is true in M or of a set Γ of sentences (M ⊨ Γ), and what it means for a sentence φ to be the semantic consequence of a set Γ of sentences (Γ ⊨ φ). Definition 1. A theory T is categorical if any two models Mi and Mj of T are isomorphic, Mi ≅Mj. 1 A is the alphabet of L, F is the set of the formulae expressed in L, Ax is the set of certain formulae taken as axioms and R is the set of rules of derivation. Adrian Ludușan 314 Definition 2. A recursive formal system S (with a rigorously defined deduction relation ├) is complete (with respect to the consequence relation ⊨) if for all sets of sentences Γ and sentences φ, if Γ ⊨ φ, then Γ├ φ. There is a tension between the two notions visible in the case of second order Peano Arithmetic, PA2: PA2 is categorical, which makes its consequence relation ⊨2 incomplete, as opposed to first order Peano Arithmetic, PA, which isn't categorical, but the first order consequence relation ⊨ is complete. The argument for the former is straightforward: PA2's (intended) model is N, so from the fact that PA2 is categorical, it follows that all models of PA2 are isomorphic to N. Let φ be any sentence which is true in N; the categoricity of PA2 assures that PA2 ⊨2 φ, i.e. all models of PA2 are models of φ. Since φ is an arbitrary true sentence of N, it can be the canonical Gödel sentence G2 (or Rosser sentence R2). By Gödel's incompleteness theorem, PA2⊬ G2, (or if one prefers working with the Rosser sentence, PA2⊬ R2) although, as argued, PA2 ⊨2 G2, (or PA2⊬ R2) so the consequence relation ⊨2 is not complete in the sense of definition 2. For reasons that we are not going to expose and investigate here, completeness became the philosophically dominant notion among the two so much that the contributions of early authors who actively participated in the development of modern logic and mathematics were interpreted through this conceptual bias. The predominance of completeness over categoricity combined with a poor knowledge of Frege's work led to a crude misinterpretation of his philosophical project. Kneale, for example, in his 1956 paper, "Gottlob Frege and Mathematical Logic,"2 interprets Frege's philosophical goal as providing a complete formal system capable to represent and characterize mathematical theories such as Peano Arithmetic or set theory. And by complete, Kneale understands what is conveyed by definition 2, as can easily be inferred from his conclusion that Frege's project was undermined by Gödel's incompleteness theorem. Since Kneale's paper, categoricity gained momentum on at least two aspects. First, it was recuperated philosophically to the degree that debates regarding its significance not only are on-going, but occupy a crucial part of today's philosophy of mathematics, and the literature is growing. Second, intensive exegetical studies have thrown a new light on the status and relation of categoricity with other logical and mathematical notions in the works of Dedekind, Veblen, Fraenkel, Frege, Carnap, Tarski and Hilbert, to name a few. 2 William Kneale, "Gottlob Frege and Mathematical Logic," The Revolution in Philosophy (London: Macmillan, 1956), 26–40. Categoricity, Open-Ended Schemas and Peano Arithmetic 315 Let us remark in passing that the philosophical ascendance of categoricity gained momentum with Georg Kreisel's 1972 article, "Informal Rigor and Completeness Proofs,"3 touching on the uses of categoricity for sustaining certain realist4 theses in the philosophy of mathematics. Since Kreisel's paper various categoricity arguments have been produced for sustaining substantial philosophical theses. In what follows, I will focus on one such philosophical use of categoricity that gives thrust to semantic realism. In order to explain the mechanism by which categoricity provides support for semantic realism I will present and explain the relation between categoricity and semantic completeness. Categoricity and Semantic Completeness There are several equivalent definitions of semantic completeness. The following seems to be quite intuitive and common: Definition 3: A theory T is semantically complete if either T ⊨ φ or T ⊨¬ φ, for all sentences φ. This definition is equivalent to: Definition 4: A theory T is semantically complete if for all T-models Mi, Mj and sentences φ, Mi ⊨ φ implies Mj ⊨ φ. Proposition 1: Definition 3 is equivalent to definition 4. Proof (sketch): 3 implies 4. Assume that either T ⊨ φ or T ⊨¬ φ, and suppose that Mi ⊨ φ. Now, if it were the case that Mj ⊨¬φ, then the theory T would have two models Mi, Mj such that Mi ⊨φ and Mj ⊨¬φ, which contradicts the assumption that either T ⊨ φ or T ⊨¬ φ, i.e. all models of T satisfies φ or all models of T satisfies ¬ φ. 4 implies 3. Assume that for all T-models Mi, Mj and sentences φ, Mi ⊨ φ implies Mj ⊨ φ. If it isn't the case that either T ⊨ φ or T ⊨¬ φ, then there are Tmodels M1, M2 such that M1 ⊨ φ and M2 ⊨¬ φ which would contradict the assumption that for all T-models Mi ⊨ φ implies Mj ⊨ φ. 3 Georg Kreisel, "Informal Rigor and Completeness Proofs," in Problems in the Philosophy of Mathematics, ed. Imre Lakatos (Amsterdam: North-Holland, 1972): 138–157. 4 For example the thesis that every mathematical sentence expressed in the language of a nonalgebraic theory has a determinate truth value. Adrian Ludușan 316 Steve Awodey and Erich Reck's article, "Completeness and Categoricity. Part I: Nineteenth-century Axiomatics to Twentieth-century Metalogic,"5 testifies, the early authors who developed formal axiomatic systems for significant areas of mathematics such as arithmetic, geometry and analysis 1) meant primarily by 'completeness' what we call categoricity, 2) considered that the philosophical significance of categoricity consists in proving the completeness of the axiomatization of a structure, regarding it as marker for the theory's successful axiomatization, and 3) took semantic completeness to follow immediately form categoricity, without feeling the need for a proof of this fact or analyzing the relations between completeness, categoricity, and semantic completeness. Also, semantic completeness is repeatedly recognized to be a direct consequence of categoricity, although no proof of that fact is ever given; and sometimes the two notions are conflated, or apparently treated as equivalent. Finally, it is only around 1904-1906 that we have found the first expression of a suspicion, in some asides of Veblen's, that neither categoricity nor semantic completeness may need to coincide with deductive or logical completeness, or more generally that the deductive consequence relation may differ from its semantic counterpart.6 Now, for theories expressed in first order logic,7 but also in higher order logic,8 we can prove that categoricity implies semantic completeness. In order to sketch the proof in the first order case, we introduce a definition and state without proof a theorem (the isomorphism theorem): Definition 3: Two models Mi and Mj are elementary equivalent, Mi ≡ Mj, if for all sentences φ, Mi ⊨ φ if and only if Mj ⊨ φ. Theorem 1 (the isomorphism theorem): If Mi ≅ Mj, then Mi ≡ Mj. Proof: by induction on the complexity of formulas and terms. Proposition 2: If a first order theory T is categorical, then it is semantically complete. Proof (sketch): Suppose a first order theory T is categorical. Assume that Mi ⊨ φ, for some T-model Mi. Now, from the assumption that T is categorical it follows that Mi ≅ Mj, for all T-models Mj, which, from the isomorphism 5 Steve Awodey and Erich Reck, "Completeness and Categoricity. Part I: Nineteenth-Century Axiomatics to Twentieth-century Metalogic," History and Philosophy of Logic 23, 1 (2002): 1– 30. 6 Awodey and Reck, "Completeness and Categoricity, Part I," 19. 7 Shortened as first order theories from now on. 8 For a (sketched) proof of the implication in higher order logic, see the proof of Proposition 2 in Steve Awodey and Erich Reck, "Completeness and Categoricity, Part II: Twentieth-Century Metalogic to Twenty-first-Century Semantics," History and Philosophy of Logic 23, 2 (2002), 83. Categoricity, Open-Ended Schemas and Peano Arithmetic 317 theorem, further implies that Mj ⊨ φ. By definition 4 T is semantically complete. An interesting problem is whether the converse of proposition 2 holds. In the case of first order logic, the answer is negative; it is an easy consequence of the Löwenheim–Skolem theorems that no semantically complete first order theories with models that have infinite domains are categorical. The answer is negative too for theories with an infinite set of axioms formulated in higher order logic. Howerver, Carnap9 conjectured that in the case of theories expressed in higher order logic with a finite set of axioms, semantic completeness implies categoricity. Although there are no known counter-examples to the implication from the semantic completeness to the categoricity in the case of such theories and several conditions10 which enable the implication have been discerned, Carnap's conjecture remains unanswered. In what follows I will discuss the use of categoricity as an argument for semantic realism, examine different proposals regarding the logical frameworks in which to prove the categoricity theorem for Peano Arithmetic, focusing on the open-ended arithmetic, investigate a critique of the ontological benefits of adopting open-ended arithmetic and show that the critique is highly problematic.11 Categoricity and Semantic Realism The core of semantic realism consists in the belief that the sentences (expressed in the languages) of certain mathematical theories have objective, and determinate truth values. I will call this belief the truth value determinacy thesis (TVD). The use of the categoricity of a theory T as an argument for the determinacy of the truth values of all the sentences φ expressed in the language of T has been vigorously championed by Vann McGee.12 Let us develop his argument a little bit. A commitment to a literal reading of mathematical sentences, consistent with a realist approach of mathematics, seems to be at odds with an irreparable form of reference inscrutability for singular terms. Without diving too much into history, we can trace the argument for the referential inscrutability of mathematical 9 For details see Steve Awodey and A. W. Carus, "Carnap, Completeness, and Categoricity: The Gabelbarkeitssatz of 1928," Erkenntnis 54, 2 (2001): 145–172. 10 Such conditions include the definability of the model, or that the model of such a theory has no proper submodels etc. 11 Which doesn't mean that the author is committed to the position that it is critiqued. 12 Vann McGee, "How We Learn Mathematical Language," Philosophical Review 106 (1997): 35–68. Adrian Ludușan 318 singular terms to the seminal paper of Paul Benacerraf, "What Numbers Could Not Be."13 Benacerraf begins by noting that in a set-theoretical framework one can construct the natural numbers system in two equivalent but incompatible ways. The popular, if not the standard construction among set theorists, involves representing 0 as Ø, and defining the successor function sN as sN(x) = x ∪ {x}. Proceeding in this manner we obtain the following equalities: 0 = Ø, 1 = {0} = {Ø}, 2 = {0, 1} = {Ø, {Ø}}, 3 = {0, 1, 2} = {Ø, {Ø}, {Ø, {Ø}}} and so on. As can be easily seen, in this construction each natural number n is identified with the set of all its predecessors, and, as a perk, the set corresponding to each number n contains n elements.14 Next, we define NN to be the smallest set containing 0 and closed under the successor function sN. It can be routinely verified that the structure <NN, 0, sN>, thus specified, is a model of a Peano system. The recipe for this particular construction was proposed by von Neumann, and the sets identified as natural numbers are called von Neumann ordinals. An alternative set-theoretic construction of the natural numbers was proposed by Ernest Zermelo; it begins with the same representation of the number 0 as Ø, but defines the successor function sZ(x) = {x}; so, in the zermelian construction, 1 = {Ø} (which is identical with its counterpart in von Neumann construction), 2 = {{Ø}}, 3 = {{{Ø}}} and so on. As in the case above, we define NZ to be the smallest set containing 0 and closed under the successor function sZ and leave to readers to convince themselves that the structure <NZ, 0, sZ>, thus specified, is a model of a Peano system. Now, the two structures are elementary equivalent although referentially different: the set corresponding to 2 in NN is different from the set corresponding to 2 in NZ; moreover, there are true statements which hold in one but not the other: for example, 3∈4 is true in <NN, 0, sN>, but not in <NZ, 0, sZ>. Benacerraf's puzzle, as it is called, may be stated simply as "Which is the right identification of numbers?" Before continuing let's address two caveats: the question regarding the identification of the natural numbers is not meant to disqualify other possible settheoretical candidates, nor to suggest that before the emergence of set theory mathematicians failed to refer to numbers. Benacerraf's puzzle, at least as I read it, concerns the referential status of natural numbers as constructed form set-theory, or, of any theory which have foundational virtues, taking the ontology of set- 13 Paul Benaceraff, "What Numbers Could Not Be," in Philosophy of Mathematics, eds. Paul Benacerraf and Hilary Putnam (Cambridge: Cambridge University Press, 1993): 272–295. 14 Of course, this observation involves a circularity, but the goal of this presentation is not to rigorously define and construct the natural number sequence, which can be found in any introductory textbook on set theory, only to make intuitive the construction. Categoricity, Open-Ended Schemas and Peano Arithmetic 319 theory, or of any particular foundational theory, as the ontology of all mathematics. To what sets do we refer when we speak, in set theoretic terms, about natural numbers: to finite von Neumann ordinals, or to Zermelo cardinals? As mentioned above, there are no mathematical reasons to distinguish between the two constructions, and to propose conventionally adopting one as a solution is hilarious. McGee takes this referential indeterminacy to be unsolvable, but benign. He argues 1) that mathematical reference is scrutable only up to isomorphism and 2) that the important goal of a mathematical theory is to secure the determinacy of the truth values of its sentences, which can be achieved if the theory is categorical. And in this respect, McGee argues, we can have determinacy of truth value without referential determinacy. The difficulty Benacerraf pointed to is a special case of a more general phenomenon of inscrutability of reference. [...] For the objects of pure mathematics, there are no contingencies and no causal connections; so the inscrutability strikes us full force. Inscrutability of reference arises from the fact that our thoughts and practices in using mathematical vocabulary are unable to discern a preference among isomorphic copies of a mathematical structure.15 Now, how do we get from categoricity to truth value determinacy? The general template of the argument runs through the following lines: if T is a categorical theory, then, by proposition 2, T is semantically complete, thus, by the definition of semantic completeness, we get that either T⊨ φ or T⊨¬ φ, for all sentences φ expressed in T's language, which means, when unpacked, that either φ is true in all models M of T or its negation ¬φ is true in all models M of T, which can be taken as an adequate operationalization of the truth value determinacy thesis. Beyond First Order Logic Let's resume the discussion form the last section. Semantic completeness is an easy consequence of categoricity, and is tight with the truth value determinacy thesis which constitutes the backbone of semantic realism. The moral is that the categoricity of a theory T, or its semantic completeness, can be used as an argument in favor of semantic realism, precisely, to argue for the thesis that each mathematical sentence couched in the language of T has a determinate truth value. So, in order to endorse semantic realism, one should focus its attention to 15 McGee, "How We Learn," 38. Adrian Ludușan 320 those logical frameworks in which the categoricity of a theory or its semantic completeness can be conducted. I will argue that this means moving beyond first order logic. As it is well known, the defining properties of first order logic makes it an unsuitable candidate for proving the categoricity of theories, at least for theories which have a model with an infinite domain. Model theoretic results characterizing first order logic tell us that categoricity in first order logic can only be obtained for theories with finite models. Suppose that a first order theory T expressed in a language with cardinality λ, λ ≥ א0, has an infinite model of cardinality κ, κ > λ. The upward Löwenheim–Skolem theorem tells us that T has models of every cardinality κ', κ'≥ κ while the downward Löwenheim–Skolem theorem tells us that T has a model of cardinality λ. Consequently, the two theorems indicate that such a first order theory T can't be categorical. If first order theories that have infinite models are not categorical, maybe we should focus on the semantic completeness of such theories, which can deliver the same result, namely, semantic realism. Unfortunately, things don't look any better on this approach either. Although there are several semantically complete (but not categorical, as we just saw) first order theories such as the theory of discrete linear order with a first and no last point, Presburger Arithmetic16 (P), or elementary geometry17, Gödel's incompleteness theorem assures us that first order Peano Arithmetic can't be among these theories. To be precise, by Gödel's incompleteness theorem there is a sentence G expressed in PA's language such that PA ⊬ G (if P is consistent) and PA ⊬ ¬G, (if PA is ω-consistent); accordingly, PA ∪ {G} and PA ∪ {¬G} are consistent, so by the model existence lemma they each have a model, let's say M1 and M2, which, a fortiori, are models of PA. In conclusion, PA isn't categorical nor semantically complete, which means that we don't have reasons to believe that PA has a unique model modulo isomorphism nor that the sentences expressed in PA's language have determinate truth values. Now, if there is a mathematical theory for which we have strong intuitions that it has a unique model up to isomorphism and that its sentences are determinately true or determinately false, that is Peano Arithmetic. So sticking with first order logic doesn't look like viable solution. Before continuing, a caveat should be addressed here: of course, we can resort to certain frame first order theories such 16 I will present and discuss Presburger Arithmetic later in the paper. For more details about the properties of Presburger Arithmetic see Herbert Enderton, A Mathematical Introduction to Logic, second edition (Boston, MA: Academic Press, 2001). 17 Tarski proved that elementary geometry formulated in first order logic is semantically complete and decidable, although not categorical. For more details see Alfred Tarski, Andrzej Mostowski, and Raphael Robinson, Undecidable Theories (Amsterdam: North-Holland, 1953). Categoricity, Open-Ended Schemas and Peano Arithmetic 321 as ACA0 or first order set theory in which we can prove the categoricity of PA, but the standard argument against it is that this maneuver will push the problem from the categoricity of PA to that of the frame first order theories. Being formulated in first order logic, these too will have non-isomorphic models, non-standard models, and the categoricity of PA proved in these settings only ensures the uniqueness of the referential structure of PA within each model of the frame theory, not across models. In distinction, in second order logic, it is argued, we have categorical characterizations not only of Peano Arithmetic but of endless mathematical structures. Let us note, in passing, that Väänänen18 argued that this distinction between first order set theory and second order logic is illusory. However, I will not engage in this issue here, as my goal is to assess a critique addressed to the full open-ended arithmetic as a medium for conducting categoricity proofs. Second Order Logic vs Open-Ended Schemas By contrasts with first order logic, in full second order logic one can categorically characterize Peano Arithmetic without the shortcomings inherent to first order settings mentioned and discussed above. But, as often, there is a price to be paid. In this case, the price regards the epistemological and ontological status of full second order logic and the epistemological significance of a categoricity proof conducted in such a system. Epistemologically, there are a number of concerns regarding, on the one hand, the presuppositions implied by adopting second order logic as the framework in which to conduct the proof of the categoricity of Peano Arithmetic, and, on the other hand, the significance of a categoricity proof given those presuppositions. Full second order logic presupposes that the range of the second order quantifiers is constituted by the power set of the domain of the first order quantifiers. In our case, the range of second order quantifiers is ℘(N). Now, this can be unsettling for three reasons. First, it presupposes that we have an infinitary conception of sets of numbers, precisely, of arbitrary infinite sets of numbers whose membership relation we can't specify. Second, as argued by Toby Meadows,19 an approach to categoricity via full second order logic presupposes a powerful philosophical thesis, the superstructure thesis,20 that each structure has a unique superstructure, where the superstructure is formed by taking the set of all 18 Jouko Väänänen, "Second Order Logic, Set Theory and Foundations of Mathematics," The Bulletin of Symbolic Logic 7, 4 (2001): 504–520. 19 For more details, see Toby Meadows, "What Can a Categoricity Theorem Tell Us?" The Review of Symbolic Logic 6 (2013): 524–543. 20 Meadows, "What Can a Categoricity," 534–535. Adrian Ludușan 322 collections of the domain and expanding the model accordingly. Thirdly, there are all the concerns regarding the determinacy and intelligibility of the powerset operation which I will not explore here. All these presuppositions make the epistemological significance of categoricity diminish. The belief in the superstructure thesis, for example, is philosophically stronger than that of the uniqueness of Peano Arithmetic modulo isomorphism, so nothing significant has been achieved in this case by providing a categoricity proof. Regarding the first presupposition it can be objected that the belief in the uniqueness of Peano Arithmetic does not commit one to an infinitary conception of arbitrary sets. On the ontological side, an adherent of second order logic seems to be committed to the existence of something more than merely the elements of the first order domain, namely, to arbitrary sets of such elements, because the range of the second order quantifiers is constituted by the powerset of the first order domain. In particular, one who adopts PA2, is committed not only to the existence of numbers, but of arbitrary sets of numbers, in virtue of the semantics of the second order quantifiers. Now, these ontological commitments have been called "unsavory" by McGee21 "because they concern entities that are not properly speaking part of the subject-matter of the target theory – thus entities which an axiomatization of the theory should not commit one to."22 This way of determining the ontology of a theory is tributary to Quine's slogan that "to be is to be the value of a bound variable."23 Of course, this ontological criterion is not the only offer on the market, nor is it unanimously embraced, but in what follows I will focus on some arguments that rely on this criterion. In view of all these difficulties raised by the full second order logic, some authors24 proposed an alternative in which to conduct categoricity proofs, an alternative suspended25 between first and second order logic: the idea is to remain 21 McGee, "How We Learn," 38. 22 Nikolaj Jang Lee Linding Pedersen, and Marcus Rossberg, "Open-Endedness, Schemas and Ontological Commitment," Nous 44 (2010): 331. 23 Willard van Orman Quine, "On What There Is," in his From a Logical Point of View, second, revised edition (New York and Evanston: Harper Torchbooks, 1963), 15. 24 I refer here to McGee, " How We Learn," Charles Parsons, "The Uniqueness of the Natural Numbers," Iyyun 39 (1990): 13–44, Charles Parsons, Mathematical Thought and its Objects (Cambridge: Cambridge University Press, 2008), and Shaughan Lavine, Skolem Was Wrong (Mansucript, 1999). 25 To make more suggestive this in-between status of open ended schemas, I'll index all such occurrences with 1⁄2, 1 being the index of formulas or sentences for first order logic and 2 for second order logic. Categoricity, Open-Ended Schemas and Peano Arithmetic 323 formally within the bounds of first order logic, but to consider axiom schemas of theories as being open-ended, meaning to consider that axiom schemas remain valid under arbitrary extensions of a theory's language. Let's restrict our attention to Peano Arithmetic, and formulate more carefully the idea behind open ended schemas in this particular case. The first order Peano Arithmetic, PA, has an induction schema: (Ind1) (φ(0)∧∀x(φ(x)→φ(s(x))))→∀xφ(x), for all φ(x) ∈ LPA. which is not a part of LPA, but every instance gotten by substituting any open sentence of LPA for φ(x) is. Now, Kreisel26 pointed out that our belief in Ind1, that is, in the validity of the outcome produced by substituting open sentences of LPA for φ(x), derives from our acceptance of the second order induction axiom: (Ind2) ∀X(X0∧∀x(Xx→Xs(x))→∀xXx), for all X ⊆ ℘(N). But, as remarked above, the philosophical price for adopting second order logic is quite high, devoiding the results that can be obtained in second order logic of epistemological value or committing one to 'unsavory' ontological entities. What McGee, Lavine and Parsons propose is to adopt the following openended schema of induction:27 (Ind1/2) (φ(0)∧∀x(φ(x)→φ(s(x))))→∀xφ(x), for all φ(x) ∈ L and all L ⊇ LPA. Various reasons have been advanced in order to support this alternative. Just to give an example, McGee28 argues that in a rational reconstruction of how we learn mathematical theories, an essential step is precisely mastering the functioning of open ended schemas, so, in learning arithmetic, we basically learn (Ind1/2). I will not present and examine all these arguments here, but focus on one reason that McGee stresses: that resorting to open ended schemas, among other philosophical benefits, purges the unsavory ontological commitments of second order logic retaining its strengths. Now, let's see how this maneuver retains the relevant properties of full second order logic that allow us to establish the categoricity of Peano Arithmetic. In order to show this we have to clarify what extensions of LPA are admissible. Briefly, the legitimate extensions of LPA are those that are formed by 26 Kreisel, "Informal Rigor." 27 Remember that the only significant change between PA and PA2 is the induction axiom and the semantics that accompanies it. 28 McGee, "How We Learn." Adrian Ludușan 324 the introduction of a name or a constant denoting any individual from the domain, or by the introduction of predicates such that for any collection C of individuals from the domain, there is a predicate that is true of C, or it is involved in the construction of an open sentence satisfied by exactly the members of C. A passage from McGee's article "How We Learn Mathematical languages" is particularly illuminating in this respect: To say what individuals and classes of individuals the rules of our language permit us to name is easy: we are permitted to name anything at all. For any collection of individuals K there is a logically possible world though perhaps not a theologically possible world in which our practices in using English are just what they are in the actual world and in which K is the extension of the open sentence 'x is blessed by God.' So the rules of our language permit the language to contain an open sentence whose extension is K. Moreover, the rules ensure that a true sentence would be obtained if such an open sentence were substituted into the Induction Axiom Schema, so they ensure that, if K contains any natural numbers at all, it contains a least natural number. This holds for any collection K whatever, whether or not we are psychologically capable of distinguishing the K's from the non-K's.29 Following Pedersen and Rossberg I will operationalize the above remarks in what they call McGee's rule: Consider a theory T formulated in a language L with at least one open-ended schema. Then: (1) Any individual is nameable. If, for a given individual, L does not already contain a name for it, such a name can be added to L. (2) Any collection of individuals C is nameable, in the sense that, if L does not already contain an open sentence φ which holds exactly of the members of C, predicates (or other expressions) can be added to L that allow formulating a sentence that holds exactly of the members of C.30 This rule coupled with (Ind1/2) is logically as powerful as (Ind2) in the setting of full second order logic. Any set S that is in the range of the second order quantifiers can be named in an extension of LPA by an open sentence, and substituted for φ(x) in (Ind1/2) in order to obtain a first order instance. This equivalence between the semantic values of second order quantifiers and the semantic values of predicates or open sentences in arbitrary extensions of LPA is 29 McGee, "How We Learn," 59. 30 Pedersen and Rossberg, "Open-Endedness," 333. Categoricity, Open-Ended Schemas and Peano Arithmetic 325 sufficient to ensure the provability of the categoricity of Peano Arithmetic. Just consider the second order formula: σ(x): ∀X((X0 ∧∀y(Xy→Xs(y)))→Xx) Intuitively, this formula expresses the property of having all the hereditary properties of 0. By the comprehension schema of full second order logic there is a set which is the extension of this formula, so such a set is in the range of the second order quantifier. Applying (Ind2) to the formula σ(x) we get (σ(0) ∧∀y(σ(y)→σ(s(y))))→∀xσ(x); proving the antecedent, which is fairly straightforward, yields PA2 ⊢∀xσ(x), from which, assuming soundness, we can infer PA2 ⊨∀xσ(x), that basically says that in every model of PA2 every element in the domain is 0 or one of its (finitely) successors. With this result established, categoricity falls shortly, all that remains to be proved is that any two such models of PA2 are isomorphic, which can be easily established. Now, the equivalence between the semantic values of second order quantifiers and the semantic values of predicates or open sentences in arbitrary extensions of LPA assures us that there is an open formula σ'(x) or a predicate letter with precisely the same extension as σ(x), which, of course, is subject to (Ind1/2). The above argument can now be reproduced and, thus, the categoricity of open-ended arithmetic established. This is the basic argument that open-ended arithmetic is categorical. Open-Ended Schemas and Ontological Commitment McGee argues that one of the advantages of adopting open-ended arithmetic is represented by its ontological parsimony. Let's sketch McGee's argument for this. We have mentioned that the active criterion employed in characterizing the ontology of a theory based on the range of its quantifiers is that proposed and advocated by Quine, that to be is to be the value of a bound variable. On a literal reading of this slogan, the open-ended arithmetic seems to be, ontologically, on a par with first order logic, for its quantifiers are first order. Every instance of (Ind1/2) is first order, so open-ended arithmetic is committed to the existence of numbers, as revealed by the presence of its first order quantifiers, and is not committed to the existence of sets of numbers as revealed by the absence of second order quantifiers. This, in a nutshell is the gist of McGee's argument that open-ended schema arithmetic is "metaphysically benign."31 31 McGee, "How We Learn," 60. Adrian Ludușan 326 Let us note that although open-ended arithmetic is ontologically as innocent as first order logic, in terms of characterizing the structure of the natural numbers is as powerful as second order logic. Now, this package consisting of open-ended schemas coupled with McGee's rule may be seen as a cheat not only in establishing categoricity but also as a maneuver of avoiding the unsavory ontological commitments of second order logic. And, indeed, it was criticized on both accounts. Hartry Field32 criticized this approach in delivering categoricity results, insisting that it is at best question begging and has nothing to do with open-ended schemas and everything to do with the admissibility of new predicates with already determined extensions. Pedersen and Rossberg criticized it as a cheat for it presupposes a narrow reading of Quine's ontological criterion. In what follows I will concentrate on this second critique. What Pedersen and Rossberg rightly observed is that the second order universal quantifier present in (Ind2) gained one level, so to speak, thus appearing in (Ind1/2) as the qualification that we have to take into consideration all (possible) extensions L of LPA, more precisely (focusing on McGee's rule), that we can introduce predicates or open sentences and constants for all individuals and collections of individuals that constitutes the first order domain. So, the second order quantifiers disappears from the object theory, thus relieving it from the unsavory ontological burden, and emerges with basically the same function in the meta-theory, this time, seemingly, with no ontological effects at all. It is this observation that motivates Pedersen and Rossberg in amending Quine's criterion in order to account for this type of maneuvers. What they propose is not a renunciation to the ontological criterion of Quine, but a modification of it so that, for some particular contexts, the first level ontological commitments of a theory, represented by the range of the theory's quantifiers, have to be coupled with the second level ontological commitments implied in the meta-theoretical principles that construe the theory. Well, the big question is to specify the cases in which we have to combine the two levels of ontological commitments. Although the authors admit that this is a "delicate and difficult issue"33 they present a landmark that signals when the modified criterion has to be deployed: the modified criterion becomes active in all the cases where the meta-theoretical principles are indispensible for construing the theory in a 32 Hartry Field, "Postscript," in his Truth and the Absence of Fact (New York, Oxford University Press, 2001). 33 Pedersen and Rossberg, "Open-Endedness," 333. Categoricity, Open-Ended Schemas and Peano Arithmetic 327 certain way, in order to achieve a goal. Let's synthesize their proposal in the following manner: Pedersen & Rossberg's ontological criterion (PROC): The ontological commitments of a theory T consists of the values of the bound variables of T together with the values of the bound variables of the metal-theoretical principles used for construing T in a certain specific way. Armed with this modified criterion we can see that open-ended arithmetic fails to be as ontologically parsimonious as first order arithmetic is; in fact, applying Pedersen & Rossberg's criterion equates the ontological commitments of open-ended arithmetic with those of second order arithmetic. The reason should be clear: as we have seen, McGee's meta-theoretical rule is indispensable in order to construe Peano Arithmetic as categorical and, thus, establishing the thesis of truth-value determinacy. As Hartry Field remarked,34 McGee's rule is where the magic of the open-ended arithmetic lies, not (Ind1/2), and, as shown in the previous section, the rule is needed in order to prove the categoricity which, further, is used for establishing the truth-value determinacy of arithmetical statements. So, if the rule is used for construing the theory in this particular way (categoricity plus truth-value determinacy), then the bounded variables specified in the rule contribute to the theory's ontology, thus leading to the nasty repercussion for the aficionados of open-ended arithmetic that its ontology is equivalent to that of second order arithmetic (in virtue of the equivalence between the semantic values of the second order quantifiers and the semantic values of the predicates and open sentences of all the admissible extensions of LPA). This should be a fairly accurate gloss of Pederson and Rossberg: Applying the modified criterion of ontological commitment, McGee's Rule is thus ontologically committing when open-ended arithmetic is thought of as a categorical theory with certain philosophical ramifications – which is exactly the way it is thought of when compared to second order arithmetic. Open-ended arithmetic – regarded in the manner indicated – is therefore not just committed to the numbers that serve as the values of the bound variables of the theory itself, but likewise to classes of these – indeed, to a class for any combination of numbers. Why? Because McGee's Rule involves a quantifier that ranges over arbitrary collections of the first-order domain: any collection of members of the first-order domain can be named.35 34 Field, "Postscript," 355-356. 35 Pedersen and Rossberg, "Open-Endedness," 336. Adrian Ludușan 328 Critiquing the Critique In this section I will assess the critique of Pedersen and Rossberg regarding the ontological commitments of open-ended arithmetic, precisely, I will argue not only that their revised ontological criterion delivers counterintuitive results in certain widely accepted cases of first order theories, but that it assigns a certain type of ontology to a theory, and a different, richer, ontology to one of its subtheories, making their proposal highly problematic. This doesn't mean that I endorse McGee's argument for the ontological parsimony of open-ended arithmetic over second order arithmetic, nor do I think that resorting to openended arithmetic is genuinely a valid maneuver for establishing categoricity. Let's start by analyzing the modified ontological criterion (PROC). A first observation is that there seems to be an ambiguity in what the construal of the theory means. In our specific case, it seems that the construal of open-ended arithmetic means establishing categoricity and, as a philosophical consequence, the truth-value determinacy of its statements. But, McGee's rule, properly speaking, allows establishing the categoricity of arithmetic not the truth-value determinacy of its sentences, and it is debatable whether the latter follows from the former. So, in a sense, the construal forced by McGee's rule covers only categoricity, not truth-value determinacy. But let's concede that the proper construal of open-ended arithmetic involves the whole package, categoricity plus truth value determinacy. If this is the case, then my contention is that PROC is too philosophically sensible to be employed as a tool of discerning the ontology of a theory. Suppose that some authors deny that the categoricity of a theory has as a "philosophical corollary"36 the truth value determinacy thesis. In fact, as Pedersen and Rossberg mention,37 Hartry Field is one of them. For these authors, McGee's rule does not enforce the truth value determinacy thesis based on categoricity. Then, is it the case that for authors like Hartry Field open-ended arithmetic has a first order ontology? Somehow, in order to determine the ontology of a theory we are supposed to recognize and agree that the theory was construed in a certain manner, for example to be categorical and characterized by the determinacy of the truth values of its sentences. The problem, in our case study, is that the connection between the two constitutive items of the construal of open-ended arithmetic is not straightforward or transparent, leaving room for disagreement between the philosophical goal and the meta-theoretical property (categoricity, in this case) that supposedly delivers the goal. Surely, an easy answer would be to argue that 36 Pedersen and Rossberg, "Open-Endedness," 336. 37 Pedersen and Rossberg, "Open-Endedness," 337, note 2. Categoricity, Open-Ended Schemas and Peano Arithmetic 329 what matters is not how a person views the relation between the goal and the meta-theoretic property, but that the theory was construed in a specific manner in order to achieve a certain goal whether one agrees that it accomplish the intended goal or not. But this presupposes that establishing the ontology of a theory requires the ability to discern the indirect goals behind the formulation of certain meta-theoretical principles. So, prior to establishing the ontology of a theory we have to discern what goals motivate the particular formulation of certain principles. But this requirement faces two difficulties. First, the goals aren't necessarily grasped form the formulation of the principles, so that one who is not aware of the intention with which the meta-theoretic principles were formulated may attribute a different ontology than one who is. Secondly, one can find numerous compatible goals with the formulation in a certain manner of some meta-theoretical principles, thus expanding the ontology even of theories with widely recognized first-order type ontology. Now, even if we grant, for the sake of argument, that the relation between the meta-theoretic property and the intended goal that it serves is not philosophically obscure, equivocal, or sensible, so that the connection is, to a functional degree, unproblematic, there is another objection that can be raised against PROC. The objection is that certain first order theories that have a first order ontology, by PROC's standards, have sub-theories with a second order ontology, according to the same ontological criterion, i.e. PROC. In the remainder of this paper I will develop such an example. Presburger Arithmetic, P, is the sub-theory of PA from which we expelled the axioms governing the behavior of multiplication. Precisely, P is defined by the following axioms: (i) ∀x ¬(0 = s(x)) (ii) ∀x∀y ((s(x) = s(y))→(x = y)) (iii) ∀x(x + 0 = x) (iv) ∀x∀y ((x + s(y) = s(x + y)) plus the axiom schema for induction: (v) (IndP) (φ(0)∧∀x(φ(x)→φ(s(x))))→∀xφ(x), for all φ(x) ∈ LP. Let's mention, without giving a proof38, a remarkable property of Presburger Arithmetic, namely, that it is semantically complete. 38 The standard way of proving the semantic completeness of P is by using quantifier elimination. Adrian Ludușan 330 Now, focusing on the induction axiom (IndP), let's note that based on the way it is formulated, one can associated with it a meta-theoretic rule, call it MTR, that, as I will argue bellow, has an indispensable role in proving the semantic completeness of the theory from which the same old truth-value determinacy thesis follows. MTR: Consider a theory T formulated in a language L with at least one axiom schema. Then: Certain sets of numbers are nameable, precisely those sets whose members satisfy an open sentence of T. For every open sentence φ(x) of L there is a set S such that φ(x) holds exactly of the members of S. We can see that, mirroring the formulation of McGee's rule, MTR just explicitly states what is involved in the appendix 'for all φ(x) ∈ LP', or, for that matter, in any appendices of first order axiom schemas. As in the case of (Ind1/2) and McGee's rule, the power of (IndP) lies in MTR. Without MTR, (IndP) has no real teeth, so, without MTR, (IndP) is useless, and P is reduced to the four axioms i) – iv) which constitutes a sub-theory of P, let's call it O. In other words, dropping MTR amounts to a renunciation of (IndP), thus leaving us with O. It can be proved, by a simple model-theoretic argument, that O is not semantically complete. In fact, one can build models of O in which intuitive true statements in the standard model of Peano Arithmetic, like ∀x(0 + x = x), and ∀x¬(s(x) = x) are false. Take the statement ∀x¬(s(x) = x). In the standard model of Peano Arithmetic, this statement is true, so in the standard model of O, OS this statement is also true, OS ⊨ ∀x¬(s(x)=x). Let's construct a model O* of O by inserting into the standard model an element a, which is its self successor, i.e. (s(a) = a) and define addition +* in the following manner: As one can verify, in this model all the axioms of O are true, yet ∀x¬(s(x)=x) is false, as witnessed by a, so O* ⊨ ¬(∀x¬(s(x) = x)). As a consequence, O is not semantically complete. So, dropping MTR amounts to dropping (IndP) which, as we have seen, has the consequence that the remaining theory O defined by axioms i) – iv) minus (IndP) is not semantically complete. Categoricity, Open-Ended Schemas and Peano Arithmetic 331 The above argument shows that the MTR rule is essential in construing P as semantically complete, which means that P is subject to PROC, so one is right to claim that P is ontologically committed to the existence of certain sets of numbers, namely to those sets that are the semantic values of the open sentences of P. Technically, the quantifier present in MTR commits P to the existence of sets of numbers, so the ontology of P is second order. Thus, applying PROC to P gives us the odd result that Presburger Arithmetic has a mixed ontology, composed of numbers and sets of numbers, basically, a second order ontology, parsimonious to be fair, but, nevertheless, second order. Of course, this goes against the widely accepted first order ontology of this theory. More importantly, applying PROC to PA gives the result that PA has a first order ontology, yet, based on the same criterion, a sub-theory of PA, namely P, has a parsimonious second order ontology. I take the result that PA has a first order ontology, corroborated by the universal consensus,39 to mean that P, as a sub-theory of PA, has to have a first order type of ontology. Yet, on this issue, PROC says something else, that P has a second order ontology. What credibility an ontological criterion has, if it assigns a certain type of ontology to a theory, and a different, richer, ontology to one of its sub-theories? The fact that PROC delivers such weird, if not inconsistent, results seems to me to be a sign that it simply does not work as an adequate and functional ontological criterion. Let's address another possible objection that may be raised against the argument developed so far. Maybe PROC is applicable only for those theories lacking a meta-theoretic property such as categoricity or semantic completeness, and for which a meta-theoretic principle is summoned in order for the theory to acquire a certain meta-theoretic property. This objection can be counter by observing that a change in MTR affects the meta-theoretic properties of P: for example, if we restrict MTR to a certain specific set of open sentences φ(x) of L, such as the Δ0 set of formulas of LP, then P is no longer semantically complete. Consider the theory PΔ0: (i) ∀x ¬(0 = s(x)) (ii) ∀x ∀y ((s(x) = s(y)) → (x = y)) (iii) ∀x ((x + 0) = x) (iv ) ∀x ∀y ((x + s(y)) = s(x + y)) and 39 I don't know whether somebody has argued that PA's ontology goes beyond first order. Adrian Ludușan 332 (v) (IndΔ0): (φ(0) ∧ ∀x(φ(x) → φ(s(x))) → ∀x(φ(x)), for all φ(x) ∈ Δ0 or for some suitable specified subset of formulas of LP. Claim: PΔ0 is incomplete. Argument: It is not hard to see that the sentence U = ∀x(¬(x = 0) → ∃y(x = s(y))) is not derivable in PΔ0, and not difficult to construct models Mi and Mj such that Mi ╞ U and Mj ╞ ¬U. Now, in order to make PΔ0 semantically complete, we can lift the restriction of considering only Δ0 open formulas as being amenable to induction and let the whole set of open formulas of LP be subjected to the rule of induction, thus adopting a full-fledged MTR. The resulting theory will be semantically complete, because of the adoption of this full-fledged MTR, so again PROC will be applicable to this particular example, delivering the same inconsistent results. As I have mentioned, this critique of PROC is not meant to be an endorsement of McGee's philosophical position on open ended arithmetic, which, for reasons that I will not explore here, I think is highly problematic too. The whole point of this section was to argue that Pederson and Rossberg's proposal to modify Quine's ontological criterion, although justly motivated, leads to some counterintuitive and hard to accept results regarding the widely accepted ontology of some simple arithmetic theories.40 40 This paper is supported by the Sectoral Operational Programme Human Resources Development (SOP HRD), financed from the European Social Fund and by the Romanian Government under the contract number POSDRU 159/1.5/S/133675.