Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can there be such a thing as a classification of classification theorems?

share|cite|improve this question
Sure. Every classification theorem is of the form "every P is of the form Q, R, S, T..." for some P, Q, R, S, T.... – Qiaochu Yuan Feb 16 '11 at 13:32
But I mean are there distinctions between various classification theorems to such a degree to allow for a non-trivial classification of them. – user7485 Feb 16 '11 at 13:55
I don't really understand what that could mean. Do you have a precise definition of "classification theorem"? – Qiaochu Yuan Feb 16 '11 at 14:16
The term 'classification' is quite ambiguous indeed. For instance the finite fields are in correspondence with primepowers, but these aren't really 'classified'. So there's some sense in saying that finite fields are classified, relative to the set of primes. Here's a similar situation: – Myself Feb 16 '11 at 14:39
Given some family of objects, we classify all the different types of objects up to some equivalence. From this we say all objects from this family are of the form A,B,C,... up to some equivalence relation, that is both X and X' are the same object from this classification where prior their only distinction was one (if any) that has been subsequently removed by the equivalence relation. Perhaps maybe in a category-theoretic manner, distinctions can be made between particular classifications, something distinct in the particular structure of the classification such that they can be classified. – user7485 Feb 16 '11 at 14:43
up vote 12 down vote accepted

In a sense, yes.

The object of descriptive set theory is to understand "definable" sets of reals (as opposed to arbitrary sets). So, for example, we concern ourselves with Borel sets, or their continuous images, or the complements of those images, or countable unions of such things, etc. Also, we study other spaces, not just the set of reals.

The basic setting is that of Polish spaces, i.e., complete metrizable spaces with a countable dense subset. This of course includes ${\mathbb R}$, but many other spaces that appear in practice are here.

It turns out that many classification problems that occur in practice have the form: We have a Polish space $X$ and an equivalence relation $E$ on $X$ (typically, $E$ is either Borel as a subset of $X\times X$, or the continuous image of a Borel set). We then study the complexity of the quotient space $X/E$.

This can be measured in several ways. For example: Can we pick in a "Borel fashion" a representative of each equivalence class? If not, can we in a sense approximate the graphs of "choice functions" even if we cannot actually single out one of them?

It turns out that we can prove results that say that certain classification problems are strictly harder than certain others, and we can study the "partial ordering" of classification problems according to complexity.

To be a bit more precise, consider the problem: Given two $5\times 5$ matrices with real entries, are they similar? This is a classification problem: We want to pair matrices that are similar, and the question is how hard is it to decide whether they are paired. It turns out that the Jordan canonical form of two matrices is the same iff they are similar, and the Jordan form can be handily coded by a real number, so the problem reduces to "can we identify if two reals are equal?"

There are two ways of measuring the complexity of this problem. One is in terms of complexity theory, and then we need to talk about how the reals are "given" to us. The other way is the descriptive set theoretic one: We have a Polish space: ${\mathbb R}$; and an equivalence relation: equality. This is as simple as a problem gets.

Another problem is: Given two auto-homeomorphisms of the unit square, when are they conjugate? This is a harder problem, meaning, there is no "Borel" map that to an auto-homeomorphism assigns a real number so that two homeomorphisms are conjugate iff they have been assigned the same real.

A good place to learn about this (and about the wide variety of examples that this approach covers) is "A survey of current and recent work on the theory of Borel equivalence relations" by G. Hjorth. It is available from his webpage, at

