I was thinking about the (philosophical) implications of the compactness theorem and the Löwenheim-Skolem theorem and so I came up with the following informal summary of my understanding so far:

A first-order theory is not expressive enought to pin down the (infinite or arbitrary large) size of its universe.

I then thought about if this can be generalized. It seems like first-order theories have general problems talking about infinite cardinalities which we usually only address from a meta perspective. So I wondered if there is any infinite part of the universe of some theory that can be grasped by the theory itself. The following conjectures/generalizations should make precise what I had in mind.

Let $T$ be a first-order theory over a language $\mathcal L$ and $\varphi(x)$ an unary predicate over $\mathcal L$. For a model $\mathcal M$ of $T$ let $\mathcal M[\varphi]:=\{x\in\mathcal M\mid \varphi(x)\}$ be a definable part of the universe. The question is now: Do there hold the same restrictions for these parts as there hold restrictions for the whole model?

Generalized compactness theorem:

If for any $n\in\Bbb N$ there is a model $\mathcal M_n$ of $T$ with $\mathcal M_n[\varphi]$ having more than $n$ elements, then there is also a model $\mathcal M$ with $\mathcal M[\varphi]$ infinitely large.

Generalized Löwenheim-Skolem theorem:

If there is a model $\mathcal M$ of $T$ with $\mathcal M[\varphi]$ infinitely large, then for any infinite cardinal $\kappa$ there is a model $\mathcal M_\kappa$ with $\mathcal M_\kappa[\varphi]$ of cardinalty $\kappa$.

You will find the usual theorems when choosing $\varphi(x)\equiv \top$, i.e. $\mathcal M[\varphi]=\mathcal M$ .

Are these results known to be true? Are they simple corollaries of compactness and Löwenheim-Skolem? Or are there any counter examples where a first-order theory is indeed able to pin down the infinite (or arbitrary large) size of some (definable) part of its universe?

  • 2
    $\begingroup$ At least the way I understand your question, this is a simple corollary to the usual compactness and LS theorems. $\endgroup$ – Asaf Karagila May 6 '17 at 15:51
  • $\begingroup$ @AsafKaragila Would you care to explain this in more detail? I do not see this directly! I would be very glad. $\endgroup$ – M. Winter May 6 '17 at 16:12
  • 1
    $\begingroup$ Add a new predicate symbol to the language, and interpret it as your $\varphi$. $\endgroup$ – Asaf Karagila May 6 '17 at 16:40
  • $\begingroup$ @Asaf But then its another theory because its another language. How can I prove the step back to $T$? $\endgroup$ – M. Winter May 6 '17 at 16:46
  • 1
    $\begingroup$ But did you really change the structure? Isn't it also a model of $T$ as a structure of another language? $\endgroup$ – Asaf Karagila May 6 '17 at 17:09

Yes, these are easy corollaries of the classical compactness and Lowenheim-Skolem theorems.

Let $\kappa$ be sufficiently large (= infinite and at least as large as the language of the theory). Consider the language $L'$ consisting of the language $L$ of $T$ together with $\kappa$-many new constant symbols $\{c_i: i\in\kappa\}$, and the theory $T'$ consisting of $T$ together with the axioms "$c_i\not=c_j$" for distinct $i,j\in\kappa$ and "$\varphi(c_i)$" for $i\in\kappa$. This theory is consistent by compactness and the assumption on $T$, and the language $L'$ has cardinality $\kappa$, so by compactness + Lowenheim-Skolem let $M'$ be a model of $T'$ of size $\kappa$, and let $M$ be the reduct of $M'$ to the language $L$. Clearly $\varphi^M$ (this is the usual notation for what you call $M[\varphi]$) has cardinality at least $\kappa$ because of the constant symbols, and at most $\kappa$ because of the size of $M$ (namely, $\kappa$).

The really interesting twist consists of simultaneous cardinality questions. For instance (below, all cardinals are infinite, all languages are countable, and all theories have infinite models):

Let $\kappa\ge\lambda$, $T$ be some theory, and $U$ a unary predicate in the language of $T$. Then under what further conditions is there a model $M\models T$ with $\vert M\vert=\kappa$ and $\vert U^M\vert=\lambda$?

(Note that we could replace $U$ with a formula, but this doesn't really add any generality.)

This is the two-cardinal question; there are many many variations possible, but this one already is incredibly interesting. Say a theory $T$ admits $(\kappa,\lambda)$ if there is such a model as described above (and call such a model a $(\kappa,\lambda)$-model). The argument above shows that every theory $T$ admits $(\kappa,\kappa)$ for every infinite $\kappa$; but it says nothing about more complicated questions, such as whether every theory $T$ admits $(\aleph_1,\aleph_0)$.

That question it turns out is easy to answer: consider the theory $T$ in the language $\{U, f\}$ asserting that $f$ is a bijection from $U$ to $\neg U$. $T$ does not admit $(\kappa,\lambda)$ for any $\kappa\not=\lambda$. To make things interesting, we add a hypothesis:

Vaught's two-cardinal theorem. Suppose $T$ admits $(\kappa,\lambda)$ for some $\kappa>\lambda$. Then $T$ admits $(\aleph_1,\aleph_0)$.

This suggests the following "super Lowenheim-Skolem theorem":

Reasonable guess: If $T$ admits $(\kappa,\lambda)$ for some $\kappa>\lambda$, then $T$ admits $(\kappa,\lambda)$ for every $\kappa>\lambda$.

This turns out to be wrong in general! And indeed even very basic questions in this area involve stepping outside the usual axioms for set theory.

For example, Chang's conjecture states that every $(\omega_2,\omega_1)$-model has an elementary substructure which is a $(\omega_1,\omega)$-model. This is false in ZFC+V=L, but at the same time is consistent assuming large cardinals (and the large cardinals are necessary!).

  • $\begingroup$ Very interesting. Does this mean that even though that FOL fails to describe cardinalities of parts of its universe it can indeed describe the reletive size of parts of its universe? $\endgroup$ – M. Winter May 7 '17 at 0:49
  • $\begingroup$ @M.Winter Only in an extremely limited way. First of all, note that there is no way in which FOL can express an inequality of infinite cardinals: we can always have our model countable. What can happen is that we can have a situation not admitting the pair $(\kappa,\lambda)$, but this is a very technical obstacle. For instance, it doesn't even say that $U$ can't be strictly smaller than $M$! Basically, FOL can assert weak inequalities ($\le$ instead of $<$) and rule out very specific strict inequalities under certain circumstances contingent on set-theoretic hypotheses. $\endgroup$ – Noah Schweber May 8 '17 at 15:53
  • $\begingroup$ In particular, to even make sense of the non-LSC-style cardinality restrictions FOL can place on models of a theory, we already need to "understand" uncountable cardinals in the background, which removes a lot of the foundational force of this fact. $\endgroup$ – Noah Schweber May 8 '17 at 15:54

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.