PREDICATIVISM AS A FORM OF POTENTIALISM

Abstract

In the literature, predicativism is connected not only with the Vicious Circle Principle but also with the idea that certain totalities are inherently potential. To explain the connection between these two aspects of predicativism, we explore some approaches to predicativity within the modal framework for potentiality developed in Linnebo (2013) and Linnebo and Shapiro (2019). This puts predicativism into a more general framework and helps to sharpen some of its key theses.

1 A question about two aspects of predicativism

It is a platitude that a definition must not be circular. A definition is said to be impredicative if it defines an entity by using quantifiers whose range includes the entity to be defined; otherwise, the definition is predicative. It is sometimes argued that impredicative definitions are circular because, by quantifying over the entity to be defined, they somehow presuppose this entity. Consider, for example, Russell’s [38, p. 237] Vicious Circle Principle:

No totality can contain members defined in terms of itself.

Or [39, p. 198]:

…whatever in any way concerns all or any or some of a class must not be itself one of the members of a class.

As is well known, Russell’s attempt to observe the Vicious Circle Principle resulted in the ramified hierarchy, which involves a notational nightmare that we hope to avoid.

In his classic “Systems of predicative analysis” [8, p. 2], Feferman highlights another aspect of predicativism, namely the view that some totalities are inherently potential:

$\dots $ we can never speak sensibly (in the predicative conception) of the “totality” of all sets as a “completed totality” but only as a potential totality whose full content is never fully grasped but only realized in stages.

As the context makes clear, the sets in question are sets of natural numbers. ¹

What is the connection between these two aspects of predicativism? That is, what is the connection between the Vicious Circle Principle and the thesis that there is no “completed totality” of all (predicatively defined) sets?

A similar question is prompted already by the work of Poincaré, the father of predicativism, who gives two prima facie different diagnoses of the logical and set-theoretic paradoxes. On the one hand, he blames the paradoxes on the use of viciously circular definitions (see, for example, [34, Section XI]). On the other hand, he also puts the blame on the Cantorian assumption that there are completed infinite collections: “There is no actual $($ given complete $)$ infinity. The Cantorians have forgotten that, and they have fallen into contradiction” (ibid.)

Our primary claim is that these two aspects of predicativism—the Vicious Circle Principle and the view of certain totalities as inherently potential—are closely related and reinforce each other. To demonstrate this, we develop a predicativist approach to arithmetic within a modal framework for potentiality from Linnebo [27] and Linnebo and Shapiro [30]. The resulting analysis of predicativism is also illuminating, we believe, because it places predicativism in a more general framework of potentiality, alongside other forms of potentialism. This allows us to sharpen some of the key theses of predicativism. In particular, we will be able to make good sense of Feferman’s more recent “semi-intuitionistic” approach to predicativity. ² Moreover, our analysis allows us to address, in a sharp manner, the charge that predicativism is unstable because the notion of predicative definability is not itself predicatively definable. We show the extent to which the various predicativist theses can be stated in a manner that is acceptable to the predicativist herself.

2 Our answer in a nutshell

Our answer to the important question of how the two aspects of predicativism are related can be found already in Poincaré’s later work on the topic. ³ As we have seen, he rejects the completed infinite. He insists instead on a potentialist conception:

when we speak of an infinite collection, we mean a collection to which we can add new elements unceasingly (similar to a subscription list which would never end, waiting for new subscribers). (Poincaré, [35], p. 463/47)

This much is similar to Aristotle’s conception of infinity as merely potential. But Poincaré goes on and asks us to consider attempts to “classify” the elements of one of these potentially infinite collections. In some cases, this poses no problems. For example, the classification as being among the first 1000 subscribers to a certain newspaper is undisturbed by later additions to the subscription list.

In other cases, however, “the principle of the classification rests on some relation of the elements to be classified with the entire collection” (ibid., pp. 46–47). An example is the classification as being the youngest subscriber to the newspaper. Although 10-year-old Billy may be thus classified today, tomorrow that honor may go to 9-year-old Sally, who may then just have started subscribing. From considerations like these, Poincaré concludes:

From this we draw a distinction between two types of classifications applicable to the elements of infinite collections: the predicative classifications, which cannot be disordered [bouleversé] by the introduction of new elements; the non predicative classifications in which the introduction of new elements necessitates constant modification (ibid., p. 47).

That is, a classification of the elements of a potentially infinite collection is deemed predicative or not in accordance with whether or not the classification can be “disordered” by later additions to the collection.

Now, the easiest and most natural way to ensure this kind of stability of a classification is to require that all of its quantifiers are restricted to elements of the potentially infinite collection that have already been introduced. For example, let some objects $aa$ be all the current subscribers to a newspaper. Then the classification as being the youngest subscriber among $aa$ is predicative in Poincaré’s sense of not being susceptible to being overturned as the collection of subscribers expands. ⁴ By restricting our attention to “old” elements of the collection, we ensure that the classification cannot be disrupted by any addition of “new” elements.

This brings us to the Vicious Circle Principle as a proposed requirement on permissible definitions. Consider the case of sets of natural numbers. Since (according to predicativists) there is no completed totality of such sets, this totality must be merely potential. In Poincaré’s words, it must be a collection “to which we can add new elements unceasingly.” Suppose now that we wish to use a formula $\varphi (n)$ to define a set $\{ n : \varphi (n)\}$ of natural numbers. For this definition to be permissible, we must ensure that it “cannot be disordered by the introduction of new elements” to the domain of sets of numbers. Suppose that all atomic formulas are unaffected by the introduction of new objects. Then the easiest and most natural way to ensure that our attempted definition of a set is stable is by requiring that all of its quantifiers be restricted to old objects, that is, to sets of natural numbers already introduced. For again, when a condition restricts its attention entirely to the old elements, it cannot be disordered by the introduction of any new ones. But to require that a definition of a new element of a collection restricts all its quantifiers to old elements of the collection is precisely to impose the Vicious Circle Principle.

To sum up, the two aspects of predicativism are connected as follows. The belief that certain domains are merely potential poses a threat to our attempts to define new elements of such domains: will our definitions be stable as more and more elements are added to the domain or might the definitions instead be “disordered” by such additions? A safe way to ensure the needed stability is to require that our definitions adhere to the Vicious Circle Principle. ⁵ Note, however, that on this analysis, the Vicious Circle Principle is merely a means to an end, namely definitional stability. The door is thus left open for other such means.

3 Potential totalities: a modal analysis

A lot of work is needed to get our Poincaré-inspired analysis out of its nutshell. The most pressing concern is to clarify what it is for a domain to be merely potential and how at least some ordinary mathematics can be understood as concerned with such domains. To keep the paper self-contained, this section provides a brief overview of the general framework for potentiality developed in Linnebo [27] and Linnebo and Shapiro [30]. Readers familiar with the framework can skip ahead to Section 4.

Beginning with Aristotle, and until the nineteenth century, the majority of major philosophers and mathematicians rejected the notion of the actual infinite—a complete, existing entity with infinitely many members. They argued that the only sensible notion is that of potential infinity.

In Physics 3.6 (206a27-29), Aristotle wrote, “For generally the infinite is as follows: there is always another and another to be taken. And the thing taken will always be finite, but always different.” As Sorabji [42, pp. 322–323] put it, for Aristotle, “infinity is an extended finitude”(see also [25, 26]). The idea seems to be that the infinite is tied to certain procedures that can be repeated indefinitely.

This orientation toward the infinite was endorsed by mainstream mathematicians as late as Gauss [19], who in 1831 wrote: “I protest against the use of infinite magnitude as something completed, which is never permissible in mathematics. Infinity is merely a way of speaking.”

A nice example is provided by Aristotle’s claim, against the ancient atomists, that matter is infinitely divisible. Consider a stick. However many times one has divided the stick, it is always possible to divide it again (or so it is assumed). It is natural to explicate this temporal vocabulary in a modal way. This yields the following analysis of the infinite divisibility of a stick s:

(1) $$ \begin{align} \Box \forall x (Pxs \to \Diamond \exists y \, Pyx), \end{align} $$

where $Pxy$ means that x is a proper part of y. If, by contrast, the divisions of the stick formed an actual infinity, the following would hold:

(2) $$ \begin{align} \forall x (Pxs \to \exists y \, Pyx). \end{align} $$

According to Aristotle, it is not even possible to complete infinitely many divisions of the stick, that is:

(3) $$ \begin{align} \neg \Diamond \forall x (Pxs \to \exists y \, Pyx). \end{align} $$

By endorsing both (1) and (3), one is asserting that the divisions of the stick are merely potentially infinite.

According to Aristotle, the sequence of natural numbers too is merely potentially infinite. We can represent this view as the conjunction of the following theses:

(4) $$ \begin{align} \Box \forall m \Diamond \exists n \, \mathrm{S}{\scriptstyle\mathrm{UCC}}(m,n), \\[-36pt]\nonumber\end{align} $$

(5) $$ \begin{align} \neg \Diamond \forall m \exists n \, \mathrm{S}{\scriptstyle\mathrm{UCC}}(m,n), \end{align} $$

where $\mathrm {S}{\scriptstyle \mathrm {UCC}}(m,n)$ states that n comes right after m. The modal language thus provides a nice way to distinguish the merely potential infinite from the actual infinite.

3.1 Three orientations toward the infinite

