MIT Logic Seminar

Fall 2009
Wednesday 4:30 - 5:30 pm
Room 2-139
(Please note the new room!)

There will be tea and cookies available before the seminar in the math department common room, 2-290. Please join us there!

For more information, or to be added to the mailing list, contact Cameron Freer or Mia Minnes.


  • September 9: Organizational meeting


    Randomness and Genericity

    No weakly 1-generic real is random for any reasonably strong definition of randomness. However, it is possible for a random real and a generic real to exist in the same Turing degree or even the same weak truth table degree. In this talk, I will describe the extent to which this is possible for one of the weakest randomness notions, Schnorr randomness, and different levels of genericity.

    This work is joint with Frank Stephan.


    Probabilistically Checkable Proofs

    As advances in mathematics continue at the current rate, editors of mathematical journals increasingly face the challenge of reviewing increasingly long, and often wrong, "proofs" of classical conjectures. Often, even when it is a good guess that a given submission is erroneous, it takes excessive amounts of effort on the editor/reviewer's part to find a specific error one can point to. Most reviewers assume this is an inevitable consequence of the notion of verifying submissions; and expect the complexity of the verification procedure to grow with the length of the submission.

    Research over the past two decades in theoretical computer science has shown that this state of affairs need not continue: There does exist a format in which we can ask for proofs of theorems to be written. This format allows for perfectly valid proofs of correct theorems, while any purported proof of an incorrect assertion will be "evidently wrong", so that a reviewer checking consistency of a very parts of the proof (probabilistically) will detect an error. This format of writing proofs are known as Probabilistically Checkable Proofs (PCPs). In this talk, we will describe the notion, explain why theoretical computer scientists are interested in theorems and proofs, and attempt to give an idea of how such PCP formats, and verification methods are designed.


    Model theory of Nakano spaces

    Working in the framework of continuous logic for metric structures, we show that some elementary classes of Nakano spaces admit quantifier elimination and are stable. If time allows, we'll discuss some partial positive results in the more general setting of Musielak-Orlicz spaces.


  • Wednesday, October 7: No seminar; special talk at Harvard the next day, however:

    Unprovable Theorems

    An unprovable theorem is a theorem about basic mathematical objects that can only be proved using more than the usual axioms for mathematics (ZFC = Zermelo Frankel set theory with the Axiom of Choice).

    The highlight of the talk is the presentation of a new unprovable theorem that involves only the usual ordering of the rationals, vectors of rationals, and the +1 function on rationals.

    We first review some previous examples of unprovable theorems in the weaker sense that the proof demonstrably requires some use of logical principles transcendental to the problem statement. These previous contexts include

    1. Patterns in finite sequences from a finite alphabet.
    2. Pointwise continuous embeddings between countable sets of reals (or, more concretely, rationals).
    3. Relations between f(n1,...,nk) and f(n2,...,nk+1).
    4. Homeomorphic embeddings between finite trees.
    5. Borel sets in the plane and graphs of one dimensional Borel functions.
    6. Boolean relations between sets of integers and their images under integerfunctions.


    Subtlety and Indescribability; Coherence and Composition

    In his seminal study of ineffable properties of cardinals, Baumgartner discovered that ineffability can be characterized as the result of "composing" the related property of subtlety with the classical property of indescribability. A similar characterization was achieved by Kanamori, with large cardinal axioms related to Vopenka's Principle. After putting these results in a unified framework, we extend them into the realm of Pκλ combinatorics. Finally, we show how subtlety itself can be similarly characterized as the "composition" of two weaker notions.


    Models of Long Sentences I

    Sufficient conditions for the existence of models of uncountably long sentences. The role of stability.


    Computable structures, effective categoricity, and Scott families

    Computability theoretic properties of computable structures often change under isomorphisms. Thus, one of the main themes in computable structure theory is effective categoricity. For a complexity class C, a computable structure A is C-categorical if for all computable isomorphic copies of A, there is an isomorphism that belongs to C. There are syntactical conditions that imply categoricity at specific levels of hyperarithmetical hierarchy, and involve the existence of certain nice Scott families for these structures. We will focus on computable equivalence structures. It is still not known whether the class of these structures with computably enumerable Scott families of computable Σ2 formulas coincides with the class of all limit computably categorical equivalence structures.


  • Tuesday November 3 (4:30 - 6:00 pm in 2-136): Harvey Friedman (Ohio State University)

    Boolean Relation Theory and More

    We discuss the contents of my forthcoming book Boolean Relation Theory and Incompleteness, and the subsequent fixed point theorems. We will provide sketches of some of proofs. A draft of the book is available on my website.

    Note: Harvey Friedman is also speaking Thursday November 5 in the Joint Mathematics Colloquium.


    Random Graphs and the Parity Quantifier

    The classical zero-one law for first-order logic on random graphs says that for any first-order sentence φ in the theory of graphs, as n approaches infinity, the probability that the random graph G(n, p) satisfies φ approaches either 0 or 1. The zero-one law fails to hold for any formalism that can express the parity quantifier; for certain properties, the probability that G(n, p) satisfies the property need not converge, and for others the limit may be strictly between 0 and 1.

    In this talk, I will describe a way of capturing the limiting behavior of properties definable in first order logic augmented with the parity quantifier, FO[parity], over G(n, p), thus eluding the above hurdles. Specifically, I will describe the following "modular convergence law": For every FO[parity] sentence φ, there are two dyadic rational numbers a_0, a_1, such that for i in {0,1}, as n approaches infinity, the probability that the random graph G(2n+i, p) satisfies φ approaches a_i. Our results also extend appropriately to first order logic equipped with Mod-q quantifiers for prime q.

    Our approach is based on multivariate polynomials over finite fields and on a new generalization of the Gowers norm. The proof generalizes the original quantifier elimination approach to the zero-one law, and has analogies with the Razborov-Smolensky method for lower bounds for AC0 with parity gates.

    (Joint work with Phokion Kolaitis.)


  • November 11: No Seminar (Veteran's Day)


    Finite sets and number from Dedekind to Tarski

    Richard Dedekind's classic essay Was sind und was sollen die Zahlen? (1888), left two loose ends: his treatment of arithmetic required an infinite set, and his argument for this was not a proper mathematical argument and used a premise that was vulnerable to paradox, and his set-theoretic definition of finite set could be proved equivalent to the standard one only by implicit use of the axiom of choice.

    The talk will trace the two related strands of subsequent work that attacked these problems. As regards arithmetic, the solution, as Zermelo perceived, was to derive arithmetic without assuming an infinite set, and he and his pupil Kurt Grelling showed how to do that. A number of definitions of finiteness were proposed by various authors, and the matter was wrapped up by the young Tarski in his paper "Sur les ensembles finis" of 1924.


  • Monday November 23 (3:15—4:15 in 3-442): Hans Schoutens (New York City College of Technology, City University of New York)

    Special Joint Meeting of the Harvard-MIT Algebraic Geometry Seminar and the MIT Logic Seminar

    Schemic Grothendieck rings and motivic rationality

    We propose a suitable substitute for the classical Grothendieck ring of an algebraically closed field, in which any quasi-projective scheme is represented, while maintaining its non-reduced structure. This yields a more subtle invariant, called the schemic Grothendieck ring, in which we can formulate a form of integration resembling Kontsevich's motivic integration via arc schemes. In view of its more functorial properties, we can present a characteristic-free proof of the rationality of the geometric Igusa zeta series for certain hypersurfaces, thus generalizing the ground-breaking work on motivic integration by Denef and Loeser. The construction uses first-order formulae, and some infinitary versions, called formularies, which in turn can be translated to some notions from topos theory: sieves and formal motives.


  • November 25: No Seminar (Thanksgiving Vacation)


  • December 2: Kerry Ojakian (Queens College, City University of New York)

    Continuous-time versus discrete-time computation over the reals

    There are various models of computation for functions with real number inputs. An intuitive distinction can be made between discrete-time models and continuous-time models. Discrete-time models, like computable analysis, compute using discrete time steps, where there is a clear "next step." For continuous-time models, like Shannon's General Purpose Analog Computer, there is no clear "next step" in the computation; instead time can be thought of as analog. I will overview some models of both kinds. In general the models are incompatible, however, I will discuss some cases where continuous-time and discrete-time models are equivalent, including some of our work on Real Recursive Functions.

    This is joint work with Manuel Campagnolo.


    Model Theory and the question of Noetherianity of Denjoy-Carleman classes

    Last year in this seminar I described a potential application of Model Theory to solve the question whether the ring of a Denjoy-Carleman quasi-analytic class of functions is Noetherian, a problem open over thirty years. (All terms will be explained in the talk.) In this talk, I will outline an argument showing that the answer is NO. The proof is by algebraic and analytic methods, however I will describe how we needed to look through Model Theory in order to see the algebraic-analytic proof. This is a joint work with Andreea Nicoara from UPenn.