4
$\begingroup$

I am currently reading "A Guide To NIP Theories" by Pierre Simon and I am a bit confused by his use of the compactness theorem. Maybe this stems from the use of a monster model $\mathcal{U}$ ($\bar \kappa$-saturated and homgeneous) which I am unfortunately not familiar with. The situation sets up as follows:

We have a partitioned formula $\phi(x;y)$. Some set $A\subset \mathcal{U}$ of $|x|$-tuples is said to be shattered by $\phi$, if for every $I\subset A$ we can find some $|y|$-tuple $b_I$ s.t. \begin{align} \mathcal{U}\models \phi(a,b_I) \iff a\in I, \, \text{for all}\, a\in A. \end{align}

The first thing Simon claims is, that by compactness this is the same as saying that every finite subset of $A$ is shattered by $\phi$. Why is that? The set of $L(A)$-formulas \begin{align} p((y_I)_{I\subset A}) = \bigcup_{I\subset A} \{\phi(a;y_I)\mid a \in I\}\cup \{\neg \phi(a;y_I)\mid a \in A\setminus I\} \end{align} is satisfiable iff $A$ is shattered by $\phi$. It is an $A$-type if all finite subsets of $A$ are shattered by $\phi$, so if $|A|< \bar \kappa$ the claim would follow from saturatedness of $\mathcal{U}$. Does he implicitely assume $A$ to be small enough?

Another consequence he draws from the compactness theorem is: If a formula $\phi(x;y)$ shatters finite subsets of $\mathcal{U}$ of arbitrary size then it shatters some infinite subset of $\mathcal{U}$. I'm not entirely sure how that works. I see that compactness guarantees the existence of some model $\mathcal{U}'$ of $\operatorname{Th}(\mathcal{U})$ (that is sufficiently small) and some infinite subset $A\subset \mathcal{U}'$ that is shattered by $\phi$. Does the "monsterness" of $\mathcal{U}$ ensure that the same holds for $\mathcal{U}$ itself?

$\endgroup$
4
  • $\begingroup$ Beware that when a model theorist says by compactness she really means by saturation. If you are familiar with the syntactic form of compactness, reasoning by saturation is not that different. Write a finitely consistent type and realize it in the model. $\endgroup$ Jul 5 at 11:48
  • $\begingroup$ Isn't this the type $p((y_I)_{I\subset A})$ I wrote down in my question? I do understand why it is finitely consistent if we assume that every finite subset of $A$ is shattered by $\phi$. What confuses me is that Simon does not add any hypothesis on the size of $A$. $\endgroup$
    – vava123
    Jul 5 at 11:52
  • $\begingroup$ @PrimoPetri I disagree with your first sentence. When I say "we can find ... by compactness", I mean that we use the compactness theorem to check that a certain type is consistent, by verifying that every finite subset is consistent. This means that we can realize the type in some model. The role of saturation is to go further and realize the type in a particular model (the monster), and this part is often left implicit. $\endgroup$ Jul 5 at 18:04
  • $\begingroup$ That is, there are really two things going on. Maybe one should always say "by compactness and saturation". $\endgroup$ Jul 5 at 18:11

2 Answers 2

4
$\begingroup$

The answer to your first question is just a matter of notational convention! Whenever Simon refers to a subset or "parameter set" $A\subset\mathcal{U}$, using the strict inclusion symbol $\subset$ instead of $\subseteq$ and letters like $A,B,C$, he implicitly means that this set is small, ie within the saturation of $\mathcal{U}$. This is common notational practice when working in a monster model.

Your second question is resolved by the following fact:

Fact: Let $\kappa$ be a cardinal, and let $M$ be a $\kappa$-saturated first-order structure. Moreover let $A\subset M$ be a subset of size $<\kappa$ and let $p(x_{\alpha}:\alpha\in\lambda)$ be a set of formulas with parameters in $A$ and variables ranging over the variables $(x_\alpha)_{\alpha\in\lambda}$ for some $\lambda\leqslant\kappa$. If $p$ is finitely satisfiable in $M$ then $p$ is satisfiable in $M$. $\blacksquare$

This is a nice exercise, and can be proved by induction on $\lambda$, where the base case of $\lambda=1$ is provided by $\kappa$-saturation; let me know if you have any trouble with it! We would call $p$ a (partial) $\lambda$-type of $M$ over $A$, and we use the usual notation $S^M_\lambda(A)$ to denote the set of all complete $\lambda$-types over $A$.

Anyway, your question is resolved by the case $\lambda=2^{\aleph_0}$, since you can write a partial type in the variables $(x_i)_{i\in\omega}\cup(y_S)_{S\subseteq\omega}$ expressing that $\phi(x_i;y_S)$ holds if and only if $i\in S$ for all $i\in\omega,S\subseteq\omega$. Since $\phi(x;y)$ shatters arbitrarily large finite sets, this partial type is finitely satisfiable in $\mathcal{U}$, and thus by the fact above is satisfiable in $\mathcal{U}$. The realizations of the $x_i$ then give an infinite set shattered by $\phi(x;y)$, as needed.

$\endgroup$
4
  • 1
    $\begingroup$ I think I remember seeing this fact. This essentially says that the two assertions are equivalent: (1) all 1-types over all $A<\kappa$ are realized in $\mathcal{M}$. (2) for all $\lambda < \kappa$, all $\lambda$-types over all $A < \kappa$ are realized in $\mathcal{M}$. $\endgroup$
    – vava123
    Jul 5 at 12:33
  • 1
    $\begingroup$ And do you mean "We would call $p$ a (partial) $\lambda$-type" instead of $\kappa$-type? $\endgroup$
    – vava123
    Jul 5 at 12:45
  • 1
    $\begingroup$ @vava123 on the second point, yes, you are absolutely correct; thank you! :) on the first point, indeed that's correct, and we can actually strengthen point (2) to say "for all $\lambda\leqslant\kappa$ instead of just $\lambda<\kappa$! $\endgroup$ Jul 5 at 12:56
  • 1
    $\begingroup$ Wonderful, I was just going to ask wether you meant $\lambda < \kappa$ instead of $\lambda \leq \kappa$. I will think about this. $\endgroup$
    – vava123
    Jul 5 at 13:01
4
$\begingroup$

Does he implicitly assume 𝐴 to be small enough?

YES! Usually capital letters A,B,C denoted small subsets of $\scr U$ and $M,N$ small elementary substructures of $\scr U$.

Another consequence he draws from the compactness theorem is: If a formula 𝜙(𝑥;𝑦) shatters finite subsets of $\scr U$ of arbitrary size then it shatters some infinite subset of $\scr U$.

For $n\in\omega$ and $A⊆\omega$ consider the type

$$ p_{n,A}(x_1,\dots,x_n;y_A) = \bigwedge_{i\in A∩n}\phi(x_i;y_A)\ \wedge\ \bigwedge_{i\in n\smallsetminus A}\neg \phi(x_i;y_A) $$

Let $q((x_i)_{i\in\omega};\ (y_A)_{A\subseteq\omega})$ be the union of all these types. If $(a_i)$ realizes $\exists\,(y_A)\ q((x_i);\ (y_A))$ then the set $\{a_i:i\in\omega\}$ is shattered. N.B. You can replace $\omega$ with any small cardinal.

$\endgroup$
2
  • $\begingroup$ haha, looks like we answered at the same time! :) (+1 of course) $\endgroup$ Jul 5 at 12:14
  • 1
    $\begingroup$ @AtticusStonestrom +1 as well. A peace of functionality that I would appreciate in SE is a warning that someone else is answering :) $\endgroup$ Jul 5 at 12:28

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.