every relation in a special structure $M$ which is first-order definable with parameters has cardinality $< \omega$ or $= |M|$.

Let $$M$$ be a special structure. I'm trying to proof that every relation in $$M$$ which is first-order definable with parameters has cardinality $$< \omega$$ or $$= \lambda$$.

By a first-order definable with parameters relation I mean a set $$A = \left \{ \psi(a_1, \cdots, a_m, b_1, \cdots, b_n): a_1, \cdots, a_m \in M,\, b_1, \cdots, b_n \in X, \, \psi(\overline a, \overline y) \text{ formula} \right \}$$ for fixed $$m$$ and $$X \subset M$$.

I don't know even how to start this question. If I suppose that a set $$A$$ as above has cardinality $$\geq \omega$$, we proof that $$|A| = |M|$$, but how can I proceed?

• What is a special structure? – Asaf Karagila Jun 6 at 12:57
• @asaf The definition I know is that a structure $A$ of infinite cardinality $\kappa$ is special if it is the union (colimit) of an elementary chain $(A_i)_{i < \kappa}$ where each $A_i$ is $|i|^+$-saturated. – Mark Kamsma Jun 6 at 13:08
• @Mark: I thought you're on a plane. – Asaf Karagila Jun 6 at 13:10
• @asaf there is lots of downtime around a flight. For example, now I actually found the time to write an answer. – Mark Kamsma Jun 6 at 14:44
• @Mark: I've never been more ashamed in my life as I am now, of the fact that we are in the same logic group. – Asaf Karagila Jun 6 at 14:47

1 Answer

In this answer I will not distinguish between elements/variables and finite tuples of elements/variables (so you may read every lowercase letter as if it denotes a finite tuple).

First I should say that your definition of "definable" it's not quite right. The way you defined it, every set would be definable. The correct definition is that $$A$$ is definable (in $$M$$) if there is a formula $$\phi(x,y)$$ and $$b \in M$$ such that $$A = \{a \in M : M \models \phi(a,b)\}.$$ We call $$b$$ the parameters.

Let me also recall the definition of a special structure here (to introduce some notation at the same time). A structure $$M$$ of infinite cardinality $$\kappa$$ is special if it is the union $$\bigcup_{i < \kappa} M_i$$ of a chain $$(M_i)_{i < \kappa}$$ such that for every $$i < \kappa$$ the structure $$M_i$$ is $$|i|^+$$-saturated.

Now that is out of the way, we can actually have a look at your question. Let $$A \subseteq M$$ be infinite and $$|A| < |M|$$. Suppose that $$A$$ is definable by some $$\phi(x, y)$$ with parameters $$b$$. We will aim for a contradiction. Since $$b$$ is just a finite tuple of parameters, there will be some $$\lambda < \kappa$$ such that $$b \in M_\lambda$$. We may assume that $$|A| \leq \lambda$$ (otherwise replace $$\lambda$$ by $$|A|$$). Now define $$\Sigma(x) = \{x \neq a : a \in A \cap M_\lambda\} \cup \{\phi(x, b)\},$$ then clearly $$\Sigma(x)$$ is finitely satisfiable. So we can extend $$\Sigma(x)$$ to a complete type $$p(x)$$ over $$(A \cap M_\lambda) \cup \{b\}$$. Since $$|(A \cap M_\lambda) \cup \{b\}| < \lambda^+$$ and $$M_\lambda$$ is $$\lambda^+$$-saturated we then must be able to find a realisation $$c \in M_\lambda$$ of $$p(x)$$ and thus of $$\Sigma(x)$$. But that means $$M_\lambda \models \phi(c, b)$$, so $$c \in A \cap M_\lambda$$ while the first part of $$\Sigma(x)$$ says that $$c$$ must be different from every element in $$A \cap M_\lambda$$. We thus reach our desired contradiction, and we can conclude that of $$A$$ is infinite and $$|A| < |M|$$, then $$A$$ cannot be definable in $$M$$.

• Not every special structure is saturated, though... – Alex Kruckman Jun 6 at 15:33
• Right - the point is that special models (of singular cardinality) provably exist in ZFC for all theories, while saturated models do not. – Alex Kruckman Jun 6 at 15:41
• @user242964 yes, I defined $\kappa$ as $|M|$ in the paragraph before. For your other questions. (1) We use here that $A$ is infinite, so every finite part of $\Sigma(x)$ will say at most "$x$ is in $A$ but unequal to a finite part of it". So then we can definitely find some realisation of that. (2) If something is finitely satisfiable it must have a realisation in some elementary extension (indeed by compactness), then taking the type of that realisation is a completion. – Mark Kamsma Jun 7 at 7:07
• @user242964 For (1) it may also be good to note why $A \cap M_\lambda$ is indeed infinite as well. This is because it is defined by $\phi(x, b)$ and the sentence "there are at least $n$ different $x$ such that $\phi(x, b)$" is true in $M$, and thus in $M_\lambda$, for all $n \in \mathbb{N}$. – Mark Kamsma Jun 7 at 7:10
• @Kat That is not needed, because if something is $\lambda$-saturated then it realises any $n$-type over less than $\lambda$ parameters. If your definition only mentions 1-types, you can still prove this statement from that definition (so it is equivalent). That may be a nice exercise (hint: induction). – Mark Kamsma Jun 9 at 22:08