Effecive Mathematics of the Uncountable, New York (August, 2009)

Borel subsets of ω₁-Baire space

It is natural to do descriptive set theory on the ω₁-Baire space, that is, (ω₁)^(ω₁), with the topology generated by the countably determined sets. Vaananen and others have done a great deal of work to prove analogs of classical theorems for this space.

In this space, the closest analog of the Borel sets are the ω₁-Borel sets, that is, the smalest ω₂ algebra contaning the open sets. Unfortunately, this space lacks a "separation" theorem, so that the ω₁-Borel sets are a paltry subclass of the Δ¹₁ sets. There is a wide gap in between them, and we will present a number of open questions concerning this gap.

Computability in Europe (July, 2009)

Inifinite-time Turing machines and Borel reducibility

The infinite-time Turing machine is a generalization of the classical Turing machine introduced by Hamkins. It has essentially the same apparatus as a Turing machine, but it is allowed to continue computation even after infinitely many steps. At limit ordinal stages, it enters a special limit state, the read/write head resets to the left of its tape, and the value of each cell passes to the lim-sup of the values that it formerly held. The sets recognized by such a machine lie properly within the class Δ¹₂. In this talk, I will outline a few recent developments in the descriptive set-theoretic aspects of inifinite-time Turing machine theory. I will also discuss some connections with the theory of Borel equivalence relations.

This talk will include work of Joel Hamkins, Philip Welch and others.

Workshop on Large Cardinals and Descriptive Set Theory (June, 2009)

On dimension and Borel reducibility

Borel reducibility of equivalence relations was introduced by Friedman and Stanley in 1989. This powerful concept allows us to use methods of descriptive set theory to compare the complexity of classification problems from other areas of mathematics.

Our starting point will be the amazing result, due to Hjorth and Thomas in 1998-2001, that the complexity of the classification problem for torsion-free abelian groups of finite rank increases strictly with the rank. Other invariants besides just the rank can be used. For instance, Thomas showed that even once the rank is fixed, the classification subproblems for p-local and q-local groups have incomparable complexities.

In each of these results, the "dimension" of the classification problem plays a crucial role. This leaves open the following natural question, which we will discuss in this talk: To what extent do the dimensions of two classification problems decide their relationship under Borel reducibility?

Oberseminar Mathematische Logik, Bonn (May, 2009)

Countable Borel equivalence relations

Borel equivalence relations is an area of descriptive set theory which concerns the complexity of equivalence relations on a standard Borel space (i.e., a Polish space equipped just with its sigma-algebra of Borel sets). There are interesting examples from within logic, such as the Turing equivalence relation on ℘(ω). Moreover, many classification problems for other areas of mathematics can be regarded as equivalence relations on standard Borel spaces. For instance, the classification problem for torsion-free abelian groups of rank n corresponds to the isomorphism equivalence relation on a suitable subspace of ℘(Qⁿ). Both of these examples are instances of countable Borel equivalence relations, that is, equivalence relations that are Borel as subsets of the plane and which have the property that every equivalence class is countable. After giving the definitions, I'll discuss what structure theory exists for these objects. I'll pay special attention to the example of torsion-free abelian groups, where there are several key applications.

CUNY Logic Workshop (April, 2009)

On dimension and Borel reducibility

Borel reducibility is a tool from descriptive set theory which can be used to measure the complexity of classification problems. Our starting point is the amazing result, due to Hjorth and Thomas, that the classification problem for torsion-free abelian groups of finite rank increases strictly in complexity with the rank. Other invariants besides just the rank can be used. For instance, Thomas showed that even once the rank is fixed, the classification subproblems for p-local and q-local groups have incomparable complexities. In each of these results, the "dimension" of the classification problem plays a crucial role. This left open the natural question: to what extent do the dimensions of two classification problems decide their relationship under Borel reducibility? In this talk, we will motivate and discuss all of the above notions, before giving a partial answer to this question.

MIT Logic Seminar (March, 2009)

Some countable Borel equivalence relations

Borel equivalence relations is an area of descriptive set theory which concerns the complexity of equivalence relations on a standard Borel space (i.e., a Polish space equipped just with its σ-algebra of Borel sets). There are interesting examples from within logic, such as the Turing equivalence relation ≡_T. Moreover, many classification problems from other areas of mathematics can be regarded as equivalence relations on standard Borel spaces. For instance, the classification problem for torsion-free abelian groups of rank n corresponds to the isomorphism equivalence relation on a suitable subspace of ℘(Qⁿ). All of these examples are instances of countable Borel equivalence relations, that is, equivalence relations that are Borel as subsets of the plane and which have the property that every equivalence class is countable. After giving the definitions, I'll discuss what structure theory exists, paying close attention to the role of these special examples.

