Special logic week September 26-30, 2005

Each day 4:30 - 5:30 p.m.

Tutorial: Monday, Tuesday, Wednesday and Friday Doherty Hall 1212

PAL Colloquium : Thursday in Baker Hall A53 with refreshments at 4 p.m.

Itay Neeman, Department of Mathematics, UCLA

"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 Gödel sentences, and they need not allow defining cardinality.

Let ON be the class of all ordinals. It is not hard to see that ω_n is definable over (ON,<) by a monadic formula, for each n < ω. Assuming large cardinals it is consistent that ω_ω+1 is definable (Magidor). I will show that ω_ω 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

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.

Contact

Ernest Schimmerling
Department of Mathematical Sciences
Carnegie Mellon University
E-mail: eschimme-at-andrew