6
$\begingroup$

As far as I am aware, it's been proven that the second order theories of $\mathbb{N}, \mathbb{Z},\mathbb{Q},\mathbb{R}, \mathbb{C}$ are categorical. I am sure that this is the case at least for $\mathbb{N},\mathbb{R}$.

But it's unclear in second order logic what actually is a "set". IE. axioms need to be added for sets. So, given that, what does the categoricity imply? Does it mean that in specific if we consider the sets of first-order ZFC, then the categoricity holds and all models are equivalent?

$\endgroup$
10
$\begingroup$

The point is that you already assume there is some set theory in play when you talk about second-order logic.

In other words, you use first-order set theory to talk about second-order "everyday theories" like the natural numbers, etc.

Different models of $\sf ZFC$ can have wildly different sets which they regard as "the true $\Bbb N$". If $M$ is a model of $\sf ZFC$, then there are $M_0$ and $M_1$ which are elementary equivalent to $M$, but $M_0$ is countable, and therefore has only countably many "natural number objects", whereas $M_1$ is such that it has uncountably many "natural number objects". Certainly these are not isomorphic, even though the models themselves pretty much agree on "how things should look like".

So yeah, what we actually have is that first-order $\sf ZFC$ proves that the second-order theories of $\Bbb N$ etc. are categorical. Or, if you will, inside a fixed universe of set theory, $\Bbb N$ has a categorical second-order theory. But moving to a different universe might produce you with different theories and different models.

$\endgroup$
  • 8
    $\begingroup$ +1. For the OP, the first sentence may feel a bit circular; this is precisely why (or rather, one reason why) second-order logic tends to be viewed very suspiciously. That's not to say it doesn't have its defenders, but you're certainly not missing something if you look at this answer and go "so second-order logic is somehow cheating, right?" $\endgroup$ – Noah Schweber Aug 2 '18 at 22:27
  • $\begingroup$ @NoahSchweber I hope I won't be thrown out for cheating now... $\endgroup$ – Dole Aug 3 '18 at 0:07
8
$\begingroup$

To supplement Asaf's answer, let me observe that there are natural second-order theories whose categoricity is undecidable in ZFC. Specifically, let's take second-order ZFC ("ZFC$_2$") itself!

It's easy to show in ZFC that any set-sized model of ZFC$_2$ (yes, models are required to be sets already, so this is redundant; but it's worth mentioning explicitly since we do sometimes care about class-sized "models," and when working with second-order logic is often such a time) is (up to isomorphism) of the form $(V_\alpha,\in)$ for $\alpha$ a strongly inaccessible cardinal. This tells us:

  • It is consistent with ZFC that ZFC$_2$ has no (set-sized) models. This nonexistence statement is just "There is no strongly inaccessible cardinal."

  • Now make the mild (hehe) assumption that ZFC + "There is exactly one inaccessible" and ZFC + "There are two inaccessibles" are each consistent (obviously the second implies the first, so this is a bit redundant, but what the hey). Then the former proves that ZFC$_2$ has a set-sized model and is in fact categorical, while the latter proves that ZFC$_2$ is not categorical.

The moral I'm trying to get at here is that second-order categoricity (and satisfiability) claims can't be made on their own; we really need a background universe of sets. Of course, every logic has some sort of set-ish commitment, but with second-order logic the overhead is just ridiculous.

$\endgroup$
  • 1
    $\begingroup$ Lucky for you that supplements are not under FDA supervision. $\endgroup$ – Asaf Karagila Aug 2 '18 at 22:33

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.