It is useful to distinguish orientations toward the infinite. Actualism unreservedly accepts actual infinities, and thus finds no use for modal notions in mathematics (or at least no use that is specific to the analysis of infinity). Actualists maintain that the non-modal language of ordinary mathematics is already fully explicit and thus deny that we need a translation into a modal language. Furthermore, actualists accept classical logic when reasoning about the infinite and typically also accept all of classical mathematics.

Potentialism stands opposed to actualism. According to this orientation, at least some of the objects with which mathematics is concerned are generated successively, and some of these generative processes cannot be completed. There is room for disagreement about which processes can be completed. An austere Aristotelian form of potentialism takes a very restrictive view, insisting that at any one stage, there are never more than finitely many such objects, but that we always (i.e., necessarily) have the ability to go on and generate more. ⁶ Generalized forms of potentialism take a more relaxed attitude. Potentialism about set theory provides an extreme example. According to this view, it is impossible to complete the process of forming sets from any objects that are available, but any generative process that is indexed by a set-theoretic ordinal can be completed. ⁷ As we shall see, Feferman himself falls in between the austere Aristotelian orientation and that of set-theoretic potentialism.

Potentialists can differ with respect to a qualitative matter as well. As characterized above, potentialism is the view that the objects with which mathematics is concerned are successively generated and that some of these generative processes cannot be completed. What about the truths of mathematics? As we see it, on any form of potentialism, these are modal truths concerned with certain generative processes. But how should these truths be understood?

Liberal potentialists regard the modal truths as unproblematic, adopting bivalence for the modal language. Consider Goldbach’s conjecture. As potentialists interpret it, the conjecture says that necessarily, any even number greater than 2 that is generated can be written as a sum of two primes. Liberal potentialists maintain that this modal statement has an unproblematic truth-value—it is either true or false. Their approach to modal theorizing in mathematics is thus much like a realist approach to modal theorizing in general: there are objective truths about the relevant modal aspects of reality, and this objectivity warrants the use of some classical form of modal logic.

Strict potentialists differ from their liberal cousins by requiring not only that every object be generated at some stage of a process, but also that every truth be “made true” at some stage. Consider, again, the Goldbach conjecture. If there are counterexamples to the conjecture, then its negation will presumably be “made true” at the stage where the first counterexample is generated. But suppose there are no counterexamples. Since the conjecture is concerned with all the natural numbers, it is far from obvious how it could be “made true” without completing the generation of natural numbers. But at least according to austere Aristotelian potentialism, there can be no such completion.

One response would be for strict potentialists to abandon any attempt at true universal generalizations over an incompletable domain. Indeed, the Vicious Circle Principle can be seen as an important step in that direction: at least when defining new members of an incompletable domain, we must refrain from quantifying over the entire domain and instead take care to restrict all quantifiers to the elements of the domain that have been generated. However, Linnebo and Shapiro [30] argues that strict potentialists have another, less restrictive option as well, namely to adopt a modal logic whose underlying logic is intuitionistic (or intermediate between classical and intuitionistic logic). In particular, strict potentialists should not accept every instance of the law of excluded middle in the background modal language. As we shall see toward the end of this paper, this dovetails with a view that Feferman and others adopt toward predicative mathematics, and it has ramifications for the articulation of predicativism and the extent of the mathematics that it captures.

3.2 The modal logic

Our next task is to identify the modal logic to be used in our modal explication of potential infinity. For the time being, we will be neutral on the liberal vs. strict divide and thus also on whether the non-modal part of the logic should be classical or intuitionistic.

It is often useful to invoke the contemporary heuristic of possible worlds, but we understand this as only heuristic, as a manner-of-speaking. Our official theory is formulated in the modal language, with (one or both of) the modal operators as primitive. The modal language is rock bottom, not defined in terms of anything else.

To invoke the heuristic, the idea is that a “possible world” has access to other possible worlds that contain objects that have been constructed or generated from those in the first world. From the perspective of the earlier world, the “new” objects in the second world exist only potentially. One sort of construction is geometric: the later world may contain, for example, a bisect of a line segment in the first. Or the later world might contain an extension of a line segment from the first world. Other sorts of constructions are arithmetic: the later world might contain more natural numbers than those of the first, say the successor of the largest natural number in the first world. Or, for a third kind of example, the later world may contain a set whose members are all the sets in the first world.

An Aristotelian assumes that every possible world is finite, in the sense that it contains only finitely many objects. This, of course, just is the rejection of the actually infinite. We make no such assumption here, however. Our goal is to contrast the actually infinite and the potentially infinite, so we need a framework where both can occur (to speak loosely). An actual infinity—or, to be precise, the possibility of an actual infinity—is realized at a possible world if it contains infinitely many objects. As will be shown, this is a fruitful background for Feferman’s articulation of predicativism.

We also assume that objects are not destroyed in the process of construction or generation. This is in keeping with most ordinary mathematical talk about construction. We construct new objects but never destroy old ones. Suppose, for example, that a given line segment is bisected. Then the resulting “world”contains the two bisects, as well as the original line segment.

To continue the heuristic, it follows from the foregoing that the domains of the possible worlds are non-decreasing along the accessibility relation. So we assume:

(6) $$ \begin{align} w_{1}\leq w_{2}\rightarrow D(w_{1})\subseteq D(w_{2}), \\[-15pt]\nonumber\end{align} $$

where ‘ $w_{1}\leq w_{2}$ ’ says that $w_{2}$ is accessible from $w_{1}$ , and for each world w, $D(w)$ is the domain of w. For present purposes, we can think of a possible world as determined completely by the mathematical objects—regions, numbers, sets, etc.—it contains. We will talk neutrally about the extra mathematical objects existing at a world $w_{2}$ but not at an “earlier”world $w_{1}$ which accesses $w_{2}$ , as having been “constructed” or “generated.”

This motivates the following principle:

Partial ordering: The accessibility relation $\leq $ is a partial order. That is, it is reflexive, transitive, and anti-symmetric.

So the underlying logic is at least S4.

As is well-known, the conditional (6) entails that the converse Barcan formula is valid. That is,

(CBF) $$ \begin{align} \exists x\Diamond\varphi(x)\rightarrow\Diamond\exists x\varphi(x). \\[-15pt]\nonumber\end{align} $$

At any stage in the process of construction, we generally have a choice of which objects to generate. For example, we might have, at some stage, two intervals that don’t yet have bisections. We can choose to bisect one or the other of them, or perhaps to bisect both simultaneously. Assume we are at a world $w_{0}$ where we can choose to generate objects, in different ways, so as to arrive at either $w_{1}$ or $w_{2}$ . It makes sense to require that the license to generate a mathematical object is never revoked as our domain expands. The option to bisect a given line segment, for example, can always be exercised at a later stage.

This corresponds to a requirement that any two worlds $w_{1}$ and $w_{2}$ accessible from a common world have a common extension $w_{3}$ . This is a directedness property known as convergence and formalized as follows:

$$\begin{align*}\forall w_0 \forall w_{1}\forall w_{2} (w_0 \leq w_1 \wedge w_0 \leq w_2 \to \exists w_{3}(w_{1}\leq w_{3}\,\wedge \,w_{2}\leq w_{3})). \\[-15pt]\end{align*}$$

We therefore adopt the following well-known principle:

Convergence: The accessibility relation $\leq $ is convergent.

This principle ensures that, whenever we have a choice of mathematical objects to generate, the order in which we choose to proceed is irrelevant. Whichever object(s) we choose to generate first, the other(s) can always be generated later. Unless $\leq $ is convergent, our choice whether to extend the ontology of $w_{0}$ to that of $w_{1}$ or that of $w_{2}$ might have an enduring effect.

The mentioned properties of the accessibility relation $\leq $ allow us to identify a modal logic appropriate for studying the generation of mathematical objects. The modal logic S4 is sound with respect to our intended system of possible worlds. As is well known, the convergence of $\leq $ ensures the soundness of a modal principle known as ‘G’ (or sometimes ‘.2’):

(G) $$ \begin{align} \Diamond\square \varphi \rightarrow\square\Diamond \varphi. \\[-15pt]\nonumber\end{align} $$

The modal propositional logic that results from adding this principle to a complete axiomatization of S4 is known as S4.2.

3.3 The logic of potential infinity

What is the correct logic when reasoning about potentially infinite collections? Informal glosses aside, the language of contemporary mathematics is strictly non-modal. We thus need a translation to serve as a bridge connecting the non-modal language in which mathematics is ordinarily formulated with the modal language in which our analysis of potential infinity is developed. Suppose we adopt a translation $\ast $ from a non-modal language $\mathcal {L}$ to a corresponding modal language $\mathcal {L}^\Diamond $ . The question of the right logic of potential infinity is the question of which entailment relations obtain in $\mathcal {L}$ .

To determine whether $\varphi _1, \ldots , \varphi _n$ entail $\psi $ , we need to (i) apply the translation and (ii) ask whether $\varphi ^\ast _1, \ldots , \varphi ^\ast _n$ entail $\psi ^\ast $ in the modal system. This means that the right logic of potential infinity depends on two factors. First, the logic depends on the bridge that we choose to connect the non-modal language of ordinary mathematics with the modal language in which our analysis of potential infinity is given. Second, the logic obviously depends on our modal analysis of potential infinity; in particular, on the modal logic that is used in this analysis—including the underlying logic of the modal language, whether it is classical or intuitionistic. The second factor has been investigated above. Let us now turn to the first factor.

