Mathematicians Solve Decades-Old Classification Problem

“[Their strategy displays] an incredible amount of cleverness in transforming a complicated problem into something easier,” added Chris Laskowski of the University of Maryland, who has collaborated with Shelah on roughly a dozen papers (though not this one). “Many had tried and not succeeded. It’s great to have this settled.”

Counting Infinities

Because the problem posed by Friedman and Stanley involves a class of infinite countable structures, it helps to understand how mathematicians work with such seemingly unwieldy quantities. For starters, what does it mean for a collection of structures to be “countable”? The natural numbers (0, 1, 2, 3 …) are infinite but still considered countable, for the same reason that they are sometimes called counting numbers. If you call out these numbers sequentially, they’ll pretty much count themselves. (Of course, you’ll be at it for a while.) The number of elements in the set of natural numbers, or its “cardinality,” is labeled aleph-zero. Mathematicians regard any set that’s the same size as the infinite set of natural numbers as countable too.

In contrast, the real numbers — which include the natural numbers as well as rational and irrational numbers — are also infinite, but they are classified as uncountable. The main reason is that there are simply too many of them: We’ve known since the late 1800s that more real numbers are crammed between 0 and 1 than all the natural numbers put together. This is another way of saying that all infinities are not created equal; some are greater than others. The set of real numbers has a bigger cardinality than the natural numbers because there are more of them. Any countable set of numbers either is finite or, if it is infinite, has a cardinality of aleph-zero.

So what can mathematicians do with these ideas? The Friedman-Stanley paper, as well as the new work by Paolini and Shelah, focused on an equivalence relation — called isomorphism — between structures. As an example, let’s consider two infinite but countable groups of numbers:

… −3, −2, −1, 0, 1, 2, 3 …
… −6, −4, −2, 0, 2, 4, 6 …

The first group consists of the integers; the second consists of just the even integers. These two groups are isomorphic to each other because, among other things, they have the same number of elements, which is to say their infinities are the same. And every element of one group corresponds to—or, as mathematicians say, “maps to”—a single element in another set. Moreover, the function used to map from one group to another also must preserve the group operations and properties (such as the associative law of addition).

Isomorphic groups like these are not identical, as they don’t have the same elements, but they do have a parallel structure: Each element in one group is directly related to a single element in another group. A function can convert the first structure into the second, as in the above example, simply by multiplying each element of the first by 2. Isomorphic structures have what Paolini calls “the same shape,” if not the exact same content.

“Saying that two structures are isomorphic means they are essentially the same,” said Laskowski. “You could have a red one or a blue one, but deep down they are the same thing.”

This notion of isomorphism lies at the heart of this decades-old problem.

How Complicated Is Complicated?

In their 1989 paper, Friedman and Stanley mainly wanted to know one thing: Given a family of countable structures — whether they’re infinite groups of numbers (like the integers mentioned above) or graphs (an infinite assortment of vertices that may be connected by edges) — how hard is it to find out whether the objects within that family are isomorphic to each other?

One case taken up by Friedman and Stanley concerned a family of graphs, each with an infinite — though countable — number of vertices. For two countable graphs to be labeled isomorphic, there must again be a 1-to-1 correspondence between vertices in one graph and vertices in the other. And if two vertices are connected by an edge in one graph, the corresponding vertices in the other graph must also be connected by an edge.

Friedman and Stanley showed that answering the question of whether two countable graphs are isomorphic is maximally complicated — as hard as it can possibly be. That qualifies the family of all countable graphs as “Borel complete.” (The pair coined the term in their 1989 paper because of their reliance on a so-called Borel function, devised by the mathematician Émile Borel.)

Friedman and Stanley then wondered: What other classes of countable objects are Borel complete? That simple question, Laskowski said, “is one of the central themes of descriptive set theory.”

In the years since, Friedman, Stanley and others have identified several classes of mathematical objects that satisfy the criteria of Borel completeness, including trees — a simplified kind of graph — and linear orders, a set of numbers (natural or real) that are literally arranged in order, just like the numbers on a number line.

But among the many different cases considered in the 1989 paper, only one — concerning the aforementioned torsion-free abelian groups — resisted classification by isomorphism. To describe this daunting term one step at a time, TFAB groups are, fundamentally, groups of numbers. Each TFAB consists of a countable subset of the real numbers that follows certain group rules, such as being closed under addition and subtraction (so that for any numbers p and q in this group, p + q and p – q also appear in the group). It also obeys the commutative law (meaning that p + q = q + p), a hallmark of abelian groups. Finally, the term torsion-free implies that if g is a nonzero element in the group, then g + g can never equal zero, nor can g + g + g, nor g + g + g +g, and so on.