share|cite|improve this answer
We are so extremely lucky to have two such marvelously knowledgeable logicians on call! :) – Mariano Suárez-Alvarez Feb 16 '11 at 21:00
Many thanks, Mariano! – Andrés E. Caicedo Feb 16 '11 at 21:45
@Andres: Should the problem about real matrices use the Jordan canonical form, or the rational canonical form? Not every real matrix has a JCF over the reals. I guess you can argue that if two real matrices have the same complex Jordan canonical form, then they are conjugate over $\mathbb{C}$, and hence over $\mathbb{R}$... still, seems like using the RCF would be simpler. – Arturo Magidin Feb 17 '11 at 2:54
@Arturo: You are right, but in the descriptive set theoretic sense both approaches have the same complexity. The point was that there is a "simple" procedure that assigns to each matrix what is essentially a number. Simple means that the map (matrix $\mapsto$ number) is Borel, and of course some Borel sets that are much more complex than others, but (currently) we largely ignore this fine structure. – Andrés E. Caicedo Feb 17 '11 at 3:34
@Arturo: I understand. The thing is that ${\mathbb C}$ and ${\mathbb R}$ are both uncountable Polish spaces, so we can "translate" between them and from the "Borel viewpoint" they are indistinguishable. – Andrés E. Caicedo Feb 17 '11 at 3:40

Allow me to supplement Andres's excellent answer by copying over the following answer that I gave over at this MO question:

How can we understand in a precise general way the idea that a given classification problem is complicated or simple? How are we to compare the relative difficulty of two classification problems?

These questions form the central motivation for the emerging subject known as Borel equivalence relation theory (see Greg Hjorth's survey article, greatly missed after his recent death). The main idea is that many of the most natural equivalence relations arising in many parts of mathematics turn out to be Borel relations on a standard Borel space. To give one example, the isomorphism problem on finitely generated groups, but of course, there are hundreds of other examples. A classification problem for an equivalence relation E is really the problem of finding a way to describe the E-equivalence classes, of finding an E-invariant function that distinguishes the classes.

Harvey Friedman defined that one equivalence relation E is Borel-reducible to another relation F if there is a Borel function f such that x E y if and only if f(x) F f(y). That is, the function f maps E classes to F classes in such a way that different E classes get mapped to different F classes. This provides a classification of the E classes by using the F classes. The concept of reducibility provides a precise, robust way to say that one relation F is at least as complex as another E. Two relations are Borel equivalent if they reduce to each other, and we are led to the hierarchy of equivalence relations under Borel reducibility. By placing an equivalence relation into this hierarchy, we come to understand how complex it is in comparision with other equivalence relations. In particular, we say that one equivalence relation E is strictly simpler than F, if E reduces to F but not conversely.

It sometimes happens that one has a classification problem E and is able to provide a classification by assigning to each structure a countable list of data, such that two structures are equivalent iff they have the same data. This amounts to a reduction of E to the equality relation =, for two structures are E equivalent iff their data is equal. Such relations that reduce to equality are called smooth, and lay near the bottom of the hierarchy of Borel equivalence relations. These are the simplest equivalence relations. Thus, one way of showing that a relation is comparatively simple, is to show that it is smooth, and to show it is comparatively hard, show that it is not smooth.

The subject of Borel equivalence relation theory, as now developed by A. Kechris, G. Hjorth, S. Thomas and many others, is focused on placing many of the natural classification problems of mathematics into this hierarchy. Some of the main early results are the following interesting dichotomies:

Theorem.(Silver dichotomy) Every Borel equivalence relation E either has only countably many equivalence classes or = reduces to E.

The relation E0 says that two binary sequences are equivalent iff they agree from some point onward. It is easy to see that = reduces to E0, and an elementary argument shows that E0 does not reduce to =. Thus, E0 is strictly harder than equality. Moreover, it is a kind of next-step up in the hiearchy, in light of the following.

Theorem.(Glimm-Effros dichotomy) Every Borel equivalence relation E either reduces to = or E0 reduces to E.

The subject continues with many interesting results that gradually illuminate more and more of the hierarchy of Borel equivalence relations. For example, the Feldman-Moore theorem shows that every Borel equivalence relation E having every equivalence class countable is the orbit equivalence of a countable group of Borel bijections of the space. The relation Eoo is the orbit equivalence of the left-translation action of the free group F2 on its power set. This relation is complete for the countable Borel equivalence relations, in the sense that every countable Borel equivalence relation reduces to it. It's great stuff!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.