At the heart of potentialism lies the idea that the existential quantifier of ordinary non-modal mathematics has an implicit modal aspect. When an Aristotelian says that a number has a successor, she really means that it potentially has a successor—that it is possible to generate a successor. This suggests that the right translation of $\exists $ is $\Diamond \exists $ . Since the universal quantifier can hardly be less inclusive in its range than the existential, this suggests that $\forall $ be translated as $\Box \forall $ . We are not, however, proposing these translations as a contribution to empirical semantics; rather, they are proposed as a useful rational reconstruction, which explicates an implicit potentialist conception of the language of mathematics. Note also that we treat the two quantifiers separately, since we consider both classical and intuitionistic backgrounds.

Thus understood, the quantifiers of ordinary non-modal mathematics are not restricted to objects that have been generated at a given stage. Rather, they are understood as devices for generalizing over all objects that can be generated. In our modal language, these generalizations are effected by the strings $\square \forall $ and $\Diamond \exists $ . Strictly speaking, these strings are composites of a modal operator and a quantifier. Invoking the heuristic of possible worlds, however, these strings behave like quantifiers ranging over all entities at all (future) worlds. We will therefore refer to the strings as modalized quantifiers.

The proposal is thus that each quantifier of the non-modal language is translated as the corresponding modalized quantifier. Each connective is translated as itself. Let us call this the potentialist translation, and let $\varphi ^\Diamond $ represent the translation of $\varphi $ . We say that a formula is fully modalized just in case all of its quantifiers are modalized. Clearly, the potentialist translation of any non-modal formula is fully modalized.

Say that a formula $\varphi $ is stable if the necessitations of the universal closures of the following two conditionals hold: ⁸

$$ \begin{align*} \varphi\rightarrow\square\varphi && \lnot\varphi\rightarrow\square\lnot\varphi. \end{align*} $$

Invoking the heuristic, a formula is stable just in case it never “changes its mind,”in the sense that, if the formula is true (or false) of certain objects at some world, it remains true (or false) of these objects at all “later” worlds as well.

We are now ready to state two key results, which answer the question about the correct logic of potential infinity. Let $\vdash $ be the relation of classical deducibility in a non-modal first-order language $\mathcal {L}$ . Let $\mathcal {L}^\Diamond $ be the corresponding modal language, and let $\vdash ^{\Diamond }$ be deducibility in this language by $\vdash $ , S4.2, and axioms asserting the stability of all atomic predicates of $\mathcal {L}$ .

Theorem 1 (Classical potentialist mirroring)

For any formulas $\varphi _{1}, \ldots ,\varphi _{n},\psi $ of $\mathcal {L}$ , we have:

$$\begin{align*}\varphi_{1},\ldots,\varphi_{n}\vdash\psi\quad\text{iff}\quad\varphi_{1}^{\Diamond },\ldots,\varphi_{n}^{\Diamond}\vdash^{\Diamond}\psi^{\Diamond}. \end{align*}$$

The proof goes by induction, on the complexity of the sentences in one direction and on the length of derivations in the other. A key lemma is that if $\varphi $ is in the range of the translation, then $\varphi $ , $\Diamond \varphi $ , and $\square \varphi $ are equivalent. ⁹

The theorem has a simple moral. Suppose we are interested in logical relations between formulas in the range of the potentialist translation, in a classical modal theory that includes S4.2 and the mentioned stability axioms. Then we may delete all the modal operators and proceed by the ordinary non-modal logic underlying $\vdash $ . This buttresses our choice of the potentialist translation as the bridge connecting actualist and potentialist theories. We will observe, as we go along, that the stability axioms on which the mirroring theorem relies are acceptable.

However, we will often use formulas outside of the range of the potentialist translation. Two examples are provided by the Aristotelian rejection of certain actual infinities, as expressed by (3) and (5). In this way, we use the extra expressive resources afforded by the modal language to engage in reasoning that cannot take place in the corresponding non-modal language, not even when all of its quantifiers are understood as implicitly modalized. The modal language thus allows us to look at the subject matter under a finer resolution, which the mirroring theorems enable us to turn on and off, according to our needs. In what follows, we will encounter many examples of reasoning that makes essential use of this finer resolution, but also ones where the finer resolution isn’t needed and can thus be turned off.

An important upshot of the theorem is that ordinary classical first-order logic is validated via this bridge. However, this response depends on the robustness of our grasp on the modality. We noted that our liberal potentialist accepts classical logic when it comes to the modality. Our first mirroring theorem fits in nicely with that perspective. As noted above, however, Linnebo and Shapiro [30] argue that a stricter form of potentialism pushes in the direction of intuitionistic logic. What to do then?

The answer is given by a second mirroring theorem, which we now explain. Say that a formula $\varphi $ is decidable in a given theory if the universal closure of $\varphi \vee \lnot \varphi $ is deducible in that theory. Let $\vdash _{\textrm {int}}$ be the relation of intuitionistic deducibility in a first-order language $\mathcal {L}$ , plus the decidability of all atomic formulas of $\mathcal {L}$ . Let $\vdash ^{\Diamond }_{\textrm {int}}$ be deducibility in the modal language corresponding to $\mathcal {L}$ , by $\vdash _{\textrm {int}}$ , S4.2, and the stability axioms for all atomic predicates of $\mathcal {L}$ .

Theorem 2 (Intuitionistic potentialist mirroring)

For any formulas $\varphi _{1}, \ldots ,\varphi _{n},\psi $ of $\mathcal {L}$ , we have: ¹⁰

$$\begin{align*}\varphi_{1},\ldots,\varphi_{n}\vdash_{{\rm int}} \psi\quad{\rm iff }\quad\varphi_{1} ^{\Diamond},\ldots,\varphi_{n}^{\Diamond}\vdash^{\Diamond}_{{\rm int}}\psi^{\Diamond}. \end{align*}$$

Together, the two mirroring theorems show how our analysis of quantification over a potentially infinite domain can be separated from the question of whether the appropriate logic is classical or intuitionistic. Hold fixed our modal analysis of potential infinity, the propositional modal logic S4.2, and the potentialist bridge. Then the appropriate logic of potential infinity depends entirely on the first-order logic used in the modal system. Whichever first-order logic we plug in on the modal end—classical or intuitionistic—we also get out on the non-modal end. Since liberal potentialists see no reason to plug in anything other than classical first-order logic, they can reasonably regard this as the correct logic for potential infinity.

4 Predicativism as a form of potentialism

Let us return to our contention that it is useful to understand predicativism as a form of potentialism. We start by explaining the predicativist conception of sets.

It is customary to distinguish between combinatorial and logical conceptions of sets (see, for example, [31]). According to combinatorial conceptions, a set is characterized by specifying each and every member, which can be chosen arbitrarily, not necessarily in accordance with any rule or principle. Here it is useful to invoke plural logic. A set can then be specified as $\{ xx\}$ for some suitable plurality $xx$ , which may be completely arbitrary. Thus, in any circumstance in which the set $\{ xx\}$ exists, its members will be precisely $xx$ . By contrast, on a logical conception, a class is characterized in terms of its membership criterion, say, as $\{ x : \varphi (x)\}$ for some suitable condition $\varphi (x)$ (which may contain parameters). Thus, in any circumstance in which the class $\{ x : \varphi (x)\}$ exists, its members will be precisely the objects satisfying the membership condition $\varphi (x)$ , which may change from circumstance to circumstance.

Predicativists are typically hostile to the combinatorial conceptions, preferring instead to develop a version of the logical conception. The reason for this preference should be clear. By rejecting the combinatorial conceptions, predicativists avoid any reliance on the idea of completing an infinite specification of its members, one by one, and can thus endorse a more thoroughgoing potentialism. This line of reasoning is nicely illustrated by the following passage by Weyl:

The notion of an infinite set as a “gathering” brought together by infinitely many individual arbitrary acts of selection, assembled and surveyed as a whole by consciousness, is nonsensical: “inexhaustibility” is essential to the infinite. [45, p. 23]

How, then, should predicativists develop the logical conception? Suppose they wish to use a formula $\varphi (x)$ to define a set X. ¹¹ In an ordinary non-modal context, this would require:

(7) $$ \begin{align} \forall x (x \in X \leftrightarrow \varphi(x)). \end{align} $$

But we are currently dealing with a domain of sets that is merely potential. We are explicating this potentiality by means of modal logic. Our explication applies the potentialist translation $\psi \mapsto \psi ^\Diamond $ to every formula of the ordinary non-modal language. Thus, instead of requiring (7), we need to consider the strong requirement that a formula necessarily defines a set: ¹²

(8) $$ \begin{align} \Box \forall x(x \in X\leftrightarrow\varphi(x)). \end{align} $$

Our aim is therefore encapsulated by the following set comprehension principle:

(S-Comp) $$ \begin{align} \Diamond\exists X \Box \forall x(x \in X\leftrightarrow\varphi(x)). \end{align} $$

For which formulas $\varphi (x)$ is this principle acceptable?

As a preliminary observation, we claim that membership has to be stable:

$$ \begin{align*} x \in X \rightarrow\square (x \in X) &&& x \not\in X \rightarrow\square x \not\in X. \end{align*} $$

We impose this requirement for two reasons. First, this coheres well with our ordinary way of thinking about sets. Once a set is formed, it never “changes its mind” about whether an object that was available at the stage of formation is or is not a member of the set. Second, and more importantly, the assumption of stability of membership is needed for the mirroring theorems to be available, which in turn is responsible for connecting our modal analysis of potentiality with the non-modal language of ordinary mathematics.

