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.


David Kueker (University of Maryland): April 11-18 TITLE: Forcing, Generics and Infinitary Logics I,II
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.

Wilfrid Sieg (Carnegie Mellon University):
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.

Charles Steinhorn (Vassar College) May 12-16


Spring 97 talks before March 12


Chris Laskowski (University of Maryland): February 22-25; lecture on 24th

Monday Feb. 24 4:00
What do the law of large numbers, PAC learning, model theory and neural networks have in common?
412 SEO

Jim Lynch (Clarkson University): Feb 23-29:

Professor Lynch will speak twice:
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.

Kevin Compton (University of Michigan): March 2-5:
Colloquium March 3 4:00 636 SEO


Probabilistic Results in Combinatorics via Ehrenfeucht-Fraisse Games

Many new results concerning random structures (e.g., random graphs, random functions, random abelian groups, etc.) have come to light through a logical approach. Rather than computing the asymptotic probabilty of a particular property (i.e., the limiting probability of the property as the structure size increases), we instead show that all properties expressible in some logic have an asymptotic probability and (in some cases) provide an algorithm for computing this probability. One of the basic techniques for proving these results is the method of Ehrenfeucht-Fraisse games. We will give a general introduction to these games and show how computing probabilities of properties in random structures reduces to computing probabilities of winning strategies in these games.

Zero-One Laws and Limit Laws from Methods of Analytic Number Theory

Kevin Compton (University of Michigan) Wed. Mar. 5, 3:00.
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.

Jouko Vaananen (University of Helsinki), March 5-11:

Friday March 7 3:00 512 SEO
Monday March 10 2:00
1. Trees and Ehrenfeucht-Fraisse games
2. Generalized quantifiers on finite models)
412 SEO


Anuj Dawar (University of Swansea): March 30-April 6


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

Oleg Belegradek (University of Kemerovo): April 3-8:


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

Yuri Gurevich (University of Michigan): April 4-6:


April 4 3:00 PM 512 SEO
Finite Model Theory - a subjective survey.

Midwest Model Theory
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