|
- September 9: Organizational meeting
Randomness and Genericity
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:
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
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
|