Suppose, therefore, that we require membership to be stable. This requirement entails that the defining condition $\varphi (x)$ too has to be stable:

$$ \begin{align*} \varphi(x) \rightarrow\square\varphi(x) &&& \lnot\varphi(x) \rightarrow\square\lnot\varphi(x). \end{align*} $$

To see this, recall that the condition $\varphi (x)$ must necessarily define the set X, as expressed by (8). Thus, if the set X cannot “change its mind” about whether or not an object x is a member, then nor can the condition $\varphi (x)$ “change its mind” about whether or not it applies to x. We therefore conclude that for (S-Comp) to be permissible, the condition $\varphi (x)$ needs to be stable. This yields an important necessary condition for permissibility. We will later articulate sufficient conditions as well.

Notice that our necessary condition echoes Poincaré’s emphasis on the importance of ensuring that all definitions of mathematical objects be stable whenever we reason about a domain that is merely potential. Although Poincaré never developed a modal analysis, at least not explicitly, he anticipated one of its key conclusions.

An obvious choice that confronts any account of sets, whether predicativist or not, concerns what objects are eligible to be elements of the sets. A simple option, which will be our main theme here, is to restrict our attention to sets of natural numbers. It will then be natural to adopt a two-sorted formalism with distinct variables for numbers and for sets thereof. More generally, a two-sorted formalism will be appropriate for any approach on which sets are not themselves eligible to be elements of sets. ¹³

How should the predicativist approach to sets be developed? We will now identify four such choices, which give rise to different varieties of predicativism. As we will see, our modal analysis sheds new light on these choices.

First, what is the starting point for the generation of sets? With our modal analysis, and engaging our heuristic of possible worlds, the question concerns the choice of a “base world,” whose ontology can then be extended in various ways, as represented by all the other possible worlds. According to what we will call absolute predicativity, the base world is empty, with the result that the entire ontology must be generated. ¹⁴ More familiar is relative predicativity, which proceeds from a non-empty base world. Indeed, the most widely studied form of predicativity—which will also be our focus here—is predicativity relative to the natural numbers. ¹⁵ Here the base world consists of all the natural numbers.

Second, are sets allowed to “grow” as the generation of the merely potential domain unfolds? As argued above, every set must be stable, in the sense that it cannot “change its mind” about whether an object is or is not an element of the set. But this requirement applies only to objects that have been generated; it leaves open the possibility that as further objects are generated, some of these will “become” elements of the set. To illustrate, consider sets of natural numbers. Suppose that natural numbers too are successively generated, as an Aristotelian would have it. Consider the formulas ‘ $n=n$ ’ and ‘n is prime’, which seem entirely predicative. If these formulas are allowed to define sets, then the resulting sets would “grow” as new numbers are generated. Let us say that a set is rigid if it cannot exhibit this kind of growth. While the requirement that sets be stable is obligatory, predicativists have a choice whether or not to require additionally that sets be rigid. ¹⁶ Notice, however, that the choice evaporates when the domain from which the elements are drawn is fixed: for stability applied to a fixed domain implies rigidity.

The two remaining choices are more general and arise for any form of potentialism (cf. Section 3.1). The third choice concerns how thoroughgoing the potentialism is. What kinds of collections can be completed, so as to “fit into” a single possible world (which need not, of course, be the base world)? As observed, an austere Aristotelian potentialist insists that no infinite collection can be completed. At the opposite end of the scale we find a relaxed set-theoretic potentialist, who allows any set to be completed, including very large transfinite sets, but insists that the totality of sets be regarded as merely potential. (Indeed, on pain of contradiction, our set-theoretic theorist must insist on this, since they hold that any given objects $xx$ potentially define a set $\{xx\}$ .)

Predicativism naturally suggests an intermediate option: while the collection of natural numbers can be completed, the collection of sets of natural numbers cannot. This view is particularly natural in connection with predicativity relative to the natural numbers, which regards the collection of natural numbers as completed already in the base world, while sets of natural numbers are generated without end and thus belong to an incompletable totality. ¹⁷ However, predicativism is interesting also in connection with the two extreme options. Aristotelian potentialists will, for example, have good reason to explore non-rigid (i.e., “growing”) sets of numbers. Moreover, set-theoretic potentialists have the interesting option of combining a combinatorial conception of sets with a logical conception of predicative classes. Since the elements of these classes are drawn from a “growing” domain of sets, we will once again have good reason to allow the classes to be non-rigid.

Finally, there is the choice between liberal and strict potentialism. Is it sufficient to require that every object be generated at some stage of a process (as the liberals think), or should we additionally require that every truth be “made true” at some stage (as strict potentialists require)? We observed that the Vicious Circle Principle involves a step in the strict direction. When a definition of a new object is only allowed to quantify over old objects available at the stage where the definition is made, then at least any atomic statement about the new object will be “made true” by that stage. For example, suppose all the natural numbers are available in the base world and that a set Y of numbers is defined by a formula $\varphi (x)$ whose second-order quantifiers are restricted to some sets $XX$ . Then the truth-value of any membership statement $n \in Y$ will be determined by how things stand with the numbers and the given sets $XX$ .

As mentioned, there is also a more radical explication of strict potentialism based on the idea of letting the modal logic be intuitionistic (or semi-intuitionistic) rather than classical. We will have an occasion to consider this more radical explication toward the end of the paper, where we argue that this is in some respects superior to the classical rivals. For the time being, however, we will focus on systems using classical logic, as is fairly standard in discussions of predicativism.

To sum up: as advertised in the introduction, our modal analysis explicates predicativism as a form of potentialism and locates it in a general framework for potentiality, alongside other forms of potentialism. We find this explication illuminating, both in its own right and because of the light that it shines on the different varieties of predicativism.

5 Some remarks on absolute predicativity

Absolute predicativity, in our sense, lets the base world be empty and thus requires that all objects be successively generated. Since it is helpful to work with a specific example, let us consider the case of the natural numbers and sets thereof.

Suppose we stipulate that any definition of a set is only allowed to quantify over objects available at the relevant stage. Of course, it is commonplace for predicativists to prohibit quantification over sets other than those that have already been generated. But we are now taking a potentialist view of the natural numbers as well. So the mentioned requirement gives rise to an addition prohibition, namely against quantifying over numbers other than those that have already been generated. This additional prohibition is stricter than anything we find in, for example, Poincaré, Weyl and Feferman. In practice, the additional prohibition means that only bounded arithmetical formulas (possibly with set parameters) are allowed to define sets. A related approach has been developed and explored by Nelson [32]. It results in a weak form of second-order arithmetic in the vicinity of the system known as I $\Delta _0$ . ¹⁸

Perhaps it is overkill, however, to require that all quantifiers occurring in a definition of a set be restricted to objects already generated. As our analysis in the previous section suggested, predicativity, at least as understood by Poincaré, is first and foremost a matter of definitional stability. By restricting all the quantifiers, even the arithmetical ones, we certainly ensure definitional stability. But perhaps there are other, less draconian ways to achieve the same result. We will now illustrate one way to develop this intriguing line of thought.

Consider liberal potentialist about the natural numbers, who take there to be robust facts about the non-actualized possibilities for generating natural numbers. Liberal potentialists are therefore prepared to engage freely in classical modal reasoning about such possibilities. Let $\varphi (x)$ be a formula of first-order arithmetic, and let $\varphi ^\Diamond (x)$ be its potentialist translation. As is easily seen, this modal formula is guaranteed to be stable [27, Lemma 5.3]. Thus, as far as stability is concerned, absolute predicativists who are also liberal potentialists about the natural numbers can accept precisely as much set comprehension as can relative potentialists who accept a completed totality of natural numbers already in the base world. The only difference is that the former theorists construe this as set comprehension on a fully modalized formula $\varphi ^\Diamond (x)$ , typically resulting in a non-rigid set of numbers, whereas the latter theorists construe this as comprehension on a non-modal formula $\varphi (x)$ applied to a fixed domain of numbers, thus resulting in a rigid set. But in light of the classical mirroring theorem (Theorem 1), these two groups of theorists agree on everything expressed in the non-modal language of ordinary mathematics; the only difference is that the former theorists insist on this language being implicitly modal, whereas the latter theorists take the language at face value.

The upshot, then, is this. Consider our running example predicative sets of natural numbers. Suppose we regard predicativity as first and foremost a matter of definitional stability, rather than a doctrinal adherence to the Vicious Circle Principle. Then it makes no difference in the ordinary language of non-modal second-order arithmetic whether one is an actualist or a liberal potentialist about the natural numbers.

As Crosilla and Linnebo argue in [4], this analysis provides an answer to a puzzle about what it means to be a predicativist relative to the natural numbers. Two of the historically most important advocates of this view, Weyl and Feferman, both use classical (non-modal) first-order arithmetic and then introduce predicative sets of numbers on top of that. But they advocate very different views of the natural numbers. As we have seen, Weyl insists that all infinities are merely potential, including the infinity of the natural numbers. By contrast, Feferman [10, p. 619] characterizes the natural numbers as a “completed totality.” How can they disagree so fundamentally about the ontological status of the natural numbers while agreeing on the logical and mathematical explication of predicativism relative to the natural numbers? The answer, Crosilla and Linnebo argue, is that Weyl [45] is a liberal potentialist about the natural numbers, whereas Feferman is an actualist—of course, both are potentialists about sets of natural numbers. As we have seen, this philosophical difference has no effect on the resulting theory in the non-modal language of ordinary mathematics.

