# 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

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.

### Contact

Ernest Schimmerling

Department of Mathematical Sciences

Carnegie Mellon University

E-mail: eschimme-at-andrew