Do second-order categoricity proofs require a background concept of set?

Question

In his article "The Set-Theoretic Multiverse", Joel David Hamkins (as part of his reply to Donald Martin's argument that the set-theoretic universe is unique, found in "Multiple Universes of Sets and Indeterminate Truth Values") states that "...a second-order categoricity argument, even just for the natural numbers, requires one to operate in a context with a background concept of set." (p. 14 in the linked arXiv edition)

This got me to wondering, is this strictly required, or is a set-theoretic context for categoricity proofs just being assumed as part of the dialectic? I certainly grant that there is a notion of categoricity which seems intimately connected with your background set theory, since the proofs are carried out within that background set theory and since the standard semantics for second-order logic is a set-theoretic semantics.

But there are alternative semantics for second-order logic (e.g., the plural quantification interpretation of monadic second-order logic suggested by George Boolos) and while it might be the case that none of them are quite as good as the standard semantics--- for example, there is the trouble that relations give plural logicians ---it seems like this might open the door to presentations of second-order logic which don't rely on a background set theory.

Is the issue that the concept of "model" utilized in statements of categoricity is that of a set-theoretic model? If we had an alternate conception of model, one not tied to set theory, would a background concept of set still be presupposed by categoricity proofs? Are there any extant examples of putative categoricity proofs which do not operate within a set-theoretic background context?

In the interest of isolating one question, take the following to be the main question here: in what sense(s) do categoricity proofs require one to operate with a background concept of set and in what sense(s) is categoricity independent of set theory?

Answer 1

I'm glad to hear that you're reading my paper, and your question is interesting. (I just noticed your question now.)

My remark about the categoricity proofs requiring set theory applies equally whether you undertake the categoricity argument in second-order logic, which I view as a flavor of weak set theory, or plural logic, which has an essential set theoretic nature. The main point I am making in the remark is that it seems hopeless to base our confidence in the definiteness of concept of the finite by appealing to the set-theoretic realm (whether via a full set-theory or via second-order logic or plurals), since we would seem to have even less confidence in the definite nature of that realm. In other words, how can we base our confidence in the easy case on our knowledge about something much murkier? (See also this informal essay about it.)

But to answer your mathematical question at the end: yes, categoricity can depend on the set-theoretic background. One easy way to see this is that basic fact that different models of set theory can have different non-isomorphic natural numbers $\mathbb{N}$, even though each of these models believes that their version of $\mathbb{N}$ is characterized by the second-order Peano axioms. In a recent joint paper of Ruizhi Yang and myself, Satisfaction is not absolute, we provide several more striking examples. Namely, there can be different models of set theory $M_1$ and $M_2$, which agree on their natural number structures $\langle \mathbb{N},+,\cdot,0,1,<\rangle^{M_1}=\langle \mathbb{N},+,\cdot,0,1,<\rangle^{M_2}$, but they do not agree on arithmetic truth, in the sense that they have an arithmetic sentence $\sigma$ such that $M_1\models\mathbb{N}\models\sigma$ and $M_2\models\mathbb{N}\models\neg\sigma$. This can be construed as a dependence of categoricity on the set-theoretic background.

Here are a few other ways to show that categoricity can change with the set-theoretic background.

• Let $t$ be the $L$-least Suslin tree with the unique branch property. Consider the theory $T$ asserting the elementary diagram of $t$ together with the assertion "$b$ is a branch through $t$", using a new predicate symbol $b$. In the forcing extension obtained by forcing with $t$, there is a unique branch through $t$, and the theory is fully categorical in that model (in second-order logic). But if one forces with $t$ again, then in that set-theoretic universe, the very same theory is no longer categorical, since there is a choice for the branch.

• Similarly, in the countable context one can write down the theory that describes the natural number structure $\mathbb{N}$ plus the assertion that $Z$ is a predicate whose extension on $\mathbb{N}$ is exactly $0^\sharp$ (this is definable in second-order logic). This theory is categorical in second-order logic, if $0^\sharp$ exists, since there is ony one thing that will satisfy it, but it is not satisfiable at all if $0^\sharp$ does not exist. Or one could make the theory say that $Z$ is $0^\sharp$, if $0^\sharp$ exists, and otherwise anything. This is categorical if and only if $0^\sharp$ exists.