Bronx Community College (December, 2008)

The set theory of classification problems

Classification problems arise everywhere in mathematics: one might wish to classify some groups or rings up to isomorphism, some group actions up to conjugacy, homeomorphisms of some space up to homotopy, etc. Descriptive set theory gives us a very simple (but totally appropriate) definition of the "complexity of a classification problem," which makes sense in a wide variety of cases. Studying things from this point of view, we can learn how close two related problems are, or when one problem is outright hopeless. I'll give all the definitions, and some important examples of recent repute.

AMS Sectional Meeting, Wesleyan (October, 2008)

Borel equivalence relations

Often a "classification problem" can be regarded as an equivalence relation on a standard Borel space (i.e., a Polish space equipped just with its σ-algebra of Borel sets). For instance, the classification problem for countable linear orders (on ω) corresponds to the isomorphism equivalence relation on a suitable subspace of ℘(ω×ω). This allows for an analysis of the complexity of the isomorphism problem for many classes of countable structures using techniques from an area of descriptive set theory called Borel equivalence relations. In this talk we shall describe some recent and important results in Borel equivalence relations, as well as a couple of interactions with model theory.

Effective Mathematics of the Uncountable, New York (August, 2008)

Equivalence relations and infinite-time computable reductions

Many classification problems can be thought of as an equivalence relations on 2^ω. For instance, any countable linear ordering on ω can be coded as an element of 2^ω, and the classification problem for countable linear orders can be identified with the isomorphism equivalence relation on these codes. If E,F are equivalence relations on 2^ω, then a reduction from E to F is a function f:2^ω→2^ω such that

Joint Meetings, San Diego (January, 2008)

On the classification of torsion-free abelian groups up to quasi-isomorphism

Up to isomorphism, the torsion-free abelian groups of rank n are members of the following standard Borel space: R_n= the subgroups of Qⁿ which contain a basis for Qⁿ. Hjorth and Thomas have shown that the isomorphism equivalence relations on the R_n increase in complexity with n.

Here is the relevant complexity notion, due to H. Friedman. For E,F Borel equivalence relations on standard Borel spaces X,Y, write E≤_BF iff there exists a Borel function f:X→Y such that

We compare the isomorphism equivalence relation on R_n with that of quasi-isomorphism. The definition is: A,B∈R_n are quasi-isomorphic iff A is commensurable with an isomorphic copy B'∈R_n of B. The advantage is that unique decomposition holds with respect to quasi-isomorphism, but fails with respect to isomorphism. This leads one to ask whether quasi-isomorphism is truly less complex than isomorphism.

Our result is a "no" answer, namely that the isomorphism and quasi-isomorphism relations on R_n are incomparable with respect to ≤_B. The proof relies on a recent superrigidity theorem, due to A. Ioana, regarding profinite actions of Kazhdan groups.

CUNY Logic Workshop (November, 2007)

On the classification of torsion-free abelian groups up to quasi-isomorphism

Hjorth and Thomas have used the theory of countable Borel equivalence relations to show that the classification problem for the torsion-free abelian groups of rank n strictly increases in complexity with the rank n. In the first half of the talk, I will present a brief introduction to the theory of countable Borel equivalence relations, including the notion of a "Borel reduction" which provides a complexity comparison for Borel equivalence relations. Then I will show how to identify the classification problem for torsion-free Abelian groups of fixed finite rank n with a suitable Borel equivalence relation on a standard Borel space.

In the second half of the talk, I will study the "quasi-isomorphism" relation on the space of torsion-free abelian groups of rank n. Here, A and B are said to be quasi-isomorphic iff A is commensurable with an isomorphic copy of B. Although Thomas has shown that the complexity of the quasi-isomorphism relation also strictly increases with the rank n, there are a number of ways in which quasi-isomorphism is "nicer" than isomorphism, and it is natural to conjecture that the isomorphism relation is simpler than the quasi-isomorphism relation. Neverthless, I will outline a proof that the isomorphism and quasi-isomorphism equivalence relations are actually incomparable with respect to Borel reducibility.