I want to prove the statement in the title using Godel's theorems. Without Godel's theorem, I may use the theorem about infinite model from cardinality $\kappa$ $\Rightarrow$ infinite models from any cardinality $>\kappa$ to get as many non-isomorphic models as I wish (cause $\mathbb{N} \models \Sigma$)

I was trying to use Godel's theorem in the next manner, every recursive $\Sigma \subset Th(\mathbb{N})$ is not complete (and so for finite subsets as they are recursive), therefore one can find sentence $\alpha$ such that $\Sigma\nvdash \alpha , \neg\alpha$ so $\Sigma\cup\alpha$ , $\Sigma\cup\neg\alpha$ has models $M_1 , M_2$ because there are consistent ($\Sigma\subset Th(\mathbb{N})$ and therefore consistent ) . $M_1,M_2$ are not isomorphic cause they are not elementary equivalent.

I don't find an Idea to generalize this approach to get $2^{\aleph_0}$ models, any other approach will be appreciated, as long as it is using Godel's theorems

  • $\begingroup$ For yet another approach, Andrés' comment on this answer suggests a compactness-based argument that $\mathbb N$ (or any other model of Q) has continuum many nonisomorphic countable elementary extensions. $\endgroup$ – Henning Makholm Jun 23 '18 at 18:37

You can use this idea to build a whole infinite binary tree of theories.

At each node in the tree you have a finite set of sentences $B$ such that $PA+\Sigma+B$ is consistent. Apply the Gödel-Rosser construction to this theory to get an undetermined $\alpha$. The two successors of the node will arise by appending either $\alpha$ or $\neg\alpha$ to $B$.

The tree has countably many nodes, but $2^{\aleph_0}$ many infinite branches. Each branch has a model thanks to compactness. The models of two different infinite branches are non-isomorphic because they disagree about the $\alpha$ where their branches diverge from each other.

  • $\begingroup$ I am having some trouble with "models of two different branched are non-isomorphic" - when branching - the descendants of $M\models \Sigma$ , $M_1\models \Sigma \cup \alpha, M_2\models \Sigma\cup\neg\alpha$ are non isomorphic but potentially one of them might be isomorphic to $M$ from which they were branched, so maybe this process doesn't result with $2^\aleph_0$ models which are not isomorphic in pairs (every 2 are non-isomorphic to each other) $\endgroup$ – dan Jun 23 '18 at 13:03
  • 1
    $\begingroup$ @dan: Sorry, sloppy phrasing on my part. I'm really only considering models for the infinite branches -- I don't count models of the finite intermediate steps at all. So in your example, $M$ is not counted in its own right among the $2^{\aleph_0}$ models. $\endgroup$ – Henning Makholm Jun 23 '18 at 13:06
  • 1
    $\begingroup$ Look at the models of the complete theories resulting from complete branches, not models of the partial theories corresponding to the nodes along the way. $\endgroup$ – Andrés E. Caicedo Jun 23 '18 at 13:13
  • $\begingroup$ @AndrésE.Caicedo: Careful with that phrasing too -- the theories corresponding to infinite branches are not all "complete". $\endgroup$ – Henning Makholm Jun 23 '18 at 13:21
  • 1
    $\begingroup$ In Gödel's original work the condition was that $\Sigma$ is "$\omega$-consistent", which is a rather technical property that he could argue is "obviously true" for a theory that is true about the actual integers. Later Rosser improved the construction so it now works for any $\Sigma$ that is merely consistent and contains sufficiently much arithmetic, no matter if it is true in $\mathbb N$. That's what I actually meant when I said "Gödel's construction". $\endgroup$ – Henning Makholm Jun 25 '18 at 9:58

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.