# Applications of descriptive set theory to mathematical logic?

The Wikipedia article Descriptive Set Theory asserts it has applications to logic, but gives no examples. Kechris' text Classical Descriptive Set Theory does not discuss logical applications, judging by the Table of Contents available at Amazon; neither does David Marker's Descriptive Set Theory.

The only text I've found so far is Moschovakis' Descriptive Set Theory, where Chapter 8 is devoted to Metamathematics.

Are there other resources anyone would like to recommend? -- Thanks.

-
I don't know what exactly you're looking for but apart from the fact that Kechris is one of the very best books on my shelves, there is a brief and informal introduction to forcing in section 16.D starting on page 99 (maybe you're lucky and can have a look). That section was extremely enlightening to me (however: I'm in the target audience of that book: mathematicians with only a modest background in set-theory and logic). –  t.b. Aug 1 '11 at 16:33
@Theo: My main interest is logic and metamathematics, and I've never studied descriptive set theory. I'm trying to make sure I'm not missing something. I think I'll start with the Moschvakis chapter and see how much descriptive set theory I need to learn. Thanks for the pointer to Kechris at Google. (I can't believe they want more for the ebook than the printed one.) –  MikeC Aug 1 '11 at 18:59

One application that I have in mind is in countable model theory:

Vaught's conjecture: If $T$ is a complete countable first order theory, then the number of nonisomorphic countable models of $T$ is either countable or $2^{\aleph_0}$

Shelah and Harrington proved the conjecture for $\omega$-stable theories, but the general problem is still open (it may be the longest standing open problem in model theory, but I'm not really sure).

However, it turns out that a more general problem can be stated in terms of Polish group actions:

Topological Vaught's conjecture: Let $G$ be a Polish group with a Borel-measurable action on a Polish space $X$ and let $A$ be a Borel set of orbits, then either $A$ contains at most countably many orbits, or $A$ contains a perfect set $B$ such that each two elements of $B$ are in different orbits.

Since isomorphism classes of $L_{\omega_1,\omega}$ theories correspond to certain orbits of Polish group actions, TVC implies VC.

See this paper for more background: http://www.jstor.org/stable/2275907

-

If you are looking for examples in other branches of Logic, I believe Higher Computability Theory uses some Effective Descriptive Set Theory. See $\textit{Higher Recursion Theory}$ by Sacks for more on this.

-
William: Thanks for the reference. For me personally, I'm afraid Rogers old text, "Theory of Recursive Functions and Effective Computability", already goes well beyond what I'm capable of grasping. –  MikeC Aug 1 '11 at 22:47
If you want to learn Classical Computability Theory, I would recommend a more modern textbook. Try Robert Soare's textbook or Barry Cooper's textbook. –  William Aug 2 '11 at 7:05

Take a look at a book called Recursive Aspects of Descriptive Set Theory.

Basically, as the book illuminates, almost all the theorems about the hyperarithmetic hierarchy, e.g., hyperarithmetic=$\Delta^1_1$ are just effective versions of their counterparts in effective descriptive set theory (in this case the counterpart would be that Borel =$\mathbf{\Delta^1_1}$ (that is a boldface class). In fact you the analogy is actually a bit stronger and results about hyperarithmetic sets of integers can be thought of as results about effectively presented Borel sets.

Ok, so that takes you one direction. Arguments in descriptive set theory can be refined to provide key arguments in computability theory. There are plenty of other examples of this as well, e.g., the perfect set theorem and the results about binary trees with no computable branches. Also inspiration has been borrowed from results about Borel equivalence relations. If you want to get really hardcore I believe that Borel determinacy has been used by (Slaman? with Steel?) to demonstrate the non-existance of certain kinds of uniform half-jump operators (I may be misremembering this one slightly but similar results do hold).

Going the other direction it's a little more fuzzy depending on what you want to call descriptive set theory vs. set theory vs. higher recursion theory but there are plenty of applications of computability theoretic methods to generate strong set theoretic results.

-