Note on Absolute Provability and Cantorian Comprehension Holger A. Leuz We will explicate Cantor's principle of set existence using the Gödelian intensional notion of absolute provability and John Burgess' plural logical concept of set formation. From this Cantorian Comprehension principle we will derive a conditional result about the question whether there are any absolutely unprovable mathematical truths. Finally, we will discuss the philosophical significance of the conditional result. 1. Absolute Provability Let us assume that there is a concept of absolute provability in mathematics, as opposed to provability construed as formal deducibility relative to a formal system. Let us also assume that absolute provability can be adequately formalized as a necessity operator attaching to mathematical statements and that this necessity operator obeys the logical laws of the system S4 of modal predicate logic (without validity of the Barcan formula). The concept was (first?) introduced by Kurt Gödel [1933] and discussed by him in Gödel [1946] and as reported by Hao Wang [1996: 187-188]. Some further philosophical issues surrounding the notion were recently discussed by Hannes Leitgeb [2009]. His article also contains an exposition of the naturally ensuing problem whether a certain proposition holds, which Leitgeb has dubbed the Holy Grail in the philosophy of mathematics, (HG). (HG) There exists a mathematical statement which is true and absolutely unprovable. Let us use the symbol "⊟" to denote absolute provability and stipulate that it is an S4 necessity operator. (This symbol stylizes Gödel's originally used symbol "B" [1933] into the 2 modal-logical box symbol; Gödel's later abbreviation "AP" in Wang [1996: 188] as well as "S4" can also be found in there.) Then we have a formal statement expressing (HG): (H) There exists an interpreted mathematical sentence A such that: A  ⊟A Note that because of the system-independent nature of absolute provability it is essential that A be interpreted, for a mere well-formed string of mathematical symbols might be provable under one interpretation and disprovable under another. 2. Cantorian Comprehension Georg Cantor communicated the following view about set existence in a letter to Dedekind: A multitude can be such that the assumption of a "being-together" of all its elements leads to a contradiction, so that it is impossible to conceive of the multitude as a unit, a "completed object". I call such multitudes absolutely infinite or inconsistent multitudes. [...] If, on the other hand, the whole of the elements of a multitude can be thought of as "being together" without contradiction, such that their collection into "one thing" is possible, I call it a consistent multitude or a "set". Cantor [1980: 443], translation by the present author. When Cantor wrote this in 1899, there were no alternative systems of axiomatic set theory known: Neither ZF and its extensions, nor set-class theories like Morse-Kelley, nor deviant systems like intuitionist set theory, AFA set theory, or NF(U). Furthermore, Cantor's writings strongly suggest that he was never very interested in logical formalizations and deductive systems. He had a clearly Platonist view of mathematical objects and thus he felt free to talk about them in a precise mathematical style, but without the use of, or any perception of a need for formal logical systems. Therefore it is plausible to interpret Cantor as talking about an absolute notion of logico-mathematical consequence, when he says "leads to a contradiction", 3 and not about a system-relative concept of formal deducibility. Absolute provability ⊟ then yields a plausible explication of what Cantor means by "A leads to a contradiction". It is "⊟(A)" or equivalently "⊟A". In order to formalize Cantor's view about set existence, let us call it "Cantorian Comprehension", we need a logically sound way of talking about set existence and set non-existence. It would be nice to avoid the use of empty set comprehension terms like "{x| x=x}". Cantor's official introduction of the concept of set [1980: 282] makes use of a plural variable "m" which denotes some multitude of objects from which a set M is formed. So Cantor's seminal definition of set strongly suggests treating his "multitudes" as pluralities in the sense of modern plural logic. If a definite plurality (or multitude) of mathematical objects mm is given, we express the statement that mm forms a definite set s by the formula mms, using John Burgess' notation [2004]. Now we can express Cantorian Comprehension as follows: (C) yy (⊟x yyx  x yyx) Here we assume pure set theory, i.e. singular quantifiers range over pure sets only, while plural quantifiers range over pluralities of pure sets only, including singleton pluralities and the empty plurality, following Burgess' convention [2004]. Let us assume that the connection between (C) and set comprehension based on monadic predicates, as in the ZF axiom of separation, for example, is given by the naïve comprehension schema of plural logic, i.e. for every predicate (x) there exists a plurality of exactly those objects satisfying the predicate. The converse of the universal conditional (C) is valid in quantified S4. So we get a proper biconditional existence criterion for sets from (C) and S4. As far as quantified modal logic is concerned, we need to assume that universal instantiation into the scope of modal operators is possible and that we can treat plural quantifiers in the same way as singular quantifiers in modal logic. 4 The use of absolute provability in (C) creates a difficulty. There may be sets which exist according to one axiomatic set theory but which do not according to another. The universal set {x| x=x} is an example: its existence is inconsistent in standard set theories but is provable in NF(U). Perhaps Burgess has given the best answer to this dilemma by proposing that Quine's systems NF and ML do not explicate Cantor's concept of set. See Burgess [2004: 203]. This view is further supported if the doctrine of limitation of size can be faithfully attributed to Cantor. For if there are multitudes which are too large to form a set, the multitude of all objects (including all sets) is certainly among them because there is no larger multitude. 3. Between (C) and (HG) Let us assume that (C) is false. Then yy (⊟x yyx  x yyx). Then there exists some plurality such that there exists an interpretation where "mm" is interpreted as denoting that plurality, such that "⊟x mmx  x mmx" is true under that interpretation. ("⊟" and "" are always given their intended interpretation.) So there exists an interpretation such that the sentence "x mmx" satisfies the schema A  ⊟A under that interpretation. Hence (H) is true. Let the propositional constant H abbreviate the statement (H). Insofar as our metatheoretic reasoning from the premise that (C) is false constitutes a proof, it follows that (H-C) ⊟(C  H) This is our conditional result: The falsity of Cantorian Comprehension implies the Holy Grail. 4. The value of bridge principles We could not determine the truth value of (HG) here. But bridge principles like (H-C) which connect the concept of absolute provability with genuinely mathematical content like (C) are useful if we want to find the truth value of the Holy Grail. Particularly because they connect 5 the S4-logic of absolute provability, which is not very strong and does not encode much information about the concept of absolute provability, with genuinely mathematical content. But then the question arises whether we can also settle the matter directly by pure logic. For example, consider the following rule of inference: (r) ⊟  /  ⊟ ( may be a singular or plural variable) The validity and non-validity of this rule each imply strong results. If (r) was not valid, (H) would follow directly from that, because there must be a counterexample to rule (r). That means there is some domain of quantification and some condition expressed by the open formula , such that it is provable that  holds of some object in the domain, but for all of them, ⊟ holds. So there is some (singular or plural) term  and some interpretation of it and the open formula  such that the sentence [] is true but absolutely unprovable. If the rule (r) was valid, we could apply it to quantification over interpretations, like the one we encounter in (H). Thus we could derive that ⊟H is inconsistent because, by (r), it implies that there is an interpretation such that for some thus interpreted sentence A: ⊟ (A  ⊟A). But ⊟ (A  ⊟A) is S4-inconsistent. Both arguments proceed without use of a logico-mathematical bridge principle like (H-C). Furthermore, a proof of the negation of (HG) by purely logical means was constructed by Horsten and Leitgeb [2009: 290-292]. The proof assumes only S4 as the logic of absolute provability, quantification over propositions, and propositional epsilon-terms governed the Hilbertian axiom schema (): p A(p)  A(pA(p)) (with p ranging over propositions). (HG) is formulated as p (p  ⊟p) and p (p  ⊟p) is the conclusion of the proof. Leitgeb does not think of the proof as conclusive because the assumed propositional epsilon-quantification might be deficient in intensional contexts. Also note that the Hilbertian epsilon-principle 6 licenses the inference (r'): ⊟p A(p) / ⊟A(pA(p)). This has almost the same effect as rule (r). From the provability of an existential statement p A(p) it is concluded that that we can choose an arbitrary object for which condition A provably holds. These attempts to determine the truth value of (H) by purely logical laws are subject to an epistemic difficulty. The validity of the supposed logical principles, rule (r) or axiom schema (), is just as elusive as the truth of (H) itself. The present author submits inference rule (r) is not intuitively plausible from the perspective of classical logic and mathematics. (Perhaps it is more plausible from a constructivist perspective.) Therefore, rule (r') is not plausible either, and, by contraposition, the axiom schema () is questionable, too. On the other hand, raw intuitions are certainly not sufficient to prove the non-validities of (r) and (), and thus we cannot derive (H) from raw intuitions about these non-validities. It seems we are in an epistemic vacuum. If, on the other hand, we found a correct disproof of (C), we would conclude that (r) and () are not valid. Given the elusiveness of these two logical principles, we would certainly not conclude that the disproof must contain some error, for (r) and () are unassailable. The reverse is the case because our understanding of concrete logical and mathematical proofs is more rigid than our grasp of the correct logic of absolute provability. Thus, questionable principles like (r) and () do not work very well as criteria for the truth value of (H) or the utility of (H-C). Rather, bridge principles like (H-C) can connect the thin logic of absolute provability with richer mathematical theories from which we can get more complex criteria for the validity of elusive logical laws like (r) and (). References Bueno, O., Linnebo, Ø. [2009]. New Waves in the Philosophy of Mathematics. Houndmills: Palgrave Macmillan. 7 Burgess, J. [2004]. E Pluribus Unum: Plural Logic and Set Theory. Philosophia Mathematica 12:193221. Cantor, G. [1980]. Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. Berlin: Springer. Gödel, K. [1933]. Eine Interpretation des intuitionistischen Aussagenkalküls. Ergebnisse eines mathematischen Kolloquiums 4: 39-40. Gödel, K. [1946]. The Princeton Lecture. In Gödel [1990]: 150-153. Gödel, K. [1990]. Collected Works vol.2. Oxford: Oxford University Press. Leitgeb, H. [2009]. On formal and informal provability. In Bueno, Linnebo [2009]: 263-299. Wang, H. [1996]. A Logical Journey: From Gödel to Philosophy. Cambridge, Mass.: MIT Press.