- Special Logic Seminar
Monday, January 25, 2010, 3 PM in 2-131:
(University of Toronto)
Cofinal Types of Ultrafilters
A directed set D is said to be Tukey reducible to another directed set
if there is a function f: D → E
which maps unbounded subsets of D to unbounded subsets of E. We say
D and E are Tukey equivalent, written
The notion of Tukey equivalence tries
to capture the idea that two directed posets "look cofinally the same",
or have the same "cofinal type". As such, it provides a device for a
"rough classification" of directed sets based upon their "cofinal
type", as opposed to an exact classification based on their isomorphism
type. This notion has recently received a lot of attention in various
contexts in set theory. In joint work with Todorcevic, I have
investigated the Tukey theory of ultrafilters on the natural numbers,
which can naturally be viewed as directed sets under reverse containment.
In the case of ultrafilters, Tukey reducibility is coarser than the well
studied Rudin-Keisler reducibility (RK reducibility). I will present some
recent progress on the Tukey theory of ultrafilters, focusing on the
question "under what conditions is Tukey reducibility actually equivalent
to RK reducibility?".
- Special Logic Seminar
Wednesday, January 27, 2010, 3 PM in
(University of California, Berkeley)
Definability and Randomness
In mathematical logic, one often tries to classify objects by their
descriptive complexity, for example, how many quantifier changes are
needed to define a subset of the natural numbers. In the theory of
dynamical systems, one uses measure theoretic concepts like entropy to
describe complex, i.e. random behavior.
Both approaches can be combined to define randomness for individual
objects such as infinite binary sequences. I will discuss various aspects
of the following general question: Given an infinite binary sequence,
does there exist a (non-atomic) probability measure with respect to which
this sequence is random? I will argue that the view from logic opens up
new and perhaps unexpected perspectives on the concept of randomness, in
particular concerning the role of infinity, but also in relation to other
areas like geometric measure theory.
- Special Logic Seminar
Friday, January 29, 2010, 3 PM in 2-131:
(Las Cruces, New Mexico)
Dichotomy Theorems in Descriptive Set Theory
Since the inception of the subject, dichotomy theorems have played a
central role in the development of descriptive set theory. We will
discuss approaches to establishing such theorems using ideas from ergodic
theory and graph theory.
The Computability of Exchangeable Sequences
Exchangeable stochastic processes are of central interest in
probability, statistics, and combinatorics. A sequence of random
variables is said to be exchangeable if its joint distribution is
invariant under the action of the symmetric group on its indices.
de Finetti's theorem states that given an exchangeable sequence of
real random variables, there is an a.s. unique random measure (whose
distribution is known as the mixing measure) conditioned on which
the sequence is i.i.d. The question of the computability of the
mixing measure has become increasingly important in machine learning
We discuss recent work with Ackerman and Roy that settles this and
related questions using techniques from computability theory.
We present a computable extension of de Finetti's theorem, and
highlight some applications to nonparametric Bayesian statistics
and to the design of probabilistic programming languages.
We also present a construction that implies the impossibility of a
general algorithm for computing conditional distributions, and
describe a new method for using forcing arguments in computable
Genericity arguments in groups of finite Morley rank
The Cherlin-Zilber Algebraicity Conjecture proposes that
the simple groups of finite Morley rank, or equivalently the uncountably
categorical simple groups, are in-fact Chevalley groups over algebraically closed
fields. We shall
give a brief overview of the progress towards this conjecture thus
far, which has generally involved transfer of methods from the classification of the finite simple groups. There are however crucial model theoretic results proved using the Cherlin's genericity arguments.
Toricity Theorem. Any p-torsion lies inside a divisible
unless the ambient group of finite Morley rank contains an infinite
C(T) Theorem. The centralizer of a divisible abelian
torsion group in
a connected group of finite Morley rank is itself connected.
We shall give a flavor of the project demonstrating how
the two theorems are applied together in the Prufer 2-rank two case, and we shall
prove the C(T) Theorem.
- February 24: No Logic Seminar
Blum-Shub-Smale machines and Turing-like degrees
The Blum-Shub-Smale (BSS) model for computation over reals generalizes
Turing machines for more general computation. Early work showed that there is a universal
BSS machine and that restricting the runtime of BSS machines leads to a complexity hierarchy
with interesting parallels and interactions with discrete complexity theory.
However, many standard techniques from computability theory cannot be transferred
over directly to the BSS context. In particular, there is no enumeration of all BSS machines because
each may include real-valued parameters. Hence, the degree structure of the BSS-degrees
(defined analogously to the Turing degrees) must be explored with novel techniques.
In this talk, we will introduce the BSS model and outline some of the foundational results and some new results (joint with Johanna
Franklin) in the exploration of the degree structure. In particular, time permitting, we will discuss connections between BSS degrees and Julia sets from
Introducing the Bounded Jump
In recent work with Rod Downey and Selwyn Ng, we show that, for
usual Turing Jump, analogs of Sacks' and Shoenfield's jump
inversion fail for
both the truth table and bounded Turing (more commonly known as weak
table) reducibilities. This gives further evidence that since the
Turing jump is
defined with respect to Turing reducibility, perhaps it is not the
to be considering on stronger reducibilities. Together with Bernie
have defined what we call the bounded jump, a jump operator on the
Turing degrees. I will present some desirable properties of the
- March 17: No Logic Seminar
- March 24: No Logic Seminar (Spring Break)
- March 31: No Logic Seminar
- Thursday April 8,
4:30 pm in 2-136:
(NYC College of Technology – CUNY)
A natural model of the multiverse axioms
In the past decades, set theorists studied a multitude of set
theoretic universes constructed as forcing extensions or sub-models
and often incorporating strong
axioms of infinity. Cohen's forcing was generalized to build
extensions according to nearly any desired recipe, while
Gödel's construction of L was generalized to obtain
increasingly sophisticated sub-models. Against this background, it
can be argued that set theory moved away from the study of the set
theoretic universe to that of the set theoretic Multiverse.
Philosophically, a multiverse encompasses a rich collection of
possible ZFC-universes. It should include universes satisfying or
failing to satisfy Continuum Hypothesis, Martin's Axiom, Diamond
Principle, etc. Some universes in the multiverse should be
countable from the perspective of other universes, some ill-founded,
and some ultrapowers. The multiverses admit a purely mathematical,
non-philosophical treatment as mathematical objects in ZFC. We
define that a multiverse is simply a nonempty set or class of models
of ZFC. The Multiverse Axioms for such collections are intended to
capture the richness and interconnectedness of the ZFC worlds. They
- A definable class of a member of the multiverse is also
- A forcing extension of a member of the multiverse is
also a member.
- Every member of the multiverse is countable/ill-founded from the perspective of another member.
- Every member of the multiverse is an internal ultrapower
of another member; every definable elementary embedding of a member is an iterate of an
embedding of another member.
In this talk, I will introduce the multiverse axioms and show that
the collection of all countable computably saturated models of ZFC
is a natural model of the multiverse axioms if it is non-empty. A
model is computably saturated if it already realizes all its
finitely realizable computable types. This is a joint work with Joel
Completeness of S4 with respect to the Measure Algebra
Long before Kripke-frames became the yardstick semantics for the propositional modal language, Tarski and McKinsey interpreted the modal language in topological spaces. Under the topological semantics, formulae are evaluated to arbitrary subsets of a topological space and necessity and possibility are interpreted, respectively, as the interior and closure topological operators. In 1944, Tarski and McKinsey showed that the logic S4 is sound and complete with respect to the usual metric topology of the real interval [0, 1]. Since then, the result has been refined and extended to higher dimensional metric spaces and subspaces.
But we can also look at the real interval from a measure-theoretic point of view. In recent talks at Stanford and Berkeley, Dana Scott introduced a new model for the propositional modal language — the Measure Algebra. Elements in the Measure Algebra are Lebesgue-measureable subsets of the real interval, [0, 1], up to sets of measure zero, and the algebra is equipped with Boolean operators as well as an interior operator. In evaluating modal formulae to the Measure Algebra, we assign to a given formula an equivalence class of sets that differ from one another by a set of measure zero. This allows us to speak of the probability or weight of any formula under a given valuation. I show that the propositional modal logic S4 is complete for the Measure Algebra. This result extends the classic 1944 result of Tarski and McKinsey to the measure-theoretic structure of the real interval and opens the way for investigating the logic of measure spaces more generally. A first corollary to the proof of completeness that I present is that non-theorems of S4 can be falsified on subsets of [0, 1] of measure arbitrarily close to 1. A second corollary is that Intuitionistic logic is complete for the sub-lattice of open elements of the Measure Algebra.
Computability and Complexity of Julia Sets
In this talk I will survey the recent study of the computational
properties of dynamical systems that arise from iterating quadratic polynomials on the complex plane. These give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. I will present both positive and negative results on the computability and computational complexity of Julia sets.
Regular representations of uniform TC0
The complexity class DLOGTIME-uniform AC0 is known to be a modest
DLOGTIME-uniform TC0. The weakness of AC0 is due, put in logical
the fact that the logics corresponding to AC0 do not have the
property and hence they are not regular. This weakness of
elaborated in the line of research on the Crane Beach Conjecture. In
talk we show that DLOGTIME-uniform TC0 can be logically
terms of quantifier logics with cardinality quantifiers
is the range of some polynomial of degree at least two. Then we
key properties of abstract logics to accomodate built-in relations
define the regular interior R-int(L) and regular closure R-cl(L), of
L. Finally we show that the Crane Beach Conjecture can be
interpreted as a
statement concerning the regular interior of a logic and that the
closure of AC0
is TC0. Joint work with Lauri Hella and Kerkko Luosto.
The limits of determinacy in second order arithmetic
The enterprise of calibrating the strength of theorems of classical
mathematics, primarily in terms of the (set existence or comprehension) axioms
needed to prove them, was begun by Harvey Friedman in the 1970's. It is now
called Reverse Mathematics as, to prove that some set of axioms is actually
necessary to establish a given theorem, one reverses the standard paradigm by
proving that the axioms follow from the theorem (in some weak base theory).
The original motivations for the subject were foundational and philosophical.
It has become a remarkably fruitful and successful endeavor supplying a
framework for both the philosophical questions about existence assumptions and
foundational or mathematical ones about construction techniques needed to
construct objects that the theorems assert exist.
There is one common base theory and four more standard systems beyond it. Most
theorems of classical mathematics have turned out to be equivalent to one of
these systems. We will briefly describe this state of affairs and then move on
to a situation that falls far outside the realm of standard reverse
mathematics: axioms of determinacy.
The story begins with Friedman's result  that Borel determinacy is not
provable in ZFC– (no power set) and Martin's proof  that it is
provable in ZFC (with just the required number of iterations of the power set
axiom). We then move to low levels of the Borel hierarchy and provability in
second order arithmetic (Z2). Friedman proved that Σ05
determinacy is not provable in second order arithmetic and Martin
 improved this to