6 The basics of relative predicativity

Our focus in what follows is on predicativity relative to the natural numbers. As just observed, there are two options. Following Feferman, we may regard the natural numbers as a given completed infinity, not constructed in stages. Alternatively, but equivalently for purely mathematical purposes, we may take a liberal potentialist view of the natural numbers. We will here adopt Feferman’s option, since this is technically simpler and thus affords a better focus on what is now our primary concern, namely how sets of natural numbers are generated in stages in a way that can never be completed.

To engage our heuristic, we therefore assume that all of the natural numbers exist in each world. Each such world can be regarded as a Henkin model, with the (standard) natural numbers as the range of the first-order variables. The second-order variables range over sets of natural numbers, those sets that exist at that world. So, the domain of sets of natural numbers grows along the accessibility relation (although, again, the first-order domain, consisting of the natural numbers, does not). ¹⁹ We can also think of the background as a two-sorted first-order language and will sometimes do so without further comment.

There are three major phases to the development of a predicativist theory of sets of natural numbers. The first phase is where we think of a set of natural numbers as definable, in a given “world,” in terms of what other sets exist at that world. The defined set exists in some later, accessible world.

The second phase is where one starts with a given world w and talks about all of the sets that are definable in w. That is, we envision another world $w^{\prime }$ that has all of the sets definable in terms of those that exist in w. We then envision a third world $w"$ that contains all of the sets definable in $w'$ . Clearly, this iterates: the second-phase procedure results in an $\omega $ -sequence of worlds.

Finally, we wish to iterate applications of the second phase into the transfinite. This is the most challenging aspect of our project. If we try to iterate the procedure through all ordinals (or all countable ordinals, or all recursive ordinals), we will end up with something more like (a part of) Gödel’s constructible hierarchy, and not a predicativist framework. The underlying predicativist theme is that if, in a given world, we can prove (predicatively) that a certain relation is a (countable) well-ordering, then we can iterate the construction through the corresponding ordinal (taking unions at limit stages).

An (alleged) conceptual instability of predicativism comes to the fore in this last phase, since it does not seem possible to give a predicatively acceptable account of a predicatively acceptable proof, or a predicatively acceptable well-ordering, or, indeed, of a well-ordering. Stay tuned.

7 Phase 1

This phase has its own challenges. Here is a first attempt at the relevant modal comprehension principle. It is a scheme:

(First Shot) $$ \begin{align} \square\forall \vec{y}\forall \vec{Y} \Diamond\exists X \Box \forall x(x \in X\leftrightarrow\varphi(x,\vec{y},\vec{Y})), \end{align} $$

one instance for each formula $\varphi $ that does not have X free. It is also important that the embedded formula $\varphi $ does not contain any modal operators. The idea is that at a given world w, we can define sets (of numbers) with reference to what exists at w (including which sets exist at w), but not with reference to what will be generated later.

This proposal faces two problems. First, as we observed, the comprehension condition $\varphi (x)$ needs to be stable, which isn’t guaranteed on (First Shot). The second problem is more subtle. Start at a given world w. The $\Diamond $ -operator takes us to an accessible world, say $w^{\prime }$ . The embedded formula—the instance of comprehension—is then evaluated at $w^{\prime }$ , not at w, as intended. That is, the second-order existential quantifier $\exists X$ in (First Shot) ranges over the sets that exist at $w^{\prime }$ . So we define a set X by reference to a formula $\varphi $ that may contain quantifiers whose range includes that very set X. So (First Shot) is impredicative! To solve the second problem, it is not sufficient to talk about a set existing in an accessible $w^{\prime }$ world: we also need the ability to talk, in that world (so to speak), about what exists only in the opening world w.

One option is to introduce one of the “backward looking” operators proposed (in a different context) by some philosophers (Fine [18] and Williamson [47]). We would like to avoid this conceptual and logical complication and stick to resources of standard modal logic. Another option is to introduce terminology for the levels in the ramified hierarchy. A standard way to do that is to attach a superscript to the set variables, to indicate their level. The comprehension principle would be something like this:

(RF) $$ \begin{align} \forall \vec{y} \forall \vec{Y}\exists X^n \Box \forall x(x \in X^n\leftrightarrow\varphi(x,\vec{y},\vec{Y})), \end{align} $$

one instance for each formula $\varphi $ that has no bound second-order variables of level n or higher, and no free second-order variables of level higher than n. This, of course, is the route of ramified type theory, dispensing with the modality altogether. As is familiar, it gets messy.

We submit that a better way to solve both of the mentioned problems is to invoke the resources of plural logic, applied to sets of numbers. These resources can either be adopted as a new primitive—which we will do at the outset, for ease of exposition—or else be “coded” by a clever use of sets. The latter option—developed in the next section—is obviously more economical and will eventually be our preferred choice.

We introduce a new style of variable $X\!X$ , $Y\!Y$ , …, for plural reference to sets, and a relation $X \prec X\!X$ , which is read “X is one of $X\!X$ .” ²⁰ And we take $X\!X \preccurlyeq Y\!Y$ (to be read as “ $X\!X$ are among $Y\!Y$ ”) as an abbreviation of $\forall X(X \prec X\!X \rightarrow X \prec Y\!Y)$ . Continuing the heuristic, we follow [27, 30] in taking pluralities to be rigid, in the sense that some given sets $X\!X$ comprise the very same sets in every world in which they exist. Consequently, the atomic formula $X \prec X\!X$ is rigid (and thus a fortiori stable). So this use of plural logic has some of the effect of a “backward looking” modal operator.

Of course, we do not want any impredicative comprehension principles for the plural variables. All we seem to need, for now, is the existence, in each world, of a “universal” plurality, one that “contains” every set in that world: ²¹

(Univ) $$ \begin{align} \square \exists X\!X\forall X( X \prec X\!X). \end{align} $$

In words: necessarily there are some sets such that every set is one of them. Notice, incidentally, how this formula makes essential use of the “finer resolution” afforded by our modal framework (cf. Section 3.3). For this formula is not the potentialist translation of any non-modal formula.

We now come to the heart of our proposal. Let $\varphi $ be a formula that does not contain the plural variable $X\!X$ . Let $\varphi ^{<X\!X}$ be the result of relativizing all second-order quantifiers to $X\!X$ . That is, replace each occurrence of the form $\forall X \dots $ or $\exists X \dots $ with $\forall X(X \prec X\!X \rightarrow \dots $ ) or $\exists X(X \prec X\!X \wedge \dots )$ , respectively. Every formula that is relativized in this way is stable, in the usual sense that it never “changes its mind” about whether or not it applies to some numbers as the domain of sets expands. The reason for this stability is that every set quantifier is relativized to a rigid plurality of sets, which ensures that its range is unaffected by the domain expansions. ²² We therefore adopt the following Phase 1 principle:

(P1) $$ \begin{align} \square \forall \vec{y} \forall \vec{Y} \forall X\!X [ \Diamond \exists Z \Box\forall x (x \in Z \leftrightarrow \varphi^{<X\!X}(x,\vec{y},\vec{Y}))], \end{align} $$

one instance for each formula $\varphi $ that does not contain $X\!X$ . In words, (P1) says that, necessarily (i.e., in any world w), for any $X\!X$ ’s (in w), there could be a set of numbers Z whose members are all and only the numbers that are $\varphi $ at w.

In fact, every set generated by (P1) is not only stable but also rigid, in the sense that it has the same members at all worlds at which it exists. To verify this, observe first that there is a formula of the form $\varphi ^{<X\!X}$ which necessarily characterizes membership in the set. Next, since this formula is stable and applied to a fixed domain, it is also rigid. Putting things together, it follows that membership in the set too is rigid. Notice that this result relies essentially on our assumption that the natural numbers form an actual or completed infinity, available at each possible world. Without this assumption, membership in a set would be stable but not rigid; for example, the set of even numbers (which is obviously arithmetically definable) would acquire a new member whenever a new even number is generated.

We submit that (P1) gives us what we want. It asserts the possible existence of a set that is definable (via $\varphi $ ) from the sets that exist in a given world. So we see that, if the predicativist accepts the modal framework, then at least this principle can be formulated in an acceptable manner.

8 Eliminating pluralities in favor of sets

As advertised, it is possible to eliminate pluralities of sets in favor of just sets. To do so, we use a pairing operation $\langle x, y \rangle $ on natural numbers. When we work over arithmetic, this operation is arithmetically definable, say, by letting $2^x \cdot 3^y$ represent $\langle x, y \rangle $ . Upper-case variables can thus be used to code sets of ordered pairs as well as sets of numbers. And, of course, the pairing function enables us to handle n-tuples as well, for arbitrary finite n.

If X is a set of numbers and n is a number, we define the n-section of X, denoted $X_n$ , as $\{x|\langle n,x \rangle \in X\}$ . This definition enables us to use a single set to represent any countable plurality of sets. To see this, consider any countable plurality of sets, say, the $X_n$ ’s for n any natural number. This plurality can be represented by the single set X whose n-section, for each n, is precisely $X_n$ .

Of course, the big question is whether this strategy for representing pluralities of sets suffices for our purposes. We contend that it does. Notice, first, that our construction of sets can be carried so as to ensure that, at every world, there is a single set whose sections represent all of the other sets at that world: ²³

(9) $$ \begin{align} \Box \exists X \forall Y (Y \neq X \to \exists n (Y=X_n)). \end{align} $$

