# Gentle introduction into stability and classification theory

I am badly looking for a (very) gentle introduction into stability and classification theory answering at least some of the following questions:

• Why is a stable theory called "stable"?

• How to prove that the (obviously classifiable) family of finite simple groups is stable (as a class) - if it can be proved?

• Why has the family of (general) finite groups not been classified up to today? Just because it is not stable? Proof?

• Why has the family of (general) finite graphs not been classified up to today? Just because it is not stable? Proof?

• Does the fact that the family of finite graphs is not classified up to today have to do with the complexity of the graph isomorphism problem (maybe NP-complete) - and if so: how?

Putting it all together:

• Where have the concepts and the connections between "stability", "order-definability", "growth-rate of the number of non-isomorphic models", "classifiability", and - eventually - "NP-completeness" been made comprehensible for the beginner?
-

I think you may be confusing the model theoretic notion of classification a la Shelah's Classification Theory with a more general (and vaguer) notion of mathematical classification.

When Shelah talks about classification, he means the classification of models of some complete first-order theory T by way of cardinal invariants. Examples:

• Let $T$ be the theory of algebraically closed fields of characteristic $0$. A model of $T$ is determined up to isomorphism by its transcendence degree over $\mathbb{Q}$. In particular, since fields with finite or countable transcendence degree are countable, there are countably many models of size $\aleph_0$. But a field with transcendence degree $\kappa > \aleph_0$ has size $\kappa$, so there is exactly one model of size $\kappa$ for each uncountable $\kappa$.

• Let $T$ be the theory of an infinite set $X$ together with an equivalence relation on $X$ with exactly three infinite classes. Models for $T$ are determined up to isomorphism by a sequence of three cardinals up to permutation - the cardinalities of the equivalence classes.

Of course, there are many mathematical classification problems which don't fit this mold. In particular, classical model theory has nothing to say about the class of finite simple groups, the class of finite groups, or the class of finite graphs, since none of these are the class of models of a first order theory (by the Compactness Theorem for first order logic, any theory which has arbitrarily large finite models also has models of every infinite cardinality). It makes no sense to ask whether an arbitrary class of structures is "stable", since this is a property of a first order theory. That's not to say that model theoretic methods can't reveal anything about finite structures, just that they're not the focus of model theoretic classification questions.

Speaking most generally, I think a reasonable definition of mathematical classification would be a map from some class of objects to another (hopefully simpler) class of objects, which preserves "equivalence" (i.e. isomorphism for example) in the sense that $X\not\equiv Y \rightarrow f(X) \not\equiv f(Y)$ (the classification should be able to tell the difference between inequivalent objects) and $X\equiv Y \rightarrow f(X) \equiv f(Y)$ (the classification shouldn't separate equivalent objects).

In fact, a philosophy has been floating around recently which you might be interested in: "Almost all classical classication problems deal with analytic equivalence relations on Polish spaces." That quote is from these slides by Farah. I don't understand this philosophy, myself, but here is an article from the Notices of the AMS about it if you want to know more.

Back to model theory, a major concern since the publication of Classification Theory has been the extension of classification methods to models of theories which are unclassifiable in Shelah's sense, for example unstable theories. Much work has been done to understand several classes of theories (simple theories, NIP theories, etc.), but this remains a vastly open field, and there is no clear idea of what a classification would look like.