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