If true, this contention means that every world contains at most a countable infinity of sets, which can be specified as a single set X and all of its sections $X_n$ .

To defend our contention, the key is to observe that, whenever new sets are generated and added to the domain to obtain a more populous possible world, this extension is systematic in a way that enables us to represent all of the sets then available by means of a single set—provided that all of the sets previously available could be so represented. This holds for our principle (P1), as well as the relevant principles from Phase 2 and Phase 3, to be introduced below. Each new set is always defined by a specific formula. Since these are the only ways to add new sets, we know that our strategy for representing sets will always suffice.

Instead of relativizing a formula to an arbitrary plurality of sets, we can relativize it to the plurality of sets represented by a single set. Let $\varphi $ be a formula without any occurrences of ‘X’. We wish to let $\varphi ^{<X}$ be the result of restricting the set-quantifiers in $\varphi $ to the sets represented by X via its sections. We achieve this by translating $\forall Y \psi (Y)$ as

$$ \begin{align*} \forall Y \forall z (Y=X_z \rightarrow \psi^{<X}(Y)), \end{align*} $$

where z is a new first-order variable, and by translating $\exists Y \, \psi (Y)$ in the obvious dual manner: ²⁴

$$ \begin{align*} \exists Y \exists z (Y=X_z \wedge \psi^{<X}(Y)). \end{align*} $$

We are now ready to formulate a purely set-theoretic formulation of our Phase 1 principle, namely:

(P1′) $$ \begin{align} \square \forall \vec{y} \forall \vec{Y} \forall X \, \Diamond \exists Z \Box\forall x (x \in Z \leftrightarrow \varphi^{<X}(x,\vec{y},\vec{Y})), \end{align} $$

one instance for each formula $\varphi $ that does not contain X. Notice that all the formulas we here use to define sets are stable, as required (cf. Section 4). Since sets are rigid, so are their sections. So restricting a formula to the sections of a set has the same effect as restricting it to a plurality. In particular, $\varphi ^{<X}$ is stable, since its first-order variables range over the natural numbers, which exist at all worlds, and its second-order variables are restricted to sets that exist in all accessible worlds.

Before proceeding to our purely set-theoretic treatment of Phases 2 and 3 of predicativity relative to the natural numbers, we wish to make some remarks about the predicativist understanding of Cantor’s theorem. From a classical point of view, the theorem is taken to show that the natural numbers are outnumbered by the sets of natural numbers: while there are only countably many such numbers, there are uncountably many such sets. As we will now see, although predicativists too can prove the theorem, they draw a rather different lesson from it, namely that the domain of sets is incapable of enumeration and “inherently potential” (as Feferman put it in the quote with which we began). ²⁵

Let us run through the reasoning behind Cantor’s theorem. Suppose for reductio that there is an enumeration of all of the sets of natural numbers. That is, there is a surjective function f from the natural numbers to the sets of natural numbers. As usual, we define a diagonal set $\Delta $ by means of the formula ‘ $n \not \in f(n)$ ’. It follows that $\Delta $ cannot be a member of the enumeration effected by f. Since the formula ‘ $n \not \in f(n)$ ’ is entirely predicative, predicativists too can conclude that there cannot be an enumeration of all the sets of natural numbers.

Let us make this reasoning fully explicit. First, we add the function symbol ‘f’ to our object language. It is natural also to add an axiom stating that for every set X, there is a function f that takes n to $X_n$ . Second, we need to spell out the implicit modality. When we assume that f is surjective, we assume that every possible set is in its image:

$$ \begin{align*} \Box \forall X \exists n (f(n) = X). \end{align*} $$

We then invoke the fact that it is possible to use the formula ‘ $n \not \in f(n)$ ’, which has no second-order quantifiers, to define a set:

$$ \begin{align*} \Diamond \exists Y \forall n (n \in Y \leftrightarrow n \not\in f(n)). \end{align*} $$

By a modal variant of the standard Cantorian reasoning, we thus prove that there can be no function from the natural numbers onto all possible sets of such numbers. In short, the merely potential domain of all possible sets of numbers cannot be enumerated.

This object language statement must of course not be conflated with the metalinguistic claim that in any Kripke model of our theory, the possible sets of numbers cannot be enumerated. From the point of view of classical mathematics, that claim is false, since our theory has Kripke models with countably many worlds each of which has countably many sets. Thus, again using classical mathematics, there is an enumeration f of all the possible sets. The apparent conflict is removed by observing that this enumeration f is not predicatively acceptable; in particular, its existence cannot be established by the axiom mentioned above.

Let us return to the object language. We have shown that it is impossible to enumerate all possible sets of natural numbers. What is possible, however, is to enumerate all the sets that are available at some given world. To prove this, we first use (9) to find a single set X such that all the sets (at the given world) are X and its sections $X_n$ . Next, using (P1′), it is possible to define a set Y such that $Y_0 = X$ and $Y_{i+i} = X_i$ for each i. We can thus obtain a single set Y that enumerates all the sets that are available at the given world, as desired. As usual, the talk about worlds is merely an eliminable heuristic. Our result can be stated in a purely modal language. If we retain plurals, the result admits of a particularly nice statement:

Necessarily, given any sets $XX$ , possibly there exists a single set Y whose sections are precisely $XX$ .

Or, even more compactly:

Necessarily, any given sets are possibly enumerated.

Even without plurals, the result can be expressed purely modally, albeit somewhat more long-winded, given (9):

Necessarily for every X, if every set is either identical with X or one of X’s sections, then possibly there exists a single set Y whose sections are precisely X and each of X’s sections.

Let us take stock. We have shown, first, that it is impossible to enumerate all possible sets of numbers, and second, that it is possible to enumerate any given such sets.

To complete our account, it remains only to connect these two claims and draw the conclusion that all possible sets of numbers cannot be simultaneously given. That is, given any sets of numbers, it is possible for there to be yet more such sets:

(10) $$ \begin{align} \Box \forall XX \Diamond \exists Y (Y \not\prec XX). \end{align} $$

We find this plural statement a particularly attractive way to express Feferman’s claim that the domain of sets of natural numbers is incompletable or merely potential. In the presence of our other assumptions about plurals, (10) ensures that no Kripke model can have a single world containing all the possible (predicative) sets of numbers. It is also possible to express the incompletability claim without recourse to plurals:

(11) $$ \begin{align} \Box \forall X \forall Y (Y \neq X \to \exists n (Y = X_n)) \to \Diamond \exists Y (Y \neq X \wedge \forall n (Y \neq X_n)). \end{align} $$

In words: given any set X such that any other set is one of its sections, it is possible for there to be a set Y that is distinct from X and each of its sections. ²⁶

Unsurprisingly, both these statements of the incompletability claim, the plural one and the singular one, admit of a direct proof as well. Consider any set X such that any other set is one of its sections. (By (9), any sets of numbers can be specified in this way.) As observed, it is possible for there to be a single set Y whose sections are precisely X and each of X’s sections. We now diagonalize on this set Y. That is, we use (P1′) to establish the possible existence of a set $\Delta $ such that $\forall n (n \in \Delta \leftrightarrow n \not \in Y_n)$ . Since $\Delta $ cannot be identical with one of Y’s sections, it follows that $\Delta $ is distinct from X and each of X’s sections, precisely as desired.

9 Phase 2

Now on to our second phase, where we want to gather together all of the sets that are definable in a given world into a single world. Informally, we begin with a world w that only contains the empty set. We want to assert the existence of a world $w^{\prime }$ , accessible from w, that has all of the sets of numbers that are definable in w via something like (P1).

Start with a world w. Notice that, in light of (P1) and the convergence principle for the modal logic S4.2, we already have that for any finite collection of sets definable in w, there is a world $w^{\prime }$ that has all of the sets in this collection. So one way to proceed would be to add a generalization of the convergence principle to the system, namely that for any (countable) set W of worlds, all accessible from a single world, there is a world $w^{\prime }$ such that every member of W has access to $w^{\prime }$ . This, however, would make the possible worlds framework more than a mere heuristic. We would be formulating a principle with respect to the space of worlds, and using that to generate more sets of numbers. ²⁷

Our first suggestion is to introduce terminology for satisfaction. For convenience, we introduce a multi-arity predicate (or a series of predicates) $\textrm {SAT}(m,\vec {y} ,\vec {Y} )$ which says, in effect, that $\vec {y}$ and $\vec {Y}$ satisfy the formula with code m (with the variables in a canonical order). ²⁸ To stay (far) away from paradox, we restrict attention to those formulas that do not have the $\textrm {SAT}$ predicate.

It seems that the predicativist herself does invoke something like satisfaction, at least informally, in the move to Phase 2. How else are we to understand phrases like “every set definable by such and such resources”? In Principia-style predicativism, for every n, we have an axiom scheme ensuring that every formula whose second-order quantifiers are restricted to order n defines a class of order $n+1$ . Intuitively, there is a single thought behind all these instances of the axiom scheme. To make this single thought explicit, we need $\textrm {SAT}$ or something like it (but see below). So if our satisfaction predicate is not acceptable to a predicativist, then we have an instance of the aforementioned instability in the position.

If z is the code of a formula $\varphi $ that has x free, let $f(z)$ be the code of $\varphi ^{<X}$ , the result of restricting the higher-order (singular and plural) variables to the sections of X.

We are now prepared to formulate the relevant Phase 2 generation principle. It is a kind of quantified “semantic ascent” of (P1): ²⁹

