1
$\begingroup$

The following line of thought came into me while studying introductory logic and set theory. I feel like there is an error in it somewhere, but I can't point it. It might even be correct.

  • We have the copy of naturals in ZF as $\omega$
  • $\omega$ is unique and with functions we can define in ZF, it satisfies the axioms of PA
  • This gives a model of PA in a first-order language in a unique way
  • We can prove that the structure in ZF satisfies the properties of PA, and even we can formulate the stronger second-order induction on this structure as in ZF subsets are just elements
  • This gives that we can capture the second order arithmetic, the intended model of the naturals.

Is there something wrong with this line of thought? If we consider different models of ZF, do we get different $\omega$? If this indeed captures the second order arithmetic, then can't we deal with second order problems in this first order representation? Maybe inherit first order properties like a deductive system?

$\endgroup$
  • 1
    $\begingroup$ What you're describing is just the way that we do mathematics! When we prove things about the natural numbers (or any other structure) in ordinary mathematics, we feel free to use all kinds of higher order reasoning. This reasoning can be carried out in first-order set theory. This is why we call first-order ZFC a foundation for mathematics. $\endgroup$ – Alex Kruckman Mar 22 at 21:55
  • $\begingroup$ Doesn't that mean we can find a deductive system for the second order arithmetic? (soundness, completeness, effectiveness) $\endgroup$ – Lewwwer Mar 22 at 22:04
  • 3
    $\begingroup$ Not a complete one: Gödel's theorem tells us that ZFC fails to prove all true facts about arithmetic, and the same goes for any other first-order set theory that interprets arithmetic. $\endgroup$ – Alex Kruckman Mar 22 at 22:08
  • 1
    $\begingroup$ What do you mean by "the structure is like PA"? PA is a theory, not a structure. $\endgroup$ – Andrés E. Caicedo Mar 22 at 22:09
  • $\begingroup$ Sorry about that, I mean something like, a set with functions and relations we can define and they satisfy the axioms of PA. $\endgroup$ – Lewwwer Mar 23 at 10:10
2
$\begingroup$

Different models of ZF(C) can have different $\omega.$ For instance, any model of ZFC plus “ZFC is inconsistent” will necessarily have a nonstandard $\omega$ (assuming ZFC is consistent, the proof of inconsistency must be coded by a nonstandard number or it would be an actual proof of inconsistency).

The reason this doesn’t conflict with categoricity of second order arithmetic that the nonstandardness can’t be seen internally. For instance, any infinite descending sequence won’t be in the model. So internally, the model’s $\omega$ is a model of second order arithmetic (after all, being the model’s natural numbers, it is isomorphic to the model’s natural numbers), but not externally.

So while ZFC interprets second order arithmetic, this doesn’t solve incompleteness since ZFC is arithmetically incomplete. We do inherent a strong deductive system for arithmetic, but there are still arithmetic statements that are undecidable, most notably the consistency of ZFC.

(Here it is also good to remember that while second order arithmetic is as strong as possible semantically, any effective deductive system for it must still be constrained by the incompleteness theorem (which shows why the completeness theorem must fail for second order logic). This of course includes the deductive system we get from ZFC, although from the perspective of ZFC it manifests as regular old first order incompleteness, where a statement is true in some models and false in others if and only if it is undecidable, etc.)

$\endgroup$
  • 1
    $\begingroup$ You are disagreeing with the second bullet, that we can define a unique $\omega$ in $ZF$. That is correct and I think needs to be made clear. It is the key to explaining why the approach does not work. $\endgroup$ – Ross Millikan Mar 23 at 2:34
  • 1
    $\begingroup$ @RossMillikan I guess you're right. What I was saying is all those nice bits are only true internally to a given model of ZF. $\endgroup$ – spaceisdarkgreen Mar 23 at 2:35
  • $\begingroup$ So if I understand right Inside a model of ZF, $\omega$ with certain operations is isometric to the second-order arithmetic but only with an isometry inside the model? But for different models of ZF this gives a different $\omega$ and they might not be isomorphic between models? So for different models of ZF we must get different models of second-order arithmetic, meaning that we have different subsets of $\omega$ we can use in induction? $\endgroup$ – Lewwwer Mar 23 at 10:04
  • $\begingroup$ @Lewwwer “Isometric” doesn’t make sense... similarly to your response to Andres above, you probably mean “$\omega$ is a model of second order arithmetic.” The model “thinks” it is in its own private understanding of model theory but it isn’t necessarily actually a model. This idea of what a model “thinks” vs what is externally true takes some getting used to. One example you may have heard of, with fewer moving parts, is that a countable transitive model of ZF thinks its set of reals is uncountable, whereas of course it is countable. There is just no bijection to the naturals in the model. $\endgroup$ – spaceisdarkgreen Mar 23 at 23:39
  • $\begingroup$ @Lewwwer and yes, this means different models of ZF may have non-isomorphic $\omega$‘s, which opens up the possibility that they may have different arithmetic truths. This possibility is realized, even amongst first order sentences. When you say “use in induction” it seems like you’re talking about proof, but this would be a bit beside the point because you can only use definiable sets in a proof in the first place. (Hence why second order deductive systems don’t really care about the distinction between full and Henkin semantics.) $\endgroup$ – spaceisdarkgreen Mar 23 at 23:46

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.