4
$\begingroup$

I have several crazy questions.

Question 1. What does generic-theory mean?

As an example: let $\mathcal{L}=\{R\}$ be the language of graphs and let $T$ be the theory of simple (undirected with no loops) graphs. Consider the theory of random graph $T_r=T\cup \{\phi_n : n\in \mathbb{N}\}$, where for each $n$, $\phi_n$ says for every $2n$ distinct vertices, $x_1,\dots, x_n$ and $y_1,\dots, y_n$, there is a vertex $z$ such that $z$ is adjacent to all $x_i$'s and not adjacent to all $y_i$'s.

On the other hand, let $\mathcal{C}$ be the class of all finite graphs. $\mathcal{C}$ is a Fraisse class and its "generic" model say $\mathcal{M}$ is a countable random graph. Usually the full theory of $\mathcal{M}$ is called the generic theory of random graphs.

Where is the word "generic" from?

Question 2. In the case that our class $\mathcal{C}$ is not a Fraisse class (and cosequently there is no generic model), what does generic theory mean?

For example, let $\mathcal{C}$ be the class of finite bowtie-free graphs, then $\mathcal{C}$ is not a Fraisse class (because it does not have AP). I n this example what does "the generic theory of bowtie-free graphs" mean?

Question 3. What does "generic" automorphism mean?

For example, let $T_r$ be the theory of random graphs. And let $\mathcal{M}\models T_r $. We say let $\sigma$ be a generic automorphism of $\mathcal{M}$. What does this mean? Does it mean that $\mathcal{M}$ is the generic model of $T_r$? I also saw the following meaning for generic automorphism in some papers: let $\mathcal{M}\models T$ be an $\mathcal{L}$-structure, $\sigma$ is a generic automorphism of $\mathcal{M}$ if the pair $(\mathcal{M},\sigma)$ is an existentially closed model (as a $\mathcal{L}_\sigma=\mathcal{L}\cup\{\sigma\}$-structure) of the theory $T_\sigma= T\cup \{\text{$\sigma $ is an automorphism}\}$. What is the difference between thess notions?

$\endgroup$
8
  • $\begingroup$ "generic" derives from "genus" or Greek genos, so it means a "typical", in the sense of non-special, general case of something. $\endgroup$ May 27, 2019 at 21:51
  • $\begingroup$ @HennoBrandsma But it seems that in the case of random graph when we say generic theory we mean a special case of the theory of random graph, i.e. the theory of a specific random graph (I mean the theory of the random graph obtained by Fraisse limit not an arbitrary random graph!) $\endgroup$
    – Alice.H
    May 27, 2019 at 21:57
  • $\begingroup$ A really random graph is "generic" in the linguistic sense. I don't know the Fraisse limit. It's just a suggestive name. $\endgroup$ May 27, 2019 at 21:58
  • $\begingroup$ @HennoBrandsma Ok, so why do not we call $T_r$ the generic theory of random graph? We just call it the theory of random graph. $\endgroup$
    – Alice.H
    May 27, 2019 at 22:02
  • 1
    $\begingroup$ These questions are not crazy at all. I don't have time to write an answer now, but I'll return later. $\endgroup$ May 27, 2019 at 22:20

2 Answers 2

5
$\begingroup$

