Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\mathfrak{A}$ be a first-order structure over a relational language and let $\kappa$ be an infinite cardinal. Lets say that $\mathfrak{A}$ has the $\kappa$-property if for every structure $\mathfrak{B}$ of size $\kappa$ over the same language as $\mathfrak{A}$ we have: $$\mathfrak{B} \mbox{ embeds into }\mathfrak{A} \Longleftrightarrow \mbox{ Every finite } \mathfrak{B}_0\subseteq\mathfrak{B} \mbox{ embeds into } \mathfrak{A}.$$

Has this property been studied before? If so, how is it called?

Note that if the theory of $\mathfrak{A}$ is $|\mathfrak{A}|$-categorical, then a simple compactness argument shows that $\mathfrak{A}$ has the $\kappa$-property for every $\kappa\leq|\mathfrak{A}|$. I don´t expect the other implication to be true, but no examples come to my mind. Hence the question in the title.

Edit: I apologize because I have broken two of the rules for good MO questions. One is Make your title your question and the other is Do your homework. Thanks to Joel, Andreas and Noah for their examples, I should really have put more effort into finding them. But what I´m really interested in is the question in the body:

Has this property been studied before? If so, how is it called?

share|improve this question
The right-hand side of your definition is equivalent to $\mathfrak B$ satisfying the $\forall$ theory of $\mathfrak A$, or in other words, to $\mathfrak B$ being embedded in an elementary extension of $\mathfrak A$. The property is thus essentially a version of $\kappa$-universality for substructures instead of elementary substructures. I don’t know if it has a separate name. –  Emil Jeřábek Sep 1 '14 at 20:14
In particular, every universal structure, and a fortiori every saturated structure, has the property, regardless of categoricity of its theory. –  Emil Jeřábek Sep 1 '14 at 20:16
Ramiro, I think @Emil has basically answered your follow-up, but I recommend asking as separate question since this one has gathered accurate answers to the original phrasing. –  François G. Dorais Sep 2 '14 at 4:16
@François, it wasn´t really a follow up, it was the original question, and I don´t think @Emil´s comment quite answers it. But you are right I sort of ruined the question with the title. In the mean time I will just accept Joel´s answer which was the first one for the question in the title. –  Ramiro de la Vega Sep 2 '14 at 13:13

3 Answers 3

up vote 6 down vote accepted

The answer is no for uncountable cardinals $\kappa$. Let $\mathfrak{A}=\langle A,U\rangle$ be a set $A$ of size $\kappa$ with a unary predicate $U\subset A$, where $U$ and $A-U$ both have size $\kappa$. It follows that $\mathfrak{A}$ has your property, since every structure $\mathfrak{B}=\langle B,U^B\rangle$ of size at most $\kappa$ in that language embeds into $\mathfrak{A}$. But the theory of $\mathfrak{A}$ is the theory of an infinite/co-infinite predicate, which is complete because it is countably categorical, but which is not uncountably categorical because there are models of uncountable size $\kappa$ where the predicate is interpreted in a set of size less than $\kappa$, and such a model is not isomorphic to $\mathfrak{A}$.

share|improve this answer
Thanks! I feel bad I didn´t find this example. Have you seen this property before? Perhaps a sufficient condition milder than categoricity? –  Ramiro de la Vega Sep 1 '14 at 19:58
I haven't seen the property before. My argument shows that whenever $\mathfrak{B}$ is universal for structures of size $\kappa$, then it has your property. But such structures are often not categorical. This observation works in the countable case also. –  Joel David Hamkins Sep 1 '14 at 20:15

The following seems to be sort of a reversed version of Joel's example, categorical in uncountable cardinals rather than in $\aleph_0$. I'll use the theory of the set $\mathbb Z$ of integers with only the immediate-successor relation. Any model of this theory looks like the disjoint union of some non-zero cardinal number of copies of $\mathbb Z$, so the theory is categorical in uncountable powers but not in $\aleph_0$. Let $\mathfrak A$ be the model consisting of $\aleph_0$ copies of $\mathbb Z$. It easily satisfies your hypothesis, essentially because any $\mathfrak B$ whose finite substructures embed in $\mathfrak A$ must satisfy that the successor relation and its inverse are functions without finite cycles. Yet the theory is not categorical in the cardinality $\aleph_0$ of $\mathfrak A$.

share|improve this answer
Does $\mathfrak{A}$ even have an $\aleph_0$-categorical expansion? –  Noah Schweber Sep 1 '14 at 20:13
Thanks a lot Andreas. Please see my edit. –  Ramiro de la Vega Sep 1 '14 at 20:18
@NoahS No, this has no countably-categorical expansion. It already (without expanding) has infinitely many formulas, with only the two variables $x,y$ free, such that each of the formulas is consistent but each two of them are contradictory. (Let the $n$-th formula say that $y$ is the $n$-fold successor of $x$.) By Ryll-Nardzewski's theorem, an $\aleph_0$-categorical theory can't have such formulas. (Actually, either this argument or a direct argument shows, unless I'm extremely tired, that a theory with an $\aleph_0$-categorical expansion must itself be $\aleph_0$-categorical.) –  Andreas Blass Sep 1 '14 at 22:44
@AndreasBlass: It seems rather simple: if we add more symbols, it's easier to differentiate structures than without the additional symbols. Hence the number of models can only go up as we extend the language (and only go down as we reduce it). –  tomasz Sep 1 '14 at 23:24
@tomasz I agree, but it seemed too simple, and I felt like I was about to fall asleep. –  Andreas Blass Sep 1 '14 at 23:36

For $\kappa=\aleph_0$, maybe I'm missing something, but:

  • Let $\Sigma$ be the language of undirected graphs

  • Let $R$ be the random graph; note that $R$ is connected, and that every countable graph embeds into $R$ (I'm taking "$\mathcal{A}$ embeds into $\mathcal{B}$" to just mean "$\mathcal{A}$ is isomorphic to a substructure of $\mathcal{B}$"; in particular, I'm assuming embeddings need not be elementary).

  • Let $Z$ be the "$\mathbb{Z}$-chain," that is, points in $Z$ are integers and there is an edge between $x$ and $y$ iff $\vert x-y\vert=1$.

Now, consider the structure $\mathfrak{A}=R\sqcup Z$. Clearly every countable graph embeds into $\mathfrak{A}$, but I believe $\mathfrak{A}$ is not $\aleph_0$-categorical by a compactness argument: let $T=Th(\mathfrak{A})$, $\Sigma'=\Sigma\sqcup\{a, b, c\}$, and for $n\in\omega$ let $$\varphi_n\equiv \text{"No distinct pair of points from $\{a, b, c\}$ are connected by a chain of size $\le n$."}$$ Clearly $T'=T\cup\{\varphi_n: n\in\omega\}$ is consistent, and the reduct of any model of $T'$ to $\Sigma$ will be elementarily equivalent to $\mathfrak{A}$; but any model of $T'$ has at least 3 connected components, and so is not isomorphic to $\mathfrak{A}$.

share|improve this answer
Drat, Andreas beat me to it - with a much simpler example, too. –  Noah Schweber Sep 1 '14 at 20:07
Although I suspect this example might work for some cardinalities other than $\aleph_0$ - maybe cardinalities where saturated models exist? –  Noah Schweber Sep 1 '14 at 20:14
Thank you Noah for your answer, please see my edit. –  Ramiro de la Vega Sep 1 '14 at 20:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.