For 30 years, Shelah said, mathematicians have wondered: “If we have two [countable] torsion-free abelian groups, and we ask if they are isomorphic, is this an easy problem, an intermediate problem or the hardest problem?”

Of all the problems raised in the Friedman-Stanley paper, this one took the longest to solve, Kechris said. “So it’s reasonable to call it the most challenging.” A new approach was needed before it would yield.

Shelah and Paolini finally found a way to break through earlier this year.

Transformations Across Structures

They did it by using a classic mathematician’s trick: reducing an intransigent problem to a somewhat more manageable one. If they could show that TFABs were as complex as another family of structures already known to be Borel complete — say, the family of countable graphs — it would prove that TFABs were, too. “If you want to find out if a person is the tallest in the world, what’s a smart way of doing it?” Paolini asked. “Rather than checking with everyone on Earth, you go instead to the person who is considered tallest and see who is taller.”

Having decided to use countable graphs as the yardstick, Shelah explained, they faced the critical next step: to create a function (specifically a type of Borel function) that could “take a graph and transform it into a torsion-free abelian group.” Their function would need to accept a graph as its input and produce a TFAB as its output, in the process transferring information from the graph to the group. More specifically, the function f would have to satisfy the following relation: Two countable graphs, G and H, are isomorphic to each other if and only if f(G) and f(H) are countable TFABs that are also isomorphic to each other.

The task was not easy, as there was no available “technology” the pair could draw upon to link such distinct mathematical objects; they had to invent it just for this problem.

“The whole game came down to building this function,” Laskowski said. “It’s like comparing apples and oranges. Graphs and groups don’t have the same vocabulary. So what you are doing in situations like this is creating a correspondence.”

And again, they’re really comparing infinite groups of apples with infinite groups of oranges. Luckily, Shelah said, they found a way to simplify things. “Instead of dealing with all graphs, you can [use] one graph that is universal” — a graph so gargantuan that its subgraphs, the smaller graphs contained within it, include all possible countable graphs.

It was an impressive tactic, Laskowski said. “Instead of trying to take on this problem directly, which would involve a heck of a lot of graphs and groups, I’ll just pick this one mother countable graph, and every countable graph appears under its umbrella.”

In this way, Paolini and Shelah were able to construct the necessary function thereby demonstrating that graphs and TFABs are on a kind of equal footing. “We found a way of associating torsion-free abelian groups with graphs so that isomorphism is preserved,” Paolini said.

And since mathematicians already knew the family of countable graphs was Borel complete — that is, maximally complicated with respect to isomorphism — this meant the family of countable TFABs must also be Borel complete. They finally had their answer.

New Jungles to Explore

Could this result lead to something more general? “That remains to be seen,” Kechris said, “but it’s quite possible.”

Paolini and Shelah are, in fact, already looking into extending their result. Having solved the case of countable TFABs, they are now investigating the larger set of uncountable TFABs, which “may have a different answer,” Shelah said.

There’s reason to think that they may find out. “Shelah has a theory,” Laskowski said, “that certain questions become easier when you push them up to higher cardinality” — higher levels of infinity — because when the numbers get really big, the distance grows between important numbers, such as primes and squares of integers. As a result, Shelah told Laskowski, “the air becomes clearer,” potentially making it easier for mathematicians to see things.

In the meantime, their paper on countable TFABs already has some immediate practical implications. “We now know that you are restricted in what you can do,” Shelah said. For example, you won’t ever find distinguishing properties (called invariants) of this family of groups that will automatically tell you if two TFABs are isomorphic.  That is a direct consequence of the fact that the set of countable TFABs is Borel complete.

“We proved that there is no easy way of determining [isomorphisms] at all,” Paolini said. “There is no middle ground. It is as difficult as possible.”

This is useful knowledge, given that searching for invariants is a major preoccupation among mathematicians. “It’s kind of like saying that people should not spend a lot of time trying to invent a perpetual-motion machine,” Shelah said, “given that we now know that such a machine cannot be built.”

Looking to the future, it’s possible that mathematicians will uncover other classes of infinite, countable structures, like graphs and TFABs, that are maximally complicated when it comes to determining isomorphisms. In the same way, Paolini said, “it’s conceivable that we could find other jungles on Earth that are as complicated as the Amazon.” But of course in this analogy, none could ever be more complicated.

Just knowing that fact, and knowing that TFABs are as complicated as possible, can simplify, or uncomplicate, the picture — for taxonomists and descriptive set theorists alike.

Correction: August 5, 2021
The Borel function was named after Émile Borel, not Armand Borel. The article has been revised accordingly.