The UCLA Logic Colloquium meets on alternate Fridays,
at 4 p.m., in MS 6627.
Here are links to the
UCLA Logic Center, the
Caltech-UCLA Logic Seminar, the
Philosophy Colloquium, and the
Marschak Colloquium.
Talks are listed here in reverse chronological order.
June 10, 2011
Speaker:
Todor Tsankov
Title: Generic Representatons of Abelian Groups
June 3, 2011
Speaker:
Matthew Foreman
Title: Classifying Measure Preserving Diffeomorphisms of the Torus
The statistical behavior of deterministic
dynamical systems can be completely random. The ergodic theorem tells
us that the statistical behavior of a system carrying an invariant
ergodic measure is captured by the isomorphism class of that measure.
Motivated by this type of phenomenon, in 1932 von Neumann proposed the
program of classifying the ergodic measure preserving systems.
This talk will discuss applications of the tools of descriptive set theory
to show that this program is impossible. In earlier joint work with
Weiss, it was shown that the isomorphism relation is "turbulent" and
hence no generic class can be reduced to an S-infinity action. With
Rudolph and Weiss it was shown that the isomorphism relation is a
complete analytic set.
But what about concrete systems: C-infinity measure preserving
diffeomorphisms of the torus? Recent work with Weiss extends these
results to such transformations.
Finally a very recent result shows that the "graph-isomorphism problem"
can be reduced to isomorphism of measure preserving diffeomorphisms.
As a corollary the isomorphism relation is complete for S-infinity
actions.
May 27, 2011
Speaker:
Sam Sanders
Title: Reverse Mathematics & Non-Standard Analysis: Why Some Theorems Are
More Equal than Others
Abstract
May 13, 2011
Speaker: John Steel
Title: The Triple Helix
Many different foundational theories have been developed and
studied by set theorists. Remarkably, no divergence at the level of
statements about "concrete" objects (for example, natural numbers)
has emerged, and indeed, these theories are linearly ordered by the
inclusion order on their sets of arithmetic consequences. The place of
a theory in this order is known as its consistency strength.
Our methods for comparing the consistency strengths of set
theories center on three intertwined canonical hierarchies of sets. In
this talk we shall describe those three hierarchies in very general
terms. We shall focus on the philosophical significance of the results
and open questions concerning them.
April 29, 2011
Speaker: Balder ten
Cate
Title: Unary Negation
We study fragments of first-order logic and of least fixed point logic that
allow only unary negation: negation of formulas with at most one free variable.
These logics generalize many interesting known formalisms, including modal
logic and the mu-calculus, as well as conjunctive queries and monatic Datalog.
We show that satisfiability and finite satisfiability are decidable for both
fragments, and we pinpoint the complexity of of satisfiability, finite
satisfiability, and model checking. We also show that the unary negation
fragment of first-order logic is model-theoretically very well behaved. In
particular, it enjoys Craig interpolation and the Beth property.
Based on joint work with Luc Segoufin (STACS 2011).
April 8, 2011
Speaker: Itay
Neeman
Title: Forcing with Side Conditions
March 4, 2011
Speaker: Henry
Wilton
Title: Conjugacy Classes of Solutions to Systems of Equations over
Hyperbolic Groups
The elementary theory of a group G is sometimes characterised as 'all the group
theory of G that a logician can see'. Around 1945, Tarski asked whether
different free groups have the same elementary theory. This extremely difficult
problem was only answered (affirmatively) in the last decade, independently by
Sela and Kharlampovich--Miasnikov. The latter also showed that the elementary
theory of a free group is 'decidable', meaning that there is an algorithm to
determine whether a given logical sentence is true or false in a free group.
Word-hyperbolic groups, introduced by Gromov in the '80s, are an enormous
class of well-behaved groups that are characterised by the geometric property
of having negative curvature. In this sense, they generalise free groups. I
will describe part of the attempt to extend these known results about free
groups to the word-hyperbolic setting. Specifically, I will describe an
algorithm that determines whether or not a given system of equations and
inequations over a torsion-free word-hyperbolic group has infinitely many
conjugacy classes of solutions.
This is joint work with Daniel Groves (UIC).
February 18, 2011
Speaker:
Alice Medvedev
Title: The Recursive Spectrum of a Strongly Minimal Modular Theory of
Groups in a Finite Language
(I will define and explain "stronly minimal," "modular," "recursive spectrum,"
and all other
frightening words.) The recursaive spectrum of a fixed strongly minimal theory
T is the set of integers n such that the model of T of dimension n admits a
recursive presentation. How complicated can this set be? Some interesting
examples can be constructed by coding complicatedness into an infinite
language, or by using Hrushovski constructions. We are working towards showing
that the recursive spectrum of a strongly minimal locally modular theory in a
finite language must be nothing, everything, or only the prime model. The title
describes the current state of this joint work with Uri Andrews.
January 28, 2011
Speaker:
Kenny Easwaran
Title: The Tarski-Gödel Thesis
A distinction is standardly drawn between so-called "structural"
axioms (those that define a type of mathematical structure, like a
group, or a field) and "foundational axioms" (those like PA or ZFC that
characterize some pre-existing structure). However, some
mathematicians with structuralist sympathies deny that there is such a
distinction, and assimilate all axioms to the "structural" type. In
this talk, I will consider Gödel's Completeness Theorem and show that
its standard interpretation depends on a non-mathematical thesis
parallel to the Church-Turing thesis in computability theory.
Consideration of this thesis shows that the type of structuralist view
mentioned above is untenable, since it suggests that any consistent
system is equally good, but says that there is no fact of the matter
about whether certain systems are consistent.
January 21, 2011
Speaker: Jack Lutz
Title: The Dimensions of Individual Points in Euclidean Space
The (constructive Hausdorff) dimension of a
point x in Euclidean space is the algorithmic information
density of x. Roughly speaking, this is the least real number
dim(x)
such that r·dim(x) bits suffice to specify x on a
general-purpose computer with arbitrarily high precisions
2-r. This talk will survey the development of this notion,
its geometric meaning, and its role in the analysis of several classes
of fractals. The results surveyed are the work of many investigators.
December 3, 2110 in MS 5127
Speaker:
Asger Tornquist
Title:
Borel reducibility and the classification of separable C*-algebras
A C*-algebra is a norm-closed *-subalgebra of the algebra of all bounded
operators on some complex Hilbert space. The Elliott programme is a large and
long-running programme in C*-algebra theory which aims to obtain a complete
characterization of those C*-algebras that are amenable (nuclear), simple and separable.
In this talk, I will discuss some recent joint work with Ilijas Farah and
Andrew Toms, where we study the isomorphism relation for separable
C*-algebras using the notion of Borel reducibility from descriptive set theory. Specifically, we prove that the homeomorphism relation for compact
Polish spaces is Borel reducible to the isomorphism relation for nuclear
simple separable C*-algebras, thus ruling out that the latter can be
classified by countable structures. We also give an upper bound on the
placement in the Borel reducibility hierarchy. In order to facilitate proving
these theorems, we develop a general theory of Borel computability of
constructions in C*-algebras, and prove Borel versions of several central
C*-algebra theorems.
November 19, 2010
Speaker:
Greg Hjorth
Title:
The fine structure of orbits
In the case of continuous actions of the infinite symmetric group, the Scott
analysis provides a sharp analysis of the Borel complexity of orbits. This
talk will compare the relatively well understood situation of the symmetric
group with the still poorly understood situation for general Polish groups.
November 5,2010
Speaker:
Matthew Foreman
Title:
Chang's Conjecture: generic elementary embeddings and inner models for huge
cardinals
This lecture describes some model transfer properties on ω4
that can be proved to be between a huge cardinal and a 2-huge cardinal in
consistency strength.
September 27, 2010
Speaker:
Anand Pillay
Title:
Measures in Model Theory
I will discuss the extension of stability-theoretic ideas to a broader
context but with measures replacing types.
June 4, 2010
Speaker:
Mia Minnes
Title:
Linear Orders -- a Case Study in Automatic Model Theory
Computable model theorists have analyzed many classical theorems on
linear orders. A standard (and important) example is that although any
infinite linear order must contain either an infinite increasing chain
or an infinite decreasing chain, there is a computable linear order with
no computable suborder of type omega or omega*. We will show that
this theorem fails in the automatic structures setting. This pronounced
difference between computable model theory and automatic model theory is
the departure point for further questions about categoricity, dimension,
homogeneity, and complexity of substructures. Differences between the
computable and automatic context with respect to each of these will be
illustrated with recent results about automatic linear orders. This is
joint work with Asher Kach.
May 28, 2010
Speaker:
Joel Friedman
Title:
Modal Platonism is a Threat to Platonism (and to its
so-called Indispensability Principle)
Abstract in pdf format.
Text of talk in pdf format.
May 21, 2010
Speaker:
Menachem Magidor
Title:
Forcing Axioms and Squares
Forcing Axioms are axioms added to the usual axioms of Set Theory with the
intuitive motivation of "A set that can be imagined to exist, does exist".
These axioms, like Martin's Axiom (MA), the Proper Forcing Axiom, (PFA) Martin's
Maximum (MM) and other variations turned out to be very successful in deciding
many problems that are otherwise independent of Set Theory.
The combinatorial principle square, which was introduced by Jensen, seems to
hold in almost all of the canonical inner models for large cardinals constructed
so far. There is a class of weakenings of the square principle, and the weakest
"weak square" that holds in a given model seems to be an indication of the
model's deviation from a canonical inner model.
One of the interesting global consequences of forcing axioms stronger than
Martin's Axiom is that square fails everywhere. The talk will survey the known
results about the interaction of different forcing axioms like PFA and MM with
weak square principles. This study may be the first step to the determination
of the consistency strength of these axioms.
May 7, 2010
Speaker:
Zlatan Damnjanovic
Title:
From Strings to Numbers
The talk articulates a minimal, formalist framework for the representation of
mathematical reasoning. We develop basic arithmetic in an elementary theory of
concatenation, simulating induction and primitive recursion without taking the
standard natural numbers for granted. The concatenation theory is proved to be
mutually interpretable with the well-known arithmetical theory Q.
April 30, 2010
Speaker:
Alex Usvatsov
Title:
Generic stability and the forking ideal
One of the main tools that model theory offers for the analysis of
structures is different abstract notions of "smallness" (such as forking). The
goal of my talk is to describe the behavior of some of these notions in the
context of generically stable types in dependent theories (theories without the
independence property).
First I will discuss the concept of generic stability, which allows to carry
many techniques from stability theory over to theories without the independence
property (such as certain valued fields). Then I will talk about the notions of
forking and thorn-forking, and their meaning in this context. In particular, I
will discuss the recent result (joint with D. Garcia and A. Onshuus) that all
the "reasonable" notions of "smallness" coincide for realizations of generically
stable types.
April 9, 2010
Speaker:
Yiannis Moschovakis
Title:
The axiomatic derivation of absolute lower bounds
The ancient Euclidean algorithm computes the greatest common
divisor gcd(m,n) of two natural numbers by iterating the remainder
operation. It requires no more than 2log(min(m,n)) extractions of
remainders to compute gcd(m,n) (for m > n > 1), and so to also check
whether m and n are coprime. It is not known whether it is
optimal, either for the computation of gcd(m,n) or for deciding
coprimeness.
In this lecture I will develop an axiomatic approach to the theory
of algorithms in the style of abstract model theory, which makes
it possible to make precise and (in some cases) derive non-trivial
lower bounds for problems like the computation of gcd(x,y) or
deciding coprimeness. These axiomatically derived lower bounds
apply to many natural complexity measures, all known computation
models and (arguably) to all algorithms from specified primitives.
The method will be illustrated with some specific results on
problems in arithmetic like those above which are joint with Lou
van den Dries.
March 12, 2010
Speaker: Inessa Epstein
Title: Measure Preserving Group Actions and Descriptive Set Theory
We are going to consider the space of free, measure preserving,
ergodic actions of a countable group on a standard probability space.
This space is of high importance in functional analysis. We will
consider equivalence relations on this space - in particular, the
equivalence relation given by orbit equivalence - and discuss the
Borel complexity of the equivalence relation. Two group actions are
orbit equivalent if these is a measurable way of almost everywhere
identifying the orbits given by the actions. Descriptive set
theoretic aspects that are of interest will be introduced as well as
recent results concerning these group actions.
February 19, 2010
Speaker:
Lou van den Dries
Title: Transseries
The differential field of Laurent series over the reals is
not closed under exponentiation, but has a canonical extension to an
exp-closed differential field T of ``transseries''. I will describe T
and mention some of the intriguing conjectures about its
model-theoretic behavior, which are analogous to the well-known
model-theoretic facts about the real field. This is a survey of joint
work with Matthias Aschenbrenner and Joris van der Hoeven.
January 22, 2010
Speaker:
Grigor Sargsyan
Title:
January 8, 2010 November 6, 2009 October 23, 2009 October 9, 2009 May 29, 2009 May 22, 2009 May 8, 2009 Note: On Thursday, April 30, there will be a public symposium,
The Convergence of Logic, Mathematics, and Computer Science,
2:00-7:00 p.m., in Kerckhoff Hall, Charles E. Young Grand Salon.
April 24, 2009 April 17, 2009 April 3, 2009 March 6, 2009 February 20, 2009 February 13, 2009: No Logic Colloquium, but note that
Moshe Vardi
is speaking at the
CS Seminar
at Caltech, 74 Jorgensen, 4:00.
January 30 to February 1, 2009 January 16, 2009 November 21, 2008 November 7, 2008 October 24, 2008 October 10, 2008 May 30, 2008 May 23, 2008 May 16, 2008 May 2, 2008 April 25, 2008 March 14, 2008 February 15, 2008 On February 1 - 3, 2008, there will be a
Very Informal
Gathering of logicians at UCLA.
The invited speakers are Jeremy Avigad, Deirdre Haskell, Marcus Kracht,
Justin Moore, Chris Pollett, Jan Reimann, and Christian Rosendal.
January 18, 2008 November 30, 2007 November 16, 2007 November 2, 2007 October 19, 2007 October 6, 2007 Saturday May 18, 2007 May 11, 2007 Note change of date! April 13, 2007 March 16, 2007 March 9, 2007 March 2, 2007 February 9, 2007 February 2, 2007 January 26, 2007 December 1, 2006 December 1, 2006 November 17, 2006 November 3, 2006 October 27, 2006 October 6, 2006 June 2, 2006 May 26, 2006 May 19, 2006 Note that on Friday, May 12, 2006 (3 p.m.),
Brian Skyrms
is delivering the
Reichenbach Lecture
at the UCLA Philosophy Department (Dodd 175).
May 5, 2006 May 5, 2006 Note that on Thursday, May 4, 2006 (4 p.m.),
Ed Keenan
is speaking at the
UCLA
Mathematical Linguistics Circle, on A Semantic Classification
of Natural Language Quantifiers.
April 21, 2006 April 7, 2006 February 10, 2006 Special event: February 3-5, 2006,
Magidorfest
at UC, Irvine.
The
Day of Algebraic
Logic is Tuesday, January 31, in MS 6118.
January 27, 2006 January 20, 2006 December 2, 2005 November 18, 2005 November 4, 2005 October 21, 2005 October 7, 2005 June 10, 2005 May 27, 2005 May 20, 2005 May 6, 2005 April 22, 2005 April 8, 2005 Note that Kit Fine is speaking March 17 (4pm, Dodd 399)
and March 18 (3pm, Dodd 161) at the
Philosophy
Department.
March 11, 2005 March 4, 2005 February 18, 2005 February 3-6, 2005: There will be a
Very Informal Gathering
of logicians at UCLA.
January 21, 2005 December 10, 2004 November 19, 2004 November 5, 2004 October 15, 2004 Click here to see the announcements for
older Logic Colloquia.
Speaker:
Fernando Ferreira
Title: Bar-Recursive Interpretations of Classical Analysis
We start by briefly describing Shoenfield's functional interpretation of
Peano arithmetic. Tao's finitization of the infinite convergence principle
can be seen as an instance of this interpretation together with a simple
majorizability argument (uniformity result). In 1962, Spector gave a
remarkable characterization of the provably recursive functionals of full
second-order arithmetic (a.k.a. analysis). We explain what is bar-recursion
and outline a direct (i.e., not via intuitionistic logic) proof of Spector's
result. We note that bar-recursive functionals are majorizable and, hence,
that majorizability arguments extend to analysis.
The bounded functional interpretation was introduced in 2005 by Oliva and
the present author. In its version for classical arithmetic, it is an
interpretation which "injects" some non set-theoretic uniformities into
Peano arithmetic. Due to its Soundness Theorem, the interpretation extracts
correct uniform bounds of AE-theorems (Proof Mining). Together with
Engrácia, we recently showed that the bounded functional interpretation also
extends to analysis.
Speaker:
Isaac Goldbring
Title:
Hilbert's Fifth Problem for Local Groups
The most common version of Hilbert's Fifth Problem (H5)
asks whether every locally euclidean topological group (i.e. a topological
group whose identity has an open neighborhood homeomorphic to some R^n)
can be given the structure of a real analytic manifold so that the group
multiplication and inversion become real analytic maps; briefly, whether
every locally euclidean topological group is a Lie group. A positive
solution to the H5 was given by Gleason, Montgomery, and Zippin in
the 1950s. Shortly after, Jacoby claimed to have proven that every
locally euclidean "local group" was locally isomorphic to a Lie group.
Roughly speaking, a local group is a hausdorff space which has a partial
group-like operation defined on it which is continuous. However,
Jacoby's proof was discovered to be flawed in the '90s, leaving some
important theorems whose truth rests on this local version of the H5 on
shaky foundation. By modifying techniques used by Hirschfeld in a proof
of the H5 using nonstandard analysis, I was able to give a correct proof
of the local H5. In this talk, I will try and sketch a part of the proof
of the local H5. No background knowledge in Lie theory or nonstandard
analysis will be necessary and all relevant terms will be defined.
Speaker:
Wai Yan Pong
Title:
Locally Finite Quantifier Eliminable Graphs
We classified the class of locally finite quantifier eliminable graphs in
the language of distance predicates.
This is a joint work with Shawn Hedman.
Speaker:
Phokion G. Kolaitis
Title: Foundations and Applications of Schema Mappings
Schema mappings are high-level specifications, typically expressed in some
logical formalism, that describe the relationship between two database
schemas. Schema mappings constitute the essential building blocks in
formalizing the main data inter-operability tasks, including data exchange
and data integration. The aim of this talk is to present an overview of
recent developments in the study of schema mappings with emphasis on the
interaction of this area of research with logic and computation.
Speaker: Jana Marikova
Title: O-minimal Fields, Standard Part Maps, and Triangulations
Speaker: Johan van Benthem
Title: Modal Lindström Theorems and Weak Abstract Model Theory
Standard abstract model theory has mainly looked at extensions of
first-order logic, taking its expressive power for encoding structure
for granted. And the classical Lindström Theorem analyzes what makes
this base system tick at a suitable abstraction level. But small can be
beautiful, too. In particular, modal languages are natural descriptions of
processes and information that can be viewed as fragments of first-order
logic with a nice balance between expressive power and (decidable)
complexity. These, too, can be captured via Lindström theorems, but
we need new proofs. Lindström's original argument breaks down at some
stage, because not enough expressive power is left to encode partial
isomorphisms or bisimulations with the right extension properties.
We present an alternative proof, its consequences for preservation
and interpolation theorems, and its upward generalizations to larger
fragments. We also discuss how far Lindström's original proof extends
'downward' into fragments, as well as new open problems at the fault
line between the two methods. Finally, we raise some questions about
fixed-point extensions of these weaker languages: an area where so far,
Lindström theorems have been famously missing. What does this mean?
References
J. van Benthem, 2007, A New Modal Lindström Theorem,
"Logica Universalis" 1, 125-138.
J. van Benthem, B. ten Cate & J. Väänännen, 2007,
Lindström Theorems for
Fragments of First-order Logic, Proceedings of LICS 2007, 280-292.
To appear in "Logical Methods for Computer Science".
Speaker: Paul Larson
Title: Universally Measurable Sets of Reals in Generic Extensions
A set of reals is said to be universally measurable if it is in the domain
of every complete finite Borel measure on
the reals. The structure of the collection of universally measurable sets is
still not well understood. We will show
that consistently there are just continuum many universally measurable sets,
answering a question of Dan Mauldin from 1978.
This is joint work with Saharon Shelah.
Speaker: John Harrison
Title: Decidability and Undecidability in Theories of Real Vector Spaces
(Joint work with Robert M. Solovay and Rob Arthan)
It's natural to formulate theories of real vector spaces using a 2-sorted
first-order language with a sort for the scalars and a sort for the
vectors. Introduction of coordinates reduces the theory of a vector space
of a specific finite dimension to the first-order theory of the real
numbers, known to be decidable since Tarski. Experience in the actual
formalization of mathematics motivates an investigation into decision
problems for various more general 2-sorted first-order theories of vector
spaces, with or without an inner product, norm, assumption of
completeness, or restriction on dimension.
Solovay, Arthan and the speaker have carried out a systematic study of
decidability for such theories. The theories of real vector spaces, inner
product spaces, and Hilbert spaces turn out to be decidable and to admit
quantifier elimination in a slightly expanded language. However, similar
theories of normed spaces, Banach spaces and metric spaces are not even
arithmetical: the theory of 2-dimensional Banach spaces, for example, has
the same many-one degree as the set of truths of second-order arithmetic.
However, by restricting quantifier alternations, we can arrive at some
decidable fragments of these theories, a fact that has proved useful in
mechanizing proofs.
Speaker: Carl Mummert
Title: Convergent and Stationary Strategies in Choquet Games
This talk describes work with Francois Dorais on the
(strong) Choquet game. We are interested in spaces where the second
player has a stationary winning strategy, which only considers the
previous move of the first player, or has a convergent strategy, which
causes the result of any play to contain a single point. We show these
properties are closely related to the structure of bases for the
space. In particular, the second player has a stationary strategy on
every second-countable T_1 Choquet space.
Speaker: Alain Louveau
Title:
Some New Results about Borel Functions
Some old questions about Borel functions, in particular their
generation by filter limits and generalizations of the Jayne-Rodgers result,
have been studied by various people, including Debs, Saint Raymond, Motto
Ross, and Semmes. I will discuss the results obtained so far and some
possible conjectures.
Speaker: Martin Dowd
Title:
A Lower Bound on the Mahlo Rank of a Pi_1^1-Indescribable Cardinal
Computing the Mahlo rank of a large cardinal provides perspective on
the cardinal.
In particular it provides a "conservative" quantitative method for
evaluating whether the existence of the cardinal should be accepted as
an axiom. The Pi_1^1-indescribable cardinals are a fundamental example.
Results related to this problem will be given, including a lower bound
on the rank.
Speaker: Solomon Feferman
Title: Conceptual Structuralism and the Continuum
Conceptual structuralism is a view of the nature of
mathematics according to which mathematics emerges from humanly
constructed, intersubjectively established, basic structural
conceptions. Some of these are so clear that every problem posed in
the language of the structure conceived can be said to have a
definite truth value, whether or not that can be determined. Other
conceptions may contain an inherently vague aspect, so that truth is
only partial in them and not every problem can be asserted to have a
definite truth value. In particular, this is behind my view that the
Continuum Hypothesis is not a definite mathematical problem.
Title: From Philosophical to Industrial Logics
One of the surprising developments in the area of program
verification is how several ideas introduced by logicians in the first part
of the 20th century ended up yielding at the start of the 21st century
industry-standard property-specification languages called PSL and SVA. This
development was enabled by the equally unlikely transformation of the
mathematical machinery of automata on infinite words, introduced in the
early 1960s for second-order arithmetics, into effective algorithms for
industrial model-checking tools. This talk attempts to trace the tangled
threads of this development.
There will be a
Very Informal Gathering
of logicians at UCLA.
Speaker: Sean Cox
Title:
Consistency Strength of Combinatorial Properties at Small
Regular Cardinals
I will present some consistency results about the following combinatorial
properties at small regular cardinals: stationary set reflection, existence
of nonregular ultrafilters, and variants of Chang's Conjecture.
Speaker: Henry Towsner
Title:
Proof Theory and the Correspondence Between Ergodic Theory and Additive
Combinatorics
In the last decade there has been a renewed interest in the
Furstenberg correspondence, a technique for relating problems in
additive combinatorics. We discuss how methods from mathematical logic
apply to this correspondence and can be used to expand the class of
problems the correspondence applies to.
Speaker: Joseph Flenner
Title:
The Relative Structure of Valued Fields
The idea of the model theory of a valued field being controlled by the
residue field and value group has been a common thread since the theorem of
Ax and Kochen, and recently has found a new level of sophistication in work of
Haskell, Hrushovski, and Macpherson. We give an overview, and then describe
an ongoing attempt to consolidate this through a general analysis of
characteristic-0 henselian fields relative to the leading terms. The talk
should be broadly accessible.
Speaker: Alex Usvyatsov
Title: Minimal Stable Types over Banach Spaces.
I will describe analysis of minimal stable wide types over
Banach spaces, which in particular leads to the solution of Henson's
conjecture on categorical classes of Banach spaces. The proofs are quite
elementary, and I will define all the basic concepts, so this talk will
require virtually no background in model theory (or logic in
general).
Speaker: Benjamin Miller
Title:
Forceless, Ineffective, Powerless Proofs and
Generalizations of Descriptive Set-Theoretic
Dichotomy Theorems
Over the last 30 years, a great variety
of dichotomy theorems concerning Borel structures
in Polish spaces have been discovered. Despite the
fact that these results only deal with classical notions,
many of their proofs require somewhat advanced ideas
from logic, e.g., recursion theory and forcing.
We will discuss an approach to giving classical proofs
of these theorems which utilizes ideas from graph theory.
Speaker: Eric Pacuit
Title:
The Tree of Knowledge in Action
Many logical systems today describe intelligent interacting agents
over time. This talk will survey various approaches to modeling rational
interaction and the questions that arise when comparing them.
Speaker: Simon Thomas
Title: A Remark on the Higman-Neumann-Neumann Embedding Theorem
The Higman-Neumann-Neumann Embedding Theorem states that
every countable group G can be embedded into a 2-generator group K. In
this talk, using the theory of Borel equivalence relations, I will explain why
there does not exist an explicit choice of the group K which has the
property that isomorphic groups G are assigned isomorphic groups K.
Speaker: Aldo Antonelli
Title: Abstraction Principles in First-Order Arithmetic
Formalizations of arithmetic ordinarily proceed along one of the three
avenues: (1) as a first-order theory in which numbers are taken as primitive
and their properties laid down by means of particular extra-logical axioms;
(2) as a second-order theory in the manner of Frege and Russell, in which
numbers are naturally identified with classes of (extensions of)
equinumerous concepts, and their properties derived from such a
characterization; or (3) as a first-order theory embedded within a
set-theoretic apparatus, in the manner of Zermelo or von Neumann, selecting
particular representatives for the equivalence classes (with respect to
equinumerosity). None of these options is completely satisfying in every
respect. Option (1) leaves the nature of number unexplained, and option (3)
does not seem general enough, in that the connection of numbers with their
cardinal properties (i.e., ultimately, with the act of counting) is lost.
Option (2) is perhaps the most conceptually satisfying, in that the
characterization of numbers as equivalence classes is well-motivated and
completely general. Unfortunately, option (2) also takes us into the hostile
landscape of second-order logic.
In this talk we show how to overcome these shortcomings. After looking at
abstraction principles in general, and with the aid of a non-standard (but
still first-order) cardinality quantifier and an extra-logical operator
representing numerical abstraction, we propose a formalization of arithmetic
at the first order, in which numbers are abstracta of the equinumerosity
relation, their properties derived from those of the cardinality quantifier
and the abstraction operator.
Speaker: Salma Kuhlmann
Title:Fragments of Peano Arithmetic and Embeddings of Valued Fields into Power Series Fields
An integer part (IP for short) Z of an ordered field F is a discretely ordered subring,
with 1 as the least positive element, and such that for every x in F, there is a z in Z such that
z <= x < z+1. The interest in studying these rings originates from Shepherdson's work in
[S] who showed that IP's of real closed fields are precisely the models of a fragment of Peano
Arithmetic called Open Induction. On the other hand, in [M-R], the authors establish the
existence of an IP for any real closed field R. The key idea of their proof is to show that
there is a "truncation closed" embedding of R in the field of generalized power series
R((G)) (G := v(R), the value group). We studied in [B-K-K] the arithmetic properties of
such rings, and consider in [F-K-K] necessary and sufficient conditions for a valued field K
with value group G and residue field k (with char K = char k) to admit a truncation-closed
embedding in the field of generalized power series k((G,f)) (with factor set f). We show
that this is equivalent to the existence of a family (tower of complements) of k-subspaces
of K which are complements of the (possibly fractional) ideals of the valuation ring. We
construct such towers if K is a Henselian field of characteristic 0 or, more generally,
an algebraically maximal Kaplansky field. Hence our results complement Kaplansky's
embedding theorem [Kap].
[B-K-K] Biljakovic, Darko; Kotchetov, Mikhail; Kuhlmann, Salma:
Primes and irreducibles in truncation integer parts of real closed fields,
in Logic, Algebra and Arithmetic, Lecture Notes in Logic 26, A K Peters (2006), 42-65.
[F-K-K] Fornasiero, A.; Kuhlmann, F.-V.; Kuhlmann, S.:
Towers of complements and truncation closed embeddings of valued fields,
submitted (2008), 41 pp.
[Kap] Kaplansky, I.:
Maximal fields with valuations I, Duke Math J. 9 (1942), 303-321.
[M-R] Mourgues, Marie-H\'el\`ene; Ressayre, Jean-Pierre:
Every real closed field has an integer part,
J. Symbolic Logic 58 (1993), 641-647.
[S] Shepherdson, J. C.:
A non-standard model for a free variable fragment of number theory,
Bulletin de l'Academie Polonaise des Sciences 12 (1964), 79-86.
Speaker: Krzysztof Krupinski
Title: Model Theoretic Ideas in Some Topological Contexts
The notion of forking independence, introduced by Shelah, turned out to be
the main tool in the study of stable and, more generally, simple theories.
This notion generalizes classical notions of independence, e.g. linear
independence in vector spaces and algebraic independence in algebraically
closed fields. The powerfulness of forking independence in stable and simple
theories comes from the fact that it satisfies the long list of nice
properties (such as symmetry or transitivity), which actually determine this
notion.
The main motivation for what I am going to discuss is to apply various ideas
from geometric stability theory to purely topological (or descriptive set
theoretic) objects. The point is that we can use a certain notion of
independence defined in a purely topological way, even if we do not work in
a first-order context.
I will discuss topological notions of profinite structure and
m-independence introduced by Newelski in the late 90's. Examples,
conjectures and some structural theorems about profinite groups regarded as
profinite structures, proved by Newelski and Wagner, will be given. Then I
will concentrate on a more general notion of Polish structure and non-meager
independence that I have introduced and been investigating for about two
years.
A Polish structure is a pair (X,G) where G is a Polish group acting
(faithfully) on a set X so that the stabilizers of all singletons are
closed. Profinite structures are particular cases of Polish structures for
X and G profinite and the action of G on X continuous. Polish
G-spaces and, more generally, Borel G-spaces are also examples of Polish
structures. We say that a Polish structure (X,G) is small if for every n
in omega there are countably many orbits on X^n under G.
Newelski has introduced the topological notion of m-independence in
profinite structures which, under the assumption of smallness, satisfies
nice properties and allows us to prove counterparts of some deep results
from stability theory. However, it is not easy to find many explicit
examples of small profinite structures (e.g. I have proved that abelian
profinite groups of finite exponent being inverse limits of countable
systems are such examples). In contrast, there are many examples of small
Polish structures. A simple non-profinite example is the unit circle with
the full group of homeomorphisms. More complicated examples are Hilbert cube
and the pseudo-arc with the full group of homeomorphisms.
I will discuss a purely topological notion of independence, called
non-meager independence, that satisfies some nice properties (e.g. symmetry,
transitivity, existence of independent extensions) in small Polish
structures, and so allows us to introduce basic stability-theoretic concepts
and to prove fundamental results about them (e.g. Lascar inequalities). In
profinite structures this notion of independence coincides with
m-independence introduced by Newelski. If time permits, I will also
discuss some examples and results describing the structure of small compact
G-groups, i.e., small Polish structures (X,G) where X is a compact
group and G acts continuously on X as a group of automorphisms.
Speaker: Su Gao
Title: A Coloring Property for Countable Groups
I will talk about a combinatorial coloring property for
countable groups that is equivalent to the existence of compact
free subflows of the Bernoulli flow. We show that every countable
group has this coloring property. This is joint work with Steve
Jackson and Brandon Seward.
Speaker: Joshua Sack
Title: On Temporal Dynamic Epistemic Logic
Epistemic logic is a modal logic that expresses knowledge and
belief of agents. We obtain dynamic epistemic logic (DEL) by adding to
epistemic logic expressions that assert that certain actions result in
certain new beliefs. In this talk, I will discuss one of several languages
that add temporal logic to DEL, focusing on the addition of a previous time
operator to DEL.
Speaker: Thomas
Scanlon
Title: Theories of Fields
Motivated by a conjecture of Florian Pop, we show that for each finitely
generated field K, there is a sentence in the language of rings so that
for any finitely generated field L, the sentence is true in L if and
only if L is isomorphic to K. In this talk, we will outline some of
the key steps involved in connecting algebra and logic and then discuss
some related questions about commutative rings.
Speaker: Marcus Kracht
Title: The Combinatorics of Interpreted Languages
Formal language theory likes to deal with languages as sets of
strings. But clearly, languages are sets of signs, which in turn
are (at least) pairs consisting of a string and some meaning. A
mathematical theory of such objects is so far missing.
In this talk I shall outline the beginnings of such a theory,
and give some results as well as open problems. For example,
we shall show that it is possible to define a notion of strong
generative capacity that does not assume structure to begin
with and yet is provably different from weak generative capacity
normally studied in formal language theory.
Speaker: Boban
Velickovic
Title: Maharam Algebras
A Maharam algebra is a complete Boolean algebra which carries a
strictly positive continuous submeasure. In 1947 Maharam asked if every
such algebra is in fact a measure algebra. This problem, which was also
known as the Control Measure Problem, was finally resolved by Talagrand in
2005 who provided a counterexample. In this talk we will survey some
recent work
on characterizations and combinatorial properties of Maharam algebras and
discuss some open questions.
Speaker: Jason Teutsch
Title: A Short History of Shortest Programs
Since the fourteenth century and certainly not before then, mankind
has demonstrated a universal preference for simplicity. This
principle, known as Ockham's Razor, still manifests itself today:
humans love short computer programs. Not surprisingly, we have a
short description for the set of shortest programs:
MIN = {e : for no j < e is phi_j = phi_e}.
I will survey the history of this set, from Cold War Russia to
modern-day Chicago.
The only thing better than a Turing machine which tells you whether
or not your program code is the shortest possible would be a machine
that does this correctly. But if your friend can do this correctly,
then she is not a Turing machine. Even an oracle machine which
completely knows the halting set will be clueless when it comes to
shortest programs. More precisely, the set of shortest programs is
Turing equivalent to 0'', the halting set of the halting set.
Recently, Stephan and Teutsch have characterized the canonical Turing
degrees 0', 0'', 0''', ... in terms of shortest programs. This should
be viewed as a generalization of the above theorem by Meyer. Our
characterization gives a partial solution to the most tantalizing
problem in all of computability theory, Schaefer's so-called MIN*
problem. The problem is this. Replace "=" in the definition for MIN
by "=*" (equal except for a finite set), and call the new set MIN*.
Schaefer himself showed that MIN* join 0' was Turing equivalent to 0''',
leaving open the question whether or not the halting set itself might be
computable from MIN*. Our answer is that this reduction holds for all
Kolmogorov numberings. For Gödel numberings in general I'm still unsure.
Speaker: Andrés Caicedo
Title:
Regressive Functions on Pairs
Let k be a positive integer. A function
f : [N]^k --> N
is called regressive iff
f(u) < min(u) whenever min(u) > 0.
A subset B of N
is min-homogeneous for f iff
f(u) = f(v) whenever
u and v are in [B]^k and 0 < min(u) = min(v).
Kanamori and McAloon showed that any regressive function admits an infinite min-homogeneous
set, but this is not provable in Peano Arithmetic.
For k = 2, this translates into the corresponding regressive Ramsey numbers having
Ackermannian rate of growth.
We present a combinatorial proof of this
result that considerably improves the previous bounds.
A special
logic colloquium
in honor of Matthew Foreman's 50th birthday.
11:00 a.m.: Menachem Magidor.
1:30 p.m.: András Hajnal,
More Rainbow Ramsey Theorems.
2:30 p.m.: James Cummings,
Full Reflection.
4:00 p.m.: Matthew Foreman.
Speaker: John D. Clemens
Title: Subshift Isomorphism is a Universal Countable Borel Equivalence Relation
A subshift on a finite alphabet A is a closed subset of the
space A^Z of bi-infinite sequences from A which is
invariant under the shift map S, where S(x)(n) = x(n+1). Two
subshifts X and Y are isomorphic if there is a homeomorphism from X
to Y which commutes with the shift. Subshifts are a widely-studied class
of dynamical systems, and much is known about their classification up to
isomorphism.
I will show that the isomorphism relation on subshifts is a
universal countable Borel equivalence relation, i.e., it is a countable
Borel equivalence relation such that every other countable Borel
equivalence relation is Borel reducible to it. Hence this classification
problem is quite complicated. As a consequence, we see that the problem of
classifying one-dimensional subshifts up to isomorphism has the same
complexity as the problem of classifying two-dimensional (or higher
dimensional) subshifts up to isomorphism.
Speaker: Joan Rand Moschovakis
Title: Brouwer's Analysis, Markov's Principle and the Church-Kleene Rule
Each of the three main schools of constructive mathematics
(Brouwer's intuitionism, Markov's recursive mathematics, and Bishop's
cautious constructivism) accepts intuitionistic (Heyting) arithmetic HA as
evident, then uses intuitionistic logic to study a (more or less restricted)
class of number-theoretic functions, eventually arriving at a characteristic
theory of real number generators. The resulting intuitionistic, recursive
and constructive analyses have acquired the acronyms INT, RUSS and BISH,
respectively. BISH can be considered as a common subset of RUSS, INT and
CLASS (classical analysis). RUSS accepts a strong form of Church's Thesis
which is inconsistent with classical first-order (Peano) arithmetic PA.
INT is consistent with PA and accepts a classically correct principle of bar
induction, but contradicts CLASS by using a strong axiom of continuous
choice ("Brouwer's Principle") which causes the intuitionistic analytical
hierarchy to collapse at the second level (an early result of Wim Veldman).
Although Brouwer and Bishop preferred to do their constructive
mathematics informally, in order to compare the three approaches -- in
particular, in order to study what can and what cannot be proved in each,
and how much of CLASS can consistently be represented in each without losing
the constructive viewpoint -- a formal treatment is evidently useful.
Heyting [1930] gave the first adequate formalization of intuitionistic
predicate logic; Kleene [1952] set the pattern for formalizing HA as a
subsystem of PA; Kleene and Vesley [1965] formalized INT and proved its
consistency; BISH can be represented (up to a point, since BISH allows the
use of constructive set theory) within Kleene and Vesley's INT by
reinterpreting the sequence variables and trimming the axioms; Troelstra and
van Dalen [1988] suggest formalizing RUSS by adding Markov's Principle and
an extension of Church's Thesis to HA. Each of these theories satisfies
Markov's Rule (which is a way of saying that the integers are standard) and
the Church-Kleene Rule (which guarantees that only recursive functions can
be proved to exist).
Douglas Bridges and his school are now working on the reverse
mathematics of BISH, and Wim Veldman is leading the study of INT from a
similar viewpoint. We give sample results of these two programs, then
discuss the consequences of adding to INT Markov's Principle and/or other
classically correct principles which preserve the Church-Kleene Rule.
Speaker: John Krueger
Title: Internally Club and Approachable
Internally approachable structures are a useful tool in set
theory. Various weakenings of internal approachability have been used and
studied; for example, internally club structures are structures which are
the union of an "epsilon-increasing" chain of models. Under some cardinal
arithmetic assumptions, these properties are all equivalent to one
another. On the other hand, it was recently discovered that these
properties are consistently distinct.
Speaker: Matthias Aschenbrenner
Title: Asymptotic Differential Algebra
This talk will be an introduction to asymptotic differential
algebra for a general mathematical audience. This subject deals with the
interplay between two approaches to the asymptotic theory of real-valued
functions: on the one hand, Hardy fields; on the other, fields of
transseries. Both have origins in the 19th century, but are closely related
with more recent developments in mathematical logic (o-minimal expansions of
the real field) and analysis (Écalle's solution of the Dulac problem).
Speaker: Julien Melleray
Title: Geometry and Dynamics in the Urysohn Space
Urysohn's universal metric space was built by P. S. Urysohn in 1924,
then essentially forgotten for 60 years. I will try to explain why this
space has attracted the attention of mathematicians in recent years; I will
discuss in particular algebraic and topological properties of the isometry
group of this space, and (if time permits) describe some open problems.
Speaker: Donald Bamber
Title:
Robust Reasoning with Rules that Have Rare Exceptions
We wish to construct one or more logics for reasoning with rules that
have rare exceptions. Such rules are statements of the type: Nearly
all As are Bs. It is assumed that an informant will assert such a
rule only if the conditional probability P(B | A) is at least 1 - e,
where the threshold parameter e is a small positive quantity whose
value is unknown to us. The approach we take is to define a
nonmonotonic form of entailment in which a conclusion is entailed by
premises if and only if, roughly speaking, nearly all probability
measures that model the premises also model the conclusion. If one
assumes that every rule in our premise set has been asserted by a
single informant, then the resulting logic is equivalent to Pearl's
System Z and Lehmann and Magidor's Rational Closure. However, if the
assumption that all premise rules have been asserted by the same
informant is not correct, then some of our conclusions may not be
justified. We consider a worst-case scenario in which each premise
rule has been asserted by a different informant and each informant
has his own personal threshold parameter, with the values of all
threshold parameters being unknown to us. The logic generated under
this scenario is equivalent to an argumentation system in which a
conclusion is entailed by premises if and only if there exists at
least one argument for the conclusion and every argument against the
conclusion is overridden by some argument for the conclusion. (Joint
work with I. R. Goodman and Hung T. Nguyen.)
Speaker: Antonio Montalbán
Title: Embeddability and Decidability in the Turing Degrees.
Computability Theory is the area of logic that studies the concept
of "being computable from." We say that a set, or a problem, is
computable from another one if there is an algorithm that decides
whether an element is in the former set, using the latter set as given
information. This allows us to measure the complexity of sets or of
mathematical problems.
We say that two problems are Turing equivalent if each one can
compute the other one. One of the main goals of computability theory is
to understand the shape of the structure of the Turing degrees. Two
common ways of studying this are by looking at structures that can be
embedded into the Turing degrees and by looking at the decidability of
the theory of this structure, varying the language or taking
substructures.
Speaker: Noam
Greenberg
Title:Strongly Jump-traceable Reals and Cost Functions
Various classes of very low degrees, such as the K-trivials, can be
constructed by using cost functions limiting the changes in the set being
approximated. It turns out that the similarity between the
construction methods yields deep connection between the various lowness
notions, as the cost function method is essentially the only way to
construct such degrees.
We give an overview and then discuss a related class, the
strongly jump-traceable reals, which is a proper sub-class of
the K-trivials. In the background lurks an attempt to characterize
lowness classes that arise from algorithmic randomness by
combinatorial means.
Speaker: Jan Reimann
Title: The Metamathematics of Algorithmic Randomness
I will discuss some recent work with Theodore Slaman (Berkeley) on the
logical structure of random reals. By relativizing Martin-Löf's test
concept to representations of measures, one can define an algorithmic
notion of randomness with respect to arbitrary (probability) measures
on Cantor space. Instead studying the properties of random reals with
respect to Lebesgue measure, we can now study a `reverse' problem: Which
properties of a real ensure randomness with respect to a reasonably
well-behaved (e.g. non-atomic) measure?
The investigation of this problem reveals interesting relations between
the logical complexity of a real and its randomness properties, for
example, strong ties to Borel determinacy. Furthermore, I will address
possible applications of algorithmic randomness to analysis.
Speaker: Jeff Remmel (at 4:00)
Title: Answer Set Programming
Answer Set Programming (ASP) is a formalism that grew out of work on
nonmonotonic logic and logic programming with negation. Recently,
a number of ASP search engines have been developed and these have been
used for various pratical applications. There are a number of variations
of ASP formalism that have led to a number of interesting theoretical
questions. We will survey some recent results in this area.
Speaker: Alain Louveau (at 2:00)
Title:The Complexity of Isomorphism between Separable Banach Spaces
It is proved that the relation of isomorphism between separable Banach
spaces is a complete analytic equivalence relation, i.e., that any
analytic equivalence relation Borel reduces to it. The, separable Banach
spaces up to isomorphism provide complete invariants for a great number
of mathematical structures up to their corresponding notion of isomorphism.
Speaker: Joan Bagaria
Generic Absoluteness and Combinatorial Properties of Projective Sets of Reals
We will present some exact equiconsistency results on the
absoluteness of the projective theory of the real numbers under some natural
classes of forcing extensions. As an application of these results we will
show, e.g., that in Solovay models the projective sets of reals enjoy
certain strong combinatorial properties.
Speaker: Alice Medvedev
Title:Model Theory of Difference Fields
A difference field is a field with a distinguished
automorphism, viewed as a structure for the language of fields with an
additional unary function symbol sigma. The theory of algebraically
closed fields with generic automorphisms, called ACFA, is
model-theoretically tractable; it is a canonical example of a
supersimple theory.
Before talking about my work, I will recall the model theory around
it. I will define and give examples of supersimple theories ,
minimal sets , combinatorial geometries (also known as a
matroid), and non-orthogonality between two minimal sets.
The basic model theory of ACFA was developed by Chatzidakis,
Hrushovski, and others over the last decade. They established the
simplicity of the theory, an analysis of finite-dimensional definable
sets in term of minimal sets, and the Zilber Trichotomy classifying
the combinatorial geometries that arise on minimal sets in ACFA. Some
fine-structure questions had been left open, although their
significance is evident by analogy with differentially closed fields.
My work explores the definability of the three cases of the Zilber
trichotomy for minimal sets defined by formulas of the form
sigma(x) = f(x) for some rational function f, and the definability of
non-orthogonality between two such sets. We show that the group-like
case of the trichotomy is definable. Since it is known that the
field-like case is definable, this makes all three cases of the
trichotomy definable. Indeed, our techniques yield definitions of each
of the three kinds of group cases -- additive, multiplicative, or
elliptic. We also show that non-orthogonality between two given
minimal sets is definable within the multiplicative case but not
within the elliptic case. A generalization of our results to all
minimal sets of sigma-degree one is a possible source of definable
classes of minimal sets closed under non-orthogonality. These would
produce new, model-theoretically interesting theories of difference
fields, in the spirit of Hrushovski and Itai's "On model complete
differential fields."
Speaker: Boban Velickovic
Title:Saturation of Aronszajn Trees and Shelah's Conjecture
Given a class of linear orderings K, a basis for K is a list K_0 of
members of K such that any member of K contains an isomorphic copy
of a member of K_0. The class of infinite linear orderings has an
obvious basis consisting of omega and its reverse omega^*. Considering
uncountable linear orderings, one can show in ZFC that any basis has to
have at least five elements. In the 1970s Shelah conjectured that it is
consistent that there be a five-element basis for the uncountable linear
orderings. This conjecture was finally confirmed by J. Moore in 2004.
However, his proof makes considerable use of large cardinals and it is
not clear if they are at all needed.
In this talk I will discuss the notion of saturation of Aronszajn trees
and show that it plays a key role in the proof of Shelah's conjecture.
This allows us to reduce dramatically the large cardinal assumptions
needed in the proof. Finally, we will discuss some open problems in
this area.
This is joint work with B. Koening, P. Larson and J. Moore.
Speaker: Pandelis Dodos
Title:A Classification of Separable Rosenthal Compacta and its Consequences
Speaker: Antonio Montalbán
Title: Equimorphism Types of Linear Orderings
We analyze the structure of equimorphism types of linear orderings
ordered by embeddability. (Two linear orderings are equimorphic if they
can be embedded in each other.) Our analysis is mainly from the
viewpoints of Computable Mathematics and Reverse Mathematics. But we
also obtain results, such as the definition of equimorphism invariants for
linear orderings, which provide a better understanding of the shape of
this structure in general.
Here are our main results: Spector proved in 1955 that every
hyperarithmetic ordinal is isomorphic to a computable one. We extend
his result and prove that every hyperarithmetic linear ordering is
equimorphic to a computable one. From the viewpoint of Reverse
Mathematics, we look at the strength of Fraisse's conjecture.
From our results, we deduce that Fraisse's conjecture is
sufficient and necessary to develop a reasonable theory of equimorphism
types of linear orderings.
Speaker: Justin Moore
Title:
Combinatorics of omega_1
In this talk I will discuss two recent results and one open
problem which concern the combinatorics of omega_1. The theorems are
the following: (1) Assume PFA. The uncountable linear orders have a
five-element basis; (2) There is a hereditarily Lindelof, non-separable
regular topological space. While these results do not overtly mention
the combinatorial properties of omega_1, they have reformulations
which are essentially Ramsey-theoretic statements about the first
uncountable cardinal.
These two theorems represent the two typical outcomes of analysis in
this area: a classification which follows from PFA and a pathological
example which can be constructed without additional axiomatic
assumptions. In this talk I will discuss the combinatorial aspects of
these problems and their relationship to each other. The talk will
finish with an open problem in the area for which the combinatorial
analysis has so far proved elusive.
Speaker: Martin Zeman
Title: Progress on Combinatorial Analysis of Extender Models
The study of combinatorial principles in extender models is a
continuation of Jensen's analysis of the combinatorial properties in
G&oml;edel's constructible universe L. Although interesting in its own
right, the knowledge of combinatorics in such models plays an
important role in applications where the constructible universe is
replaced by some extender model, which is necessary if the applications
involve large cardinals incompatible with L. Substantial progress
on developing methods for studying the combinatorics of such models was
made by Schimmerling and myself at the end of 1990's and led to the
characterization of Jensen's principle square_kappa. I will review some
results building on that characterization which were made during the
recent few years and also explain the progress on techniques used in
combinatorial analysis of extender models.
Speaker at 4:00 in MS 6627:
Nate Segerlind
Title:On the Sizes of Propositional Proofs
Propositional logic is reasoning about true/false assertions built up from
atomic true/false assertions (variables). A propositional proof system
is an efficiently checkable method for certifying that propositional
statements evaluate to true for all assignments to the variables (that
the statement is a tautology). A fundamental question in the study of
propositional proof complexity is whether or not there is a propositional
proof system P and a constant c > 0 so that for all tautologies tau
written in n symbols there is a P-proof of tau of size at most n^c.
This problem is equivalent to the NP versus coNP problem of computational
complexity, and its negative resolution implies that P is not NP.
Motivated by this connection to computational complexity and an interest
in unconditional results for satisfiability algorithms, there has been
much interest in this problem for specific propositional proof systems.
In this talk, we will discuss results for extensions of the resolution
system. The methods of probabilistic combinatorics enter in two ways.
The first is in the construction of the tautologies which are candidates
for requiring large proofs. The second is a method of converting k-DNFs
into constant height decision trees, by the application of a random
partial assignment to the variables.
Speaker at 2:00 in MS 7608:
Stelios
Negrepontis
Title: Schreier Sets in Ramsey Theory
The lecture is based on joint work with V. Farmaki. I will describe how
classical Ramsey theory can be extended by the introduction of families
of Schreier sets for every countable ordinal. Thus Ramsey's, Hindman's,
Milliken-Taylor's theorems, and van der Waerden's, Hales-Jewett's,
Carlson's, and Furstenberg-Katznelson's theorems can be so extended.
By way of applying these results we are currently interested in two
questions, still in the area of speculation; one is a question in
mathematical logic, arising from the Paris-Harrington result, the other
a broad attempt to apply these results to Ramsey ergodic theory.
[1] V. Farmaki, Ramsey and Nash-Williams combinatorics via Schreier
families, arXiv: math FA/0404014
[2] V. Farmaki, S. Negrepontis, Block Combinatorics, Trans. A.M.S.,
January 2006.
[3] V. Farmaki, S. Negrepontis, Schreier sets in Ramsey theory, arXiv:
math.CO/0510102
Speaker: Johan van Benthem
Title: Modal Logics for Space and Knowledge
Spatial interpretations for modal logics go back to Tarski's work in the 1930s.
We will explain the newly emerging interest in this area, but now with modern
modal techniques such as bisimulation games, extended languages, and product
constructions. New modal structures are emerging in topology, affine and metric
geometry, and linear algebra. Next, we cross over to epistemic interpretations,
and show how a topological viewpoint leads to a more sensitive modeling of
'common knowledge' as advocated by Barwise in the mid-1980s. The proper
setting here is fixed-point languages, but now with spatial interpretations.
References:
Marco Aiello, Johan van Benthem, & Ian Pratt-Hartmann, editors,
Handbook of Spatial Logics, Springer, Dordrecht, to appear (2006).
J. van Benthem & G. Bezhanishvili, 2006,
Modal Logics of Space.
Note that Johan van Benthem will also be speaking at the
Mathematical Linguistics Circle
on Thursday, April 20.
Speaker: Greg Hjorth
Title:Borel Equivalence Relations
We survey how the theory of Borel equivalence relations has developed
since Harrington-Kechris-Louveau at the end of the 1980's.
Speaker: Martin Davis
Title: Gödel: Missed Connections, Alternate Directions
I'll point out a number of ways in which Skolem and Gödel talked past
each other in the early 1930s. Finally, in a more speculative vein, I'll
explore a suggestion Gödel made in his Gibbs Lecture from which he
later decisively distanced himself.
Speaker: Alain Louveau
Title:Countable Quotients for Combinatorial Structures
Speaker: Yiannis N. Moschovakis
Title: Recursion and Complexity
My aim is to explain how the faithful representation of algorithms
by systems of recursive equations can be applied to complexity
theory, specifically in the derivation of worst-case lower bounds
which hold for all algorithms from specified givens. I
will use for examples some results in [1] and related, unpublished
joint work with van den Dries on arithmetic complexity,
but, in this lecture, I will put more emphasis on the conceptual
problems which arise in this enterprise: How can you make precise
and prove that to decide R(x) from given functions
g_1, ... , g_m,
you will need at least Kh(x) "calls to the givens,"
no matter which algorithm you use?
[1] Lou van den Dries and Yiannis N. Moschovakis.
Is the Euclidean algorithm optimal among its peers?
The Bulletin of Symbolic Logic, 10: 390-418, 2004.
Speaker: Eli Gafni
Title:
Distributed Symmetry-Breaking:
Renaming is Weaker than Set Agreement!
We resolve a problem in distributed computing, open since the discovery
of the connection between distributed computing and topology, back in 1993.
Then, the problems of renaming and set agreement
were proved to be impossible
to solve wait-free in a read-write shared-memory model.
However, the proofs were very different, and the relation
between the problems was left unclear. Moreover, the renaming
impossibility proof relied on non-trivial algebraic topology
techniques.
Our main result is that renaming is strictly weaker than
set agreement.
To prove this impossibility, we design a new model of
computation, that we believe is interesting
by itself. It is the first model we know of where an easy
analysis of the topology of a protocol
that invokes other protocols can be performed, and hence for a general
setting to study reductions. To study reductions between
renaming and set agreement, we identify and study a symmetry
breaking class of tasks, where processes decide on binary
output values. We show that set agreement and renaming are just
variations of symmetry breaking.
Also, we formulate a new version of the celebrated
index lemma, that yields the first elementary
proof of the renaming impossibility proof.
Finally, by exhibiting a symmetry breaking task that is
a symmetric manifold and solves renaming, we pinpoint the difference
between set-agreement and renaming. While the former is impossible
to solve using tasks that are manifolds,
the latter cannot be solved by a task that is an orientable manifold.
Unfortunately read-write memory is an orientable manifold.
Joint work with Sergio Rajsbaum, UNAM
Speaker: Assaf Sharon
Title: Reflection of Stationary Sets and the SCH.
Speaker: Alex Usvyatsov
Title: Are Different Approaches to Model Theory of Analysis So Different?
I will describe the history of different model theoretical
approaches to studying natural classes arising in functional analysis
and topology, and recent developments showing that once generalized
appropriately, all these approaches converge to the same context.
Speaker: Moti Gitik
Title:On the General Behavior of the Power Set Function
Speaker: Jean-Yves Béziau
Title: Universal Logic: Towards a General Theory of Logics
In this talk I will outline the basic ideas of universal logic, a
general theory of logics considered as mathematical structures. I will
present the main lines of research of this field and some recent
developments.
Speaker: Dominique Lecomte
Title:
Hurewicz-like Tests for Borel Subsets of the Plane
Speaker: Stevo Todorcevic
Title:
Universally Meager Sets and Principles of Generic Continuity
and Selection in Banach Spaces
Speaker:
Matthew Foreman
Title: Automorphisms of the Measure Algebra
The measure-preserving transformations of the unit interval form a Polish
group. This group acts on the ergodic measure-preserving transformations
by conjugacy, and this action coincides with isomorphism of
measure-preserving transformations. The main result of the talk is that
this equivalence relation is complete analytic and therefore not Borel.
The argument involves randomized cut-and-stack arguments. This is joint
work with D. Rudolph and B. Weiss.
Speaker:
Phokion Kolaitis
Title: On Preservation under Homomorphisms in the Finite
Slides in postscript format.
It is well known that many classical results of mathematical logic
about all structures (finite and infinite) fail,
if only finite structures are considered.
The classical preservation-under-homomorphisms theorem asserts that
the existential positive formulas are the only first-order formulas
(up to logical equivalence) that are preserved under homomorphisms
on all structures, finite and infinite.
The aim of this talk is to present an overview of recent
results concerning the status of the preservation-under-homomorphisms
theorem on various classes of finite structures, including the class
of all finite structures over a fixed relational vocabulary
and the classes of all finite graphs of bounded treewidth.
Speaker:
Harvey Friedman
Title: Boolean Relation Theory
Boolean Relation Theory is the study of the Boolean relations between sets
and their forward images under multivariate functions. More precisely,
consider (V,K), where V is a natural set of multivariate functions and K is
a natural family of associated one dimensional sets. BRT studies statements
of the form "for all f1,...,fn in V, there exists A1,...,Am in K such that a
given Boolean relation holds between the A's and their forward images under
the f's". Experience shows that the analysis of such statements, even for
small n,m, and basic discrete (V,K), has diverse connections with various
mathematical topics, including large cardinals. We discuss the contents of
my book Boolean Relation Theory, nearing completion.
Speaker:
Leo Marcus
Title: Logical Foundations of an Adaptive Security Infrastructure:
Delegation and Response
Current distributed system security mechanisms cannot adapt adequately
to either rapidly changing, or long-term evolution of, threat
environments or system components and architectures. While substantial
effort has been expended to improve the localized adaptability of
individual security mechanisms (e.g., firewalls, network routers,
intrusion detection systems), there is little understanding of the
ramifications of the interactions of such adaptations on the larger
system. We are developing a model-theoretic framework on which to
build a semantics for an "adaptive security infrastructure" (ASI).
The goal is to be able to use this framework and associated semantics
to specify and verify ASI architectures.
Here we discuss some model-theoretic problems that result from two
central issues: "delegation" -- which yields questions of property
composition, and "response" -- which yields questions of model and
theory evolution.
Speaker:
Marcus Kracht
Title: Semantics for Modal Predicate Logics
The semantics for modal predicate logics is standardly taken to be
the one proposed by Kripke. Whatever its philosophical merits, it is
mathematically unsatisfactory because it is incomplete. It is not even
the case that if a propositional modal logic L is complete so is its
predicate extension. The first complete semantics has been proposed by
Shehtman and Skvortsov in 1993, building on work by Ghilardi.
Subsequently, this semantics has been greatly simplified. The talk
gives a summary of the development.
Speaker:
William Mitchell
Title: Finite Forcing and I[omega_2]
Speaker: Vladimir Kanovei
Title: On nonstandard set theories
Speaker:
Zlatan Damnjanovic
Title: On the logical foundations of arithmetic and
the uniqueness of the natural numbers
Philosophically speaking, what is ordinary number theory about?
Does the existence of non-standard models of (first-order) arithmetic
imply that the concept of natural number is in some way indeterminate?
Recent work of Charles Parsons seeks to answer these questions based on
a first-order analysis of Dedekind's famed Categoricity Theorem. This
paper critically examines Parsons's response and outlines a novel
conception of the subject matter of arithmetic which affirms its
determinateness while denying that it is constituted by a uniquely
privileged natural number sequence.
Speaker:
Andrés Caicedo
Title: Projective well-orderings and bounded forcing axioms
We show that fine structural inner models for mild large cardinal
hypotheses but below a Woodin cardinal admit forcing extensions where
bounded forcing axioms hold and the reals are projectively well-ordered.
Speaker:
Ben Miller
Title: Automorphisms of sigma-complete Boolean algebras
The group of Borel automorphisms of the reals and the group of
non-singular Lebesgue-measurable automorphisms of the reals have a
surprising number of properties in common. One reason for this is that
many problems involving these automorphism groups can be reduced to
questions about infinite permutation groups in certain restricted
languages. This viewpoint simultaneously clarifies the combinatorial
core of the problem at hand, and allows one to see that many properties
of the groups mentioned above are in fact shared by the automorphism
groups of a very wide class of sigma-complete Boolean algebras. This
class includes all complete Boolean algebras and all sigma-algebras on
the reals which contain the Borel sets. We will examine various
examples of this phenomenon.
Speaker:
Tony Martin
Title: Gödel's Conceptual Realism.
Gödel is commonly regarded the paradigm of a platonist: of someone
who believes that mathematics is about a realm of independently
existing abstract objects. Gödel certainly is a platonist in this
sense. But his brand of platonism, which he calls "conceptual
realism," has a whole other aspect. For example, Gödel holds that
the truths of mathematics are analytic: that a true mathematical
proposition is true in virtue of the meanings of the terms occurring
in it. This aspect of Gödel's position puts concepts, rather than
objects, to the forefront. I will discuss the relation between the two
aspects of Gödel's realism, and I will try to show that the object
aspect has a smaller role than it is usually taken to have.
Speaker:
Paul Eklof
Title: On Set theory applied to Ext theory
We survey some applications of set-theory to the study of the
homological functor Ext. This includes theorems of ZFC proved using
set-theoretic methods, as well as independence results. As time permits,
topics include such ancient ones as Whitehead groups as well as more
recent ones such as the Flat Cover Conjecture and tilting theory.