The Ryll-Nardzewski Theorem states that an equivalent condition to $\omega$-categoricity is that there is a finite number of $n$-types for any $n$. So what happens when you add a countably many unary predicate to the signature of an $\omega$-categorical theory?

Two examples:

  • Let $\mathcal{G}_1$ be infinite empty graph, augmented with predicates $P_i$ each true on $i$ vertices.
  • Take an enumeration of rigid graphs $(G_i)$ of increasing size, such that $P_i$ is true only on the vertices of $G_i$. Let $\mathcal{G}_2$ to be the union of these graphs.

How many models do the theory of these graphs have? Can they all obtained by some standard model-theoretic construction?

Thanks for your help.

  • $\begingroup$ What is an "infinite empty graph"? Infinitely many vertices, no edges? Surely there's a better term than "empty". $\endgroup$
    – BrianO
    Jan 27, 2016 at 20:57
  • $\begingroup$ @BrianO Yes, that's it. If you prefer, you can call it an "infinite anticlique". $\endgroup$
    – Graffitics
    Jan 27, 2016 at 21:10
  • $\begingroup$ Two comments: 1. Your second example doesn't appear to be an example. That is, $\mathcal{G}_2$ isn't $\omega$-categorical even if you forget the $P_i$. 2. The question is a little unclear. Are you just asking "What can happen if we expand an $\omega$-categorical structure with infinitely many unary predicates?" At that level of generality, the answer is going to be "just about anything" (in fact, adding just one predicate to the theory of the random graph can give you a very complicated theory indeed, if the subgraph picked out by the predicate is complicated enough). $\endgroup$ Jan 27, 2016 at 23:54
  • $\begingroup$ @AlexKruckman For $\mathcal{G}_2$, it depends if it constructed carefully enough right? Regarding 2, in both cases I see a possible axiomatization of the resulting theories, but fail to see what could be a model other than the 'intended model'. The question is actually what is below the examples, can we say something about the number of possible models ($\omega$?), and is it possible to build some (all?) via standard constructions. Thank you for taking the time to answer. $\endgroup$
    – Graffitics
    Jan 28, 2016 at 19:36
  • $\begingroup$ Oh, when you wrote "let $\mathcal{G}_2$ to be the union of these graphs", I understood this to mean "disjoint union". I guess you intended the $G_i$ to form a chain under inclusions whose union is the random graph? In both of your examples, you can get countable models which aren't the "intended model" by realizing the type $\{\lnot P_i(x)\mid i\in \omega\}$. $\endgroup$ Jan 28, 2016 at 20:28

1 Answer 1

  1. Let $M$ be our $\omega$-categorical structure, and let $\hat{M}$ be $M$ expanded by the predicates $\{P_i\mid i\in\omega\}$ and say that two predicates $P_i$ and $P_j$ are equivalent if they have the same interpretation on $M$. As you note, Ryll-Nardzewski tells us that in an $\omega$-categorical theory, there are only finitely many $1$-types, so $\text{Th}(\hat{M})$ has no hope of being $\omega$-categorical, unless the new predicates are partitioned into only finitely many equivalence classes (i.e. if we only really added finitely many predicates). But even if we only add $1$ predicate, we can still get a theory which isn't $\omega$-categorical, see point 4.

  2. Here's an example where we easily get $2^{\aleph_0}$-many countable models. Let $M$ be an infinite set (a structure in the empty language), and interpret the $P_i$ so that for any finite sets $X,Y\subset \omega$ such that $X\cap Y = \emptyset$, there exists an $x$ such that $\hat{M}\models P_i(x)$ for $i\in X$ and $\hat{M}\models \lnot P_i(x)$ for $i\in Y$. Then there are already continuum-many quantifier-free $1$-types consistent with $\text{Th}(\hat{M})$, so this theory has continuum-many countable models.

  3. You can also get exactly $n$ models for any $n\in \omega$, $n \neq 2$ as an expansion of DLO with countably many unary predicates. Take the standard examples and replace the constant symbols with predicates that pick out exactly one element.

  4. It's a fun fact (see Section 5.5 of Hodges' big Model Theory) that for any first-order structure $N$ in a finite language $L$, there is a graph $G$ such that $N$ and $G$ are bi-interpretable. Given a countable structure $N$, let $G$ be the (countable) graph which interprets it, and let $M$ be the random graph. Then $G$ embeds in $M$, since $M$ is universal for countable graphs. Let $P$ be a new predicate and expand $M$ to $\hat{M}$ by letting $P$ pick out the copy of $G$ in $M$. Then $\text{Th}(\hat{M})$ interprets $\text{Th}(G)$, which interprets $\text{Th}(N)$. So, for example, by adding a single predicate to the random graph we can obtain a theory which interprets ZFC set theory.

  • $\begingroup$ Great answer with good pointers. Thank you. $\endgroup$
    – Graffitics
    Jan 28, 2016 at 21:05

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.