9
$\begingroup$

I believe the model-theoretic version of the question is: is there a theory in finitary first-order logic which has, for each cardinal $\lambda$, a set $C_\lambda$ of $\lambda$-many models, such that if $M,N \in C_\lambda$ then there is no elementary embedding from $M$ to $N$ or vice versa (in ZFC)?

One statement of the large cardinal axiom Vopěnka's Principle is that no accessible category has a full subcategory which is both large and discrete.

Adámek and Rosický point out (Remark 6.2(2)) that for any cardinal $\lambda$, it's trivial to come up (in ZFC) with an accessible category with a full discrete subcategory with $\lambda$-many objects. They use the example of the theory $\mathbf{Rel}_\lambda$, with $\lambda$-many unary relation symbols, and the set of objects $A_i$, each carried by the one-point set, where $A_i$ has just the $i$th relation turned "on". Here the accessible category in question is allowed to vary with the cardinal $\lambda$.

But, in ZFC, is there one single accessible category $\mathcal{K}$ which has a full, discrete subcategory $\mathcal{K}_\lambda \subset \mathcal{K}$ of cardinality $\lambda$, for each cardinal $\lambda$?

Of course, the union $\cup_\lambda \mathcal{K}_\lambda$ is large, so (assuming that Vopěnka's principle is consistent over ZFC), if such a category exists, then one won't be able to show that $\cup_\lambda \mathcal{K}_\lambda$ is discrete. But it could be that all of its morphisms go from objects of one $\mathcal{K}_\lambda$ to another $\mathcal{K}_{\lambda'}$, and the $\mathcal{K}_\lambda$'s themselves might all be discrete.

Bonus question: in your example, are there clearly morphisms between objects in different $\mathcal{K}_\lambda$'s, or is your example a candidate to become a counterexample to Vopenka in some models (in which connection, this question may be relevant)?

Improve this question
$\endgroup$
2
  • $\begingroup$ I've accepted Joel's answer for sheer elegance. Thanks to Jiří, too -- it's important to know that examples also flow naturally from the existing theory of accessible categories. $\endgroup$
    – Tim Campion
    Commented May 6, 2015 at 17:22
  • $\begingroup$ Another point is that $\mathsf{Gph}$ apparently also embeds fully into familiar categories like Fields (and hence Rings), Groups, and Partial Orders, so these categories also have this property. Actually, the linked answer (of Joel's, ironically) discusses this with elementary embedding as the morphisms; I'm not sure whether the same goes for homomorphisms as morphisms. $\endgroup$
    – Tim Campion
    Commented May 6, 2015 at 20:09

2 Answers 2

Reset to default
12
$\begingroup$

The answer is yes. One can do this with pointed directed graphs.

Specifically, for any infinite cardinal $\lambda$, let $C_\lambda$ consist of all structures of the form $\langle V_{\lambda+2},{\in},\beta\rangle$, where $\beta<\lambda$ and $V_{\lambda+2}$ consists of the sets of von Neumann rank at most $\lambda+1$. So this is a pointed directed graph. Since there are $\lambda$ many choices for the constant $\beta$, we have $\lambda$ many models here.

But there can be no elementary embedding between any two such structures, since any such embedding would give rise to a nontrivial elementary embedding $j:V_{\lambda+2}\to V_{\lambda+2}$, which is impossible by the Kunen inconsistency.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Wow! I was not expecting an answer from set theory, despite the set-theoretical nature of the question. Now let me advertise my ignorance and ask: in ZFC are there any elementary embeddings $V_{\lambda+2} \to V_{\lambda'+2}$ for $\lambda < \lambda'$? Or is this an example that might become a counterexample to Vopenka in some models? $\endgroup$
    – Tim Campion
    Commented May 6, 2015 at 5:32
  • 1
    $\begingroup$ @TimCampion Thanks! The existence of an elementary embedding $j:V_{\lambda+2}\to V_{\lambda'+2}$ is exactly connected with the extendible cardinals, which are fairly high in the large cardinal hierarchy, and so you cannot prove that in ZFC alone. Indeed, this is how one can show that Vopenka's principle has large cardinal strength, by considering the class of all structures $\langle V_\theta,\in\rangle$, and then getting elementary embeddings $j:V_\theta\to V_\lambda$. $\endgroup$
    – Joel David Hamkins
    Commented May 6, 2015 at 10:12
  • 1
    $\begingroup$ With a similar idea as in my post, you can get rid of the points, by considering $\langle V_{\lambda+\beta},\in\rangle$ for $2\leq \beta<\lambda$. There can be no elementary embedding $j:V_{\lambda+\alpha}\to V_{\lambda+\beta}$ for such distinct $\alpha,\beta<\lambda$. $\endgroup$
    – Joel David Hamkins
    Commented May 6, 2015 at 10:42
  • $\begingroup$ One can also get rid of the need for a special point simply by adding a self-edge on that point; it will be the only one. $\endgroup$
    – Joel David Hamkins
    Commented May 7, 2015 at 1:51
10
$\begingroup$

Another, less elegant, but not so set-theoretical positive answer using graphs: Any accessible category has an accessible full embedding to graphs.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I have a question about this construction. Thinking model-theoretically, the idea here, I assume, is to code a given first-order structure $M$ with a graph $G_M$ in such a way that an elementary embedding $j:G_M\to G_N$ amounts to an elementary embedding $j^*:M\to N$. This is a common construction, and one can easily do this in the case where the signature of the structure $M$ is small, such as when it is countable.... $\endgroup$
    – Joel David Hamkins
    Commented May 6, 2015 at 12:34
  • $\begingroup$ ...But when the language of $M$ is enormous, then in order to code all the various relations on $M$ and ensure that maps between the $G_M$ actually respect those relations, it seems to me that one needs at bottom to produce large families of graphs that are rigid in the sense of having no elementary self-embeddings or elementary embeddings between them. In this case, I worry that the construction is circular, since it seems that we have come around to the very same question of the post again.... $\endgroup$
    – Joel David Hamkins
    Commented May 6, 2015 at 12:34
  • $\begingroup$ Or can one undertake the coding-into-graphs construction with first-order models in an arbitrary language without already having examples as in the original question? $\endgroup$
    – Joel David Hamkins
    Commented May 6, 2015 at 12:34
  • 1
    $\begingroup$ I see, it is as I suspected, since that fact already answers the question, if you look at pointed graphs like that, on a set of size $\lambda$. Is the proof of that fact non-set-theoretic? I can prove it using set-theoretic ideas... $\endgroup$
    – Joel David Hamkins
    Commented May 6, 2015 at 13:57
  • 1
    $\begingroup$ A certain graph is built on $\lambda$ by viewing it as the ordinal $\lambda+2$. Some care is needed to ensure that cardinals with cofinality $\omega$ and certain sequences approaching them are fixed by any endomorphism $f$, and then by considering the sup of the iterates of the critical point of $f$ (which has cofinality $\omega$) a contradiction is obtained. The appearance of $\lambda+2$ and an iteration argument (which, I gather from wikipedia appears in the proof of Kunen inconsistency) suggest that maybe this is a similar idea to that used in Kunen inconsistency? $\endgroup$
    – Tim Campion
    Commented May 6, 2015 at 15:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .