Past Seminars and Colloquia
In 20102011 and 20112012, the Logic Colloquium met (roughly) once every three weeks and involved a major figure in logic. Speakers were asked to provide a topic and some suitable references to the necessary background material required to obtain a better understanding of their talk. The Logic Colloquium was somewhat different than standard colloquia in that there was a closely associated Logic Workshop, which met during the two weeks prior to the talk and consisted of presentations (by local students and faculty) on the background material for the upcoming colloquium.
The 20112012 Logic Colloquium was part of the EFI project, and the Logic Workshop was given by Peter Koellner in preparation for EFI presentations. View the associated syllabus and course website.

September 29, 2010. Peter Koellner: Background Material for October 8 Colloquium.
Andre Nies, "Computability and Randomness" (Chapters 13).
Measures and their Random Reals.
Randomness for continuous measures 
October 8, 2010. Theodore A. Slaman: "Randomness and Mathematical Logic". Download slides. Abstract.
• There has been considerable progress in the recursion theoretic study of randomness in the past several years. I will give a conceptual overview of the area and a more focused discussion of my joint work with Jan Reimann, in which we study the question, "For which infinite binary sequences X is there a (continuous) probability measure relative to which X is effectively random?" The investigation has a surprisingly metamathematical character, and necessarily so.
• Background material will be covered in the September 29 Workshop.
• Location: Science Center 309. 
October 13, 2010. Rachel Epstein: Fundamental Concepts of Computability Theory. Background Material for October 29 Colloquium.
Andre Nies, "Computability and Randomness" (Chapter 1)
Soare, "Computability Theory and Applications" (Chapters 7, 9.12, 10.1)  available by email. [Alternatively: Soare, Recursively Enumerable Sets and Degrees, Chapters 7 and 14.1.] 
October 20, 2010. Rachel Epstein: Injury Arguments and Trees. Background Material for October 29 Colloquium.
Soare, "Computability Theory and Applications" (Chapters 9.12, 10.1)  available by email.

October 27, 2010. Cameron Freer: Invariant measures on countable models. Abstract.
• Abstract: The ErdosRenyi random graph construction can be seen as inducing a probability measure concentrated on the Rado graph (sometimes known as the countable "random graph") that is invariant under arbitrary permutations of the underlying set of vertices. The following question arises naturally: On which countable combinatorial structures is there such an invariant measure? Up until recent work of Petrov and Vershik (2010), it was not even known if Henson's universal countable trianglefree graph admitted an invariant measure.
We provide a complete characterization of countable structures admitting invariant measures, in terms of the modeltheoretic notion of definable closure. This leads to a characterization for ultrahomogeneous structures, as well as new examples of invariant measures on graphs and other combinatorial structures.
Joint work with Nate Ackerman and Rehana Patel.
• Location: Science Center 113. 
October 29, 2010. Rachel Epstein: "Definability in the Computably Enumerable Sets". Download slides. Abstract.
• Definability is one of the fundamental themes of computability theory. We examine the structure of the computably enumerable (c.e.) sets under set inclusion. The problem of which classes of degrees are definable in this structure has been an important topic of study in computability theory. In particular, it has been shown that all upwardclosed jump classes (such as high, nonlow2, etc.) are definable except for the nonlow degrees, which are not definable. To show that the nonlow degrees are not definable, we use automorphisms, which we build on trees of strategies. We will discuss the history of the problem and some of the ideas of the proof.
• See R. Epstein, Invariance and automorphisms of the computably enumerable sets. [pdf]
• Background material will be covered in the in the October 13 and October 20 Workshop.
• Location: Science Center 309. 
November 12, 2010. Gerald Sacks: "Models of Long Sentences II". Abstract.
• The construction of uncountable models of certain infinitary theories via intransitive countable hulls.
• Background material will be covered in the in the Novermber 3 Workshop.
• Location: Science Center 309. 
November 17, 2010. Hugh Woodin: "The Search for Mathematical Truth". Download slides. Abstract.
• The evident ubiquity of (formally) unsolvable problems in Set Theory argues for a reexamination of the conception of truth at least for Set Theory. The mathematical investigation of this apparently nonmathematical problem has led to a surprising series of mathematical conjectures, problems and successes. The stage is now set for either: (1) The validation of a single additional axiom which if added to the traditional ZFC axioms would entirely eliminate the phenomena of unsolvability based on Cohen's method of forcing while preserving the fundamental strong axioms of infinity; or (2) The refutation from the same strong axioms of infinity of any such possibility based on anything like that currently imagined. In other words, Set Theory is facing a critical dichotomy in possible futures.
• Location: Fong Auditorium, at Boylston Hall 110. 
February 4, 2011. Michael Rabin: "Notions of Mathematical Proofs and Persuasions from Computer Science". Abstract.
• Abstract: Over the past thirtyfive years theoretical computer scientists invented new methods and notions of proofs for mathematical statements. These represent a departure from the classical notions of mathematical proofs going back to Euclid. Examples are proofs employing randomization, interactive proofs, zeroknowledge proofs, probabilistically checkable proofs, and computer generated proofs. The lecture will be self contained.
• Background material: M.O. Rabin Probabilistic Algorithm for Testing Primality, Journal of Number Theory, 12, 128138, 1980.
 J.T. Schwartz, Fast probabilistic algorithm for verification of polynomial identities, Journal of the ACM, 27(4), 701717, October 1980.
 S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, 18, 186208, 1989.
• Location & Time: Science Center 309, 4pm. 
February 25, 2011. Warren Goldfarb: "Herbrand and the early development of proof theory". Abstract.
• Abstract: A historical account of the achievements in logic of Jacques Herbrand (19081931), in particular the central result of his 1930 dissertation, often called Herbrand's Theorem (but nowadays often misdescribed); and the significant impact that the Theorem had in application to prooftheoretic questions in the 1930s and later.
• Location & Time: Science Center 309, 4pm. 
March 25, 2011. Harvey Friedman: "Algorithmic Unsolvability in Euclidean Geometry". Manuscript. Abstract.
• Abstract: We show the algorithmic unsolvability of a number of decision procedures in ordinary two dimensional Euclidean geometry, involving lines and integer points. We also consider formulations involving integral domains of characteristic 0, and ordered rings. The main tool is the solution to Hilbert's Tenth Problem. The limited number of facts used from recursion theory are isolated at the beginning.
• Location & Time: Science Center 309, 4pm. 
April 8, 2011. Bjorn Poonen: "Diophantine subsets of rational numbers". Abstract.
• Abstract: I will discuss recent work of Koenigsmann, building on work of the speaker, showing that the complement of Z in Q is diophantine (or equivalently, defined by an existential formula). If Z itself were shown to be diophantine in Q, it would follow that there is no algorithm to decide whether a multivariable polynomial equation has a solution in rational numbers.
• Background material (in the order that they should be read): B. Poonen, Undecidability in number theory, Notices Amer. Math. Soc. 55 (2008), no. 3, 344350. Online version at http://wwwmath.mit.edu/~poonen/papers/h10_notices.pdf.
 B. Poonen, Characterizing integers among rational numbers with a universalexistential formula, Amer. J. Math. 131 (2009), no. 3, 675682. Online version at http://wwwmath.mit.edu/~poonen/papers/ae.pdf
 J. Koenigsmann, Defining Z in Q, preprint, http://arxiv.org/abs/1011.3424
• Location & Time: Science Center 309, 4pm.