The goal of these seminars is to capitalize on the new additions to
the logic scene in the greater Toronto area and to explore points of
commonality between these two areas; talks are meant to be expository
and informal. Meetings take place on select Mondays in the Fields Institute
Boardroom. Look for announcements in the weekly seminar listings.

Organizers: **Bradd Hart**, McMaster University, **Toniann Pitassi**,
University of Toronto

### Schedule

November 12, 2002 **Neil Thapen**, University of Toronto.

*Models of bounded arithmetic*

Definition of theories, model-theoretic proof of witnessing theorem;

The weak pigeonhole principle; if it isn't provable in ID0, then ID0
isn't finitely axiomatizable;

WPHP for polynomial time functions; witnessing in probabilistic polynomial
time; some consequences;

Characterization of WPHP as saying that large initial segments of a
model are more complicated than small ones; co-ordinatization theorem;
some speculation.

November 21, 2002 **Neil Thapen**, University of Toronto.

*Models of bounded arithmetic II*

December 5, 2002 **Neil Thapen**, University of Toronto.

*Models of bounded arithmetic III*

January 16, 2003 **Neil Thapen**, University of Toronto.

*Models of bounded arithmetic IV*

February 3, 2003 **Neil Thapen**, University of Toronto.

*Models of bounded arithmetic V*

February 10, 2003 **Bradd Hart**, McMaster University

*Triangle-free graphs and the finite model property*

back to top