2. A nuisance to neo-Fregeans

Fregean logicism, as I shall use the term, is distinguished by the interpretation of arithmetic in a second-order theory of extensions. Such a theory presumes second-order logic with full comprehension (“full second-order logic”), and issues the principle BLV as describing the behavior of extensions:

(1) $$ \begin{align} (\forall X)(\forall Y)(\breve{\varepsilon} X = \breve{\varepsilon} Y \leftrightarrow X=Y), \end{align} $$

where “ $X = Y$ ” abbreviates “ $(\forall x)(Xx \leftrightarrow Yx)$ .” Frege’s theory of extensions was found to be inconsistent by Russell.Footnote ²

But to interpret arithmetic, Frege does not need to use BLV once he has the principle HP:

(2) $$ \begin{align} (\forall X)(\forall Y)(\# X = \# Y \leftrightarrow (\exists g)(g:X \mathrel{\mathop{\rightarrow}^{\mathrm{1-1}}_{\mathrm{onto}}} Y)). \end{align} $$

Frege’s Theorem is the result that HP suffices to interpret second-order Peano Arithmetic in second-order logic with full comprehension. So if HP is analytic—which for our purposes will just mean that it has some privileged status preserved by second-order deduction—then so is arithmetic.

Neo-Fregeans suggest that HP may be analytic because it is an abstraction principle: it determines the behavior of an abstraction operator—a functor taking concepts and returning object called abstracts—to respect a given equivalence relation. In Frege’s phrase, such principles “carve up the content” in a new way [Reference Frege and Austin16, Section 64]. The neo-Fregean’s hope is that if the original content is sufficiently logical, its re-carving will be analytic.

The complication for the neo-Fregean comes in the fact that being an abstraction principle on an equivalence relation definable in second-order logic is not sufficient for analyticity.Footnote ³ For BLV meets these conditions, and yet is inconsistent. So any argument for HP’s analyticity must distinguish HP, in a principled way, from the abstraction principles that are not analytic. Of course HP is distinguished from BLV by its consistency in full second-order logic. But what if there are abstraction principles that are consistent, like HP, but jointly inconsistent with HP? Then the neo-Fregean must give criteria for the acceptability of abstraction principles that sorts the sheep from the goats, and HP with the sheep.

Heck [Reference Heck20] shows that it is easy to construct such goats by abstracting on an equivalence relation which is a disjunction of “ $X=Y$ ” with any condition incompatible with HP. For example, the condition that the universe—which we will denote with “V”—is Dedekind finite.Footnote ⁴ Such principles, however, have the air of contrivanceFootnote ⁵ ; their contrivance renders these principles dubious as challenges to the neo-Fregean project.

Are there any goats—principles inconsistent with HP—that are also mathematically interesting? There are several candidates, the simplest of which is the NP given by:

(4) $$ \begin{align} (\forall X)(\forall Y)(\S X = \S Y \leftrightarrow |X \triangle Y|<\omega). \end{align} $$

We can characterize NP by: the nuisance of X is identical to the nuisance of Y just in case the symmetric difference $X\triangle Y = (X-Y)\cup (Y-X)$ is Dedekind finite. Notice that NP’s equivalence relation does not contrive inconsistency with HP by disjoining an inconsistent “out clause.” It is also of some mathematical interest, as this equivalence relation is studied in point-set topology.Footnote ⁶

The existing literature does not show NP and HP are jointly inconsistent. It shows that they are jointly unsatisfiable: there are no models of both principles in which the second-order domain is the full power-set of the first-order domain. Proofs of this fact, however, are not obviously adaptable to the restricted deductive context of second-order logic.Footnote ⁷ Since the deductive system for second-order logic is not complete with respect to standard semantics, the existing results do not settle the question of the deductive compatibility of HP and NP.

The Heck-like examples, as well as BLV and NP, are considered by neo-Fregeans to be “Bad Company”: the most natural criteria by which HP is privileged let in at least some of these principles. The neo-Fregean can, of course, make the rather desperate argument that at least the most challenging bad companion makes a tolerable guest: NP, at least, is not known to be inconsistent with HP. The results of this paper show this to be a losing strategy.

Of course, neo-Fregeans have hardly been so unwise as to embrace such a strategy: they have attempted to find criteria according to which NP is defective, and HP not. Even so, the most prominent programs have been put in model-theoretic terms: HP, and not NP, is said to be conservative, unbounded, stable, and irenic.Footnote ⁸ All but the first of these criteria are described in terms of standard models. Much of the research has therefore been set in semantic terms. But this makes the philosophical sacrifice described by Linnebo:

Perhaps for this reason, Wright’s early call for deductive investigation of NP’s has persisted:

As we will show below, deductive matters are as bad as feared for the neo-Fregean. But “as bad as feared” is not the same as “as bad as can be.” In other words, that NP is inconsistent with HP raises the question of whether mathematically natural principles jointly inconsistent with HP are all of the same type—are they all, in some sense, like NP? It would be bad news for the neo-Fregean if the bad companions were multitude in kind as well as in number.Footnote ¹⁰ This question is answered in Theorem 2, a corollary of the main theorem of [Reference Ebels-Duggan13]: mathematically natural bad companions can be classified into just two types. Whether that is few enough for the neo-Fregean I will leave for another occasion.

3. Abstraction principles and Cantorian results

The joint inconsistency of NP and HP is of interest to neo-Fregeans and their critics. But the result is interesting beyond these discussions in the philosophy of mathematics, for the reason that the result is of the same kind as Cantor’s theorem in set theory. This point can be made with two observations: first, the traditional identification of BLV’s inconsistency with Cantor’s theorem,Footnote ¹¹ and second, that NP and BLV are instances of the same parameterized abstraction principle.

3.1. Cantor’s theorem in weak systems

“Cantor’s theorem” means different things in different contexts. Its usual context is in the theory of sets, it can be stated in the following ways:

Cantor’s Theorem (Injections). For any set X there is no injection from the power-set of X into X.

Cantor’s Theorem (Surjections). For any set X, there is no surjection from X to its power-set.

But in this context (where “the theory of sets” means something like ZF or ZFC), there are two elements that might be regarded as extraneous. One is the mention of the power-set: it is the fact that the elements of the power-set are subsets of X that matters, not so much that they can themselves be gathered together into a set. The other is the meaning, in set theory, of “the existence of an injection (surjection).” In this context that means the existence of a specific kind of subset of a certain Cartesian product. But of course this can be removed as well.

In stripping away these specifically set-theoretic elements, one is left with a more general statement of “Cantor’s theorem”: there is no way to correlate all the sub-collections of a given collection with the objects of that collection so that certain cardinality properties are preserved.Footnote ¹² Since the “core” of Cantor’s theorem is something that does not need all of set theory, it makes sense to study the phenomenon in weaker theories. A relatively weak theory relating objects to their collections, of course, is second-order logic (with full comprehension, but without axioms of choice).Footnote ¹³

While there is, in pure second-order logic, a way to express the surjective version of Cantor’s theorem, there is no easy method by which to express the specifically injective version, since a formula defining a function from the sub-concepts of X to its objects will automatically define a surjection from the latter to the former.Footnote ¹⁴ For this reason, something more is needed to study the injective version of Cantor’s theorem in second-order logic. Type-lowering operators offer a natural fix for this problem. With an operator $\breve {\varepsilon }$ taking concepts to objects, the existence of an injection from second-level objects (concepts) to first-level objects (objects) would then be represented by

(7) $$ \begin{align} (\forall X)(\forall Y)(\breve{\varepsilon} X = \breve{\varepsilon} Y \rightarrow X = Y). \end{align} $$

Concepts and sub-concepts, in the context of Cantor’s result, are extensional, and the natural way to represent this is that $\breve {\varepsilon }$ is not extensionally ill-defined: there are not co-extensive X and Y that return different objects under $\breve {\varepsilon }$ :

(8) $$ \begin{align} (\forall X)(\forall Y)(X = Y \rightarrow \breve{\varepsilon} X = \breve{\varepsilon} Y). \end{align} $$

Putting together (7) and (8) yields Frege’s BLV (1). So a natural way to present the injective version of Cantor’s theorem in second-order logic is by means of BLV.

Cantor’s theorem is robust, then, in the sense that both its surjective and injective versions can be obtained in treatments of concepts and objects far weaker than ZF and ZFC. But Cantor’s theorem is just the most distinguished member of a family of results. For extensional equality between concepts is an equivalence relation between concepts—the finest such extensional relation. What the respective versions of Cantor’s theorem do is show that, given a notion of relative cardinality (specified by either something like injections or something like surjections), there are more equivalence classes of this finest relation then there are objects.

Putting it this way invites the question of whether the same is true for other equivalence relations. Here, the argument for the use of abstraction principles to represent injections translates neatly to the more general case. That is, suppose one has defined an equivalence relation E on concepts of a domain of objects, and one wants to know how many equivalence classes there are. In particular, one wants to know if there are more equivalence classes than there are objects. One can pursue these questions in second-order logic by adding an abstraction principle

(9) $$ \begin{align} (\forall X)(\forall Y)(\hslash X = \hslash Y \leftrightarrow E(X, Y)) \end{align} $$

provided E is expressible in second-order logic. If, for example, the principle (9) only has models whose first-order domain is in a certain range of cardinalities, that means that on all other cardinalities, there is no injection from those E-equivalence classes to that many objects. In what follows, we will refer to results of the form “Abstraction principle $A_E$ only has models of such and such cardinalities” as Cantorian cardinality results (“Cantorian results” for short).

3.2. Uniform separations and complementations

A second source of interest in this paper’s main result depends on that result being Cantorian. Clearly the inconsistency of BLV is, by the above reckoning, a Cantorian result. The purpose of this section is two-fold: first, to show that the joint inconsistency of HP and NP is, by similar reckoning, also a Cantorian result. In fact, NP and BLV are just instances of the same parameterized abstraction principle, and so are in the class of uniform separations. The second purpose of this section is to describe yet another parameterized abstraction principle, which determines the class of uniform complementations. As will be shown below, the results we prove for NP—and so those for uniform separations—have analogues for uniform complementations.

The first step, then, is to describe how BLV and NP are similar.

The equivalence relation of NP, recall, is $|X \triangle Y|<\omega $ —that is, that the symmetric difference of X and Y is Dedekind finite. Notice now that $X=Y$ is equivalent to $|X \triangle Y|<1$ . So both BLV and NP can be considered to be uniform separations; that is, abstraction principles $\texttt {US(}\kappa {\texttt {)}}$ of the form

(10) $$ \begin{align} (\forall X)(\forall Y)(\sigma X = \sigma Y \leftrightarrow |X\triangle Y|<\kappa), \end{align} $$

where “ $|A|<\kappa $ ” is definable in pure second-order logic for the parameter $\kappa $ .Footnote ¹⁵ So, for example, “ $|A|<\omega $ ” will express that A is Dedekind finite, while “ $|A|<\omega _1$ ” will express that if a Dedekind infinite concept injects into A, then A injects into every Dedekind infinite concept. Thus the principle BLV is $\texttt {US(}1\texttt {)}$ and NP is $\texttt {US(}\omega \texttt {)}$ . As described in Section 3.1, the inconsistency of BLV can be regarded as a Cantorian result. So, however, can the joint inconsistency of NP and HP, since it is a corollary of the fact that NP deductively implies the universe is finite.

This again raises the question (of Section 3.1) of whether there are other kinds of abstraction principles jointly inconsistent with HP that are sufficiently unlike NP. There are: consider an abstraction principle that “halves” BLV, the Liberated Complementation Principle LCP of [Reference Ebels-Duggan13]:

(11) $$ \begin{align} (\forall X)(\forall Y)(\ell X = \ell Y \leftrightarrow X= Y \vee X = V-Y). \end{align} $$

The equivalence relation of this principle sorts concepts with, and only with, their complements. Now, LCP is not inconsistent; it is easy to verify that it has standard models with first-order domain of sizes 1 and 2. However, one cannot go beyond that.

Proposition 1. LCP deductively implies $|V| \leq 2$ .

Proof. If $\ell \varnothing = \ell \{\ell \varnothing \}$ then $V = \{\ell \varnothing \}$ . So we may assume that $\ell \varnothing \neq \ell \{\ell \varnothing \}$ .

Suppose $V' = V-\{\ell \varnothing , \ell \{\ell \varnothing \}\} \neq \varnothing $ . For any $X \subseteq V'$ , let $X^* = X \cup \{\ell \{\ell \varnothing \}\}$ . Now if $\ell X^* = \ell \varnothing $ or $\ell X^* = \ell \{ \ell \varnothing \}$ , then either $X^* = \varnothing $ , $ X^*=V$ , $X^* = \{\ell \varnothing \}$ , or $X^* = V- \{\ell \varnothing \}$ . Each contradicts the fact that $\varnothing \neq X^* \subseteq V-\{\ell \varnothing \}$ . Thus for each $X\subseteq V'$ , $\ell X^*$ falls under $V'$ .

But then consider the concept R defined by

$$ \begin{align*} Rx \leftrightarrow (\exists Y\subseteq V')(x = \ell Y^* \mathbin{\wedge} \neg Yx);\end{align*} $$

we recreate the Russell paradox: if $\ell R^*$ falls under R, then let $Y\subseteq V'$ with $\ell R^* = \ell Y^*$ . Since $Y^* \cap R^* \neq \varnothing $ , it follows that $Y = R$ ; and so we have that $\neg R(\ell R^*)$ . So $\ell R^*$ must not fall under R. But then by the definition of R, as $R\subseteq V'$ , we have that $R(\ell R^*)$ , a contradiction.□

Though LCP is not like BLV in one way (it is not a uniform separation), it is in another: a Russellian diagonal construction can be deployed to obtain the cardinal interval on which it has models (standard or not).

We generalized BLV by introducing uniform separations; we can do the same for LCP. Say that a uniform complementation is an abstraction principles $\texttt {UC(}\kappa \texttt {)}$ of the form

$$ \begin{align*} (\forall X)(\forall Y)(\chi X = \chi Y \leftrightarrow |X \triangle Y| < \kappa \vee |X \triangle (V-Y)| < \kappa) \end{align*} $$

again for definable parameter $\kappa $ . It is easily seen that LCP is just UC(1).

Finally, I mentioned earlier (Section 3) that deductive bad companions—principles inconsistent with HP—can be classified into two kinds. This follows from the main theorem of [Reference Ebels-Duggan13],Footnote ¹⁶ which can be stated thus:

Equivalence Classification Theorem ECT. Let E be an equivalence relation definable in pure second-order logic,Footnote ¹⁷ and let $\mathcal M$ be a model with universe V infinite and well-ordered in $\mathcal M$ . For $X\in \mathcal M$ let

$$ \begin{align*}[X]_{E(\boxminus)} = \{Y \subseteq V \mid E(X,Y) \mathbin{\wedge} |X|=|Y|\mathbin{\wedge} |V-X|=|V-Y|\}.\end{align*} $$

Exactly one of the following holds for each $X\in \mathcal M$ :

(12) $$ \begin{align} [X]_{E(\boxminus)} = \{ Y \subseteq V \mid |X|=|Y|= |V-X|=|V-Y|\}, \end{align} $$

(13) $$ \begin{align} [X]_{E(\boxminus)} \subseteq \{ Y \subseteq V \mid |X\triangle Y|< \omega \vee |V-(X\triangle Y)|<\omega\}. \end{align} $$

The latter divides into two cases, depending on whether

(14) $$ \begin{align} [X]_{E(\boxminus)}\subseteq \{ Y \subseteq V \mid |X\triangle Y|< \omega \} \end{align} $$

holds. Where $\mathcal M \models |V|\geq \omega $ and (12) holds for X with $|X|=|V-X|$ we say that E has a bicardinal top in $\mathcal M$ . If both (13) and (14), we say that E has a separative top in $\mathcal M$ . If (13) but not (14) hold we say that E has a complementative top in $\mathcal M$ .

It is plain that if E has a separative top in $\mathcal M$ , then it behaves like $\texttt {US(}(|V|)\texttt {)}$ on those concepts X with $|X|=|V-X|$ , and if it has a complementative top, it behaves like $\texttt {UC(}|V|\texttt {)}$ on those same concepts. The following result shows that any abstraction principles jointly inconsistent with HP can be characterized as “like” either $\texttt {US(}\omega \texttt {)}$ or $\texttt {UC(}\omega \texttt {)}$ based on how their equivalence relations behave in countable standard models.

Theorem 2. Let E be an equivalence relation definable in pure second-order logic. If E has a bicardinal top in a countable standard model, then there is a countable standard model of $A_E$ and $\texttt {HP}$ , and so $A_E$ and $\texttt {HP}$ are jointly consistent.

If $A_E$ and $\texttt {HP}$ are not jointly consistent, then E has a separative or complementative top on all countable standard models.

Proof. Suppose for all countable standard models $\mathcal M$ , (12) holds for $X\in \mathcal M$ with $\mathcal |X|=|V-X|$ . Let $\mathcal M$ be a standard model with first-order domain $V=\omega $ , and let f map the finite and co-finite subsets of  $\omega $ to $\omega -\{0\}$ . Set $@_E X = 0$ if $|X|=|V-X|$ and $@_EX = f(X)$ otherwise; and $\# X = 0$ if $|X|=\omega $ and $\# X = |X|+1$ otherwise. It is plain that $(\omega , P(\omega ), \ldots , \#, @_E)$ satisfies $A_E \mathbin {\wedge } \texttt {HP}$ . This establishes the first assertion.

The second assertion follows from ECT and the contrapositive of the first.□

Thus each abstraction principle inconsistent with $\texttt {HP}$ is of one of two types; a fortiori this holds of all mathematically interesting bad companions.

4. Cantorian results, cardinal notions, and Russellian methods

As described in Section 3, when described in set-theoretic terms, Cantorian cardinality results concern the existence or non-existence of certain kinds of functions. Translating this into the context of second-order logic, the injective versions of Cantor’s theorem were Cantorian in the sense that the abstraction operator $\breve {\varepsilon }$ , governed by BLV, took the place of the injection asserted by the set-theoretic formulation of the theorem.

In both cases, however, to state the Cantorian result requires only that there be formal machinery answering to these set-theoretic notions: the cardinal notions of injections, surjections, and bijections. This is true of Cantorian results in general, especially in a second-order context. For example, the Cantorian result at the center of this paper can be given by “ $\models \texttt {NP}\rightarrow |V|<\omega $ ”: it is a theorem of second-order logic that NP implies the (Dedekind) finitude of the universal concept V. All that is used in the statement of this result are the cardinal notions in second-order logic sufficient to characterize infinity, and the added machinery needed for NP. But that machinery, as we argued above, is just the machinery asserting what (in ZF would be) the existence of an equivalence-respecting injection. So to state this result, we need only deploy these cardinal notions.

To the extent that Cantor’s theorem on power-sets typifies Cantorian results, the diagonal method of proving it typifies the proofs of such results. Which conceptual resources are used in the diagonal construction? In what we will call Russellian methods—those deployed in the classic derivation of Russell’s paradox from BLV—one diagonalizes using only cardinal notions.

Diagonalizing using such notions is a powerful tool: in semantic settings, one can prove a large class of Cantorian results by mimicking the derivation of Russell’s paradox.Footnote ¹⁸ Let $\mathcal M$ be a standard model with $\mathcal M \models \texttt {US(}|V|\texttt {)} \mathbin {\wedge } |V|\geq \omega $ . Since $\mathcal M$ is an infinite standard model, there is an injection $\langle \cdot , \cdot \rangle :V \times V \rightarrow V$ . Letting

(15) $$ \begin{align} \langle X, V \rangle = \{ \langle x, v \rangle \mid x \in X, v \in V\},\end{align} $$

we can see that if $X\neq Y$ , then $|\langle X, V\rangle \triangle \langle Y, V\rangle |\not < |V|$ . Clearly if $X=Y$ then $|\langle X, V\rangle \triangle \langle Y, V\rangle | < |V|$ . So we have shown that

(16) $$ \begin{align} (\forall X)(\forall Y)(\sigma \langle X, V\rangle = \sigma \langle Y, V\rangle \leftrightarrow X=Y). \end{align} $$

Notice the similarity of (16) to BLV: one can, as in [Reference Ebels-Duggan12], define the Russell set by

$$ \begin{align*} R = \{\sigma \langle X, V\rangle \mid \neg X(\sigma\langle X, V \rangle) \}.\end{align*} $$

From here, one can use the argument used in getting Russell’s paradox out of BLV. As noted earlier, the mathematical machinery built in to standard models suffices to make the last step of the proof “Russellian.”

The same can be done for $\texttt {UC(}|V|\texttt {)}$ : if $X\neq Y$ , then by the above argument $|\langle X, V\rangle \triangle \langle Y, V\rangle |\not < |V|$ . Likewise if $X \neq V-Y$ , then $|\langle X , V\rangle \triangle \langle V-Y, V\rangle |\not < |V|$ . So, as above, we obtain

(17) $$ \begin{align} (\forall X)(\forall Y)(\chi \langle X, V\rangle = \chi \langle Y, V\rangle \leftrightarrow X=Y\vee X = V-Y). \end{align} $$

One can then replicate the Russellian argument of Proposition 1 to obtain a contradiction from (17). Again, then, exclusively cardinal notions suffice for the last step of establishing the semantic Cantorian result:

But this only shows that, once one has imported the mathematical machinery of the semantic setting, only cardinal notions are required at the last step of the proof. So, these diagonal proofs used in semantic settings use extra-cardinal notions to prove Cantorian results. As such, to determine the conceptual resources needed to prove Cantorian results, it is best to proceed in a deductive, rather than a full semantic, setting.

This raises the question of whether all Cantorian results can be proved using just cardinal notions. Of course some can: the inconsistency of BLV is one; Proposition 1 is another. For such results as these, there is a kind of harmony between the resources needed to state the result, and those needed to prove it.Footnote ¹⁹

It would be interesting if there is a Cantorian result that could not be proved using just cardinal notions. And it would be of further interest if that result could be obtained by generating, from a specified injection from concepts to objects, some of the mathematical machinery one finds in the standard semantics for second-order logic. A result that could not be proved using Russellian methods, but could be proved using additional notions, would be interesting for the lack of availability of the simpler methods.

5. On the difficulties of Russellian diagonalization

The joint inconsistency of NP and HP is, as I have argued, a deductive Cantorian result. And while I cannot prove that Russellian methods are insufficient to prove the joint inconsistency of NP and HP, no such proof has thus far been found. This is evidence that if Russellian methods are available at all, they are not easily available. By examining the structure of Russellian methods, we can see why such proofs are hard to find, if they exist at all.

Russell himself gave a compelling general analysis of set-theoretic paradox in [Reference Russell26, p. 142–3].Footnote ²⁰ Transferred into the second-order context, Russell provides the following theorem schema:

Theorem 4. (RussellFootnote ²¹ )

Let f be a functor from concepts to objects, and $\phi (x)$ be any formula with the first-order variable x free. Then second-order logic (in the language including f) proves the following:

(18) $$ \begin{align} (\forall U)[(\forall x)(Ux \rightarrow \phi(x))\rightarrow \phi(fU)\mathbin{\wedge} \neg U(fU) ] \rightarrow \neg (\exists W)(\forall y)(Wy \leftrightarrow \phi(y)). \end{align} $$

By our stipulation “second-order logic” includes full comprehension, so (18) is equivalent to the negation of

(19) $$ \begin{align} (\forall U)((\forall x)(Ux \rightarrow \phi(x))\mathbin{\wedge} \phi(fU)\mathbin{\wedge} \neg U(fU) ). \end{align} $$

As Russell shows, both the paradox bearing his name and the Burali–Forti paradox can be obtained by the “recipe” [Reference Russell26, p. 144] given in Theorem 4. For the former, let f be $\breve {\varepsilon }$ and $\phi (x)$ be $(\forall X)(x = \breve {\varepsilon } X \rightarrow \neg Xx)$ . For the latter, one generates from any concept X using familiar methods (“y follows in the f-sequence that starts with $fX$ ”) a sequence

$$ \begin{align*} f_0X &= fX\\ f_1X&=f(X \cup \{f_0X\})\\ \vdots \\ f_\omega X &= f(X \cup \{f_0X, f_1, \ldots \})\\ \vdots \end{align*} $$

One can then let $\phi (x)$ be “x is in the f-sequence that starts with $fX.$ ” Provided the members of this sequence never repeat (as if f is $\breve {\varepsilon }$ from BLV), this sequence is order-isomorphic to the f-sequence generated when $X=\varnothing $ . These ordinal properties suffice to establish (19).Footnote ²²

One might conclude from Russell’s analysis that cardinal notions (as deployed in Russell’s paradox) and ordinal notions (as deployed in Burali–Forti’s) are symmetric in their ability to generate Cantorian results. But Russell’s analysis, as it stands, does not work for $\texttt {US(}\omega \texttt {)}$ , either using cardinal or ordinal notions. The trouble is that the clauses $\phi (fU)$ and $\neg U(fU)$ in (19) discriminate more finely than the equivalence relation of $\texttt {US(}\omega \texttt {)}$ . This can be seen from the following analysis.

First, observe that in the case of BLV, the Russell concept can be constructed like this:

(20) $$ \begin{align} Rx \leftrightarrow (\exists Y)(\breve{\varepsilon} Y = x \mathbin{\wedge} \{x\}\not\subseteq Y). \end{align} $$

Looked at this way, to construct the Russell concept, first recover a concept from an abstract (in the above, Y), then associate the abstract with another concept ( $\{x\}$ ), and then assert that some defined relation ( $\subseteq $ ) between those two concepts fails to hold. So we can describe the general form of a Russell set by:

(21) $$ \begin{align} Rx \leftrightarrow (\exists Y)(@ Y = x \mathbin{\wedge} \neg \Phi_E(Y, F_E(x))). \end{align} $$

Here $F_E(x)$ is the concept associated with the object x, and $\Phi _E$ is the defined relation said not to hold between the recovered concept Y and the determined concept $F_E(x)$ . Both are indexed by the equivalence relation E since these constructions will vary depending on the equivalence relation in question, E.

One can discern the general problem by seeing first what goes right with the argument in the case of BLV. Notice that concepts (in this case R) are defined in the finest terms: by specifying exactly the objects that fall under them. Thus, the left-hand side of (21) involves the application of a concept to an object. We can see that in the case of BLV, $\Phi _=(Y, F_=(x))$ is calibrated exactly to this degree of specification: for BLV, $\Phi _=$ is $\subseteq $ , and $F_E(x)$ is $\{x\}$ , and so $\Phi _=(Y, F_=(x))$ is implied by (and in fact is equivalent to) the predication of Y to x. That is why it is so easy to obtain a contradiction: both R and $\Phi _=(Y, F_=(x))$ are specified with an equally fine grain. That is, in the case of BLV, we have:

(22) $$ \begin{align} (\forall Z)(Z = Y \rightarrow (F_=(x)\subseteq Z \rightarrow \Phi_=(Y, F_=(x)))). \end{align} $$

But in general the relation described by $\Phi _E(Y, F_E(x))$ is not calibrated to the fine grain of predication, as occurs in the left of definitions like (21). More specifically, if the equivalence relation E is coarser than equality, as it is for separations where $\kappa \neq 1$ , then it is natural that $\Phi _E(Y, F_E(x))$ would be coarser than is defined for BLV, and so that (22)’s correlate will fail.

It is then hard to obtain the paradoxical construction as in the case of BLV. For if $F_E(x)$ is not just $\{x\}$ , then it is hard to find an appropriate $\Phi _E$ that will force $@ R$ outside of R in the event that $\neg \Phi _E(Y, F_E(x))$ . For if $F_E(x)$ is not a singleton, then even if $\Phi _E$ is as fine-grained as $\subseteq $ , then failure of $\Phi _E$ can occur when any of the many members of $F_E(x)$ falls outside of Y. As such, even if $@R$ is in $F_E(@R)$ , $F_E(@R)\not \subseteq R$ does not imply that $\neg R(@R)$ .

That is if one can determine Y. Of course, where E is coarser than extensional equality, there will be more than one concept represented by a given abstract. So here again, even if $\Phi _E$ is as fine-grained as subset,

(23) $$ \begin{align} (\forall Z)( E(Y,Z) \rightarrow (F_E(x) \subseteq Z \rightarrow \Phi_E(Y, F_E(x)))) \end{align} $$

might fail. This is what happens with a straightforward attempt to use Russellian diagonalization on NP. From

(24) $$ \begin{align} Rx \leftrightarrow (\exists Y)(x= \S Y \mathbin{\wedge} \{x\}\not \subseteq Y) \end{align} $$

one can easily obtain that $R(\S R)$ , since $\S R = \S (R-\{\S R\})$ whether R is finite or not. No contradiction beckons—not obviously anyway—since there seems not to be a way to obtain something like (23).

None of this is to say that Russellian methods cannot be used to show NP deductively implies a Dedekind finite universe—someone may prove that tomorrow, for all I know. But proofs of this kind have been elusive, and I think this explains why: if one uses only notions like “set and element” or “object and predicate,” it is hard to hit upon just the right $F_E$ and $\Phi _E$ that will ensure that $@R$ falls outside of R in case $\neg \Phi _E(R, F_E(@R) )$ .

This point is interesting in light of the proof given below that NP implies a Dedekind finite universe. That proof uses ordinal notions to generate a contradiction. I have just said that Russellian proofs are hard to find for uniform separations and complementations with $\kappa \neq 1$ , because when $\kappa>1$ , our diagonal constructions lose the degree of control needed for easy exit from the diagonal concept. It is easier to recover at least some of that control if the locus of the contradiction we seek is in ordinal notions, rather than in the logical notion of predication.

This can be seen by imposing the structure of (21) on the Burali–Forti paradox for those ordinal notions. As a first pass consider how to generate the Burali–Forti paradox in second-order logic plus BLV: one would first develop a membership relation $\eta $ between extensions (that is, BLV-abstracts), and then characterize certain abstracts as satisfying some condition $\Psi $ that qualifies them as BLV-ordinals.

(25) $$ \begin{align} Ox \leftrightarrow (\exists Y)(x = \breve{\varepsilon} Y \mathbin{\wedge} \Psi(Y)). \end{align} $$

The usual construction will characterize ordinals as the extensions of concepts that are $\eta $ -transitive and well-ordered by $\eta $ .

This does not look immediately like the kind of construction in (21), but a little massaging shows that it is. For what differentiates $\Psi $ from something like $\Phi _E(Y, F_E(x))$ is the absence of two things: invocation of the equivalence relation E, and a concept determined by the abstract x. However, in the case of (26), this is supplied by theorems in second-order logic about well-orderings. For where $\Psi (Y)$ implies that $(\eta , Y)$ is a well-ordering, it also implies that $\breve {\varepsilon } Y$ does not fall under Y—for otherwise $(\eta , \{y \in Y \mid y \eta (\breve {\varepsilon } Y)\})$ would be an isomorphic proper initial segment of $(\eta , Y)$ . As such, we have (25) is equivalent to

(26) $$ \begin{align} Ox \leftrightarrow (\exists Y)(x = \breve{\varepsilon} Y \mathbin{\wedge} \Psi(Y) \mathbin{\wedge} \{\breve{\varepsilon} Y\} \not\subseteq Y). \end{align} $$

One can thus reproduce the reasoning of the Russell paradox on an ordinal construction by using the fact that $\neg Y(\breve {\varepsilon } Y)$ if $(\eta , Y)$ is a well-ordering, for clearly, aligning with (22), we have

(27) $$ \begin{align} (\forall Z)(Y = Z \rightarrow (\{\breve{\varepsilon} Y \}\subseteq Z \rightarrow \neg(\Psi(Y) \mathbin{\wedge} \{\breve{\varepsilon} Y\}\not \subseteq Y) )). \end{align} $$

Shoehorning the Burali–Forti paradox into Russell’s diagonal form reveals the contrast between the bare Russellian methods and those which use ordinal constructions. The difficulty in using Russellian methods in obtaining Cantorian results from separations with $\kappa> 1$ comes from finding a formula $\Phi _E(Y, F_E(x))$ that satisfies (22). In the case of ordinal constructions, it is not easy, but it is comparatively easier: one needs only to use the at-hand theorems of second-order logic that prohibit well-orderings from being isomorphic to their proper initial segments.

The suggestion of constructing ordinals in turn suggests a format for the proof. In [Reference Kanamori22] (see also [Reference Kanamori, Pincus, Halász, Lovász, Simonivits and Sós23]), Kanamori examines Zermelo’s proof of the Well-ordering Theorem in [Reference Zermelo and van Heijenoort38]. Kanamori’s analysis separates it into two parts:

But Theorem 5 has another curious corollary: a strong version of Cantor’s theorem.Footnote ²³

This proof of Cantor’s Theorem uses the fact that a well-ordered set can be constructed from any function from a power-set to its base set. It is not hard to see that the proof given in [Reference Kanamori22] of Theorem 5 can be adapted to a second-order setting, where abstraction operators take the place of the function $F:P(X)\rightarrow X$ .

However, adaptation of Corollary 7 is more difficult. The problem is that one needs more information about W than is given in the proof of Theorem 5: in particular, that the nature of W depends partly on F (or its correlate, the abstraction operator $\S $ ), and partly on the size of the universe. This is essentially what we do in proving our main result: construct from $\S $ and an infinite universe a well-ordered concept. Our task for the next section, then, is to sketch this proof.

6. An outline of the proof

Given what we have said so far, we can state the main result of this paper as follows:

We will refine the statement of the CLT before proving it; it needs, for example, a more precise statement of the background logic. In any case, it is a direct corollary of CLT that HP, conjoined with either of $\texttt {US(}\omega \texttt {)}$ or $\texttt {UC(}\omega \texttt {)}$ , is inconsistent, since HP deductively implies the universe is Dedekind infinite. (In Section 7 I will discuss the reasons why the proof of this theorem does not easily generalize to $\kappa>\omega $ .)

The case of $\texttt {UC(}\omega \texttt {)}$ reduces to that of $\texttt {US(}\omega \texttt {)}$ (Proposition 10), so all the work of the proof concerns the latter principle.

The first thing to do is to define a relation between nuisances: $\S A \vartriangleleft \S B$ if and only if $B-A$ is finite but $A-B$ is not. Next, if a concept P is infinite and well-ordered by $\vartriangleleft $ , we will say that the nuisance of that concept is a preordinal. Now, in second-order logic, a Dedekind infinite universe allows for the definition of a natural number structure N. The key, then is to show that from this structure we can define nested sequences of concepts with infinite differences. In particular, we show that there is an infinite preordinal $\S \Omega $ , and that given a preordinal p and natural numbers m and k we can define further preordinals $p + n\S \Omega ^k$ . These defined preordinals behave as one would expect: $p + n\S \Omega ^j \vartriangleleft p + m \S \Omega ^k$ for nonzero natural numbers $n\leq m\ \mathrm{and}\ j\leq k$ , with at least one of these inequalities strict (Preordinal Arithmetic 26).

Preordinals are not well-behaved: there are too many distinct preordinals of similar order-type to be well-ordered. However, because of the properties of well-orderings in second-order logic, we can define a relation $\ll $ between preordinals. Modulo a defined equivalence ( $\asymp $ of Definition 16), preordinals satisfy trichotomy with respect to $\ll $ . This then enables us to collect preordinals into concepts containing all and only the $\ll $ -predecessors of a given preordinal p. We designate the nuisance of said concept $O_p$ . The $O_p$ s are, unlike the preordinals themselves, quite well-behaved: they are well-ordered by $\vartriangleleft $ . We therefore may designate these nuisances to be our nuisance ordinals. The construction of the nuisance ordinals gives us a large degree of control over their behavior given the preordinals we use to determine them; in particular, we show in the Ordering Lemma 33 that for preordinals p and q, $p \ll q$ if and only if $ O_p \vartriangleleft O_q$ .

These facts enable us to prove the Translation Lemma 37, according to which two truncations of the nuisance ordinal sequence are isomorphic:

$$ \begin{align*} (\vartriangleleft, Ord_{O_p} + \Omega^n)\cong (\vartriangleleft, Ord_{O_{p+\S \Omega^{n+1}}}).\end{align*} $$

But this in turn enables the definition of an infinite decreasing subsequence of nuisance ordinals: where $Ord$ is the concept containing all and only nuisance ordinals, we have

$$ \begin{align*} \ldots\vartriangleleft O_{\S Ord_{O_{\S Ord_{O_{\S Ord}}}}}\vartriangleleft O_{\S Ord_{O_{\S Ord}}} \vartriangleleft O_{\S Ord}. \end{align*} $$

But this, of course, contradicts the fact that $Ord$ is well-ordered by $\vartriangleleft $ .

7. On the strength of various proof methods

I have endeavored to argue in this paper that it is worth examining the methods of proof used for Cantorian results in the relatively modest setting of second-order logic. With the exception of the full proof (given in Section 8), all that remains to do is to draw some tentative conclusions.

As shown in Section 3.2, Russellian methods work for a large class of semantic Cantorian results. We might say, in light of this, that Russellian methods for semantic Cantorian cardinality results generalize both vertically and horizontally. They generalize vertically in the sense that, the known result that $\texttt {US(}\kappa \texttt {)}$ has no standard model of size at least $\kappa $ remains true as no matter how one varies the parameter $\kappa $ . They generalize horizontally in that the arguments establishing these results for uniform separations easily adapt to establish correlated results for uniform complementations.

Things are less settled when it comes to deductive Cantorian results in second-order logic. Russellian methods certainly work for $\texttt {BLV} = \texttt {US(}1\texttt {)}$ and $\texttt {LCP} = \texttt {UC(}1\texttt {)}$ , so on the lowest level, they generalize horizontally. But do the Russellian methods apply deductively for anything other than $\kappa = 1$ ? This is anybody’s guess, but I have given reasons in Section 5 to think that such proofs are not among the low-hanging fruit.

On the other hand, what I have called Burali–Fortian methods—those that construct well-orderings—generalize both horizontally and, to a degree, vertically. With the usual construction described in Section 5, one can prove BLV inconsistent using the regular Burali–Forti paradox. This method generalizes horizontally, since one can adapt this proof as we adapted the Russellian method in Proposition 1: copy that proof until construction of the diagonal concept R, and instead define the relation $\eta ^*$ so that for abstracts a and b in $V'$ , $a\eta ^* b$ holds just if there is a concept $B\subseteq V'$ with $Ba$ ; the ordinals are then constructed as usual with the relation $\eta ^*$ . The proof of CLT shows that in fact the Burali–Fortian method generalizes vertically from $\texttt {US(}1\texttt {)}$ to $\texttt {US(}\omega \texttt {)}$ , and horizontally from $\texttt {US(}\omega \texttt {)}$ to $\texttt {UC(}\omega \texttt {)}$

I have said that these results may reveal connections between Cantorian cardinality results and the availability of well-orderings. It is tempting in such a context—especially since a Russellian proof of these results is presently unavailable—that the core explanation of the Cantorian phenomena is something to do with well-orderings. But such an assertion would be rash. Even if Russellian proofs are permanently unavailable, such a claim would be unwise in the absence of a more considered account of what makes a mathematical explanation the right one. Having not examined these, I refrain from the more robust conclusion.

These considerations, however, raise further questions about a general Cantorian result. For what we will have shown with CLT is in effect the result that for all $\kappa \leq \omega $ , if $|X\triangle Y|<\kappa $ is an equivalence relation, then:

(28) $$ \begin{align} \texttt{US(}\kappa\texttt{)} &\vdash_{SOL} |V|<\kappa & \texttt{UC(}\kappa\texttt{)} &\vdash_{SOL} |V|<\kappa. \end{align} $$

The natural generalization is that (28) holds for all the various $\kappa $ that can be characterized in second-order logic. But this question is open. In the proof of CLT we used the existence of Dedekind injections (Section 8.2.1)—essentially the fact that any concept X of size $\geq \omega $ is the union of two concepts, one the same size as X and the other of size $\omega $ . But the decomposition of sets of higher cardinalities is not guaranteed in the absence of choice-like principles (such as the existence of a pairing injection). As is shown in [Reference Creed and Truss10], ZF admits models with quasi-amorphous sets: uncountable sets that are not the union of two disjoint uncountable sets, and such that every uncountable subset contains a countably infinite subset. So for uncountable $\kappa $ , one could not help oneself to the analogue of Dedekind injections, and so cannot follow the same method to construct $\texttt {US(}\kappa \texttt {)}$ -ordinals as we construct the nuisance ordinals in Sections 8.3–8.7.

8. Proving the CLT

8.1. Second-order logic

To state CLT more clearly, we need to be more specific about what is meant by “full second-order logic.” I will assume general familiarity with second-order languages and second-order logic; the real question is in specifying what is meant by “full.” As for expressions of the language, I am going to abuse notation and use both $Xt$ and $t\in X$ to mean the predication of a monadic second-order term X of a first-order term t.Footnote ²⁴ The language of pure second-order logic contains first- and second-order variables, the latter taking all finite arities, as well as the usual logical vocabulary “ $($ ,” “ $)$ ,” “ $\forall ,$ ” “ $\neg ,$ ” “ $\vee ,$ ” and “ $=,$ ” where “ $=$ ” means identity of objects. However, I will abuse notation to use “ $=$ ” also to mean coextensiveness of concepts so that “ $X=Y$ ” will mean $(\forall z)(Xz \leftrightarrow Yz)$ as in (1).

A concept (or relation) X is said to be Dedekind infinite if there is an injection $f:X\rightarrow X$ such that $f(X)\neq X$ . A concept is (Dedekind) finite just if there is no such injection. Though it is an abuse of notation, I will use $|X|<\omega $ to mean X is Dedekind finite, and $|X|\not < \omega $ to mean X is Dedekind infinite. In what follows, “infinite” just means “Dedekind infinite.”

One can find in [Reference Shapiro29, Section 3.2, p. 108] a deductive system $D2^*$ for second-order languages that is complete for the Henkin semantics; it is worth noting that this does not include any “axioms of choice” as part of our background logic. But in addition to the usual axioms governing quantifiers, identity, and logical connectives, we do include the axioms that make second-order logic “full” for a language. These are the comprehension axioms for every formula $\Phi (\bar X, \bar x)$ of that language; namely axioms of the form:

(29) $$ \begin{align} (\forall \bar X) (\exists Z)(\forall \bar x)(Z\bar{x} \leftrightarrow \Phi(\bar{X},\bar{x}). \end{align} $$

It is therefore somewhat misleading to state CLT as we have above: it is not that we are “adding” abstraction principles to pure, full, second-order logic; rather, we are adding the abstraction principles to a second-order theory that includes comprehension axioms for all formulae of the language of that theory—including those formulae in which the abstraction operator appears.

Let us then give names to these second-order theories. Abusing our notation somewhat, let us call $\texttt {US(}\omega \texttt {)}$ the second-order theory which includes $\texttt {US(}\omega \texttt {)}$ (that is, NP) as an axiom in addition to the usual axioms governing quantifiers, identity, and logical connectives, plus comprehension axioms for all formulas including those in which the abstraction operator $\S $ appears. (Likewise for $\texttt {UC(}\omega \texttt {)}$ .)

We aim to show that $\texttt {US(}\omega \texttt {)}$ (respectively, $\texttt {UC(}\omega \texttt {)}$ ) deductively implies $|V|<\omega $ (that the universal concept is Dedekind finite); to do this it will suffice to show that the theory $\texttt {US(}\omega \texttt {)}+ |V|\not <\omega $ (respectively for $\texttt {UC(}\omega \texttt {)}$ ) is deductively inconsistent. We will abbreviate these theories $\texttt {US(}\omega \texttt {)}^\omega $ and $\texttt {UC(}\omega \texttt {)}^\omega $ .

A more precise version of the CLT , can now be stated by:

Theorem 8. The theories $\texttt {US(}\omega \texttt {)}^\omega $ and $\texttt {UC(}\omega \texttt {)}^\omega $ are inconsistent.

8.2. Cardinality and arithmetic in second-order logic with infinity

I will now review some results we need; these are all provable in what we have called “second-order logic.”

Schröder-Bernstein Theorem SBT. If there are injections $f:A\rightarrow B$ and $g:B\rightarrow A$ , then there is a bijection $h:A\rightarrow B$ . That is, if $|A|\leq |B|$ and $|B|\leq |A|$ then $|A|=|B|$ . (The interested reader can find a proof in [Reference Shapiro29, Theorem 5.2, p. 102].)

Injections and bijections are measures of the relative cardinality of different concepts and relations. The addition of an axiom of infinity provides more resources for dealing with concepts of cardinality corresponding to the natural numbers. In particular, as Dedekind shows,Footnote ²⁵

Interpretation of Peano Arithmetic IPA. If there is an infinite concept, then there are a concept N, an object $0$ , a function $s:N\rightarrow N$ , and a relation $<$ , such that:

• • $(N, 0, s)$ interpret the five Dedekind-Peano axioms,

• • N is infinite and injects into every infinite concept,

• • $(<, N)$ is a well-ordering, and

• • One can define relations $sum(x,y,z)$ and $mult(x,y,z)$ in $(N, 0, s)$ that are provably functional and satisfy the recursion axioms, respectively, for addition and multiplication (relativized to N), which we state in functional notation:

  (30) $$ \begin{align} (\forall x\in N)(x+0&=x) & (\forall x, y\in N)(x +s(y) &= s(x+y)), \end{align} $$
  (31) $$ \begin{align} (\forall x\in N)(x \cdot 0 &= 0)& (\forall x, y\in N)(x \cdot s(y)& = (x\cdot y)+ y). \end{align} $$

We will be working in a theory that assumes the existence of an infinite concept, so throughout the remainder of this proof we will use “ $N,$ ” “ $0,$ ” “ $s,$ ” and “ $<$ ” to be arbitrarily selected so as to satisfy IPA . We will also continue to use functional notation for addition and multiplication. Moreover, since N is well-ordered and satisfies induction, every function definable by recursion exists in $\texttt {US(}\omega \texttt {)}$ ; we will therefore also help ourselves to exponentiation, again to be expressed in the usual functional notation (by $x^y$ ).

One consequence of IPA we will use below is worth stating by itself, as we will use it in Section 8.4:

Proposition 9. There is a bijection $\pi :N\rightarrow N\times N$ , and functions $\pi _1, \pi _2:N\rightarrow N$ such that $\pi (n)= (\pi _1(n), \pi _2(n))$ .

8.2.1. Dedekind injections

For X an infinite concept, say that $d_X:X\rightarrow X$ is a Dedekind injection for X just if $d_X$ is an injection and $|X- d_X(X)|\geq \omega $ .

Existence of Dedekind Injections EDI. If X is infinite, then there is a Dedekind injection for X. That is, if X is an infinite concept, there is a $d:X\rightarrow X$ such that $X-d(X)$ is Dedekind infinite, or equivalently, $|X-d(X)|\geq |N|$ .

We will really need just one Dedekind injection, so we fix one here for the rest of this section, and designate it “ $d.$ ” For simplicity we will also assume that $N\subseteq V-d(V)$ .

The existence of Dedekind injections will be crucial to the proof of the main result of this paper, but it has an immediate consequence that vastly simplifies our work. The proof given below to establish Theorem 8 shows the inconsistency of $\texttt {US(}\omega \texttt {)}^\omega $ . The following proposition shows that this is sufficient to prove Theorem 8:

Proposition 10. If $\texttt {UC(}\omega \texttt {)}^\omega $ is consistent then so is $\texttt {US(}\omega \texttt {)}^\omega $ .Footnote ²⁶

Proof. Let $\mathcal M \models \texttt {UC(}\omega \texttt {)}^\omega $ , with $\chi $ the abstraction operator. Let $f:V \rightarrow V$ be a Dedekind injection in $\mathcal M$ .

If $|X\triangle Y|<\omega $ , then as f is injective $|f(X)\triangle f(Y)|<\omega $ , and thus $\chi f(X) = \chi f(Y)$ by $\texttt {UC(}\omega \texttt {)}$ .

Conversely, assume $|X\triangle Y|\not < \omega $ . As f is injective, $|f(X)\triangle f(Y)|\not < \omega $ . Now notice first that $V-f(V)\subseteq V-f(Y)$ , second that $|V-f(V)|\not < \omega $ , and third that $(V-f(V)) \cap f(X) = \varnothing $ . It follows that $|f(X) \triangle (V-f(Y))| \not < \omega $ . By $\texttt {UC(}\omega \texttt {)}$ it follows that $\chi f(X) \neq \chi f(Y)$ .

So we have shown that

(32) $$ \begin{align} (\forall X)(\forall Y)(\chi f(X) = \chi f(Y) \leftrightarrow |X\triangle Y|<\omega). \end{align} $$

Set $\sigma X = \chi f(X)$ for each concept X in $\mathcal M$ ; and let model $\mathcal M'$ be the model extending $\mathcal M$ with the abstraction operator $\sigma $ . As $\sigma $ is definable in $\mathcal M$ , the concepts and relations of $\mathcal M'$ are exactly those of $\mathcal M$ ; namely f is in $\mathcal M'$ . Thus $\mathcal M'$ satisfies $\texttt {US(}\omega \texttt {)}^\omega $ .Footnote ²⁷ □

It therefore suffices in the below to show $\texttt {US(}\omega \texttt {)}^\omega $ inconsistent.

8.2.2. Well-orderings

We also have at our disposal several results concerning well-orderings. A binary relation R on X is said to be a well-ordering of X (abbreviated $WO(R,X)$ ) just if R linearly orders X and for every non-empty $Y\subseteq X$ , there is an R-least object falling under Y. Given $R, S, X$ , and Y with $WO(R, X)$ and $WO(S, Y)$ , we write $(R,X)\leq (S,Y)$ to mean that there is an order-isomorphism $i:X\rightarrow Y$ where $i(X)$ is an initial segment of Y. (Context will make clear when “ $\leq $ ” and its derivatives indicate relative cardinality, the well-ordering of N, or isomorphism to a proper initial segment of a well-ordering.) If $i(X) = Y$ we write $(R,X)\cong (S,Y)$ ; if $i(X)$ is a proper initial segment of Y, we will write $(R,X)<(S,Y)$ ; and when needed we will indicate the witnessing isomorphism by superscripting, as in “ $(R,X)\stackrel {i}{<}(S,Y)$ .”

All of this is expressible in second-order logic, and the following is a theorem of second-order logic.

Order Isomorphism Theorem OIT. For any well-orderings $(R, X)$ and $(S, Y)$ , exactly one of

(33) $$ \begin{align} (R,X)&< (S,Y) & (R,X)&\cong (S, Y) & (R,X)&> (S, Y) \end{align} $$

obtains. Moreover, the witnessing isomorphisms are unique.

Further, no well-ordering is isomorphic to a proper initial segment of itself: $(R,X)\not <(R,X)$ .

The theorem OIT has the nice consequence that well-orderings are themselves “well-ordered” in the following sense:

Well-orderings of Well-orderings WOWO. Let $\varphi (R, X)$ be a formula. The following is a theorem of second-order logic:

(34) $$ \begin{align} (\exists R, X)(WO(R,X) &\mathbin{\wedge} \varphi(R,X) \rightarrow {} \nonumber\\ &\quad(\exists S, Y)(WO(S,Y) \mathbin{\wedge} \varphi(S, Y) \mathbin{\wedge} {} \nonumber\\ &\quad(\forall R,X)(WO(R,X) \mathbin{\wedge} \varphi(R,X) \rightarrow (S,Y)\leq (R,X)))). \end{align} $$

In words: If there is a well ordering R of X such that $\varphi $ holds of R and X, then there is a $<$ -least well-ordering of some S and Y such that $\varphi $ holds of S and Y. The proof is left as an exercise to the reader.

We will also use the fact that in second-order logic, one can define functions and relations by recursion on well-ordered concepts. In particular, we will use recursion on the well-ordering $(<,N)$ .

Definition by Recursion DBR. Let $g, h:N^k \rightarrow N$ be functions, $S(\overline x)$ be a k-ary relation, and $\Phi (R, S, y, \overline x)$ be a formula with $k+1$ -ary relation variable R and k-ary relation variable S free, and $y, \overline x$ be $k+1$ free variables. Then the equations in (35) suffice to define a function $f:N^{k+1}\rightarrow N$ , and the equations in (36) suffice to define a $k+1$ -ary relation R.

(35) $$ \begin{align} f(0, \overline n) & = g(\overline n) & f(m+1, \overline n)& = h(f(m, \overline n), g(\overline n)), \end{align} $$

(36) $$ \begin{align} R(0, \overline n) &\Leftrightarrow S(\overline n) & R(m+1, \overline n) & \Leftrightarrow \Phi(R(m, \overline n), S(\overline n)). \end{align} $$

Finally, we make the following observations:

Proposition 11. Let $(R, X)$ be a well-ordering and let X be finite. Then $(R,X) < (<,N)$ .

Proof. If $(R, X) \geq (<,N)$ then X is infinite, so the result follows by OIT .□

8.3. Preordinals

Our construction thus begins by defining a privileged relation $\vartriangleleft $ , which I will call “subvention.” In what follows, we will take “ $\S $ ” as the abstraction operator for $\texttt {US(}\omega \texttt {)}$ , as in (4).

Definition 12. For all $\S X, \S Y\in \mathrm {rng}(\S )$ :

(37) $$ \begin{align} \S X \vartriangleleft \S Y \Leftrightarrow (\forall X', Y')(\S X &= \S X' \mathbin{\wedge} \S Y = \S Y' \rightarrow {} \nonumber\\ &\qquad|X'-Y'|<\omega \mathbin{\wedge} |Y'-X'|\geq \omega). \end{align} $$

The subvention relation $\vartriangleleft $ has certain desirable properties:

Proposition 13. First, if $\S X = \S Y$ , then

(38) $$ \begin{align} (\forall Z)(\S X \vartriangleleft \S Z \leftrightarrow \S Y \vartriangleleft \S Z), \end{align} $$

(39) $$ \begin{align} (\forall Z)(\S Z \vartriangleleft \S X \leftrightarrow \S Z \vartriangleleft \S Y). \end{align} $$

Thus $\vartriangleleft $ holds independently of the concept X determining the abstract $\S X$ .

Proposition 14. If $f:X\cup Y \rightarrow V$ is an injection and $Z \cap f(X) = \varnothing $ , then:

(40) $$ \begin{align} \S X \vartriangleleft \S Y \leftrightarrow \S (Z \cup f(X)) \vartriangleleft \S (Z \cup f(Y)). \end{align} $$

Proposition 15. The relation $\vartriangleleft $ is irreflexive and antisymmetric.

Definition 16. An abstract $\S X$ is a preordinal ( $\S X \in POrd$ ) if and only if there is an infinite $Y\subseteq \mathrm {rng}(\S )$ with $\S Y = \S X$ such that $WO(\vartriangleleft , Y)$ .

If $p, q$ are preordinals, we will say that $p \asymp q$ just if $\S P = p, \S Q= q$ such that $(\vartriangleleft , P)$ and $(\vartriangleleft , Q)$ are well-orderings and $(\vartriangleleft , P)\cong (\vartriangleleft , Q)$ .

8.4. Countable preordinals in $\texttt {US(}\omega \texttt {)}^\omega $

The collection of preordinals is interesting in $\texttt {US(}\omega \texttt {)}^\omega $ only if there is an infinite preordinal. Think for a moment how one would show, in ZF, that there is an infinite collection of well-ordered nested subsets, each differing infinitely from its predecessors. Two sequences can be generated in ZF that satisfy these desiderata: the sequences $\omega , 2 \omega , 3\omega , \ldots $ and $\omega , \omega ^2, \omega ^3, \ldots $ . Both because they provide infinite preordinals, and because we will need them later to control certain constructions, we will show in this section how to get preordinals of these order-types.

Our first task will be to define preordinals $\Omega ^k$ , for each k in N. These are the preordinal surrogates for the ordinals $\omega ^k$ appearing in ZF.

To begin, we can define a relation on N recursively as follows:

(41) $$ \begin{align} R(0, n,m) & \Leftrightarrow n<m, \end{align} $$

(42) $$ \begin{align} R(k+1, n,m) & \Leftrightarrow R(k, \pi_1(n), \pi_1(m)) \vee (\pi_1(n)=\pi_1(m) \mathbin{\wedge} \pi_2(n)<\pi_2(m)). \end{align} $$

The relation R can be considered as the dictionary ordering on its second and third parameters n and m, while the first parameter k determines that they will be treated as $k+1$ -tuples. Since $R(k, \cdot , \cdot )$ is the dictionary-order for $k+1$ -tuples, we will henceforth write $R(k,n,m)$ by $n<_{k+1} m$ . So, for example, $n<_3 m$ holds just if n is less than m in the dictionary order when n and m are decoded as triples.

We now define another sequence of relations. Informally, start with N under the well-ordering $<_k$ . Now notice that for $m_1< m_2$ , the concepts

(43) $$ \begin{align} \pi^{-1}(m_1, N)& = \{ \pi^{-1}(m_1, n)\mid n\in N\} \end{align} $$

(44) $$ \begin{align} \pi^{-1}(m_2, N)& = \{ \pi^{-1}(m_2, n)\mid n\in N\} \end{align} $$

are disjoint and infinite. Thus, if $n_1<n_2$ , we have that

(45) $$ \begin{align} \bigcup_{m<_kn_1} \pi^{-1}(m,N) \subset \bigcup_{m<_kn_2} \pi^{-1}(m,N) \end{align} $$

with an infinite difference. We can collect the nuisances of the unions listed in (45) into a single concept, designated $\Omega ^k$ . More formally:

Definition 17. Define $\Omega ^k(x)$ by

(46) $$ \begin{align} \Omega^k(x) \Leftrightarrow (\exists Y)(x = \S Y \mathbin{\wedge} (\forall y)(Yy\leftrightarrow(\exists n,m\in N)(m<_k n \mathbin{\wedge} \pi_1(y) = m))). \end{align} $$

Equivalently,

(47) $$ \begin{align} \Omega^k = \left\{ \S \left( \bigcup_{m<_kn} \pi^{-1}(m,N) \right) \mid n\in N \right\}, \end{align} $$

where $(m,N) = \{ (m,z)\in N\times N \mid z\in N \}$ . We stipulate that $\Omega ^0 = \varnothing $ .

The concept $\Omega ^k$ is constructed to have the same structure under $\vartriangleleft $ as N under the ordering $<_k$ :

Ω ^k -Well-Ordering Lemma 18. For each $k>0$ , $(\vartriangleleft , \Omega ^k) \cong (<_k, N)$ . Thus each $(\vartriangleleft , \Omega ^k)$ is a well-ordering.

Proof. We proceed by induction; let $k = 1$ . Let $F^1:N \rightarrow \Omega $ be defined by

(48) $$ \begin{align} F^1(n) = \S \left( \bigcup_{j <n} \pi^{-1}(j,N) \right). \end{align} $$

Clearly $F^1$ is a bijection; to see it is an isomorphism it is enough to show

(49) $$ \begin{align} m<n \rightarrow F^1(m) \vartriangleleft F^1(n). \end{align} $$

For (49) implies its converse, since if $m\not <n$ then either $n=m$ or $n<m$ . If the former, $F^1(m)\not \vartriangleleft F^1(n)$ by the irreflexivity of $\vartriangleleft $ , and if the latter, $F^1(m)\not \vartriangleleft F^1(n)$ by (49) and the antisymmetry of $\vartriangleleft $ .

Towards (49), observe that if $m<n$ , then

(50) $$ \begin{align} \left( \bigcup_{j <m} \pi^{-1}(j,N) \right) \subset \left( \bigcup_{j <n} \pi^{-1}(j,N) \right) \end{align} $$

with $\pi ^{-1}(m,N)$ an infinite subset of the difference. Thus $F^1(m)\vartriangleleft F^1(n)$ .

Assume now that $(\vartriangleleft , \Omega ^k)\stackrel {F^k}\cong (<_k, N)$ , and consider $(\vartriangleleft , \Omega ^{k+1})$ . Define $\lessdot $ to be a relation on $N \times N$ by

(51) $$ \begin{align} (a, m) \lessdot (b, n) \Leftrightarrow a <_k b \vee (a = b \mathbin{\wedge} m<n). \end{align} $$

Clearly $(\lessdot , N\times N)\stackrel {i}\cong (<_{k+1}, N)$ , so it will suffice to show that $(\lessdot , N\times N)\cong (\vartriangleleft , \Omega ^{k+1})$ . Define $F^{k+1}:N \times N \rightarrow \Omega ^{k+1}$ by

(52) $$ \begin{align} F^{k+1}(b,n) = \S \left( \bigcup_{(a,m)\lessdot(b,n)} \pi^{-1}( i((a,m), N)) \right), \end{align} $$

where $(i(a,m),N) = \{ (i(a,m), x)\mid x\in N \}$

As in the case of (49), it is enough to show

(53) $$ \begin{align} (a, m) \lessdot (b, n) \rightarrow F^{k+1}(a,m) \vartriangleleft F^{k+1}(b,n) \end{align} $$

since, like (49), (53) proves its converse.

But clearly if $(a,m)\lessdot (b,n)$ then

(54) $$ \begin{align} \left( \bigcup_{(c,j) \lessdot (a,m)} \pi^{-1}(i(c,j),N) \right) \subset \left( \bigcup_{(c,j) \lessdot(b,n)} \pi^{-1}(i(c,j),N) \right). \end{align} $$

Moreover, $\pi ^{-1}(i(a, m), N)$ is an infinite subset of the difference. So again, $F^{k+1}(a,m) \vartriangleleft F^{k+1}(b,n)$ , as required.□

In addition to the above exponential expansion of the preordinal $\S \Omega $ , we will need to be able to multiply these preordinals by natural numbers—allowing us to obtain preordinals that behave like the set-theoretic ordinals $m\omega $ and $m \omega ^k$ . These ordinals, of course, behave like $N^m =\underbrace {N\times \cdots \times N}_m$ and $(N^k)^m=\underbrace {N^\times \cdots \times N^k}_m$ under their respective dictionary orderings. If we were working in a normal set-theoretic environment, we would consider $N^m$ and $(N^k)^m$ with the sets

$$ \begin{align*}\{(n,j)\in N\times N \mid j\leq m \}\subseteq N\times N\end{align*} $$

and

$$ \begin{align*}\{(n,j)\in N^k\times N \mid j\leq m \}\subseteq N^{k+1},\end{align*} $$

respectively. Under their respective dictionary orderings, these are order-isomorphic to $m\omega $ and $m\omega ^k$ .

The next construction gives us these preordinal surrogates, but using the ordering $<_{k+1}$ of N so that N behaves like $N^{k+1}$ . It is then easily obtainable by the $\Omega ^k$ -Well-Ordering Lemma 18. Let

(55) $$ \begin{align} N_m = \{n \in N \mid \pi_2(n) \leq m \} \end{align} $$

and consider $N_m$ under the ordering $<_{k+1}$ . Clearly $(<_{k+1}, N_m) <(<_{k+1}, N)$ for each m. The embedding $e_m^{k+1}$ witnessing this is unique, as is the isomorphism $i^{k+1}$ witnessing $(<_{k+1}, N)\cong (\vartriangleleft , \Omega ^{k+1})$ . Thus we may give the following:

Definition 19. For $k, m>0$ , let

$$ \begin{align*}(m+1) \Omega^k = \{i^{k+1}(e^{k+1}_m(n))\mid n\in N_m \}.\end{align*} $$

We stipulate that $0\Omega ^k = \varnothing $ .

Set $m \S \Omega ^k = \S (m\Omega ^k)$ .

It follows now by the construction of $m \S \Omega ^k$ :

Corollary 20. For each $k,m\in N$ with $k,m>0$ , $m\S \Omega ^k$ is a preordinal. Clearly, as well, for each $w \in m\Omega ^k$ , there is a $W\subseteq N$ with $w = \S W$ .

Further, if $(R, X)$ is a well-ordering and $(\vartriangleleft , m\Omega ^k)<(R, X)$ for all m, then $(\vartriangleleft , \Omega ^{k+1}) \leq (R, X)$ .

8.5. Preordinal addition and the “move over” construction

The next task is to define functions on preordinals, which we will call “Addition by $\S m\Omega ^k$ .” Again, recall from Section 8.2.1 that d is a Dedekind injection, and we assume $N\subseteq V-d(V)$ .

We need to show that for any $k,m\in N$ and for any preordinal p, the expression $p+\S m\Omega ^k$ determines a unique preordinal. Because (as we shall see in Proposition 27) distinct preordinals may be the nuisances of $\vartriangleleft $ -isomorphic concepts, we will also need to show that if $\S P$ and $\S Q$ are distinct preordinals with $p \asymp q$ , then $p+m\S \Omega ^k \asymp q + m\S \Omega ^k$ .

The method of defining addition by $\S \Omega ^k$ could be called the “move-over” construction: the selected Dedekind injection d “moves over” all of V to make room for countable concepts.

Definition 21. We will say that a concept Q is numerically based if for each $w\in Q$ , there is a $W\subseteq N$ with $w = \S W$ . Further, if q is a preordinal, we will say that it is numerically based just if there is a numerically based Q such that $(\vartriangleleft , Q)$ is a well-ordering and $q = \S Q$ .

Definition 22 (The “move over” construction)

Let $(\vartriangleleft , P)$ be a well-ordering with $P\subseteq \mathrm {rng}(\S )$ , and $(\vartriangleleft , U)$ a well-ordering with U numerically based. Then define

(56) $$ \begin{align} P+U = \{ \S d(Q) \mid \S Q \in P\} \cup \{\S (d(V)\cup W)\mid \S W \in U \; \text{and}\; W\subseteq N\}. \end{align} $$

The Dedekind injection “moves over” the concepts Q and V so that each $d(Q)$ , and $d(V)$ , are disjoint from each infinite $W\subseteq N$ :

(57) $$ \begin{align} d(Q) \cap W & = \varnothing & d(V)\cap W & = \varnothing. \end{align} $$

This ensures that $\S d(Q) \vartriangleleft \S (d(V)\cup W)$ for each such W. Moreover, if $\S W \vartriangleleft \S W'$ with $\S W, \S W'\in U$ , then (57) requires that $\S (d(V)\cup W) \vartriangleleft \S (d(V)\cup W')$ .

Finally, it is easy to see that $P+U$ does not vary according to the choices of Q and W for $\S Q\in P$ and $\S W \in U$ . For if $\S Q' = \S Q$ , clearly then $\S d(Q) = \S d(Q')$ . If $\S W' = \S W$ , then as $W \triangle W'$ is finite, $(d(V)\cup W) \triangle (d(V) \cup W')$ will also be finite (again by (57)).

Proposition 23. Let $(\vartriangleleft , P), (\vartriangleleft , Q)$ be well-orderings with $\S P = \S Q$ . Then for each $k,m\in N$ , $\S (P+ m\Omega ^k) = \S (Q + m\Omega ^k).$

Proof. Clearly $(\vartriangleleft , P\cap Q)$ is a well-ordering and $\S (P\cap Q) = \S P = \S Q$ . By the construction of $P+m\Omega ^k$ and $Q+m\Omega ^k$ , $\S (P+m\Omega ^k) = \S ((P\cap Q)+ m\S \Omega ^k) = \S (Q+m\Omega ^k)$ .□

Definition 24. Given Proposition 23, we may define: for a given preordinal p, let $p+m\S \Omega ^k = \S (P+m\Omega ^k)$ for each $k,m\in N$ .

Proposition 25. Let $p, q$ be preordinals with $p \asymp q$ . Then for each $k,m\in N$ , $p \vartriangleleft p + \S m\Omega ^k \asymp q + m\S \Omega ^k$ .

Proof. That $p\vartriangleleft p+m\S \Omega ^k$ follows from the construction of $p + m\S \Omega ^k$ .

As $p \asymp q$ , let $p = \S P, q = \S Q$ and $(\vartriangleleft , P) \cong (\vartriangleleft , Q)$ be well-orderings. It is easy to see then that $(\vartriangleleft , P+m\Omega ^k) \cong (\vartriangleleft , Q+ m\Omega ^k)$ , and thus that $p + m\S \Omega ^k = q + m\S \Omega ^k$ .□

At last we obtain the distilled essentials we will need from preordinal addition:

Preordinal Arithmetic 26. Let p be any preordinal and $j,k, m,n\in N$ with $0<j<k$ and $0<n<m$ . Then:

(58) $$ \begin{align} \S \Omega^j &\vartriangleleft n\S \Omega^j \vartriangleleft m\S \Omega^j \vartriangleleft \S \Omega^k, \end{align} $$

(59) $$ \begin{align} p+ \S \Omega^j &\vartriangleleft p+ n\S \Omega^j \vartriangleleft p+m\S \Omega^j \vartriangleleft p+ \S \Omega^k. \end{align} $$

Proof. The first, (58), is an immediate consequence of the $\Omega ^k$ -Well-Ordering Lemma 18: it follows from the fact that

$$ \begin{align*}(<_j, N^j) < (<_{j+1}, N^{j+1}_n) < (<_{j+1}, N^{j+1}_m) < (<_{k}, N^k).\end{align*} $$

The next, (59), then follows from (58) and the construction of $p+q$ , where q is numerically based. Note that $m\S \Omega ^j$ , etc., are by construction numerically based.□

We will conclude with another result of the “move over” construction, which will be important for the transition from preordinals to full-blown nuisance ordinals.

Proposition 27. Let p be a preordinal. There are infinitely many preordinals q such that $p \asymp q$ .

Proof. Let $(\vartriangleleft , P)$ be a well-ordering and $\S P = p$ ; again let d be our designated Dedekind injection. Now define, for each $k\in N$ :

(60) $$ \begin{align} 2^kN = \{ 2^k n \mid n \in N\}. \end{align} $$

Observe that for distinct $j<k\in N$ ,

(61) $$ \begin{align} 2^jN &\subset 2^kN & |2^kN-2^jN| \not < \omega. \end{align} $$

Thus, set

(62) $$ \begin{align} P^k = \{ \S (d(Q)\cup 2^kN)\mid \S Q\in P\}. \end{align} $$

The arguments given following Definition 22 and in proving Proposition 23 show that each $\S P^k$ is uniquely determined and that $p \asymp \S P^k$ for each k. Further, by (61), $\S P^j \vartriangleleft \S P^k$ for $j<k$ , so $\S P^j \neq \S P^k$ by the asymmetry of $\vartriangleleft $ .□

8.6. The relation $\ll $

The astute reader may have complained up until now, in the back of her mind, that “preordinals” are rather ill-behaved for our purposes: for in ZF, a set which represents one order type is distinct from the set which represents any other. This is because sets are distinguished extensionally, and so if, e.g., $\omega $ differs from $\omega + 1$ (as it does) by just one element, then $\omega \neq \omega +1$ .

But this is not the case for preordinals as we have defined them, since preordinals are nuisances, and nuisances are differentiated by infinite difference between the concepts they represent. As such, consider that $(\vartriangleleft , \Omega )$ is (in ZF) of order-type $\omega $ , while $(\vartriangleleft , \Omega \cup \{\S N\})$ is of order-type $\omega + 1$ . However, since $\Omega \triangle (\Omega \cup \{\S N\}) = \{\S N\}$ , the nuisances of these two concepts are identical: $\S \Omega = \S (\Omega \cup \{ \S N\})$ .

But we need not give up hope. Our goal is to generate the Burali–Forti paradox, and it will be enough if we can generate a theory of nuisance ordinals based on infinite differences between order-types. For this reason, define the following relation:

Definition 28. Let $p, q$ be preordinals. Then we say that $p \ll q$ if and only if there are $P, Q$ such that $p = \S P$ and $q = \S Q$ with $(\vartriangleleft , P) \stackrel {i}< (\vartriangleleft , Q)$ and $|Q-i(P)|\not < \omega $ .

Notice that the relation $\ll $ is well-defined:

Proposition 29. If $p = \S P = \S P'$ and $q = \S Q = \S Q'$ , then the following two either both obtain or both fail:

(63) $$ \begin{align} (\vartriangleleft, P) &\stackrel{i}< (\vartriangleleft, Q) , & |Q-i(P)|& \not < \omega, \end{align} $$

(64) $$ \begin{align} (\vartriangleleft, P') &\stackrel{i'}< (\vartriangleleft, Q') , & |Q'-i'(P')|& \not < \omega. \end{align} $$

Proof. We will just prove one case to give a flavor for how to proceed: As $P, P'$ and $Q, Q'$ are all well-ordered by $\vartriangleleft $ , suppose

(65) $$ \begin{align} (\vartriangleleft, P)& \stackrel{j}<(\vartriangleleft, P'), \end{align} $$

(66) $$ \begin{align} (\vartriangleleft, Q)& \stackrel{j'}<(\vartriangleleft, Q'). \end{align} $$

Since $\S P = \S P'$ , $P'-j(P)$ is finite. Since it is moreover well-ordered, by Proposition 11, $(\vartriangleleft , P'-j(P)) < (\vartriangleleft , \Omega ) \leq (\vartriangleleft , Q- i(P))$ since $(<,N) \cong (\vartriangleleft , \Omega )$ . So assuming (63), let k witness $(\vartriangleleft , P'-j(P)) < (\vartriangleleft , Q-i(P))$ .

Then the homomorphism $i'$ in (64) is witnessed by

(67) $$ \begin{align} i'(x) = \begin{cases} i(x) & x \in P, \\ j'(k(x)) & x \in P'-j(P). \end{cases} \end{align} $$

□

Proposition 30. For $\S P, \S Q$ preordinals with $(\vartriangleleft , P)$ and $(\vartriangleleft , Q)$ well-orderings, if $\S P \not \ll \S Q$ and $\S Q \not \ll \S P$ then $\S P \asymp \S Q$ .

Proof. Suppose by WOWO that $(\vartriangleleft , P)\stackrel {i}{<}(\vartriangleleft , Q)$ . As $\S P \not \ll \S Q$ , $Q - i(P)$ is finite. Thus $\S Q = \S i(P)$ . But clearly $(\vartriangleleft , P ) \cong (\vartriangleleft , i(P))$ . If $(\vartriangleleft , P)>(\vartriangleleft , Q)$ the argument is the same.□

Adding the relation $\ll $ allows us to state more facts about preordinal addition:

Preordinal Arithmetic 31. Let p be any preordinal and $j,k, m,n\in N$ with $0<j<k$ and $0<n<m$ . Then:

(68) $$ \begin{align} n\S \Omega^j & \ll m\S \Omega^j \ll \S \Omega^k, \end{align} $$

(69) $$ \begin{align} p+ n\S \Omega^j & \ll p+ m\S \Omega^j \ll p+ \S \Omega^k. \end{align} $$

Proof. Like (58), (68) follows from the constructions of $m\Omega ^j$ and $\Omega ^k$ ; for by the $\Omega ^k$ -Well-Ordering Lemma 18, $n \Omega ^j$ , $m\Omega ^j$ , and $\Omega ^k$ are respectively isomorphic to the structures in the sequence:

(70) $$ \begin{align} (<_{j+1}, N^j_n)<(<_{j+1}, N^j_m)<(<_k,N^k) \end{align} $$

with an infinite remainder in each case—in fact, remainder on the left is isomorphic to $(<, N)$ , and on the right isomorphic to $(<_{k-j}, N^{k-j})$ .

The equation (69) follows from (68) and the construction of $p+m\S \Omega ^j$ , etc.□

8.7. Nuisance ordinals

As mentioned above, we will define nuisance ordinals as concepts of preordinals.

Definition 32. Say that x is a nuisance ordinal (which we will write with “ $x\in Ord$ ”) just if there is a preordinal p such that $x = \S \{q \mid q \ll p\}$ . The nuisance ordinal determined by the preordinal p we will designate $ O_p$ . We will let:

(71) $$ \begin{align} POrd& = \{ p \mid p \text{ is a preordinal} \} & Ord & = \{O_p \mid p \in POrd\}. \end{align} $$

It is clear from the definition that if $p \asymp q$ , then $O_p = O_q$ . From this it follows that the nuisance ordinals behave like the limit ordinals in ZF:

Ordering Lemma 33. For any well-orderings $(\vartriangleleft , P)$ and $ (\vartriangleleft , Q)$ :

(72) $$ \begin{align} \S P \ll \S Q \leftrightarrow O_{\S P} \vartriangleleft O_{\S Q}. \end{align} $$

Proof. $(\rightarrow )$ : Suppose first that $\S P \ll \S Q$ . Clearly $O_{\S P}\subseteq O_{\S Q}$ with $\S P \in O_{\S Q}$ . By Proposition 27, there are infinitely many $\S P'$ with $\S P' \asymp \S P$ , and so each such $\S P' \ll \S Q$ as well; thus each such $\S P'\in O_{\S Q}$ but not in $O_{\S P}$ . Hence $O_{\S P} \vartriangleleft O_{\S Q}$ .

$(\leftarrow )$ : By $\rightarrow $ and the asymmetry of $\vartriangleleft $ , if $O_{\S P} \vartriangleleft O_{\S Q}$ then $\S Q \not \ll \S P$ . Likewise, if $\S P \asymp \S Q$ , then $O_{\S P} = O_{\S Q}$ , contradicting $O_{\S P}\vartriangleleft O_{\S Q}$ . Thus by Proposition 30, $\S P \ll \S Q$ .□

Remark 34. We have required that each preordinal be the nuisance of an infinite concept. Notice that the Ordering Lemma 33 fails if we allow preordinals $\S P$ for P finite. For if P is finite and Q is $\Omega $ , then we have:

$$ \begin{align*} \S P & = \S \varnothing & O_{\S P} & = \S \{r \mid r \ll \S P \} = \S \varnothing \\ \S Q & = \S \Omega & O_{\S \Omega} & = \S \{r \mid r \ll \S \Omega\} \\ &&& = \S \{ \S X \mid |X| < \omega \} \\ &&& = \S \{ \S \varnothing\} = \S \varnothing. \end{align*} $$

However, we do have as a corollary to Lemma 33:

Well-ordering of Ord 35. $(\vartriangleleft , Ord)$ is a well-ordering.

Proof. By Proposition 30, for any $p, q\in POrd$ , exactly one of the following holds:

(73) $$ \begin{align} p & \ll q & q&\ll p & O_p = O_q. \end{align} $$

And so by Lemma 33, we have exactly one of

(74) $$ \begin{align} O_p & \vartriangleleft O_q & O_q & \vartriangleleft O_p & O_p = O_q. \end{align} $$

So $(\vartriangleleft , Ord)$ is a linear ordering.

Let $X\subseteq Ord$ be non-empty; we show X has a $\vartriangleleft $ -least element. Let $Y = \{ p \in POrd \mid O_p \in X\}$ ; note that $Y\neq \varnothing $ . Now let $\varphi (R, Z)$ be the following formula

(75) $$ \begin{align} (\forall p)(\forall q)(Rpq \leftrightarrow p\vartriangleleft q)\mathbin{\wedge} (\exists P)(\S P = \S Z \in Y \mathbin{\wedge} WO(R, P)). \end{align} $$

It follows from the fact that there is a $\S P\in Y$ that $\varphi (R,Z)$ for some R and Z. By WOWO , there is then a relation R and a concept Z such that $WO(R,Z)$ , $\varphi (R,Z)$ , and for any $(R', Z')$ with $WO(R',Z')$ and $\varphi (R', Z')$ , $(R,Z)\leq (R',Z')$ . Each such $R'$ must be $\vartriangleleft $ , so there is a P such that $WO(\vartriangleleft , P)$ with $\S P\in Y$ and $(\vartriangleleft , P)\leq (\vartriangleleft , P')$ for every $\S P' \in Y$ . By the definition of Y, $O_{\S P}\in X$ .

It remains to show that $O_{\S P}\vartriangleleft O_{q}$ for all remaining ordinals in X. If not, then by the linear ordering of the $O_q \vartriangleleft O_{\S P}$ , the Ordering Lemma 33 yields $q \ll \S P$ . But then there is a Q with $WO(\vartriangleleft , Q)$ and $\S Q \in Y$ such that $(\vartriangleleft , Q)<(\vartriangleleft , P)$ , contradicting the choice of P. So $O_{\S P}$ is the least element of X, and so $(\vartriangleleft , Ord)$ is a well-ordering.□

8.8. Contradiction via the Translation Lemma

Observe that we are quite close to the Burali–Forti paradox. For any $O_p\in Ord$ , let

(76) $$ \begin{align} Ord_{O_p} = \{ O_q \in Ord\mid O_q \vartriangleleft O_p\}. \end{align} $$

Clearly, for any $O_p\in Ord$ , $(\vartriangleleft , Ord_{O_p})$ is an initial segment of $(\vartriangleleft , Ord)$ . Now, since $(\vartriangleleft , Ord)$ is a well-ordering, it follows that $\S Ord \in POrd$ . And thus, that there is a nuisance ordinal $O_{\S Ord}$ . By what was just said, it follows that $(\vartriangleleft , Ord_{O_{\S Ord}})$ is an initial segment of $(\vartriangleleft , Ord)$ .

If we could show that $(\vartriangleleft , Ord_{O_{\S Ord}})\cong (\vartriangleleft , Ord)$ , we would have the Burali–Forti contradiction. Doubtless this can be done, but I think what is given below is a more direct route to a contradiction. The Burali–Forti paradox finds a well-ordering that is isomorphic to a proper initial segment of itself, and that is a problem because such an isomorphism generates a non-empty set of ordinals with no least element. In what follows below, we will skip the isomorphism and go right to the construction of a subconcept of nuisance ordinals without a $\vartriangleleft $ -least object.

Our goal will be to define a function $B:N \rightarrow Ord$ such that

(77) $$ \begin{align} B(0) \vartriangleright B(1) \vartriangleright B(2) \vartriangleright \cdots B(n)\vartriangleright B(n+1) \cdots \end{align} $$

We will define this function B, and an auxiliary function A, by recursion (see DBR ):

(78) $$ \begin{align} A(0) & = \S Ord & B(0) & = O_{\S Ord} = O_{A(0)}, \end{align} $$

(79) $$ \begin{align} A(n+1)& = \S Ord_{O_{A(n)}} & B(n+1) & = O_{\S Ord_{B(n)}} = O_{A(n)}. \end{align} $$

Notice now that if we can prove the following lemma, then we have a contradiction:

Lemma 36. For all $n, m\in N$ ,

(80) $$ \begin{align} n< m \leftrightarrow B(m)\vartriangleleft B(n). \end{align} $$

For if Lemma 36 holds, then $B(N)\subseteq Ord$ is non-empty with no $\vartriangleleft $ -least object falling under it.

But to prove Lemma 36, we need to peer deep beneath the surface so that we can focus on how nuisance ordinals ordinals determined by a sum $p + m\S \Omega ^k$ relate to preordinal sums, and so to the entire structure $(\vartriangleleft , Ord)$ . This is what we show in the following lemma.

Translation Lemma 37. For any preordinal p and any $n\in N$ with $n>0$ ,

(81) $$ \begin{align} (\vartriangleleft, Ord_{O_p }+ \Omega^n) \cong (\vartriangleleft, Ord_{O_{p + \S \Omega^{n+1}}} ). \end{align} $$

Proof. Note first that

(82) $$ \begin{align} (\vartriangleleft, (Ord_{O_p} + \Omega^n) - Ord_{O_p}) & \cong (\vartriangleleft, \Omega^n), \end{align} $$

(83) $$ \begin{align} (\vartriangleleft, Ord_{O_{p+\S \Omega^{n+1}}} - Ord_{O_p}) & \cong (\vartriangleleft, Ord_{O_{\S \Omega^{n+1}}}). \end{align} $$

So it will suffice to show that $(\vartriangleleft , \Omega ^n)\cong (\vartriangleleft , Ord_{O_{\S \Omega ^{n+1}}})$ .

Next observe that $(\vartriangleleft , \Omega ^{n+1}) \cong (\lessdot , \Omega ^n \times N)$ , where $\lessdot $ is as in (51); let g witness this order isomorphism. Now define $G:\Omega ^n \rightarrow \Omega ^{n+1}$ by

(84) $$ \begin{align} G(a) = g(a, 0). \end{align} $$

To see what is going on here, recall that the objects falling under $\Omega ^n$ are ordered by $\vartriangleleft $ like n-tuples are ordered by the dictionary ordering. So G starts with such an object, first sends it to the pair $(a,0)$ in $\Omega ^n \times N$ , and then sends it, via g, to the object in $\Omega ^{n+1}$ that has the same place in the structure $(\vartriangleleft , \Omega ^{n+1})$ as does the object $(a, 0)$ in the structure $(\lessdot , \Omega ^n \times N)$ .

Now, let $a \in \Omega ^n$ and b the $\vartriangleleft $ -least object in $\Omega ^n$ such that $a\vartriangleleft b$ . If $x\in \Omega ^{n+1}$ with $G(a)\vartriangleleft x \vartriangleleft G(b)$ , then $a \asymp x$ : for then $g^{-1}(x) = (a, k)$ for some k, and thus while $(\vartriangleleft , (\Omega ^{n+1})_{G(a)}) < (\vartriangleleft , (\Omega ^{n+1})_x)$ , the difference is finite. Consequently, $\S (\Omega ^{n+1})_{G(a)} \asymp \S (\Omega ^{n+1})_x \ll \S (\Omega ^{n+1})_{G(b)}$ . It follows from the Ordering Lemma 33 that

(85) $$ \begin{align} O_{\S (\Omega^{n+1})_{G(a)}} = O_{\S (\Omega^{n+1})_{x}} \vartriangleleft O_{\S (\Omega^{n+1})_{G(b)}} \vartriangleleft O_{\S \Omega^{n+1}}. \end{align} $$

Now consider the function $H: \Omega ^n \rightarrow Ord_{\S \Omega ^{n+1}}$ defined by:

(86) $$ \begin{align} H(a) = O_{\S (\Omega^{n+1})_{G(a)}}. \end{align} $$

By (85), $\mathrm {rng}(H)\subseteq Ord_{\S \Omega ^{n+1}}$ , and H is injective and $\vartriangleleft $ -preserving. For surjectivity, suppose that $ O_p \in Ord_{\S \Omega ^{n+1}}$ , and let $a\in \Omega ^n$ be the $\vartriangleleft $ -least element of $\Omega ^n$ such that for all $b\in \Omega ^n$ , if $a \vartriangleleft b$ then $ O_p \vartriangleleft H(b)$ . It follows then that $H(a)\vartriangleleft O_p \vartriangleleft H(a')$ if $H(a)\neq O_p$ , where $a'$ is the successor of a in $(\vartriangleleft , \Omega ^n)$ . But if $H(a)\neq O_p$ , then by the Ordering Lemma 33,

(87) $$ \begin{align} \S (\Omega^{n+1})_{G(a)} \ll p \ll \S (\Omega^{n+1})_{G(a')}. \end{align} $$

Thus there is an $x\in \Omega ^{n+1}$ and a P with $p = \S P$ such that $(\vartriangleleft , (\Omega ^{n+1})_x) \cong (\vartriangleleft , P)$ . As above, then,

(88) $$ \begin{align} (\lessdot, (\Omega^n \times N)_{(a,0)}) & \cong (\vartriangleleft, (\Omega^{n +1})_a) \end{align} $$

(89) $$ \begin{align} &< (\vartriangleleft, (\Omega^{n+1})_x) \end{align} $$

(90) $$ \begin{align} &\cong (\lessdot, (\Omega^n \times N)_{(a,k)}) \end{align} $$

(91) $$ \begin{align} & < (\lessdot, (\Omega^n \times N)_{(a',0)}) \end{align} $$

(92) $$ \begin{align} & \cong (\vartriangleleft, (\Omega^{n+1})_{G(a')} \end{align} $$

for some $k\in N- \{0\}$ . But then $\S (\Omega ^{n+1})_{G(a)} \not \ll \S (\Omega ^{n+1})_{x}$ , whence also $\S (\Omega ^{n+1})_{G(a)} \not \ll p$ and so $\S (\Omega ^{n+1})_{G(a)} \asymp p$ (by Proposition 30). Thus

(93) $$ \begin{align} H(a)= O_{\S (\Omega^{n+1})_{G(a)} } = \S O_p. \end{align} $$

□

Corollary 38. For any $n\in N-\{0\}$ ,

(94) $$ \begin{align} \S Ord_{O_p} + \S \Omega^n = \S Ord_{O_{p+\S \Omega^{n+1}}}. \end{align} $$

As a consequence we have:

Boundedness Lemma 39. Let p be a preordinal and $n\in N$ . Notice that $\S Ord_{O_p}$ is then a preordinal. Then

(95) $$ \begin{align} \S Ord_{O_{p}} + \S \Omega^n \ll \S Ord. \end{align} $$

Proof. By (69) of Preordinal Arithmetic 31 and Corollary 38:

(96) $$ \begin{align} \S Ord_{O_{p}} + \S \Omega^n \ll \S Ord_{O_p} + \S \Omega^{n+1} = \S Ord_{O_{p+\S \Omega^{n+1}}}. \end{align} $$

The result follows from the fact that $(\vartriangleleft , Ord_{O_{p+\S \Omega ^{n+1}}})<(\vartriangleleft , Ord)$ .□

The Translation Lemma 37, its Corollary 38, and the Boundedness Lemma 39 were all in the service of proving Lemma 36, which finally we can prove. We proceed by induction on n to show that for each $n, k\in N$ ,

(97) $$ \begin{align} A(n+1) + \Omega^k &\ll A(n) & B(n+1) & \vartriangleleft B(n) \end{align} $$

(see (78) and (79)).

For the base case, first notice by the Boundedness Lemma 39 that $A(1)+ \S \Omega ^k = \S Ord_{O_{\S Ord}} + \S \Omega ^k \ll \S Ord = A(0)$ . It follows then by the Ordering Lemma 33 that $B(1) = O_{\S Ord_{\S Ord}} \vartriangleleft O_{\S Ord} = B(0)$ .

Now suppose that $A(n+1) + \S \Omega ^k \ll A(n)$ for all $k\in N$ , and $B(n+1)\vartriangleleft B(n)$ . We obtain, starting from the former, the sequence:

(98) $$ \begin{align} A(n+1)+ \S \Omega^{k+2} & \ll A(n), \end{align} $$

(99) $$ \begin{align} O_{A(n+1)+ \S \Omega^{k+2}} & \vartriangleleft O_{A(n)}, \end{align} $$

(100) $$ \begin{align} (\vartriangleleft, Ord_{O_{A(n+1)+ \Omega^{k+2}}}) & < (\vartriangleleft, Ord_{O_{A(n)}}), \end{align} $$

(101) $$ \begin{align} (\vartriangleleft, Ord_{O_{A(n+1)}} + \Omega^k) < (\vartriangleleft, Ord_{O_{A(n+1)}}+ \Omega^{k+1}) & < (\vartriangleleft, Ord_{O_{A(n)}}). \end{align} $$

Line (99) follows from the Ordering Lemma 33. Line (100) follows from the preceding line since both terms are ordinals. The right-hand relation of (101) is then a result of the Translation Lemma 37; the left is by the definition of $\Omega ^k$ . Notice that the difference on the left of (101) is infinite. It follows then that:

(102) $$ \begin{align} A(n+2) + \S \Omega^k = \S Ord_{O_{A(n+1)}} + \S \Omega^k & \ll \S Ord_{O_{A(n)}} = A(n+1), \end{align} $$

(103) $$ \begin{align} B(n+2)= O_{\S Ord_{O_{A(n+1)}}} & \vartriangleleft O_{\S Ord_{O_{A(n)}}} = B(n+1). \end{align} $$

Line (103) follows from (102) by the Ordering Lemma 33.

The induction is complete, and thus so is the proof of Lemma 36. And with it, then, the proof of the Cardinal Limitation Theorem CLT .