and presented a proof of
determinacy that he claimed could be carried out in Z2.
Moving up from the bottom, Steel  showed that open
determinacy is equivalent to the fourth of the standard systems while Tanaka
 showed that determinacy for the difference of two open sets is
equivalent to the fifth and strongest of them. Various researchers then
investigated the strength of
Our recent work with Montalbán on this topic began with the realization
that the proof by Martin apparently establishing the boundary between
provability and unprovability for levels of arithmetic determinacy in second
order arithmetic was not a proof in Z2. We have now established
the true results which turned out to be quite different and unusual.
Determinacy at the various levels of the difference hierarchy on
sets climb up the entire hierarchy of
comprehension axioms in
proof theoretic strength. Thus the provability boundary lies well below
determinacy. These results supply the first natural
mathematical theorems that occupy any, let alone all, of the levels above
They also provide a Gödel like phenomena for
sentences in second order arithmetic (or ZFC–) with natural
mathematical sentences: φ(n) is provable for each n but
∀ n φ(n) is not provable.
Joint work with Antonio Montalbán.
An essential feature of Gödel's 1931 incompleteness proofs
is the use of an encoding ("Gödel numbering") of syntactical
and and relationships (for a given formal system) as non-negative
integers and relationships among those integers. We describe a new
encoding based on Cantor's pairing function
f(x,y) = (1/2)[xx+2xy+yy+3x+y]
and use it to obtain simpler and more direct proofs of theorems
of Gödel and Matiyasevich. In particular, we use the coding to
that for every recursively enumerable set W there is a polynomial
p(x,y,...) such that
∀ x [x ∈ W ⇔ ∃ y,... (p(x,y,...) = 0)].
We also note possible applications of Cantor coding to analysis and