Consider a language L and a set of sentences $\Sigma$ of predicate logic from than L-structure $\mathcal A = \{ A ; \{ R \}_{R\in L^r}, \{ F \}_{F \in L^f} \}$. Say that $\Sigma$ is complete so it proves either $\Sigma \vdash p$ or $\Sigma \vdash \neg p$. Thus, it means that all models of $\Sigma$ must satisfy either the above. However, intuitively it seemed to me that all models must satisfy the same set of sentences (since they are complete they decide everything). Since sentences I am considering are ultimately predicate sentences where the base case ends up with relation symbols or equations (and function), it seemed reasonable to me that all these L-structure must be equivalent.

Is this correct?

I thought of this after reading these notes by Van Dries page 62.

  • $\begingroup$ Lowenheim-Skiolem holds for any first order theory. $\endgroup$ – Malice Vidrine Oct 21 '18 at 3:30
  • $\begingroup$ @MaliceVidrine can you provide me an intuition why I'm wrong? No pressure, I thought it should be obvious but its not... $\endgroup$ – Pinocchio Oct 21 '18 at 3:32
  • $\begingroup$ What first order sentences fix the cardinality of the model? If you look up a proof of the Lowenheim-Skolem theorem, you will see that none do. Isomorphic structures, however, need to have the same cardinality, because an isomorphism is, among other things, a bijection. $\endgroup$ – Malice Vidrine Oct 21 '18 at 6:54
  • $\begingroup$ anyone has an idea what the comment: "No, because there can be models of arbitrary cardinality." means and how it applies to my question, it would be very helpful. $\endgroup$ – Pinocchio Oct 21 '18 at 15:45
  • $\begingroup$ My most recent comment is exactly an explanation of that. Isomorphic models cannot have different cardinalities. $\endgroup$ – Malice Vidrine Oct 21 '18 at 18:12

Intuitively, you're right if the language is powerful enough to talk about each individual element of the model. But if the model is really big, there are too many things in it for the language to talk about - and models can therefore differ on those "undescribed" elements.

The classic example goes something like this: let $T$ be the set of true sentences about $\mathbb{R}$. $T$ is clearly a complete theory. Build a new model $M$ by first putting in $0$. Then, for every sentence in $T$ of the form $\exists x\varphi(x)$ with $\varphi$ quantifier-free, add into $M$ an $x$ so that $\varphi(x)$ holds. Repeat, doing some tricks to deal with multi-quantifier formulas (take a look at Lowenheim-Skolem for details). The end result is that after adding countably many elements to $M$, you've made $M$ satisfy every sentence in $T$. So $M$ and $\mathbb{R}$ are both models of $T$; but since $M$ is countable and $\mathbb{R}$ is not, they can't be isomorphic.

The key idea here is that in this example, we added to $M$ only the members of $\mathbb{R}$ that were "important" to the theory - and because the theory was a countable theory, there could only be countably many "important" things.

  • $\begingroup$ I think $M := \Bbb R \cap \bar{\Bbb Q}$ suffices. $\endgroup$ – Kenny Lau Oct 21 '18 at 3:43

No, because there can be models of arbitrary cardinality.

  • $\begingroup$ can you provide me an intuition why I'm wrong? No pressure, I thought it should be obvious but its not...Or why your right? Anything that can help me understand. :) $\endgroup$ – Pinocchio Oct 21 '18 at 3:32
  • $\begingroup$ Any isomorphism preserves cardinality. $\endgroup$ – Kenny Lau Oct 21 '18 at 3:34
  • $\begingroup$ how does that matter? $\endgroup$ – Pinocchio Oct 21 '18 at 3:35
  • $\begingroup$ @Pinocchio If you have two models of different cardinality they can't be isomorphic! $\endgroup$ – Noah Schweber Oct 21 '18 at 16:43

You are confusing elementary equivalence with isomorphism. (Two models are elementarily equivalent if they satisfy precisely the same set of sentences. It's easy to see that a first-order theory is (negation) complete -- complete in the sense you described -- if and only if all its models are elementarily equivalent.)

This is one of the surprising distinctions of mathematical logic, but it is basic and important. "All models are isomorphic" (categoricity) implies "all models are elementarily equivalent," but the converse is not true.

The reason these notions come apart is that the language one uses may not be strong enough to detect the difference between the models. All the models may agree on what sentences of the languages are true, but they may disagree in ways the language can't express.

So you're right that a complete theory makes all models elementarily equivalent. But you're wrong to infer the models "really" have the same structure (in the sense of isomorphism). Agreeing on which sentences in a language are true is coarser and weaker than agreeing on all aspects of structure, over and above what the language can capture.

For a concrete example, just take any complete first-order theory, say the theory of real closed fields. All the models are elementarily equivalent. But the Lowenheim-Skolem theorem says the theory has models of arbitrary infinite cardinality, so not all models can be isomorphic (because isomorphism preserves cardinality).


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.