Abstract
Quine’s most important charge against second-, and more generally, higher-order logic is that it carries massive existential commitments. The force of this charge does not depend upon Quine’s questionable assimilation of second-order logic to set theory. Even if we take second-order variables to range over properties, rather than sets, the charge remains in force, as long as properties are individuated purely extensionally. I argue that if we interpret them as ranging over properties more reasonably construed, in accordance with an abundant or deflationary conception, Quine’s charge can be resisted. This interpretation need not be seen as precluding the use of model-theoretic semantics for second-order languages; but it will preclude the use of the standard semantics, along with the more general Henkin semantics, of which it is a special case. To that extent, the approach I recommend has revisionary implications which some may find unpalatable; it is, however, compatible with the quite different special case in which the second-order variables are taken to range over definable subsets of the first-order domain, and with respect to such a semantics, some important metalogical results obtainable under the standard semantics may still be obtained. In my final section, I discuss the relations between second-order logic, interpreted as I recommend, and a strong version of schematic ancestral logic promoted in recent work by Richard Heck. I argue that while there is an interpretation on which Heck’s logic can be contrasted with second-order logic as standardly interpreted, when it is so interpreted, its differences from the more modest form of second-order logic I advocate are much less substantial, and may be largely presentational.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
See Quine (1970), pp. 66–68. Most of his other complaints—that reading predicate letters as attribute variables is the product of a use-mention confusion, that putting predicate letters in quantfiers, as in \(\exists F\), must involve treating predicates as “names of entities of some sort”, and that “variables eligible for quantification ... do not belong in predicate position ... [but] in name position”—rest on what seems to me an unjustified refusal to entertain the possibility of non-nominal quantification. It is certainly true that higher-order quantification does not read back easily into natural English, so that we are likely, faced with a sentence such as \(\exists F\forall xFx\), to resort to a nominalizing paraphrase, such as ‘There is some property which every object has’; but that hardly justifies insisting that we can only make sense of it by confusing predicates with names.
Charles Parsons had already argued, some years before Quine’s famous onslaught, that even when the values of second-order variables are taken to be “incomplete” entities, such as Fregean concepts, second-order logic—or at least ‘full’ second-order logic, with unrestricted impredicative comprehension—carries existential commitments comparable to those of standard set theory. See Parsons (1965).
In his very useful exposition and defence of second-order logic, Stewart Shapiro seeks to remain officially neutral on the issue whether second-order variables range over classes, with their purely extensional identity-conditions, or properties, which ‘are often taken to be intensional’ (Shapiro (1991), p. 16)—however, he makes it clear that his preference, ‘if pressed’, would be for an extensional interpretation (see pp. 63–64). Shapiro’s own response to Quine’s charge is quite distinct from the one I am recommending. In essence, he counters by appealing to another Quinean doctrine—if, as Quine maintains in line with his holistic methodology, there is no useful distinction between mathematics and physics, why should he think there is one between logic and mathematics (‘especially the logic of mathematics’, op.cit. p. 17, Shapiro’s emphasis).
For simplicity, I discuss only properties explicitly-adapting what I say to relations is a routine matter.
Of course, any departure from extensionality will mean giving an account of property identity which Quine would have found unacceptable, for that very reason. It is no part of my project to meet all Quine’s demands on his terms, some of which I reject as unreasonable. For a somewhat fuller response to Quine, see Hale (2013b).
It might be thought that individuating properties more finely—i.e., more finely than sets—would mean that there would be more properties than sets, rather than fewer. It is true, of course, that individuating properties non-extensionally may entail recognizing distinct (co-extensive) properties where there may be but one set. But it matters much how precisely properties are individuated. The condition for property identity and existence I shall recommend later in this section will mean that properties cannot outrun the definable sets. Since these are usually (i.e., classically) taken to constitute a tiny minority of the sets, it might be thought that my proposed condition is unduly restrictive. From what might be a called a full-blooded classical standpoint, it is restrictive—but whether it is unduly so depends, of course, on the defensibility of that standpoint. In another sense, the condition I recommend is less restrictive than one might suppose. See the closing paragraphs of Sect. 3 below.
Leibniz gives his definition in several places (see, for example, Gerhardt (1875-90), vol. 7, pp. 219–220, 225, 228, 236, Couturat (1961), p. 362—these passages are all translated in Parkinson (1966), pp. 34–35, 43, 52–53, 122, 131). Here is a typical formulation: “Those terms are ‘the same’ of which one can be substituted in place of the other without loss of truth, such as ‘triangle’ and ‘trilateral’, ‘quadrangle’ and ‘quadrilateral’.” Although my formulation in the text is quite common, it is not, as far as I know, used by Leibniz. It is plausibly taken to be a consequence of Leibniz’s definition in terms of intersubstitutability salva veritate. Intersubstitutability guarantees that for any context \(\phi (-)\), \(\phi (\alpha )\) is true iff \(\phi (\beta )\) is, so that provided one can take \(\phi (-)\) to stand for a property which \(\alpha \) and \(\beta \) have or lack, they must have all their properties in common. The steps are reversible. The formulation in terms of sharing all properties has the advantage of avoiding the use-mention confusion with which Leibniz is sometimes—and, in my view, somewhat pedantically—charged. But it is worth noting that his own definition is more general, and not restricted to identity of objects. On the contrary, the majority of his examples involve pairs of general terms, as in the examples quoted. Thus the un-necessitated version of the definition of property-identity I go on to propose in the text has a good claim to be a further special case of Leibniz’s definition. I am grateful to Maria Rosa Antognazza for some references and advice on Leibniz’s views.
It is obvious that the strengthened condition is necessary. For an argument for its sufficiency, see Hale (2013a), pp. 187–188.
By this, I mean only that it is probable that no definition of the word or concept can be given. I do not mean that there can be no definition of the relation of identity itself, in the sense of a specification of its essence or nature (for some general remarks on definition in the latter, broadly Aristotelian, sense, see Hale (2013a), pp. 150–156).
I am thinking, of course, of the “sparse properties” and “sparse universals” advocated by David Lewis and David Armstrong. Lewis’s own usage of ‘property’ is quite different from mine, and potentially confusing. He distinguishes between what he calls sparse and abundant properties, identifying the latter with sets. See Lewis (1986), pp. 55–69.
An accurate statement of a necessary as well as sufficient condition calls for somewhat greater care than is exercised here—see Hale (2013a), pp. 36–37.
Let P be any purely general property, p the proposition that P exists and q the proposition that there is a predicate standing for P. Given the abundant conception of properties, \(\Box (p\leftrightarrow \Diamond q).\) By the Law of Necessity, it follows that \(p\leftrightarrow \Diamond q\), and by the K-principle, \(\Box p\leftrightarrow \Box \Diamond q.\) Provided that the logic of the modalities involved is S5, we have \(\Diamond q\leftrightarrow \Box \Diamond q.\) Whence by the transitivity of the biconditional, \(p\leftrightarrow \Box p\). For a slightly fuller statement, see Hale (2013b), p. 135, Hale (2013a), pp. 165–167.
For a very clear and detailed account of these results, see Shapiro (1991), Chaps. 3,4. I am assuming, with Shapiro, that we restrict attention to what he calls faithful Henkin models.
I did think this, and said as much in Hale (2013b), where I sought—needlessly, as I now see—to argue that the loss of categoricity results was not a crippling disadvantage, and made what I now see was badly confused attempt to show that the usual first-order metatheorems hold at second-order if one adopts my proposed semantics. In essence, my mistake resulted from paying insufficient heed to a crucial point of similarity between my proposed semantics and the standard semantics, in contrast with the general Henkin semantics. The mistake was repeated in Hale (2013a), published a few months later, and went unnoticed (by me at least) until I was prompted to rethink by a helpful reminder from Ian Rumfitt that a categorical axiomatization of arithmetic can be given in an extension of first-order logic much weaker than second-order logic (John Myhill’s ancestral logic, q.v. Myhill (1952)). Ancestral logic adds to first-order logic an operator * which applies to any dyadic relation to yield its ancestral; a categorical axiomatization is obtained by adding to the first-order Dedekind–Peano axioms a further axiom asserting that each natural number other than 0 bears the ancestral of the successor relation to 0.
At least, it does so from the standpoint of the set-theoretic orthodoxy which sees its second-order domains as restrictions of the standard domains. From that orthodox point of view, there are many properties on (or subsets of) the first-order domain which go unrecognized in my modest semantics. But a proponent of modest semantics who is motivated by the deflationary theory of properties should insist that the definable properties are all the properties there are, so that there is no shortfall. Although the deflationary theory of properties does not directly conflict with the idea that there are, if the first-order domain is infinite, many subsets of that domain besides the definable subsets, it is a further question whether it would do so, if combined with a similar, deflationary conception of objects, according to which it is necessary for the existence of an object that there could be a singular term having that object as its referent. If it did so, the deflationary position would be potentially revisionary, not only of the standard second-order semantics, but of the orthodox set theory which lies behind it. The question is as delicate and difficult as it is important—and too large to take on here. One source of difficulty, crucial to a proper discussion of the issue, is that whilst, for model-theoretic purposes, ‘definable’ has to be understood as definability in some fixed language, no such restriction to a fixed language is involved in the deflationary theory’s general statement of existence-conditions for properties and objects—there need not be (and indeed, surely cannot be) some single language in which all objects and properties are specifiable. A further complication is that one can prove in second-order logic both the uncountability of the real numbers, and a version of Cantor’s Theorem that for any set is strictly smaller than its powerset, to the effect that the sub-properties of any property outrun its instances (see Shapiro (2000), pp. 343–345; Shapiro (1991), pp. 103–104)—of course, while these results are not in question, their philosophical significance is very much open to discussion.
I am grateful to an anonymous reviewer for pressing this point.
Nevertheless, it appears to have escaped serious challenge until relatively recently—as far as I know, until Rayo and Yablo (2001).
In Wright (2007), Crispin Wright argues for a “neutralist” conception of quantification, according to which it is simply a device for what he terms generalization of semantic role. The idea is, roughly, that quantifying into the position occupied by an expression s of a certain syntactic type in a sentence [...s...] does not invoke a range of entities—the possible values of the variable replacing s—rather, it takes us to a content or thought whose truth-conditions requires a certain kind of distribution of truth-values over contents of the type of [...s...]. The conception is neutral in the sense that it takes no stand, either way, on whether s stands for an entity of a certain type. So neutralism is compatible with a view on which second-order quantification carries no ontological commitment at all; but it does not entail such a view.
If one combines Wright’s neutralist interpretation (see fn. 18) with the view that first-level predicates don’t stand for entities of any kind, one will deny that comprehension axioms have any such existential content. As Wright puts it: “It goes with neutralism, as I have been outlining it, that there need be—more accurately: that for extreme neutralism, at least, there is—no role for comprehension axioms” (Wright (2007), p. 164).
Whether we have what is usually called full second-order logic depends on whether \(\phi \) is allowed to contain further free first-order variables besides x or free second-order variables other than X. In what follows, I assume that \(\phi \) does not contain additional free variables. I am indebted to an anonymous reviewer for stressing the need for clarity on this point. I believe what I say below can be extended to the more general case, but do not claim that here.
The argument of the last two paragraphs puts together pieces of two given in Hale (2013b), pp. 137–139, 152–155. Although the present version omits much of the detail of its predecessors, I have tried to bring out more clearly what I think is right in what Parsons says and to separate it more cleanly from what I disagree with.
Or a collection of any other sort, such as a proper class. The assumption that ‘to quantify over certain objects is to presuppose that those objects constitute a “collection,” or a “completed collection”—some one thing of which those objects are the members’ is what Richard Cartwright calls the All-in-One Principle. See Cartwright (1994), sec.IV for some compelling arguments against it.
As Frege put it, in his review of Husserl’s Philosophy of Arithmetic vol. I, “It should be clear that someone who utters the proposition ‘All men are mortal’ does not want to state something about a certain chief Akpanya of whom he may never have heard” Frege (1984), p. 205. He makes the same point in his 1895 elucidation of Schröder’s lectures (Frege (1984), p. 227), and in his 1914 lectures on logic in mathematics (Frege (1969), p. 230; Frege (1979), p. 213). I am grateful to Ian Rumfitt for assisting my failing memory of these passages by supplying precise references. It appears that Akpanya actually existed, and that Frege knew of him. He was a chief in Togo, which became a German colony in 1884—‘to Frege’s joy’ according to Wolfgang Künne (2009).
I am, of course, assuming that impredicative specification is not to be ruled out on other grounds, such as vicious circularity. In the present disagreement, that assumption is common ground. However, as an anonymous reviewer observes, impredicative specification of properties may be thought especially problematic when properties are conceived, as on the abundant conception, as individuated by the satisfaction-conditions of possible predicates. More specifically, it may be feared that this will lead to situations in which the satisfaction-conditions for one first-level predicate, \(\phi \), depend upon or include those of another, \(\psi \), which in turn depend upon or include—with vicious circularity—those of \(\phi \)? This issue is difficult, and I cannot discuss it properly here. For reasons indicated above, p. 4.2, I think the circularity need not be vicious. It is not difficult to find examples where impredicative quantification over properties in the definition of further properties or relations need raise no such problem. Pertinent examples are the Fregean definitions of predecession by \(Pmn\leftrightarrow \exists F\exists x(Fx\wedge n=NuFu\wedge m=Nu(Fu\wedge u\ne x))\) and its ancestral by \(P^{*}mn\leftrightarrow \forall F((Fm\wedge \forall x\forall y(Fx\wedge Pxy\rightarrow Fy))\rightarrow Fn)\), which are unproblematic—at least provided that the bound property variables do not include within their range properties which can only be defined in terms of the predecession relation. A simpler example would be the definition of a property, \(\phi \), by \(\phi x\leftrightarrow \forall F(\forall y(Fy\rightarrow Gy)\rightarrow Gx)\)—that is, \(\phi \) holds of an object iff it possesses all those properties which suffice for being G—where the quantification over properties raises no special problem provided that G is not itself defined in terms of \(\phi \).
To be clear: I am not claiming that the deflationary conception of properties forces the adoption of fully impredicative comprehension, only that it does not preclude it.
In his very interesting paper in this volume, Roy Cook tends to give the impression that my deflationary conception of properties will not allow endorsement of fully impredicative comprehension, and recommends a weakening of what he takes to be my overly austere position, in the interests of achieving a version of second-order semantics which will support proof of some of the standard metalogical results which, he thinks, must fail on my approach (as I wrongly claimed—vide supra, p. 8, esp. fn. 13—in the earlier paper Cook is discussing). In particular, with the weakening he favours, one could prove the categoricity of arithmetic, and a weakened categoricity result for second-order analysis. In essence, the weakening consists in allowing expressions of countably infinite length, whose utterance or inscription would therefore require performance of a supertask.
Obviously a footnote is not the place for the substantial response which Cook’s paper merits. Here I can only observe, without argument, first, that, for reasons given here, I do not think my position precludes acceptance of fully impredicative comprehension; second, that while Cook seems to think that the key difference between us concerns the admission, or otherwise, of the logical possibility of supertasks being completed, it seems to me that this is incorrect—at at least one crucial point, his argument depends upon the assumption of arbitrary countably infinite sequences. This assumption remains problematic, even if one grants the logical possibility of completing a supertask. For these, and perhaps some other reasons, my admiration for Cook’s paper cannot be accompanied by agreement with it. This is, perhaps, an appropriate place to record my gratitude to him, for earlier and very helpful discussion of some of the ideas in this paper.
That \(\Pi _{1}^{1}\)-comprehension suffices is noted in Heck (2000) and Heck (2011), p. 270. For detailed results and proofs, see Linnebo (2004). The insufficiency of predicative comprehension is as one might expect, given that key definitions, such as the Fregean definition of predecession by \(Px,y=\exists F\exists z(y=NuFu\wedge Fz\wedge x=Nu(Fu\wedge u\ne z))\), require impredicative comprehension.
That is, comprehension restricted so that second-order quantification in the defining formula \(\phi \) may only take the form \(\forall F_{1}\ldots \forall F_{n}\phi ^{\prime }\) where \(\phi ^{\prime }\) has no bound second-order variables.
\(\phi ^{*}ab\) abbreviates \(*_{xy}(\phi xy)(a,b)\)—see Heck (2011), p. 275.
A more precise statement would involve taking arity into account, but such details need not distract us here.
In this respect, the situation may differ in an important way from understanding the first-order induction schema, \(\phi (0)\wedge \forall n(\phi (n)\rightarrow \phi (n+1)\rightarrow \forall n\phi (n)\), where—pending some specification of which properties the schematic \(\phi \) varies over—there is no definite domain for a bound second-order variable to range over, so that the schema cannot be properly regarded as equivalent to its second-order closure. But it seems to me that an alternative and perhaps more reasonable view would be that, in the absence of a definite specification, the schema makes no clear claim, but is effectively ambiguous between a range of alternative second-order closures which differ from one another over precisely what \(\phi \)’s range of variation is taken to be.
Where \(\phi _{x}(Fx,\xi )\) is some formula with just F and \(\xi \) free.
Heck (2011), pp. 294–295. I have reproduced Heck’s footnote 48 because he clearly thinks the point is telling. But I have to confess that it eludes me. He can scarcely mean to suggest that the putative arbitrary infinite subsets of an infinite first-order domain which we cannot define can be picked out demonstratively. But if all he means is that, in case of small finite subsets, we might pick them out by pointing (‘Those ones’, said while gesturing at a pile of planks, say), then even if we agree that these words together with the gesture don’t amount to a definition, there is no clear reason to think that the set of objects singled out is not definable.
See the final paragraph of Sect. 3, p. 7.
In addition to those whose help is explicitly acknowledged in earlier footnotes, I should like to thank Stewart Shapiro for some very helpful discussion and advice, and two anonymous reviewers whose perceptive and constructive suggestions have, I hope, helped me to make this a better paper than it would otherwise have been.
To be be clear on a point rightly emphasized by one reviewer, it has not been shown that second-order logic is incomplete or non-compact with respect to my semantics; my claim is only that the usual completness and compactness proofs fail, just as they do with respect to the standard semantics.
References
Couturat, L. (Ed.). (1961). Opuscules et fragments inédits de Leibniz. Hildesheim: Georg Olms Verlag.
Frege, G. (1969). Nachgelassene schriften. Hamburg: Felix Meiner Verlag.
Frege, G. (1979). Posthumous writings. Oxford: Basil Blackwell.
Frege, G. (1984). Collected papers on mathematics, logic, and philosophy. Oxford: Basil Blackwell.
Gerhardt, C. I. (Ed.). (1875–90). Die philosophisches Schriften von Gottfried Wilhelm Leibniz. Berlin: Weidmann.
Hale, B. (2013a). Necessary beings: An essay on ontology, modality, and the relations between them. Oxford: Oxford University Press.
Hale, B. (2013b). Properties and the interpretation of second-order logic. Philosophia Mathematica, 21(2), 133–156.
Heck, R. G, Jr. (2000). Cardinality, counting, and equinumerosity. Notre Dame Journal of Formal Logic, 41, 187–209.
Heck, R. G, Jr. (2011). Frege’s theorem. Oxford: Clarendon Press, Oxford.
Lewis, D. (1986). On the plurality of worlds. Oxford: Blackwell.
Linnebo, Ø. (2004). Predicative fragments of frege arithmetic. Bulletin of Symbolic Logic, 10(2), 153–174.
Myhill, J. (1952). A derivation of number theory from ancestral theory. Journal of Symbolic Logic, 17, 192–197.
Parkinson, G. H. R. (Ed.). (1966). Leibniz: Logical papers. Oxford: Clarendon Press, Oxford.
Parsons, C. (1965). Frege’s theory of number. In M. Black (Ed.), Philosophy in America (pp. 180–203). London: George Allen and Unwin.
Quine, W. V. (1970). Philosophy of logic. Englewood Cliffs: Prentice-Hall. (Foundations of philosophy series).
Rayo, A., & Yablo, S. (2001). Nominalism through de-nominalization. Noûs, 35, 74–92.
Stewart, S. (1991). Foundations without foundationalism. Oxford: Oxford University Press. (Number 17 in Oxford logic guides).
Shapiro, S. (2000). Frege meets dedekind: A neologicist treatment of real analysis. Notre Dame Journal of Formal Logic, 41(4), 335–364.
Cartwright, R. (1994). Speaking of everything. Noûs, 28(1), 1–20.
Wolfgang, K. (2009). Die philosophische logik gottlob freges. Frankfurt am Main: Klostermann. (RotReihe).
Wright, C. (2007). On quantifying into predicate position. In A. P. M. Leng & M. Potter (Eds.), Mathematical knowledge (pp. 150–174). Oxford: Oxford University Press.
Author information
Authors and Affiliations
Corresponding author
Appendix: categoricity, etc.
Appendix: categoricity, etc.
I claim in Sect. 2 that the usual proofs of categoricity results for second-order axiomatizations with respect to the standard semantics go through when my modest semantics is adopted, and that the proofs of completeness, etc., results for second-order logic which can be given with respect to the Henkin semantics and others essentially equivalent to it (q.v. Shapiro (1991), Chap. 4) fail with my semantics, just as they do with the standard semantics. I shall not here seek to provide a rigorous proof of this claim. Since the domains of the second-order variables are taken, in my proposed semantics, to comprise those properties and relations definable in the meta-language, this would, inter alia, require a much more careful specification of that language than I wish to undertake here. My aim instead is to support the claim by lightly sketching standard proofs in what I hope to be just enough detail to make clear that, and why, the categoricity proofs still go through when my modest semantics is adopted, while proofs of completeness, etc., still fail, as they do when the semantics is standard. The proofs sketched correspond to those given in detail in Shapiro (1991), Chap. 4.
1.1 Categoricity
For arithmetic, we assume a second-order axiomatization with the usual axioms for successor, addition, multiplication, and induction. The categoricity theorem asserts that any two models of these axioms, \(M_{1}=\langle d_{1},I_{1}\rangle \) and \(M_{2}=\langle d_{2},I_{2}\rangle \) are isomorphic. In essence, this is proved by defining a relation f on \(d_{1}\times d_{2}\), and proving that f is a one-one function from \(d_{1}\) onto \(d_{2}\), that f is structure preserving. A subset \(S\subseteq d_{1}\times d_{2}\) is closed under the successor relation (s-closed) iff \(\langle 0_{1},0_{2}\rangle \in S\) and \(\langle a,b\rangle \in S\rightarrow \langle s_{1}a,s_{2}b\rangle \in S\), where \(s_{i}\) is the successor function of \(M_{i}\). f is defined to be the intersection of all s-closed subsets of \(d_{1}\times d_{2}\). It is easily shown that f is non-empty and s-closed. To prove that f is a function from \(d_{1}\) to \(d_{2}\), two lemmas are needed: that every element of \(d_{1}\) bears f to some element of \(d_{2}\), and that f is many-one. The first lemma is proved by defining \(P=\{a\in d_{1}:\exists b\in d_{2}(\langle a,b\rangle \in f\})\) and proving that \(P=d_{1}\) and the second by defining \(P=\{a\in d_{1}:\exists !b\in d_{2}(\langle a,b\rangle \in f)\}\) and proving once again that \(P=d_{1}\). In both cases the proofs apply the axiom of induction with respect to P. This is legitimate when the semantics is standard, since then the bound second-order variable in the axiom is interpreted as ranging over the complete power set of the first-order domain. The proofs fail under the general Henkin semantics, since then the second-order domain may be any subset of the power set of the first-order domain, so there is no guarantee that the set P lies in the range of the bound second-order variable in the induction axiom. They fail when the axiomatization is only first-order, since then we have only an axiom scheme for induction, which can be applied only to subsets specifiable by a formula of the object-language, and clearly P is defined only in the metalanguage. However, precisely because P is so defined, the proofs still go through under my modest semantics, in which the relevant second-order domain comprises all the subsets of the first-order domain definable in the metalanguage. In a similar way, we can prove, using the fact that \(M_{2}\) satisfies the successor and induction axioms that f is 1–1 and onto \(d_{2}\), and, using the addition and multiplication axioms in \(M_{1},M_{2}\), that f preserves structure.
The situation with respect to real analysis is similar. In this case, the stumbling block for attempts to prove categoricity when the semantics is general Henkin or the axiomatization first-order is the need to appeal to the second-order completeness axiom, asserting that every bounded property (or set) of reals has a least upper bound. In case the semantics is general Henkin, or the axiomatization first-order, there is no guarantee that the relevant property (or set) of reals lies within the relevant second-order domain, or is covered by the first-order axiom scheme. This guaranteed when the semantics is standard, because all the second-order domain includes all properties (or subsets) of elements of the first-order domain. However it is also guaranteed when the semantics is modest, for the same reason as above.
1.2 Completeness, etc.
The proof that second-order logic is complete with respect to the Henkin semantics (or the essentially equivalent ‘first-order’ semantics—see Shapiro (1991), pp. 74–76) is a fairly straightforward extension of the usual completeness proof for first-order logic. That is, we show that any deductively consistent set of sentences has a denumerable model by expanding it to a maximally consistent set which includes ‘witnesses’ for each of the existentially quantified sentences of the language suitably enriched with denumerable many new constants, and then use these new constants to build a denumerable model. In the second-order case, the expansion of the language consists in adding denumerable sequences of n-place relation letters, and function symbols, as well as of individual constants. Starting with our given consistent set of sentences, we then construct an infinite sequence of sets of sentences, adding at each stage the sentences \(\exists x\Psi _{m}(x)\rightarrow \Psi _{m}(c_{i}),\exists X^{n}\chi _{m}(X^{n})\rightarrow \chi _{m}(C_{j}^{n}),\exists f^{p}\Phi _{m}(f^{p})\rightarrow \Phi _{m}(g_{k}^{p})\), where \(c_{i},C_{j}^{n},g_{k}^{p}\) are the first individual, n-ary relation and p-ary function constants not already used. It can be shown that the union of the sets in this sequence is consistent, and by Lindenbaum’s Lemma, it can be extended to a maximally consistent set. A model is then constructed, using the set of new individual constants itself as the first-order domain, and choosing the second-order domains so that one can prove that a sentence is true in this model iff it belongs to the expanded set. Since this latter includes the original set, it follows that the model is a model of that set also. The proof depends crucially on the fact that in the Henkin semantics, the choice of second-order domains is not fully determined by the choice of first-order domain—the domain over which the monadic second-order variables range, for example, can be any subset of the power set of the first-order domain.
To see this, suppose instead that the second-order domains are determined by the choice of first-order domain, as in the standard semantics, so that the domain for the second-order 1-place relation variables is the set of all subsets of the first-order domain. Let the assignments to individual constants, n-place relation letters, and function symbols be just as in the Henkin completeness proof, based on the denumerable set of new individual constants \(\{c_{0},c_{1},\ldots \}\) as the first-order domain. In particular, each new constant denotes itself, and each constant c already occurring in our original consistent set of sentences \(\Gamma \) denotes the first \(c_{i}\) such that \(c=c_{i}\) is in our maximally consistent expansion \(\Gamma ^{\prime }\) of that set; and each 1-place relation letter F is assigned the set of individual constants c such that Fc occurs in \(\Gamma ^{\prime }\); similarly for n-place relation-letters generally, and function-symbols. What needs to be proved, once the model M is defined, is that for any sentence \(\Phi \) of the extended language, \(M\models \Phi \) iff \(\Phi \in \Gamma ^{\prime }\). Proof is to be by induction on the complexity of \(\Phi \). A crucial case is when \(\Phi \) is, say, \(\forall XB(X)\) where B(X) is a formula with only X free. Since \(\Gamma ^{\prime }\) is maximal, it will contain \(B(\psi )\) or \(\lnot B(\psi )\) for each formula \(\psi \) of the language of \(\Gamma ^{\prime }\) with just one free individual variable. Suppose \(\Gamma ^{\prime }\) contains \(B(\psi )\) for every choice of \(\psi \), so that \(\forall XB(X)\) is in \(\Gamma ^{\prime }\). Do we have \(M\models \forall XB(X)\)? Well, clearly this is not guaranteed. Our assignments defining M will ensure that B(X) comes out true whenever X is assigned a subset of the first-order domain specified by a formula \(\psi \)of the object-language. But these do not exhaust the subsets of the first-order domain. Thus we have no guarantee that there are no subsets for which B(X) comes out false. In short, the completeness proof collapses when the standard semantics is employed, essentially because we no longer have the requisite freedom to restrict the choice of the second-order domains. And clearly, for essentially the same reason, it fails under my modest second-order semantics, in which the second-order domain must be chosen as the set of all and only the subsets of the first-order domain definable in the metalanguage—crucially, the relevant subsets need not all be definable in the object-language.
Given Henkin semantics, the proof of compactness is an easy consequence of completeness and soundness, as in the first-order case. Without completeness, the proof cannot be given.Footnote 36
That the Löwenheim–Skolem Theorems are not obtainable with the standard semantics follows, given the categoricty results for arithmetic and analysis. Likewise for my modest semantics.
Rights and permissions
About this article
Cite this article
Hale, B. Second-order logic: properties, semantics, and existential commitments. Synthese 196, 2643–2669 (2019). https://doi.org/10.1007/s11229-015-0764-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11229-015-0764-7