(Finite) Classification Theory

Question

In the context of asking about the classification of finite simple groups, the question arose: what exactly is meant by a "classification"?

Perhaps unsurprisingly, there is in fact a whole branch of model theory called classification theory, and an epynomous book by Shelah which apparently is unreadable. My impression is that the notion of "classifiable" in this subject is that of a stable theory, but probably there are other notions I'm not aware of. Unfortunately, this notion seems best suited for talking about infinite models of a theory. Moreover, it's not clear to me that this definition gives a complete answer to my question:

What does it mean to say that the models of a theory (with some cardinality limit, particularly the case where the models are required to be finite) admit a classification?

Answer 1

The notion of classification seems to depend rather strongly on the particular field of mathematics, and in the (very few) cases I'm acquainted with, it seems easier to give a criterion for unclassifiability.

In model theory, a (complete, countable) theory is considered unclassifiable if it has the largest possible number of non-isomorphic models, namely $2^\kappa$ models of cardinality $\kappa$ (where $\kappa$ is infinite). One of Shelah's great discoveries is that, when a theory isn't like that, then one can say quite a lot about the structure of its models.

(Warning: The following is at the outermost fringes of what I know; I count on the MO community to correct errors.) In the theory of representations of algebras, there is a classification of algebras (and related structures like quivers) as "of finite type," "tame," or "wild." "Wild" means that the representations are as bad as those of a particular algebra (probably the free one on two generators) whose representations are considered a hopeless mess. ("As bad as" means that the latter representations can be somehow coded into the former.) Again, if this doesn't happen, then one can say quite a lot about the representations, like that there are only finitely many irreducible ones (or should that be "indecomposable"?) or only finitely many of any given dimension.

I would guess that other fields also have their own criteria for what constitutes a hopeless mess; in good cases, there would be an accompanying theory telling you good things about anything that isn't a hopeless mess. The key point, at least in the few cases I've seen, is that there's no gradual slope from nice to messy; there's a fairly sharp dividing line.

Answer 2

Every class of finite structures closed under isomorphism can in principle be classified by a (countable) list of representatives of the isomorphism types.
I agree that such a list would be uninteresting if it was not computable. I wouldn't insist on "decidable in polynomial time" as Richard Borcherds did above. Even a list that is computably enumerable (r.e.) might be interesting for pure math purposes: At least their is a way to effectively (but maybe not efficiently) generate a list of representatives.

There is another approach to classification taken in descriptive set theory:
Consider a class of countable models of a certain theory or of separable objects such as manifolds and so on.

Then typically there is a natural separable complete metric space (a Polish space) of representatives (wrt to isomorphism) of the objects in your class.
Note that I do not require that each isomorphism class is represented only once.
You can usually not get this.
Isomorphism is now an equivalence relation on a Polish space, usually relatively easily definable.

There is a wellstudied hierarchy of definable equivalence relations on Polish spaces.
Namely, an equivalence relation $E$ on $X$ is Borel reducible to a relation $F$ on $Y$ ($E\leq_{\text{Bor}}F$) if there is a Borel measurable map $f:X\to Y$ such that for $x_1,x_2\in X$, $x_1Ex_2$ iff $f(x_1)Ff(x_2)$.

Now, if the isomorphism relation is as simple as the identity on the reals, then the objects in the class have a "simple" classification.
If the relation is not as simple as that, but for example as simple as "two sequences of 0's and 1's agree on a final segment", then the classification is more difficult, but still not very difficult (since there are more complicated isomorphism relations).

Names connected to this approach to classification are Kechris, Hjorth, and Su Gao.

Answer 3

I suggest that a classification for finite models is in practice equivalent to a polynomial-time algorithm for the number of models of size ''n''. There are some refinements and variations of this idea: for example if the number of models of size n is polynomial in n then one would presumably want a polynomial-time algorithm that lists them all. Something like permutations are obviously classifiable in any reasonable sens, but the number of types of size n grows more than polynomially fast in n, so one cant always demand a polynomial-time listing of them.

Added later: the reason for the condition "polynomial time" rather than "enumerable" is for cases like the classification of finite simple groups, where it is trivial that the ones of order n can be effectively listed, and the problem is to do this reasonably fast.

Answer 4

In addition to Andreas' remark on the number of non-isomorphic models, perhaps it's noteworthy to say that many non-structure theorems are aiming at the construction of many models which not only are non-isomorphic, but also are hard to tell apart. This may be achieved by requiring the models to satisfy the same set of sentences of some infinitary logic. By taking infinitary logics into consideration, we may consider a theory T to be classifiable if elementary equivalence in L_(infty, lambda) is a sufficient condition for an isomorphism between a given pair of models of cardinality lambda (this should be found in Shelah's book).