The Department of Mathematics, Statistics, and Computer Science
is sponsoring a series of lectures in logic and computer science
during the spring semester of 1997. The speakers will discuss
topics including model theoretic algebra, descriptive complexity theory, the
history of logic,
and random graphs. Abstracts of the earlier talks in the series are at the end of
this list.

ABSTRACT: We use model-theoretic forcing to study the properties, finitary and infinitary, of generic models obtained from smooth classes of finite structures.

April 15 -. 3:00 PM room tba

Apr 16 - 3:00 PM room tba

The intended visit of Angus Macintyre (Oxford University)has been postponed to the Fall. Talks during the week will be in the Science and Engineering Offices Building.

Colloquium April 17 NOTE DATE CHANGE: TALK on THURSDAY

Hilbert's Programs: 1917-1922

Abstract: Hilbert~s finitist program was not created at the beginning of the twenties solely to counteract Brouwer~s Intuitionism, but rather emerged out of broad philosophical reflections on the foundations of mathematics and out of detailed logical work; that is evident from notes of lectures that were given by Hilbert and prepared in collaboration with Bernays, in the period from 1917 to 1922. These notes reveal a dialectic progression from a critical logicism through a radical constructivism towards finitism; the progression has to be seen against the background of the stunning presentation of mathematical logic in the lectures given during the winter term 1917/18. In this talk, I sketch the connection of Hilbert~s considerations to issues in the foundations of mathematics during the second half of the 19th century, describe the work that laid the basis of modern mathematical logic, and analyze the first steps in the new subject of proof theory. A broad revision of Hilbert~s and Bernays~ contributions to the foundational discussion in our century has long been overdue. It is almost scandalous that their carefully worked out notes have not been used yet to understand more accurately the evolution of modern logic in general and of Hilbert~s Program in particular. One conclusion will be obvious: the dogmatic formalist Hilbert is a figment of historical (de)construction! Indeed, the study and analysis of these lectures reveal a depth of mathematical-logical achievement and of philosophical reflection that is remarkable. In the course of my presentation many questions are raised and many more can be explored.

What do the law of large numbers, PAC learning, model theory and neural networks have in common?

412 SEO

Wed. Feb. 26 3:00 427 SEO

Fri. Feb. 28,

3:00 512 SEO.

His topics are: 1. convergence and nonconvergence laws for first-order logic of random structures with built-in order relations (successor, linear order).

2. convergence and nonconvergence laws for random graphs.

Colloquium March 3 4:00 636 SEO

627 SEO

A class of structures has a (first-order) limit law if every property expresible in first-order logic has a limiting probability in random structures chosen from this class. If, in addition, the limiting probability is always either 0 or 1, the class is said to have a 0-1 law. Most of the work concerning limit laws and 0-1 laws has focussed on combinatorial structures such as graphs and permutations. However, limit laws and 0-1 laws for various classes of algebraic structures such as groups and rings have been shown recently using methods of analytic number theory. We will give a general introduction to enumeration by means of Dirichlet series and Tauberian methods for obtaining asymptotics. Related methods were used to prove the Prime Number Theorem and other results in number theory. We then show how these methods yield limit laws and 0-1 laws.

Monday March 10 2:00

1. Trees and Ehrenfeucht-Fraisse games

2. Generalized quantifiers on finite models)

412 SEO

Mar 31 - The Search for a Logic for P. 3:00 PM 512 SEO

Apr 2 - Elementary Properties of the Finite Ranks. 4:00 PM 427 SEO

April 3: 4:00 512 SEO Definability in the finite over infinite ordered structures I

April 7: 3:00 512 SEO Definability in the finite over infinite ordered structures II

April 4 3:00 PM 512 SEO

Finite Model Theory - a subjective survey.

Saturday, April 5, 1997

Room C-3 Lecture Center

9:00 AM: Coffee and Dougnuts

9:30 AM: Oleg Belegradek (Kemerovo) Quasi-o-minimal groups

11:00 AM: Mark Schlatter (Kirksville): Extensions of Results of Shelah and Morley to Permutation Groups

2:00 PM: Anuj Dawar (Swansea): Generalized Quantifiers and 0-1 Laws.

3:30 PM: Yuri Gurevich (Ann Arbor): Finite Model Theory, Abstract State Machines and Choice-less Polynomial Time

After dinner there will be a party at Baldwin's 1064 W. Polk.

Some sleeping accomodations are available. Chez Baldwin now has more floor space.

E-mail: jbaldwin@math.uic.edu (Note this has changed and my old address has become limbo.)

phone: 312-226-1897

Back Home