Itay Neeman
University of California, Los Angeles

"Finite state automata and monadic theories of ordinals"

Abstract:

A formula is monadic second order (monadic for short) if each of its variables is assigned a type, either the type ``first order'' or the type ``second order''. In defining the truth value of a formula in a structure (A,...) we take the first order variables to range over elements of A, and take the second order variables to range over subsets of A. Note that monadic formulae do not allow, at least not directly, talking about sets of pairs of elements of A. In particular they need not introduce Goedel sentences, and they need not allow defining cardinality.
Let ON be the class of all ordinals. It is not hard to see that omega_n is definable over (ON,<) by a monadic formula, for each n < omega. Assuming large cardinals it is consistent that omega_{omega+1} is definable (Magidor). I will show that omega_omega is not definable. In fact, no singular cardinal is definable. The proof uses finite state automata, acting on infinite strings, to convert monadic formulae over the ordinals to formulae of a specific kind that allows talking about clubs, stationary sets and reflection, but does not allow quantifying over individual ordinals. Many other questions concerning the power of the monadic language over (ON,<) remain open, and I will mention these at the end of my talks.
I will assume familiarity with basic logic and set theory, including ordinals, cardinals and stationary sets. Knowledge of finite state automata and the classical decidability results (cf. Chapters 2 and 3 of Automata theory and its applications by Khoussainov and Nerode) would be helpful but not necessary.

Preprint: www.math.ucla.edu/~ineeman/fsa.pdf

Biography: Itay Neeman is best known for his work in set theory, particularly on the determinacy of games and inner models for large cardinals. He received the Ph.D. in Mathematics from UCLA in 1996 and shared the Sacks Prize with Byunghan Kim for the two best doctoral dissertations in mathematical logic that year. Between 1996 and 2000, Neeman was a Harvard Junior Fellow. He was awarded a Humboldt Research Fellowship in 1999 and an NSF CAREER Award in 2001 among other honors. Currently, he is an Associate Professor of Mathematics at UCLA.

Further Information about this event:

Itay Neeman will lecture on this topic during the week of September 26-30. He will give a series of seminars (tutorial) on Monday, Tuesday, Wednesday and Friday from 4:30 to 5:30 in DH 1212

Back to Talks Page