(P2) $$ \begin{align} \square \forall \vec{y} \,\forall \vec{Y} \forall X \Diamond \exists W \forall z \forall x (\langle z,x \rangle \in W \leftrightarrow SAT(f(z),x,\vec{y},\vec{Y})). \end{align} $$

Call the resulting principle (Phase $2$ ). It says that, in any world w, for any set X in w, there could be a set that has, as sections, all of the sets that are definable from the sections of X. Notice that this formula does not require the “finer resolution” afforded by our modal framework (cf. Section 2.3). For this formula is equivalent to the potentialist translation of a non-modal formula. ³⁰

The resources we have developed in Section 8 enable us to avoid the introduction of a satisfaction predicate, and this, as we will see, facilitates Phase 3. We characterize the predicative jump of a set by means of the following axiom scheme:

(Pred Jump) $$ \begin{align} J(X,Y) \rightarrow \forall x \forall \vec{y} (\langle \ulcorner \varphi \urcorner, x, \vec{y} \rangle \in Y \leftrightarrow \varphi^{<X}(x,\vec{y})), \end{align} $$

where $\varphi $ can be any formula without bound second-order variables and with no free variables other than $\vec {y}$ and X. ³¹ Thus, when Y is the predicative jump of X, then Y has sections corresponding to any set of numbers that is definable with a single second-order parameter X (and first-order parameters $\vec {y}$ ).

We contend that J can be assumed to be stable. Whether or not $J(X,Y)$ is true at some stage is a matter of whether or not, at this stage, Y codes all the sets that are predicatively definable from X. But since the statement that Y codes all the sets that are predicatively definable from X uses only bounded set quantification, it is independent of the particular stage at which it is evaluated.

We can now further streamline our second phase with an axiom to the effect that predicative jumps potentially exist:

(P2″) $$ \begin{align} \Box \forall X \Diamond \exists Y \, J(X,Y). \end{align} $$

10 Phase 3

In the final, third phase we consider transfinite iterations of the predicative jump. This phase poses some entirely new problems.

As a warm-up, let us begin with finite jumps. For each natural number n, we wish to be able to talk about the nth predicative jump of a given set of numbers. Recall that $Y_i$ is the ith section of Y, i.e., $Y_i = \{n \ | \ \langle i, n \rangle \in Y\}$ . Let $JSeq(X,Y,n)$ abbreviate the formalization of the following:

$Y_0 = X$ and for each $i < n$ , $J(Y_i, Y_{i+1})$ .

We can formulate an axiom asserting the possible existence of n-fold iterations of the predicative jump:

(n-fold) $$\begin{align*} \Box \forall X \forall n \Diamond \exists Y \, JSeq(X,Y, n). \end{align*}$$

Next, what we might call stage $\omega $ can be obtained as follows:

(Stage ω) $$ \begin{align} \Box \forall X \Diamond \exists Z (\forall n \exists Y \, JSeq(X,Y, n) \wedge Y_n = Z_n). \end{align} $$

For each set X, (Stage $\omega $ ) gives us a world with a set Z of numbers whose nth section is the nth jump of X, for each natural number n.

So far, so good. But this is surely not the limit of how “far” the predicativist can go. The purpose of the third phase of predicativism is to express the possibility of iterations of the jump operation along any (predicatively definable) well-ordering. Here we encounter one of the most interesting, and subtle, issues behind the enterprise—and we run up against the charge that predicativism is unstable. Recall that a relation is a well-ordering on, say, the natural numbers, just in case every non-empty set of numbers has a least element in that ordering. But, for the predicativist, there is no stage at which all of the sets of numbers exist. So the very notion of a well-ordering is impredicative! In a retrospective article, Feferman [10, p. 606] himself complains of some previous proposals that

they ignored one crucial point if predicativity is only to take the natural numbers for granted as a completed totality: namely, that they involve in an essential way … the impredicative notion of being a well-ordering relation.

Let us examine the complaint in the context of our modal analysis of predicativism as a form of potentialism. The present modal framework certainly seems to provide a way for the predicativist to express the notion of a well-ordering. The modalized quantifiers provide a way to talk of all sets of numbers, whenever they are generated. As we have seen, predicativists rely on this kind of talk in order to state their position, for example, to express that no matter how far the generation of sets has proceeded, it is possible to continue by further steps corresponding to Phase 1 or 2.

Using these expressive resources, let $WO(R)$ abbreviate the formalization of the following:

• • R is stable.

• • R is a set of ordered pairs of numbers.

• • Necessarily for any X, if X is not empty, then there is a number n such that n is the R-least member of X.

We can now define the notion of a jump sequence along some well-ordering R, formalized as $JSeq'(X,Y, R)$ , as follows:

• • $WO(R)$ ,

• • $Y_0 = X$ and, for each n,

  • – if n is the R-successor of m, then $J(Y_{m}, Y_{n})$ ,

  • – if n occupies a limit position in R, then $(Y_n)_m = Y_{m}$ for each m that precedes n in the ordering R.

This, in turn, enables us to formulate an axiom asserting the possible existence of transfinite iterations of the predicative jump along any well-ordering R:

(P3) $$ \begin{align} \Box \forall X \forall R (WO(R) \to \Diamond \exists Y \, JSeq'(X,Y,R)). \end{align} $$

In words, (P3) says that if R is a well-ordering, then there is an iteration of predicative jumps along R. ³²

However, as the passage by Feferman reminds us, an objection looms. Our principle (P3) avails itself of the impredicative notion of R being a well-ordering in order to characterize what sets can be generated by predicative means. As observed, some use of modalized quantifiers has to be acceptable in general in order to enable the predicativist to state her position, and to prove key theorems. The present concern is that reliance on modalized quantifiers in axioms with existential import might inadvertently admit impredicative reasoning.

It is instructive, in this connection, to compare our previous (P1) and (P2″) with the present (P3). The former two principles have the form “ $\Box \forall \, \Diamond \exists $ .” Despite the (modalized) quantification over all sets, the predicativist is able to make good sense of these principles: both involve some predicatively acceptable operation which necessarily, given any numbers and sets as input, generates some further set that satisfies a certain condition. Predicativists can understand this as involving only a form of free-variable-based generalization over sets: given any numbers and sets that might become available, the operation can be applied to generate yet another set. Thus, no completed or determinate totality of sets of natural numbers is presupposed.

By contrast, (P3) has the form “ $\Box \forall (WO(R) \to \Diamond \exists \ldots )$ .” This logical form is fundamentally different. (P3) says we have some predicatively acceptable operation which necessarily, given any input that satisfies some impredicative condition, generates something or other. This principle cannot be understood as involving only free-variable-based generalization over sets: for the italicized part of the antecedent makes essential use of (modalized) quantification over sets. Thus, there is a fundamental difference between (P1) and (P2″), on the one hand, and (P3), on the other. While the former two principles can be seen as involving only free-variable-based generality over the merely potential totality of sets of natural numbers, the third cannot. This difference means that (P3) is problematic, from a predicativist point of view, in a way that the first two principles are not.

How, then, can predicativists develop an acceptable version of Phase 3? We will consider two options: a more traditional one based on classical logic and a more radical one based on a semi-intuitionistic logic.

The first option is to try to find a version of Phase 3 that gets by with only the kind of free variable reasoning about sets that predicativists license anyway. To see how this might be possible, observe that predicativists can sometimes prove that a given relation R is a well-ordering. The proof can be given using only parameters, or free variables, ranging over sets. Consider the standard ordering $<$ on the natural numbers. Let X be any non-empty set of numbers (i.e., one that gets generated somehow—at some stage). Suppose that X has no least element. Consider the set Y of all numbers x such that x is not in X and neither is anything smaller than x. This definition is predicative because it is first-order (with X as a parameter). We now proceed by induction to show that every number is in Y. We establish the base case, 0 is in Y, by observing that 0 would otherwise be in X, which would thus have a least element. For the induction step, suppose n is in Y. Then n is not in X, and neither is anything smaller. If $n+1$ were not in Y, either $n+1$ is in X or something smaller is in X. The latter is ruled out by the induction hypothesis. So $n+1$ is in X and is the smallest member of X. Contradiction. So, by induction, all numbers are in Y. So no number is in X, which contradicts our assumption that X is non-empty.

We contend that this proof does not presuppose the existence of a completed totality of all sets of natural numbers. ³³ Using only free variable reasoning, we show that any set X, whenever it is generated, has a least element. In an analogous way, predicativists can show that $\omega +1$ is a well-ordering, and so is $\omega +2$ , …, $\omega \cdot 2$ , and so on, for a while, anyway. Exactly how far is a delicate matter.

These considerations suggest the possibility of a rule-based version of Phase 3, along the following lines.

Suppose we can prove, by predicatively acceptable means, that R is a well-ordering of the natural numbers. Then it is possible to iterate J along R. ³⁴

Of course, this suggestion presupposes that we can articulate precisely what counts as a proof by “predicatively acceptable means.” We need to specify a deductive system, or a series of deductive systems, for the enterprise. Here it would be natural to follow the lead of Feferman (and Schütte [40, Part C]), who develop a system of ramified type theory, with variables $X^\alpha $ indexed by predicatively acceptable ordinals. Feferman [10] writes:

The crucial new point … is that the predicative ordinals not only are those that can be defined by (what happen to be) well-ordering relations in the given systems, but also must previously be proved to be such relations. The problem is how to meet this requirement without unrestricted second-order quantification; the answer comes from the provability condition …

As noted above, however, this would introduce variables indexed by predicatively acceptable ordinals, and this brings back some of the notational nightmare of ramified type theory.

A second, more radical option is to respond to the prevailing objection by turning to intuitionistic logic. As observed, predicativists are entitled to free-variable reasoning about sets. Perhaps they are also entitled to intuitionistic quantification over sets since—unlike classical quantification—this doesn’t presuppose a completed or determinate totality of sets. Claims of this sort are familiar from Dummett [6, p. 319]. In more recent work, Feferman too expresses sympathy for the idea. In an unpublished, but widely circulated and discussed manuscript [13, p. 23], he writes: ³⁵

One way of saying of a statement $\varphi $ that it is definite is that it is true or false; …that’s the same as saying that the Law of Excluded Middle (LEM) holds of $\varphi $ , i.e., one has $\varphi \vee \neg \varphi $ . Since LEM is rejected in intuitionistic logic as a basic principle, that suggests the slogan, “What”s definite is the domain of classical logic, what’s not is that of intuitionistic logic.” In the case of predicativity, this would lead us to consider systems in which quantification over the natural numbers is governed by classical logic while only intuitionistic logic may be used to treat quantification over sets of natural numbers or sets more generally.

Based on these ideas, Feferman formulates a “semi-intuitionistic” system, whose axioms we will describe shortly.

First, however, we wish to reflect on his slogan that “What’s definite is the domain of classical logic, what’s not is that of intuitionistic logic.” How might such a claim be substantiated? One option is to invoke the so-called Brouwer–Heyting–Kolmogorov (BHK) readings of the logical operators. (P3) would then be interpreted as something like “there is a way to transform any proof of $WO(R)$ into a proof that J can be iterated along R.” We would thus avoid the need for a determinate totality of sets, as desired. ³⁶ Another option is to develop a realizability interpretation, on which (P3) would say that there is an effective way to transform a realizer of $WO(R)$ into a realizer of iterability of J along R. ³⁷ By contrast, since the natural numbers are assumed to be complete, quantification over them can still be assumed to behave classically.

More generally, what we need is a distinction between instance-based and non-instance-based explanations of universal generalizations. Let us explain. Suppose that all of your students are born on a Monday. The only explanation, we may assume, proceeds via each of your students. This explanation is highly instance-based. Other generalizations permit an entirely non-instance-based explanation. For example, to explain why every whale is a mammal, there is no need to invoke any particular whale; it suffices to observe that it is part of the nature of whales that they are mammals. When a domain is indeterminate, instance-based explanations won’t always be available, since there may be no determinate totality of instances to consider. Linnebo [29] develops the intuitive distinction between instance-based and non-instance-based explanations and finds a connection with the logic that is validated. If every true universal generalization permits an instance-based explanation, then the logic is classical; but if not, then only intuitionistic logic (or semi-intuitionistic logic, of which more shortly) is validated. If correct, this supports the mentioned claim that intuitionistic, but not classical quantification is permitted over an indeterminate domain.

Our distinction between liberal and strict potentialism (Section 3.1) is also relevant in this connection. The former takes the modalized quantifiers to be unproblematic, and applies classical logic to the background modal language. By contrast, the latter requires that any truth about the system must somehow be “made true” at some stage. As observed, this requirement poses a challenge to any universal generalization over a merely potential domain. How can such a generalization be “made true” at some stage, given that many of its instances haven’t even been generated? The idea of non-instance-based generality provides an attractive answer: the generalization may well be “made true” independently of all of its instances, thus freeing strict potentialists from a requirement they cannot satisfy, namely that all the instances be available to underwrite the generalization. As Feferman observes, however, this approach to generality naturally gives rise to intuitionistic logic (or some slight strengthening thereof). In our modal setting, this means that strict potentialism is naturally developed by adopting an intuitionistic modal logic. ³⁸

Returning to our main line of argument, the second option for responding to Feferman’s objection to the naive version of Phase 3 is that predicativists should be strict potentialists about sets of numbers and accordingly adopt an intuitionistic modal logic. In this modified context, they can accept the axiomatic statement of Phase 3, namely (P3), precisely as stated. ³⁹

With this explication and defense of Feferman’s slogan in place, we turn to the precise formulation of the relevant system. We begin with an intuitionistic modal logic S4.2, as above. As before, we use a two-sorted system, with one sort of variable ranging over natural numbers and the other ranging over sets of natural numbers. We add the closure of all instances of excluded middle in which the embedded formula contains no second-order quantifiers and is not modal. That is, we add each instance of:

$$ \begin{align*} \forall \vec X \forall \vec x(\varphi(\vec X, \vec x) \vee \neg \varphi(\vec X, \vec x)), \end{align*} $$

where $\varphi $ contains no bound set-variables.

Notice that this axiom schema allows the aforementioned proof that $<$ is a well-ordering, and so $WO(\omega )$ , $WO(\omega +1)$ , …, $WO(\omega \cdot 2)$ , …. By contrast, it is well-known that one cannot prove the least-number principle in a completely intuitionistic setting. Moreover, the axiom schema ensures that an essential assumption of the intuitionistic mirroring theorem is satisfied, namely the decidability of each atomic predicate.

Following Feferman, we might also add further principles such as that of Bounded Omniscience:

(BOM) $$ \begin{align} \forall n (\varphi(n) \vee \neg \varphi(n)) \ \to \ \forall n \, \varphi(n) \vee \exists n \neg \varphi(n). \end{align} $$

The idea is that quantification over the natural numbers behaves classically because the natural numbers form a “definite” domain. One might attempt to explicate this idea by means solely of the consequent of (BOM), namely $\forall n \, \varphi (n) \vee \exists n \neg \varphi (n)$ . But that would be too quick: non-classical behavior might sneak in via the formula $\varphi (n)$ that is generalized. The correct explication is that, conditional on the classical behavior of $\varphi (n)$ for each instance—that is, conditional on the antecedent of (BOM)—the consequent holds.

To sum up our discussion thus far, when faced with the objection that Phase 3 illegitimately assumes the impredicative notion of a well-ordering, predicativists have two options. One is to adopt a rule-based version which handles the notion of well-ordering by means of free set variables only and stick with classical logic. Another option is to weaken the logic for quantification over sets to intuitionistic logic and permit (P3) as formulated.

We wish to end by observing how we are now in a position to acquit predicativism of a well-known charge that it is incoherent. Hellman [21, p. 299] expresses the charge well:

the predicativist implicitly transcends predicativity him/herself in the very formulation of the limitative theses!

What are we to make of this?

Hellman is obviously right that it can be useful to “transcend” predicativism in favor of a stronger, classical approach in order to study the limits of predicative definability. Feferman and Schütte show this limit to be a certain countable ordinal $\Gamma _0$ (see [40, Part C]). ⁴⁰ Predicativists cannot themselves recognize that result, since this would require a predicatively coherent definition of “predicatively definable.”

Nevertheless, we submit that our two versions of Phase 3 can be used to show that predicativism is internally coherent, what Feferman and Hellman call “stable” [15, 16]. The modal framework can be used to state all the principles and closure conditions that the approach requires, in a way that predicativists themselves can endorse.

Notice, finally, that predicativism is different, in an interesting way, from many other forms of potentialism, especially of the liberal kind, such as Aristotelian or Cantorian. For most of these, we are able to state the generating principles once and for all. In most cases, the principles are just the modalized counterparts to the axioms of the given theory (arithmetic, set theory, etc.). In predicativism, by contrast, the generating principles are, in a sense, themselves generated. As we generate more and more sets of natural numbers, we also have more and more resources that can be used to prove that various numbers code recursive well-orderings, and thus we generate more and more instances of (P3) that can be then used to generate more sets of numbers.

11 Concluding summary

Since we have come a long way, a brief summary may be useful. We opened by asking about the connection between two seemingly completely different aspects of predicativism: an adherence to the Vicious Circle Principle and the view that certain totalities, such as that of sets of natural numbers, are incompletable or merely potential. Taking a cue from Poincaré, we proposed a simple answer. Potentialism poses a challenge to the stability of our definitions. Might not a definition be disrupted by the stepwise generation of the domains with which they are concerned? We observed that adherence to the Vicious Circle Principle provides a simple and effective response: when all its quantifiers are restricted to objects already generated, a definition is immune to disruption by any future generation of further objects.

Inspired by this simple answer, we presented a general framework for analyzing potentiality in mathematics. We located predicativism in this general framework in a way we find illuminating, as it reveals various choices confronting predicativists and locates the resulting options in a larger landscape of different forms of potentialism.

Using our analysis of predicativism as a form of potentialism, we have also tried to shed light on some important questions concerning predicativity. First, we presented the predicativist take on the logical conception of set, highlighting a simple modal explication of the stability requirement: to define a set, a formula must never be allowed to “change its mind” on whether or not it applies to an object. Second, we solved a puzzle about predicativism relative to the natural numbers, explaining how, at least for logical and mathematical purposes, it doesn’t matter whether one is an actualist or a liberal potentialist about the natural numbers. Third, we used the potentialism to explain the predicativist understanding of Cantor’s theorem. Fourth, we presented Feferman’s semi-intuitionistic approach to predicativity, arguing that this is usefully regarded as a form of strict potentialism. Finally, we observed that our explication of predicativism is acceptable to predicativists themselves, thus rebutting the charge that the view cannot coherently be stated.