11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @JDH I figured I might as well ping you here, since it's your paper which prompted me to ask this question. $\endgroup$ – Dennis Jan 3 '14 at 19:48
  • $\begingroup$ That one can state and prove categoricity in second-order logic was pointed out in Geoffrey Hellman's (1989) book "Mathematics without numbers" (p. 38-39). Given pairing in the background, this obviously extends to monadic second-order logic, and thus to plural logic. $\endgroup$ – GME Jan 3 '14 at 21:41
  • $\begingroup$ @user104955 Thanks for the reference! I actually just was reading Hellman's book, but that portion escaped my memory. Just for the sake of clairification, by "pairing" you mean "pairing functions" in the sense given here, right? I suppose, then, that as long as you don't think that pairs need to be reduced to one of their set-theoretic definitions, this would count as an example of categoricity w/o sets. Thanks a lot, really, very helpful! $\endgroup$ – Dennis Jan 3 '14 at 21:46
  • 1
    $\begingroup$ Yes. There are two thoughts here: (1) even if pairing is set theoretic, it would only be true that categoricity requires one to work in the context of a minimal theory of sets; and (2) there are ways to get pairing without sets using mereology - see, for instance, Hellman's "Structuralism without structures" and the Burgess, Hazen, and Lewis's "Appendix on pairing" in David Lewis's "Parts of classes" $\endgroup$ – GME Jan 3 '14 at 21:53
  • 2
    $\begingroup$ Btw, I imagine that Joel will think that which pluralities are available is relative to which universe one is considering. For instance, it's plausible that there's a concept of set on which every subplurality of any set forms a set. If the range of the plural quantifiers was invariant across all universes, the continuum would be invariant across all universes. Since the size of the continuum can vary from universe to universe according to Joel, the range can't be invariant. $\endgroup$ – GME Jan 3 '14 at 22:06
11
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice answer! $\endgroup$ – Vladimir Reshetnikov May 20 '15 at 3:34
  • $\begingroup$ Thanks very much; I'm glad you like it. $\endgroup$ – JDH May 20 '15 at 10:29
  • $\begingroup$ Wow, thanks for the bounty, Vladimir! You are very kind. Concerning non-absoluteness of arithmetic truth, the paper I link to (with Ruizhi Yang) is about the non-absoluteness of what the models think is first-order assertions. That is, we find two models of set theory with the same natural numbers and what they think is a first-order arithmetic assertion $\sigma$, which one model thinks is true and other does not. The trick in these cases is that both models must have non-standard $\mathbb{N}$ in order for it to work, and $\sigma$ itself must be non-standard. $\endgroup$ – JDH May 21 '15 at 14:07
  • $\begingroup$ In your answer you gave 2 examples (Suslin trees and existence of $0^\sharp$). At the first glance, it looks to me they can only be formalized in the second-order arithmentic, with quantification over sets of natural numbers. Am I wrong here? Can you give an example of a first-order arithmetic sentence that can have different truth-values in two models, despite they have the same natural numbers? Also, could you please explain what does it mean for a statements $\sigma$ to be non-standard? $\endgroup$ – Vladimir Reshetnikov May 21 '15 at 14:56
  • $\begingroup$ The assertion that $0^\sharp$ exists has complexity $\Sigma^1_3$, which is indeed a part of second-order arithmetic, as you stated. For the Suslin tree example, however, one needs to go to third-order arithmetic, or equivalently, second-order analysis, since the tree itself amounts to a certain definable set of reals, and the branch also. We have lots of first-order arithmetic assertions that are not absolute between various models of set theory, such as large cardinal consistency assertions. $\endgroup$ – JDH May 21 '15 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.