6
$\begingroup$

A typical classification result for a class $C$ of objects looks like that:

Theorem. Each object of $C$ is isomorphic to one object of the following list: [insert list here].

Examples are the classification of finite simple groups and the classification theorem of closed surfaces.

Now I noticed sometimes people also call theorems of the following type "classification results". Here, $I$ is a sufficiently strong invariant of the class $C$ of objects.

Theorem. Let $X$ and $Y$ be two objects of $C$. Then $X\cong Y$ if and only if $I(X)= I(Y)$.

Question: In which way are the two different types of "classification theorems" related? Does a classification theorem of the first type imply a classification theorem of the second type or vice versa?

$\endgroup$
7
  • 2
    $\begingroup$ A classification should include both results, and it is indeed the case in the example of finite simple groups, and closed surfaces. Just it turns out that often the first part is by far the hardest, notably in the case of the classification of finite simple groups. For instance, for the classification of 7-dimensional nilpotent Lie complex algebras, I think that several initially publish lists were slightly flawed because they failed to correctly characterize isomorphism. $\endgroup$
    – YCor
    Commented Oct 20, 2022 at 8:49
  • 5
    $\begingroup$ A classification theorem of the first type tautologically gives one of the second, where $I(X)$ is the element $Y$ of the list which is isomorphic to $X$. Of course, the real issue is how the object $X$ is presented, so that we can see what sort of maps $I$ are computable in terms of that presentation. $\endgroup$
    – Ben McKay
    Commented Oct 20, 2022 at 9:04
  • 1
    $\begingroup$ Having a complete invariant which is also effectively computable is quite a rare thing. $\endgroup$ Commented Oct 20, 2022 at 10:01
  • $\begingroup$ @BenMcKay "A classification theorem of the first type tautologically gives one of the second, where 𝐼(𝑋) is the element 𝑌 of the list which is isomorphic to 𝑋." If you set $I(X):=X$, then the second theorem becomes trivial - even without using the first theorem!! So I don't get what you are saying. $\endgroup$
    – user493267
    Commented Oct 20, 2022 at 12:00
  • 2
    $\begingroup$ @user493267: true: If you set $I(X)=X$, then the second theorem becomes trivial. What I am saying is that if you have a list containing one element in each isomorphism equivalence class, as is supposed in the first theorem, then you can map the entire class $C$ to the elements of that list by a map taking each element to the unique isomorphic element of the list, defining a map $I$ which makes the second theorem true. But this is only interesting if we expect, in circumstances likely to be encountered, that we could decide which element of the list a given element $X$ of $C$ is isomorphic to. $\endgroup$
    – Ben McKay
    Commented Oct 20, 2022 at 14:29

1 Answer 1

6
$\begingroup$

There is no precise definition of a "classification theorem," so I don't think one can assert with mathematical certainty that a classification theorem of type 1 implies a classification theorem of type 2, or vice versa. As others have remarked, most "satisfactory" classification theorems enjoy both properties, so the question of whether one implies the other is perhaps not so important in practice.

Having said that, I think one can make a case that type 1 and type 2 are logically independent. For simplicity, let's assume that there are only countably many objects, so that we can think of $C$ as a set of binary strings. Think of $C$ as being partitioned into disjoint subsets $C_1, C_2, C_3, \ldots$ where each $C_i$ represents an isomorphism class of objects. I'm going to reformulate your two types of classification theorems in the language of computability theory. By a machine I will mean a Turing machine that halts on every input.

Type 1 Result. We write down a machine which accepts (i.e., outputs 1 for) exactly one element from each $C_i$ and rejects (i.e., outputs 0 for) everything else.

Type 2 Result. We write down a machine which takes two inputs $x$ and $y$; it gives an error message if either $x\notin C$ or $y\notin C$, and otherwise it produces a pair of outputs $I(x)$ and $I(y)$ with the property that $I(x) = I(y)$ if and only if $x$ is isomorphic to $y$. (Note carefully that I have written $I(x) = I(y)$ and not $I(x) \cong I(y)$.)

I'm not claiming that what I've called Type 1 and Type 2 results perfectly capture what you or anyone else means by a classification theorem, but I think it's a reasonable approximation, and it gives us a way to examine the logical relationship between Type 1 and Type 2.

A Type 1 result exhibits what one might call a choice function. If you have a Type 1 result, then you can list exactly one element from each isomorphism class, just by looping over all binary strings $x$, printing out $x$ if the machine accepts $x$ and printing out nothing if the machine rejects $x$. Furthermore, if someone hands you something that is allegedly on the list, you can use the machine to check if it really is on the list.

A Type 2 result provides what one might call a complete set of invariants $I(x)$ for any $x\in C$. To check whether two things are isomorphic, you compute the complete set of invariants in each case, and see if they are equal.

Having a Type 1 result does not automatically mean you have a Type 2 result. It is tempting to think that if $x\in C$, then we should be able to set $I(x)$ equal to the unique $y\in C$ that is isomorphic to $x$ and that the machine accepts, but the trouble is that there could be infinitely many elements that are isomorphic to $x$, and we do not necessarily have an algorithm to find which one of them the machine accepts.

Similarly, having a Type 2 result does not automatically mean you have a Type 1 result. A Type 2 result does in some sense let you "list" exactly one element from each isomorphism class, because you can loop over all binary strings $x$ and print it out if and only if $I(x)$ is a set of invariants that you have not already seen, but it does not automatically give you an algorithm for choosing a unique representative from each $C_i$.

I should point out, though, that if we demand a little bit more from a Type 2 result—namely, that $I(x)$ is actually something isomorphic to $x$ (so that $I(x)$ is a canonical representative and not just a complete set of invariants)—then a Type 2 result does automatically give a Type 1 result (at least if it is decidable whether $x\in C$ at all). Simply accept $x$ if and only if $I(x) = x$ (and $x\in C$).

$\endgroup$
1
  • $\begingroup$ Thanks! What then, is the relationship between type 1 and type 2 results? Wikipedia claims the classification problem is related to the equivalence problem: en.wikipedia.org/wiki/Classification_theorem. $\endgroup$
    – user493267
    Commented Oct 21, 2022 at 7:56

You must log in to answer this question.

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