The word "generic" is used in model theory for several different (but closely related) notions. Because the analogies and connections between these notions are so strong, I think this is a case where the overloading of terminology is useful. But it means that you always need to look for clarification of what precisely is meant by "generic" in any given situation.

  • The model companion / existentially closed structures. So if $T$ is an inductive, i.e. $\forall\exists$-axiomatizable, theory, then a "generic model of $T$" is an existentially closed model of $T$, and the "theory of generic models of $T$" is the model companion of $T$.

  • Fraïssé limits. So if $K$ is a Fraïssé class, then its associated "generic structure" is its Fraïssé limit. Since Fraïssé limit is a perfectly good (and more precise) term, you usually hear the terminology "generic structure" used in the context of one of the many variations on the notion of Fraïssé class that appear in the literature (as in dav11's answer).

I believe these uses derive from the meaning of "generic" in general topology. Here a property (of points in a space) is called "generic" if the set of all points satisfying this property is comeager. So sometimes you will see:

  • In a setting in which structures of a certain kind can be viewed as points in a nice topological space, a "generic structure" of that kind is a structure whose isomorphism class is comeager.

In nice situations (but certainly not all), the above uses of "generic" agree. For example, if $K$ is a Fraïssé class in a finite relational language, then $K$ is the class of all finite models of a universal theory $T$, and the set of all models of $T$ with domain $\omega$ is naturally viewed as a Polish space. Letting $M$ be the Fraïssé limit of $K$, the isomorphism class of $M$ is comeager in this space, and $M$ is the unique countable model up to isomorphism of the model companion of $T$.

It is also possible that the word "generic" entered model theory via forcing. To a Fraïssé class $K$ or to an inductive theory $T$, you can associate posets (e.g. $K$ with the substructure relation), such that forcing with these posets produces a generic filter which encodes a Fraïssé limit of $K$ or an existentially closed model of $T$, respectively. Of course, these "generic structures" will actually be isomorphic to structures in the ground model, so there's no set-theoretic independence going on here, and we don't actually have to appeal to the machinery of forcing. This kind of "easy forcing" with structures goes by the name "model-theoretic forcing" - it has as special cases the Fraïssé limit construction and the construction of existentially closed models.

Of course, the meaning of "generic" in forcing is also closely related to the meaning of "generic" in topology. So this is yet another side of the same coin.


Finally, on terminology:

You wrote "Usually the full theory of $\mathcal{M}$ is called the generic model of random graphs". I think you meant "Usually the full theory of $\mathcal{M}$ is called the generic theory of random graphs". But I would not call it either of these things. For me, the random graph is a particular countably infinite graph (up to isomorphism), and its theory is called either "the theory of the random graph" or "the generic theory of graphs".

I would only pluralize "random graphs" if I were talking about graphs selected from some random process (not necessarily the Erdös-Rényi process that produces the random graph with probability $1$). So I do not call uncountable models of the generic theory of graphs "random graphs".

Because it arises as a Fraïssé limit, the "random graph" could also reasonably be called the "generic graph". Of course, it is called the "random graph" because it arises with probability $1$ from a natural random process. Sometimes people apply the adjective "random" to other Fraïssé limits by analogy with the random graph, e.g. "random triangle-free graph" or "random partial order". I think it is much better to say "generic triangle-free graph" or "generic partial order" in these cases, since these structures don't arise with probability $1$ from any particularly natural random process. Of course, the question of what counts as a "natural" random process is quite interesting. Even more interesting is the question of when "random" (measure) and "generic" (Baire category) agree, as in the case of the random graph.

$\endgroup$
1
  • $\begingroup$ Thank you Alex for your nice answer. I also, corrected a typo that you mentioned about generic theory instead of generic model. $\endgroup$
    – Alice.H
    May 30, 2019 at 17:58
3
$\begingroup$

The word generic, in the context of modified Fraisse classes is introduced in the paper "On generic structures" by D. Kueker and M. Laskowski. I believe the idea is that under a correct notion of "alike" no two finite substructures that are alike can be distinguished from each other. For example in the random graph, any two finite substructures with the same quantifier free type are "alike". The fact that they "cannot be distinguished" is witnessed by the fact that any isomorphism between two such structures extends to an automorphism of the whole random graph. Note that this usage of the word matches the comments by Henno Brandsma.

To my understanding the bowtie free graph can be viewed in this light: see theorem 3.7 of https://arxiv.org/pdf/1705.01347.pdf and the surrounding discussion on how it relates to the above.

In a similar vein, I believe that a "generic automorphism", is meant to capture the idea of an automorphism lacking too many special properties. For example think about the identity automorphism. This is a special automorphism with many special properties and is not the sort of object you wish to study. In many cases which the notion of "generic automorphism" arise (there are Truss generics etc which you have not mentioned that arise in contexts other than the ones you have mentioned), you will be able to fairly easily show that the identity does not fit the notion of a "generic automorphism".

$\endgroup$

You must log in to answer this question.

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