0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What is a special structure? $\endgroup$ – Asaf Karagila Jun 6 at 12:57
  • $\begingroup$ @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. $\endgroup$ – Mark Kamsma Jun 6 at 13:08
  • $\begingroup$ @Mark: I thought you're on a plane. $\endgroup$ – Asaf Karagila Jun 6 at 13:10
  • $\begingroup$ @asaf there is lots of downtime around a flight. For example, now I actually found the time to write an answer. $\endgroup$ – Mark Kamsma Jun 6 at 14:44
  • 1
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Jun 6 at 14:47
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Not every special structure is saturated, though... $\endgroup$ – Alex Kruckman Jun 6 at 15:33
  • 1
    $\begingroup$ Right - the point is that special models (of singular cardinality) provably exist in ZFC for all theories, while saturated models do not. $\endgroup$ – Alex Kruckman Jun 6 at 15:41
  • 1
    $\begingroup$ @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. $\endgroup$ – Mark Kamsma Jun 7 at 7:07
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Mark Kamsma Jun 7 at 7:10
  • 1
    $\begingroup$ @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). $\endgroup$ – Mark Kamsma Jun 9 at 22:08

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.