May 18, 2007
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.
May 11, 2007 Note change of date!
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.
April 13, 2007
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.
March 16, 2007
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).
March 9, 2007
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.
March 2, 2007
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.)
February 9, 2007
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.
February 2, 2007
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.
January 26, 2007
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.
December 1, 2006
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.
December 1, 2006
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.
November 17, 2006
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.
November 3, 2006
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."
October 27, 2006
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.
October 6, 2006
Speaker: Pandelis Dodos
Title:A Classification of Separable Rosenthal Compacta and its Consequences
June 2, 2006
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.
May 26, 2006
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.
May 19, 2006
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.
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
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.
May 5, 2006
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
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
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.
April 7, 2006
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.
February 10, 2006
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.
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
Speaker: Alain Louveau
Title:Countable Quotients for Combinatorial Structures
January 20, 2006
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.
December 2, 2005
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
November 18, 2005
Speaker: Assaf Sharon
Title: Reflection of Stationary Sets and the SCH.
November 4, 2005
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.
October 21, 2005
Speaker: Moti Gitik
Title:On the General Behavior of the Power Set Function
October 7, 2005
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.
June 10, 2005
Speaker: Dominique Lecomte
Title:
Hurewicz-like Tests for Borel Subsets of the Plane
May 27, 2005
Speaker: Stevo Todorcevic
Title:
Universally Meager Sets and Principles of Generic Continuity
and Selection in Banach Spaces
May 20, 2005
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.
May 6, 2005
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.
April 22, 2005
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.
April 8, 2005
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.
Note that Kit Fine is speaking March 17 (4pm, Dodd 399)
and March 18 (3pm, Dodd 161) at the
Philosophy
Department.
March 11, 2005
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.
March 4, 2005
Speaker:
William Mitchell
Title: Finite Forcing and I[omega_2]
February 18, 2005
Speaker: Vladimir Kanovei
Title: On nonstandard set theories
February 3-6, 2005: There will be a
Very Informal Gathering
of logicians at UCLA.
January 21, 2005
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.
December 10, 2004
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.
November 19, 2004
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.
November 5, 2004
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.
October 15, 2004
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.
June 21-25, 2004. Note that the
North American
Summer School in Logic, Language and Information is being held
at UCLA.
June 11, 2004
Speaker:
John Steel
Title: The Proper Forcing Axiom implies determinacy in L(R)
Our most all-purpose method for producing
canonical inner models satisfying large cardinal hypotheses is
the core model induction method. In a core model induction
argument, one produces canonical inner models
which are correct for statements at a given level of complexity,
using core model theory together with the existence of models
which are correct at lower levels. We shall try to convey in
greater detail the structure of such arguments, and illustrate
them by outlining a proof of the theorem quoted in the title.
June 4, 2004. The UCLA Philosophy Department is having its
Reichenbach Lecture, given by Charles Parsons, at 3:00 p.m.
May 28, 2004
Speaker: Mack Stanley
Title: The Branch Problem
Abstract in pdf format.
May 14, 2004
Speaker:
Slawomir Solecki
Title: Projective Fraisse Limits and the Pseudo-arc
The talk will be about an application of logic to topology
of indecomposable continua. A continuum is a compact connected space.
A continuum is indecomposable if it is not the union of two proper
subcontinua. The pseudo-arc is a hereditarily indecomposable
continuum, that is, all of its subcontinua are indecomposable. It is,
in a sense, the generic continuum since its homeomorphic copies form a
dense G_delta subset of the space of all continua.
We develop a dualization of the classical Fraisse limit
construction from Model Theory. The dual limit of a class of structures
is a highly homogeneous structure (in the model-theoretic sense) but it
also has a natural metric zero-dimensional topology. We show that after
appropriately moding out the model-theoretic content of the dual
Fraisse limit of a certain class of structures one obtains the
pseudo-arc. Using this connection we are able to transfer results about
automorphisms of the dual Fraisse limit to results about homeomorphisms
of the pseudo-arc. In this fashion, we obtain strengthenings of results
of Mioduszewski and of Lewis and Smith on the pseudo-arc and we
establish a new topological characterization of the pseudo-arc.
This is a joint work with T. Irwin.
May 7, 2004
Speaker:
Aldo Antonelli
Title: First-Order Quantifiers
In this talk we survey a number of results concerning
first-order quantifiers and report on some work in progress. After
briefly introducing generalized quantifiers, we identify some of their
interesting properties and address the issue of their expressive power.
Special attention is paid to a particular dyadic cardinality quantifier
and its properties. Finally, we take up the question of the sense in
which first-order quantifiers, similarly to second-order ones, might be
open to a "non-standard" interpretation.
April 30, 2004
Speaker: Vladimir Uspenskiy
Title: Four Algorithmic Faces of Randomness
Let us consider infinite sequences of zeros and ones.
The classical probability theory fails to distinguish
between random and non-random sequences. The first attempt to do that
is due to von Mises (1919) but it suffered some vagueness. The theory
of algorithms contributed new ideas to the task of defining what an
individual random sequence is.
In fact, a random sequence has at at least four faces.
First, it is stochastic; that means, the sequence
itself as well as any of its reasonable subsequences has the property
of frequency stability. Second, it is chaotic; that
means, it is disordered, i.e., the occurrences of its terms are not
governed by any reasonable rule. Third, it is
typical; that means, it belongs to any reasonable majority.
Fourth, it is unpredictable; that means, one who
gambles on it cannot win by using any reasonable strategy.
All the four formulations use the word "reasonable." In
each of four cases, the theory of algorithms allows one to fill that
word with some exact meaning. So four well-defined classes of
sequences appear. And each of them claims to be the true class of
random sequences. Some of those claims are more justified than
others.
References:
1. A. N. Kolmogorov, and V. A. Uspensky.
Algorithms and randomness.
SIAM J. Theory of Probability and Its Applications, vol. 32 (1987),
pp. 389-412.
2. V. A. Uspensky, A. L. Semenov, and A. Kh. Shen.
Can an individual sequence of zeros and ones be random?
Russian Mathematical Surveys, vol. 45 (1990), no. 1, pp. 121-189.
3. V. Uspensky, and A. Semenov.
Algorithms: Main Ideas and Applications.
Kluwer, 1991. 269 pp.
4. An. A. Muchnik, A. L. Semenov, V. A. Uspensky.
Mathematical metaphysics of randomness.
Theoretical Computer Science, vol. 207 (1998), pp. 263-317.
April 23, 2004
Speaker:
Paolo Mancosu
Title: Tarski on Models and Logical Consequence
In the last fifteen years there has been a heated debate on
exactly what is going on in Tarski's theory of logical consequence.
Since Etchemendy's publications in the eighties, contributions by,
among others, Sher, Ray, Gomez-Torrente, and Bays have provided a
much more detailed picture of Tarski's seminal 1936 paper. However,
this intense focus on the original publication has led to several
disagreements with respect to important interpretative issues related
to Tarski's contribution. One of the bones of contention, and the
only one I will treat in the talk, concerns Tarski's notion of
model, the key element of Tarski's famous definition of logical
consequence. I will argue that Tarski upheld a
fixed-domain conception of model in his 1936 paper and that he was
still propounding it in 1940. Thus, the 1936 conception of logical
consequence is both intensionally and extensionally different from
the one which is nowadays commonly accepted.
March 12, 2004
Speaker:
Ted Slaman
Title: Recursive Measures and Their Random Reals
There is a well-developed theory of effective randomness,
originating with the work of Kolmogorov (1965) [independently
Chaitin (1975)] and Martin-Löf (1966). According to Chaitin and
Kolmogorov, an infinite binary sequence X is random iff each of
its initial segments is difficult to describe. According to
Martin-Löf, X is random iff X does not belong to any effectively
presented set of measure 0. However, the two notions pick out
the same set of sequences as random, and this coincidence is
commonly cited as evidence that they identify a robust and
correct notion of randomness.
Both the Chaitin-Kolmogorov and Martin-Löf formulations of
randomness are naturally equipped with random sets: the Chaitin
Omega-numbers and the Universal Martin-Löf Tests. We will
discuss these objects and recount results of Kuchera and Slaman
(2001) and Merkle, Mihailovich and Slaman (2003) which show that
they are generic examples of random sequences with recursively
enumerable approximations.
We will end with an examination of the coincidence between
descriptive randomness (Chaitin-Kolmogorov) and measure-theoretic
randomness (Martin-Löf). By the following theorem of Reimann
and Slaman, this coincidence is not a truism.
Theorem 1 (Reimann and Slaman). There is a recursive measure mu,
necessarily discontinuous, and a sequence X such that X is
Martin-Löf random relative to mu and yet for every nondecreasing
recursive function f there is an n such that the first f(n)
values of X can be specified by a program of length less than n.
In other words, there is a mu-random sequence on which mu does
not concentrate whose information content is arbitrarily
compressible.
References
Chaitin, G. J. (1975). A theory of program size formally
identical to information theory, J. Assoc. Comput. Mach. 22:
329-340.
Kolmogorov, A. N. (1965). Three approaches to the definition of
the concept "quantity of information", Problemy Peredachi
Informacii 1(vyp. 1): 3-11.
Kuchera, A. and Slaman, T. A. (2001). Randomness and recursive
enumerability, SIAM J. Comput. 31(1): 199-211 (electronic).
Martin-Löf, P. (1966). The definition of random sequences,
Information and Control 9: 602-619.
Merkle, W., Mihailovich, N. and Slaman, T. A. (2003). Some
results on effective randomness. Preprint.
February 27, 2004
Speaker: Christian Rosendal
Title: Incomparable or Minimal Banach Spaces
Using the new methods of Ramsey theory in Banach spaces
developed by Gowers, plus additional tools of descriptive set theory,
we show that any infinite dimensional Banach space contains either a
minimal subspace or a continuum of incomparable subspaces.
February 6, 2004
Speaker: Martin Dowd
Title: Iterating Mahlo's Operation
The principle of "collecting the universe" justifies axioms asserting
the existence of large cardinals which can be "built up" by iterating
Mahlo's operation. In a previous paper, "schemes" were used to
define iterations of length up to kappa^+. This talk gives a method
for defining iterations of length up to kappa^{++}. Assuming GCH,
this is an unsurpassable limit, and the question of what ranks are
achievable is complicated. Results will be given which suggest that
weakly compact cardinals can be built up, and give an idea of their
rank. It will also be argued that the notion of "built up" cardinals
suggests, along with other evidence, that all sets are constructible.
January 23, 2004
Speaker: Itay Neeman
Title: Games of Length omega_1
The pattern of connections between determinacy and large cardinals
suggests that there should be games which capture the theory of
indiscernible Woodin cardinals. We present such games in the talk,
and establish precisely the connection between the games and
iterable models for indiscernible Woodin cardinals. We note that
this connection allows finding definable winning strategies in
closed games of length omega_1, and end with the (open) problem
of constructing such winning strategies "purely", that is using
descriptive set theory rather than large cardinals.
November 21, 2003
Speaker: Berit Givens
Title: The Bohr Topology on Various Abelian Groups
The Bohr topology on an Abelian group is the coarsest topology
that makes all homomorphisms from the group into the unit circle
continuous. In spite of this simple definition, the topology is
very slippery, and I will talk about what it looks like for some
common groups. In addition, I will discuss what is known about
comparing two groups with the Bohr topology and how techniques
from logic have been used in some of the proofs.
November 7, 2003
Speaker: Bernhard König
Title:
Fragments of Martin's Maximum in Generic Extensions
We look at the following three properties of forcing notions,
increasing in strength: weak omega_1-strategic closure (e.g.
forcing a square sequence), strong omega_1-strategic closure,
and omega_1-closure (e.g. Cohen subset of omega_2).
It turns out that each type has different impact when forcing
over a model of MM. Some new consistency results can be
obtained with this.
October 24, 2003
Speaker: Andrew Arana
Title: Degree Complexity of Models of Arithmetic
and Connections with Independence Results
In his 1958 paper, "Mathematical Significance of Consistency
Proofs", G. Kreisel asked whether model-theoretic independence proofs
for arithmetic could be made constructive by using recursive models of
arithmetic. In 1959, S. Tennenbaum gave a negative answer for
first-order Peano Arithmetic (PA), by showing that no nonstandard model
of PA is recursive. This result suggested a battery of other questions
about the Turing complexity of models and complete extensions of PA.
We will survey work in this area, from the late 1950s through today.
We will focus on a line of questioning in this area instigated by
C. Jockusch, who asked for a characterization of the degrees of models
of True Arithmetic (the theory of the standard model of PA), and of
other specific complete extensions of PA. R. Solovay answered
Jockusch's questions, in theorems made widely known by J. Knight.
Knight asked later whether Solovay's theorems could be simplified in
any of three natural ways. We discuss why these simplifications are
impossible. Our discussion rests on some independence results that are
useful here and in other contexts, so we will discuss these results as
well.
October 10, 2003
Speaker: Matthew Foreman
Title: Has the CH been Settled?
May 30, 2003
Speaker: Edward Keenan
Title: Excursions in Natural Logic
Working with generalized quantifiers (GQs) we study some novel
entailment paradigms in English determined by the "4-group" of negation
operators {identity, complement, post-complement, dual}. For example
the paradigm in (1) is novel, even cute, in that Qx.A and Qx.notA are
not logically equivalent when Q = 'for all' or 'there exists'.
(1) a. Exactly half the students passed
b. Exactly half the students didn't pass
The GQs that can replace 'exactly half the students' are just those
fixed by the post-complement operator. We characterize this set, whose
members are more numerous than (1) might suggest. The second paradigm
we study is illustrated in (2):
(2) a. More than two thirds of the students read at least as many
poems as plays
b. Less than a third of the students read
fewer poems than plays
We characterize the pairs of GQs that enter this paradigm in terms of
"Facing Negations". For both paradigms we characterize the permutation
invariant GQs in the paradigm. We note that the paradigms naturally
apply to a variety of non-first order definable quantifiers.
May 23, 2003
Speaker: Jindrich Zapletal
Title: Descriptive Set Theory and Definable Forcing
This is an overview of a book accepted to the Memoirs of the
AMS. I will show the basic ideas connecting the iterations
of definable proper forcing with descriptive set theory, and
quote and explain the main theorems of the book.
May 16, 2003.
No Logic Colloquium, but note that Krister Segerberg is speaking at the
Philosophy Colloquium.
May 9, 2003
Speaker: Jiri Wiedermann
Title: A Formal Model of Fuzzy Computations
Fuzzy Turing machines and fuzzy languages were introduced by Zadeh, Lee
and Santo in the 1970s. Unfortunately, it appears that from a
computability point of view, their model is too powerful -- its
nondeterministic version accepts non-recursively enumerable fuzzy
languages. Moreover, from the viewpoint of modern fuzzy logic theory,
the model is too restrictive since it is defined only for a specific
t-norm (the Gödel norm). Therefore, we propose a generalization of the
original model that is based on rigorous mathematical fundamentals of
fuzzy logic. Its acceptance criterion is modified so that the resulting
model obeys the Church-Turing Thesis. Fuzzy Turing machines then
accept exactly the enumerable languages with partially computable fuzzy
membership functions. The results open the way for simulating fuzzy
computations by any other device obeying this thesis. However, the
intended use of the model is in computability and complexity-theoretic
investigations aiming at the power, limits and efficiency of fuzzy
computations, rather than in design of efficient fuzzy algorithms.
April 25, 2003
Speaker: Martin Davis
Title: Gödel's Developing Platonism
April 18, 2003
Speaker: Johan van Benthem
Title: Rational Dynamics: the Logical Structure in Games
Logicians have used special games for a long time already
when studying expressive power or argumentation structure.
But there is also a logical structure to games in the more
general sense of game theory. Games may be analyzed as
interactive processes in dynamic, temporal, or linear
logics, linking up with concerns in computer science.
On top of that, deliberations and decisions by players
in the course of such a process can be modelled in epistemic
logics, linking up with key issues in philosophical logic.
Many of the current contacts between logic and game theory
have to do with explaining the emergence and stability of
game-theoretic equilibria in terms of epistemic assumptions,
and there are important results to this effect by authors
like Aumann and Stalnaker. In this talk, we propose a new
twist. We analyze game-theoretic equilibria as arising in
the limit from repeated announcements by players of their
rationality -- a bit like the way in which the Muddy Children
arrive at enlightenment through repeated assertion of their
status. This idea can be made precise in dynamic logics of
information update. More technically, this analysis leads
to connections between different notions of game equilibrium
and different fixed-point logics: monotonic or inflationary.
Literature
'Logic in Games', 1999 ->, electronic lecture notes
in progress, ILLC, Amsterdam: see the home pages
http://staff.science.uva.nl/~johan/Teaching/
and more general info on
http://www.illc.uva.nl/lgc/
'Extensive Games as Process Models'. Journal of Logic,
Language and Information 11 (2002), 289-313.
'Rational Dynamics and Epistemic Logic in Games',
ILLC Tech report, January 2003,
http://www.illc.uva.nl
April 4, 2003
Speaker: Wayne Richter
Title: Inductive Definability
Inductively defined sets are formed by repeatedly applying an
inductive operation until closure is reached. The study goes back to
Kleene's systems of notations for the constructive ordinals. The
general theory is concerned with the relationship between, on the one
hand the form of an inductive operator, and on the other hand the form
of the set and closure ordinal defined by that operator. Inductively
defined sets provide "recursive analogs" of small, large cardinals.
Of special interest is the relationship between monotone and
nonmonotone inductive definability.
The subject has applications in proof theory and finite model
theory. The talk should be accessible to beginning graduate students.
February 28, 2003
Speaker: Marcus Kracht
Title: Reduction Functions
The finite model property and decidability are typically shown in modal
logic via filtration of the canonical model. This method is highly
nonconstructive. Another method is the tableau method, which has the
disadvantage that completeness is difficult to show. We shall present
a third way, by means of reduction functions, which establishes in a
uniform way finite model property, decidability and interpolation
(wherever applicable). Also, the best known space complexity bounds
can be obtained with it. The core of the method is to reduce
derivability of a formula P in an axiomatic extension L to derivability
in K from a set of theorems of L that need to be found a priori on the
basis of P.
February 7, 2003
Speaker: Paul Larson
Title: The Canonical Function Game
The canonical function game is a definable game of length omega_1
indentified by Hugh Woodin which falls inside a class of games known as
Neeman games. It turns out that this game is consistently undetermined.
I will discuss this result and its relationship to some major open
questions in set theory.
January 31, 2003
Speaker: Alain Louveau
Title: Dichotomy Results for Analytic Graphs
We will present some dichotomy results about analytic
(directed and undirected) graphs, which involve the ordering of Borel
homomorphic reducibility, and generalize a dichotomy of Kechris,
Solecki, and Todorcevic about the Borel chromatic number of such
graphs.
January 24-26, 2003, there will be a
Very Informal Gathering
of logicians at UCLA in honor of the 65th birthday of
Yiannis N. Moschovakis.
January 10, 2003
Speaker: Richard Ketchersid
Title: Comparing Boolean(Pi^0_3) Cardinals is Hard
Abstract: An early result in the theory of Borel equivalence relations
on R states that for each S included in P(omega) there is an associated
Pi^0_3 (later improved to Sigma^0_2) equivalence relation E_S such that
E_S leq E_T iff T - S is finite (under AD). This shows that the Pi^0_3
"real" cardinals are a mess, but left open the question of how
complicated the reducibility relation "leq" is among Borel
equivalence relations.
I will give Boolean(Pi^0_3) equivalence relations E and E_x (uniformly
for x in R) so that {x : E leq E_x} is complete Sigma^2_1, i.e., as
complicated as possible. All this is done under "AD^+ + V = L(P(R))."
Similar results where one restricts the notion of reduction can be
obtained using less determinacy. Moreover, it seems plausible that
Boolean(Pi^0_3) should be replaced by Pi^0_3 or even Pi^0_2, but I do
not see how to do this.
November 22, 2002
Speaker: Kai Wehmeier
Title: A Metalogical (?) Argument in Frege
In the context of the recent resurgence of interest in the logical
system of Frege's Grundgesetze der Arithmetik (1893/1903),
originating with work by George Boolos, Terence Parsons, and Peter
Schroeder-Heister in the 1980's, it has become clear that we have a
somewhat poor understanding of the exact nature of Frege's project. In
particular, there is some debate as to whether metalogic plays any
substantial role in it. Two passages in Grundgesetze
appear to lend a great deal of support to the claim that it does,
namely, section 10, containing the 'permutation argument' by means of
which Frege attempts to show that he can safely identify the truth
values with certain sets (the 'identifiability thesis'), and sections
29-32, containing an attempted proof that every begriffsschrift term
denotes. In my talk, I shall focus on the permutation argument and try
to show that the standard, metalogical interpretation is untenable. I
shall advocate a 'mathematical' interpretation, first suggested by
Thomas Ricketts, instead. This interpretation has the advantage of
allowing a consistent model-theoretic reconstruction according to which
both the permutation argument and the identifiability thesis are
valid.
November 15, 2002
Speaker: Burkhard Englert
Title: Lower Bounds on the Shared Memory Requirements
for Long-lived and Adaptive Objects
Recently, several different long-lived adaptive algorithms whose
operation step complexity is a function of the actual number of
processors running concurrently with the operation execution, have been
presented. Regardless of the type of adaptiveness and the type of
object implemented, they require Omega(N) MWMR registers in their
implementation, where N is the total number of processors that
may participate in the implementation. We show that this is a
necessity. We furthermore show that even if the maximum allowed
concurrency m is a constant and m < d, where d is the number of
MWMR registers used, that for any such d there exists n_d, such
that every long-lived adaptive read/write implementation of collect and
renaming with n_d processors must use at least d MWMR registers.
This is joint work with Eli Gafni.
November 8-9, 2002: The Philosophy Department presents the
Rogers Albritton Commemoration.
November 1, 2002
Speaker: Wai Yan Pong
Title: Finiteness Principles for Monomial Ideals and their
Applications
I will present some "finiteness" results on monomial ideals. The
main tool used here is the theory of Noetherian orders. This turns out
to have some interesting applications to differential algebra. In
particular, one can derive a model theoretic rank called the
differential order which generalizes the notion of the order of a
differential equation.
October 26, 2002 (Saturday): There will be a
Logical Constants workshop
at UC Irvine.
October 18, 2002
Speaker: Marcus Kracht
Title: The Lattice of Modal Logics
Unlike in predicate logic, there is no simple reduction from axiomatic
extensions to the basic logic. Thus, in modal logic one must be
interested in the totality of all logics. They form a lattice, whose
structure has been studied throughout the last 25 years. A principal
tool is the notion of a splitting, which proved to be of central
importance in trying to establish not only the structure of the lattice
itself, but also in solving many genuine logical problems. In this
talk I shall give an overview of the principal results concerning the
lattice of modal logics and present some open problems.
June 7, 2002
Speaker: Michael Rathjen
Title: The Axiom of Choice in Constructive Set Theory
The axiom of choice does not have an unambiguous status in
constructive mathematics. On the one hand it is said to be an
immediate consequence of the constructive interpretation of the
quantifiers. Any proof of
forall x in a, exists y in b, phi(x,y)
must yield a function f : a --> b such that
forall x in a, phi(x,f(x)).
This is certainly the case in Martin-Löf's intuitionistic
theory of types. On the other hand, from the very earliest days, the
axiom of choice has been criticised as an excessively non-constructive
principle even for classical set theory. Moreover, it has been
observed that the full axiom of choice cannot be added to systems of
constructive set theory without yielding constructively unacceptable
cases of excluded middle. On the other hand, it has been shown by
Peter Aczel that constructive set theory has a canonical interpretation
in Martin-Löf's type theory and that this interpretation also
validates several choice principles, e.g., the axiom of countable
choice and the axiom of dependent choices. The main aim of the talk is
to present joint work with Sergei Tupailo in which we give a
characterization of a restricted class of set-theoretic statements
realizable in Martin-Löf type theory. This class contains all the
statements that figure in ordinary mathematics. The realizable
statements turn out to be those provable in an extension of CZF via the
so-called Pi-Sigma-axiom of choice.
June 1-4, 2002, the ASL
meeting in Las Vegas is held.
May 31, 2002
Speaker: Lefteris M. Kirousis
Title:
Review of the Results on the Approximation of the 3-SAT Threshold
Consider the space of uniformly random 3-CNF Boolean formulas phi
with density (clauses to variables ratio) r. Computer experiments
performed by several researchers starting a decade ago suggest that
there exists a number r_3 around 4.2 such that if r < r_3 then the
probability that phi is satisfiable has limit 1, as the number
variables n becomes large, whereas this limit is 0, if r > r_3. This
0-1 or phase transition phenomenon has also been corroborated by
methods of Statistical Physics (the replica method). Mathematically,
it has been proved that there exists a sequence of intervals
I_n = 3D(a_n, b_n), whose lengths approach 0, such that the
probability of satisfiability of a random 3-CNF formula has limit 0 if
its density r < a_n and has limit 1 if r > b_n. However, the existence
of a threshold number r_3 is still an open problem. On the other
hand, increasingly larger values l_3 < 4.2 and increasingly smaller
values u_3 > 4.2 have been found such that the probability of
satisfiability is almost 1 for r < l_3 and is almost 0 for r > u_3.
Some of these upper and lower threshold-bound results will be
reviewed.
May 17, 2002
Speaker: Rosalie Iemhoff
Title: The Provability Logic of Constructive Theories
The provability predicate of an arithmetical theory T is a
predicate in the language of T which, when applied to the code of a
formula, expresses that that formula is provable in T. Already the
second incompleteness theorem by Goedel shows that T cannot prove
everything that is true about this predicate; the sentence expressing
that T is consistent is such an example. The provability logic of T
consists of all (propositional) schemes that T does prove about its
provability predicate.
On the classical side provability logics are well investigated.
A remarkable thing is their stability; many classical theories, like
for example Peano Arithmetic and set theory ZF, have the same
provability logic, the decidable modal logic GL. On the constructive
side much less is known. For example, no r.e. axiomatization of the
provability logic of Heyting Arithmetic, the constructive counterpart
of Peano Arithmetic, is known, and it is not even known if it exists.
However, over the last few years significant parts of this logic have
been characterized and for the first time there is a reasonable
conjecture what the axiomatization of this provability logic actually
might be. In the talk I will give an overview of the main results in
this area.
May 3, 2002
Speaker: Derrick DuBose
Title: Determinacy and Sharps
We shall discuss some determinacy results concerning
classes within the difference hierarchy on co-analytic sets.
April 26, 2002
Speaker: Tetsuya Ishiu
Title: Club Guessing Sequences and Filters
S. Shelah proved under ZFC that for every regular
uncountable cardinal kappa, there exists a sequence which "guesses" all
closed unbounded sets in kappa. Such a sequence is called a club
guessing sequence and has been used to prove various theorems. Also we
can construct filters naturally associated with club guessing
sequences. These filters have some interesting properties, too. In
this talk, I would like to present basic facts and new results on these
objects.
April 19, 2002. No Logic Colloquium, but note that the
UCLA Philosophy Department is having its
Reichenbach Lecture, given by Michael Friedman.
April 12, 2002
Speaker: Jouko Väänänen
Title: Some Results in Infinitary Logic
I will give a survey of recent work in infinitary logic based on
the use of transfinite games and set-theoretic properties of trees.
April 5, 2002
Speaker: Juliette Kennedy
Title:
Some Results in Classical Model Theory Based on Transfer Principles
We study universality of regular reduced powers of first order
structures and get positive results under GCH or just a transfer
principle. Under GCH (or less) we can also prove that regular
ultrapowers of elementary equivalent structures are isomorphic,
improving earlier results by Keisler and Shelah. This is joint
work with Saharon Shelah.
March 15, 2002. No Logic Colloquium, but Charles Parsons
is speaking at the
UCLA
Philosophy Colloquium, 3pm.
March 8, 2002
Speaker: Albert Visser
Title: Logics for Provability and Interpretability
March 1, 2002
Speaker: Benedikt Löwe
Title: Variants of Blackwell Determinacy
February 1, 2002
Speaker: Victor W. Marek
Title:
Some Applications of Universal Algebra to Semantics of
Nonmonotonic Logics
(joint work with M. Denecker, KU Leeuven, Belgium and
M. Truszczynski, University of Kentucky)
We prove a number of results on operators in lattices. These results
are used to revisit the issue of connections between leading formalisms
in nonmonotonic reasoning: logic programming with stable semantics,
autoepistemic logic and default logic. For each logic we develop a
comprehensive semantic framework. This framework is based on a family
of operators in suitably chosen lattices. These operators represent
constructions introduced in each of these domains independently. It
turns out that all three formalisms become closely related when these
semantics are properly aligned.
Abstracting from the operators used in these formalisms, we study
approximations of operators in lattices by means of operators in the
product lattice. It turns out that, with a suitably chosen ordering,
every operator possesses a best approximation. These approximations
generalize constructions such as the 3-valued T_P operator of Fitting
and the van Gelder operator for computation of alternating fixpoint.
January 11, 2002
Speaker: Tomek Bartoszynski
Title: Perfectly Meager Sets of Reals
A set of reals is perfectly meager if it is meager inside every
perfect set. I will discuss several results concerning the properties
of these sets.
December 7, 2001
Speaker: Harvey Friedman
Title: Boolean Relation Theory
Boolean relation theory is simply the study of the Boolean relations
between one-dimensional sets and their images under multivariate
functions. This study naturally leads to a variety of statements
equivalent to the 1-consistency of Mahlo cardinals of finite order,
even in concrete settings in the integers which are subject to known
quantifier elimination. In addition, there are classifications of
large finite families of such statements (as to truth value) which can
be proved to be correct with and only with the use of Mahlo cardinals
of finite order. A complete proof of the forward direction will be
given. Ideas from the reversal will be sketched.
November 30, 2001
No colloquium, because of the
Ruthfest
at the Philosophy Department.
November 16, 2001
Speaker: Boban Velickovic
Title: Long Ehrenfeucht-Fraïssé Games and Forcing
We consider Ehrenfeucht-Fraïssé games of uncountable length
between first-order structures and relate this to the existence of
certain forcing notions which make the two structures isomorphic. In
particular, we show that it is consistent to have two structures which
are L_{\infty,\omega_1} equivalent but they cannot be made isomorphic
by a sigma-closed poset consisting of partial isomorphisms. The
construction involves a special kind of a gap-1 morass.
November 2, 2001
Speaker: James Cummings
Title: Scales and Squares
We discuss some problems in combinatorial set theory which
involve successors of singular cardinals, and show that ideas from PCF
theory are relevant to their solution. In particular we discuss the
role of two canonical stationary sets, the "good points" and the
"approachable points."
October 19, 2001
Speaker: Martin Zeman
Title: The Current State of Combinatorial Analysis
of Extender Models
October 5, 2001
Speaker: John Clemens
Title: Conjugacy of Borel Automorphisms
I will discuss the difficulty of determining when two Borel
automorphisms of a Polish space are isomorphic, i.e., conjugate via
another Borel automorphism. By using the theory of definable
equivalence relations, we can show that this is a very complicated
equivalence relation. We can also view this as showing that we can not
find "simple" invariants which completely characterize the isomorphism
class of a given Borel automorphism.
June 8, 2001
Speaker: Slawomir Solecki
Title: Descriptive Set Theory and Continua
May 25, 2001
Speaker: Peter Cholak
Title: The Latest News about the Computably Enumerable Sets
As partially suggested by the title, this talk will focus on
the latest (exciting) results of Leo Harrington and the speaker on the
computably enumerable sets.
May 4, 2001
Speaker: Steve Jackson
Title: A New Kind of Pathological Set
We answer a question posed by Steinhaus by showing that
there is a set in the plane meeting every isometric copy of the
integer lattice in exactly one point. Numerous questions remain
open.
April 20, 2001: No colloquium, due to the AMS
set theory meeting in Las Vegas the next day.
April 6, 2001
Speaker: Simon Thomas
Title: Countable Borel Equivalence Relations
and the Classification Problem for
Torsion-free Abelian Groups of Finite Rank
I will discuss some recent contributions to the project
of explaining why no satisfactory system of complete invariants
has been found for the classification problem for torsion-free
abelian groups of finite rank. The talk will include a discussion
of where this problem is situated within the descriptive
set-theoretic context of countable Borel equivalence relations.
March 16, 2001
Speaker: Robert Solovay
Title: Consistency Strength of Some Variants of NFU
The system of set theory, New Foundations, proposed by Quine is still
not known to be consistent. Some years ago, Jensen formulated a slight
variant of NF, NFU, which is demonstrably consistent. I have been
computing the consistency strength of some variants of NFU and they
turn out to be surprisingly strong. One, NFUA, has the approximate
consistency strength of a Mahlo cardinal. Another, NFUB has the
approximate consistency strength of a weakly compact cardinal.
The main focus of this talk will be on a third variant, NFU*, whose
consistency strength is approximately Sigma_2-replacement.
March 2, 2001
Speaker: G. Aldo Antonelli
Title: The Second-Order Propositional Theory of Two S5 Modalities
(Joint work with Rich Thomason, University of Michigan)
After introducing and motivating a poly-modal version of S5 with
propositional quantifiers, we consider the decidability problem for
such a language. We show that the language is quite expressive, indeed
equivalent to full second-order logic (under the standard
interpretation). This is in contrast to the case of one S5 modality
with propositional quantifiers, which is decidable (as proved
independently by Kit Fine and David Kaplan).
February 16, 2001
Speaker: Richard Ketchersid
Title:
On the Strength of omega_1-Dense Ideals on omega_1
I will outline how to get non-tame mice from the existence of an ideal
on omega_1 which is slightly stronger than an omega_1-dense ideal.
This puts the consistency strength of such an ideal somewhere past
"There is a proper class of strong cardinals the least of which is a
limit of Woodin cardinals."
February 2, 2001
Speaker: Eli Gafni
Title:
Uniform Protocols and a Design Methodology for Adaptive Algorithms
We propose a new meaning that one can attach to the notion that a
sequence of tasks T_1, T_2, ... is solvable. While the celebrated
Herlihy-Shavit conditions characterize when T_i is solvable, they may
give rise to a distinct protocol Pi_i to solve each task T_i. We
introduce the notion of a uniform protocol to capture the requirement
that the whole sequence is solvable by a single protocol.
We argue that this notion captures the recently researched
notion of one-shot adaptive protocols. Adaptive protocols have been
defined via step-complexity notions. By regarding adaptive protocols
as a special case of uniform protocols, where the latter involve
computability questions rather than complexity questions, we are able
to bring to bear all the topological machinery developed for such
questions, and completely characterize when is a task solvable
uniformly or adaptively. Furthermore, we motivate a simple sufficient
conditions for a task to be solved adaptively. These sufficient
conditions result in a methodology to develop adaptive algorithms. We
employ the methodology to develop a new adaptive immediate-snapshot
algorithm of complexity O(k^2) (compared with the current best of
O(k^3)), where k is the number of processors actually active in the
protocol.
January 19, 2001
Speaker: Drew Moshier
Title: Multi-lingual Sequent Calculi: Proof Theory and Topology
We introduce Gentzen-style sequent calculi where the formulas on the
left and right of the turnstile need not come from the same logical
system. In such calculi, sequents can be seen as consequences between
different domains of reasoning. We discuss the ingredients of proof
theory needed to set up calculi generalized in this fashion. The
result is the category MLS (multi-lingual sequent calculus) in which
the morphisms are generalized calculi and objects are calculi that
capture "domain internal" reasoning.
To develop a semantic theory for MLS, we turn to spectral theory,
showing that the MLS objects give rise to spectra (spaces of prime
filters) that are, up to homeomorphism, exactly the locally compact,
strongly sober spaces (aka Nachbin spaces). Such spaces, studied first
by Nachbin in the 1940's, are arguably the natural T_0 generalizations
of compact Hausdorff spaces. The morphisms of MLS correspond to
"continuous relations" between these spaces. In turn, a continuous
relation from X to Y corresponds to a continuous function from X to the
Smyth powerdomain of Y. Thus we establish category equivalences: MLS
to N^* (the category of Nachbin spaces and continuous relations) and
MLS to the Kleisli category for the Smyth powerdomain monad on N
(Nachbin spaces and continuous functions).
Several useful topological concepts, such as the Hausdorff condition,
zero-dimensionality, functionality of a relation, and properness of a
function (f^-1 preserves the "well-below" relation on opens), have
interesting characterizations within MLS as proof-theoretic properties
of the corresponding sequent calculi. As time allows, we will discuss
some of these characterizations and demonstrate how proofs within MLS
of familiar topological results shed light on the topological concepts
involved.
December 1, 2000
Speaker: Burkhard Englert
Title: Lattice Embeddings into the Computably Enumerable Degrees
The decidability of the two-quantifier theory of the partial order of
computably enumerable degrees R is still one of the major open problems
in computability theory. Since one can easily verify that for every
finite lattice L, there is a two-quantifier sentence phi such that L
is embeddable in R if and only if phi is true in R, the
characterization of all finite lattices embeddable into R has been of
particular interest to researchers (lattice embedding problem). In
this talk we will first survey the current status of this problem. We
will then present a condition that is necessary and sufficient for the
embeddability of a finite lattice without critical triples preserving
greatest element.
November 3, 2000
Speaker: Carlos Uzcátegui
Title: Analytic Topologies over Countable Sets
I will present in this talk some results of joint work with
S. Todorcevic about analytic topologies. A topology T over the natural
numbers is said to be analytic if T as a subset of the Cantor cube is
an analytic set. Some motivations for studying analytic topologies:
(1) Descriptive set theoretic aspect: The study of analytic topologies
is a continuation of what has been done for analytic filters (or
ideals) over countable sets. For instance: complexity of topologies
and their generating families, Baire measurability.
(2) General topological aspects: Most natural examples of countable
topological spaces found in the literature are analytic. Many
questions involving convergence are frequently questions about
countable spaces with an analytic topology.
The general goal is to make the connection between descriptive set
theoretic properties and purely topological properties of a given space
more explicit.
October 13, 2000
Speaker: Michael Beeson
Title: Logic and Computation: Putting Mathematics on a Computer
Today there exist computer programs which can perform algebra and
calculus (computation), and there also exist programs which attempt to
find proofs of theorems. But the former get wrong answers because they
have no logical capabilities, and the latter can't prove anything very
interesting, because they have no computational abilities, and can't
remember what they proved yesterday.
The talk will explain a suitable theoretical framework for the
integration of logic and computation, and discuss how that framework
has been implemented in two programs: MathXpert and Weierstrass. The
former does computation without logical errors, and the latter finds
proofs involving computations.
Mathpert is a symbolic-computation program designed with education as
the primary purpose. It can produce step-by-step solutions, not just
one-line answers, and keeps track of logical conditions to ensure that
the steps, and hence the answers, are correct.
Weierstrass can prove various specific functions are continuous, such
as f(x) = x^3, sqrt(x), or sin(x). (Previously the best that
theorem-provers could do was the continuity of a linear function.) It
can also prove that e is irrational, a nontrivial theorem which might
occur in an upper-division number theory course.
June 9, 2000
Nonstandard time and room: 2:00pm, MS 7608
Speaker: Abbas Edalat
Title: Foundation of a Computable Solid Modelling
Link to gzipped paper.
Solid modelling and computational geometry are based on classical
topology and geometry in which the basic predicates and operations,
such as membership, subset inclusion, union and intersection, are not
continuous and therefore not computable. But a sound computational
framework for solids and geometry can only be built in a framework
with computable predicates and operations. In practice, correctness
of algorithms in computational geometry is usually proved using the
unrealistic Real RAM machine model of computation, which allows
comparison of real numbers, with the undesirable result that correct
algorithms, when implemented, turn into unreliable programs. Here, we
use a domain-theoretic approach to recursive analysis to develop the
basis of an effective and realistic framework for solid modelling.
This framework is equipped with a well-defined and realistic notion of
computability which reflects the observable properties of real solids.
The basic predicates and operations on solids are computable in this
model which admits regular and non-regular sets and supports a design
methodology for actual robust algorithms. Moreover, the model is able
to capture the uncertainties of input data in actual CAD situations.
May 26, 2000
Speaker: James Hardy
Title: On the Interpretation of Variables
May 5, 2000
Speaker: Alain Louveau
Title: Covering of Compact Sets
April 21, 2000
Speaker: Arnold Beckmann
Title: Model-theoretic Characterizations of
the Separation Problem of Bounded Arithmetic
Link to paper.
Bounded arithmetic is designed to characterize low complexity
computability, i.e., the polynomial hierarchy. The main open
problem for bounded arithmetic is the question if bounded
arithmetic is finitely axiomatizable, which is equivalent to
asking if the levels of bounded arithmetic S^i_2, T^i_2 collapse.
Furthermore, this question is also connected to the open
problem whether the polynomial hierarchy collapses. The
precise connection is that bounded arithmetic is finitely
axiomatized if and only if bounded arithmetic can prove that
the polynomial hierarchy collapses [Buss 1995].
In this talk we will give model-theoretic characterizations
of the separation problem of bounded arithmetic. The main
tool will be restricted consistency statements, whose
complexity is captured by a bounded analog of Pi_1. Our
characterizations will be as the following one:
Two levels of bounded arithmetic -- say S^i_2 vs. T^j_2 for
j >= i -- are separated by a bounded Pi_1 sentence if and
only if there exists a model of the smaller theory (i.e.,
S^i_2) without proper bounded-elementary extensions to a
model of the stronger theory (i.e., T^j_2).
Remark for experts: By "bounded Pi_1" we mean the universal
closure of Pi^b_1, and "bounded-elementary extensions" is the
restriction of elementary extensions to sharply bounded formulas.
April 14, 2000
Speaker: André Nies
Title: Global Properties of Degree Structures
We investigate degree structures induced by many-one reducibility and
Turing reducibility on the computably enumerable (c.e.) sets, the
arithmetical sets, and all subsets of the natural numbers. We ask
which subsets of the degree structure are automorphism bases: For
instance, the minimal degrees form an automorphism base of the c.e.
many-one degrees, but not for the other two degree structures based on
many-one reducibility. Furthermore, we discuss whether a copy of
(N,+,x) can be defined without parameters in the structure, and
whether the structure is a prime model of its theory.
April 7, 2000
Speaker: Phokion G. Kolaitis
Title: The Complexity of Minimal Satisfiability Problems
A dichotomy theorem for a class of decision problems is a result
asserting that certain problems in the class are solvable in polynomial
time, while the rest are NP-complete. The first remarkable such
dichotomy theorem was proved by T. J. Schaefer in 1978. It concerns
the class of generalized satisfiability problems SAT(S), whose input is
a CNF(S)-formula, i.e., a formula constructed from elements of a fixed
set S of generalized connectives using conjunctions and substitutions
by variables.
In this talk, we first review Schaefer's dichotomy theorem and then
present some new results concerning the class of minimal satisfiability
problems MINSAT(S), where S is a fixed set of generalized connectives.
The input to such a problem is a CNF(S)-formula and a satisfying truth
assignment; the question is to decide whether there is another
satisfying truth assignment that is strictly smaller than the given
truth assignment with respect to the coordinate-wise partial order on
truth assignments. Minimal satisfiability problems were first studied
by researchers in artificial intelligence while studying the
computational complexity of propositional circumscription. Our main
result is that a dichotomy theorem holds for the class of all MINSAT(S)
problems, where S is a finite set of generalized connectives.
Moreover, we give simple criteria that tell apart the polynomial-time
solvable cases of MINSAT(S) from the NP-complete ones.
This is joint work with Lefteris M. Kirousis of the University of Patras.
March 3, 2000
Speaker: Theodore A. Slaman
Title: Definability in the Turing Degrees
A set of natural numbers B is Turing reducible to another set A iff
there is an effective algorithm to determine which numbers belong to B
when given complete information about A. Here is a simple example:
{n : 2n is in A and 2n+1 is not in A} is recursive in A
The Turing degrees are the equivalence classes of the induced
equivalence relation, and are naturally ordered by Turing
reducibility. We use D to denote this partial ordering.
The hierarchies of definability as represented by their universal sets
and their associated collections of definable sets have natural images
in D as degrees and ideals. We will discuss the extent to which these
degrees and ideals are intrinsic to D: which are invariant under
automorphisms of D and which are first-order definable in D.
We will pay particular attention to the Turing jump, which maps the
degree x of a set X of natural numbers, to the degree x' of the halting
problem relative to X.
Theorem (Slaman-Shore, 1999)
The function x maps to x' is definable in D.
The audience will find that this theorem has a checkered past, but that
the line of inquiry has an interesting future.
Note: On Thursday February 24, Matthew Foreman will speak
at the UCLA Mathematics Colloquium.
February 11, 2000
Speaker: Philip Welch
Title: On Gupta-Belnap Revision Theories of Truth
Revision Theories of Truth have been developed by Herzberger,
Belnap, and Gupta to give an alternative model to Kripke's of a theory
of truth for languages in which there is a (classically or otherwise)
defined truth predicate. In such schemes the extension of a truth
predicate is successively revised or "improved." This has been
broadened in a recent book of Belnap and Gupta to include a general
theory of circular definitions.
We classify the complexity of such concepts as stably true
or categorical in such schemes (which can be non-absolute
between different models of set theory); thereby raising some
mathematically based queries concerning their status. The discussion of
which revision rule to adopt at limit ordinals (amongst the three
theories of the authors above) is seen to be irrelevant when it comes
to revision-theoretically definable predicates -- which are seen to
include also the predicate of stable truth.
We argue that these theories are better considered
as extensions to the theory of inductive definability, rather than
actual theories of truth.
January 28, 2000
Speaker: Lajos Soukup
Title: On Weak Freese-Nation Property of Boolean Algebras
A partial ordering P has the weak Freese-Nation (wFN) property if there
is a mapping f : P -> [P]^omega such that for any p, q in P with p \le q
there is r in f(p) \cap f(q) such that p \le r \le q.
In the Cohen model, (P(omega), \subset) has the wFN-property.
We study the consequences of the wFN property of (P(omega), \subset).
Under this assumption, we prove that most of the known cardinal
invariants including all of those appearing in Cichon's diagram take
the same value as in the corresponding Cohen model.
If a cBA has the wFN property then it should satisfy the c.c.c. We
prove that GCH does not decide whether every c.c.c. cBA has the wFN
property. We also investigate the relationship between the wFN
property of different cBAs.
January 14, 2000
Speaker: Su Gao
Title: On the Classification of Countable Boolean Algebras
We consider the question: How many countable Boolean algebras
are there up to isomorphism? The best possible answer in the
terminology of 1900 is that there are continuum many. However,
with the theory of equivalence relations developed in the last
decade we can answer the question in a much stronger way.
In this talk I will survey some results about the isomorphism
relation for countable Boolean algebras and some applications
of these results to other related algebraic and topological
equivalence relations. This is joint work with R. Camerlo.
December 3, 1999
Speaker: Donald Bamber
Title:
Reasoning with Fallible Rules: A Second-Order Probability Approach
This talk describes a logic founded on two basic ideas.
First, motivated by the fact that most rules in rule-based systems
have exceptions, Adams' high-probability semantics was adopted. In
this semantics, a rule "If A then B" is interpreted as meaning that
the conditional probability of B given A is close to one.
Second, it was desired to have a logic that would produce (a) many
inferences having a small probability of error rather than (b) only a
few inferences having no possibility of error. Consequently, the
Bacchus-Grove-Halpern-Koller inference criterion was adopted. With
this criterion, a conclusion is inferred from a set of premises if,
roughly speaking, nearly all models of the premises are models of the
conclusion. To implement this quasi-Bayesian approach to inference,
Adamsian probability models were represented as vectors in Euclidean
space and a uniform prior probability distribution over models was
employed.
The resulting logic is equivalent to a logic of Lehmann and Magidor
and nearly equivalent to logics of Goldszmidt and Pearl.
November 19, 1999
Speaker: Norman Danner
Title: Capturing Function Classes with the Lambda Calculus
One of the first results regarding Church's untyped lambda calculus is
that, relative to an appropriate encoding of the natural numbers,
exactly the total recursive functions are representable. Much of the
power of the untyped calculus arises from its (intentional) failure to
distinguish between function and argument (i.e., the same term can be
used in both capacities). A typing discipline for the lambda calculus
reinstates this distinction, and when a typing discipline is imposed,
the collection of representable numeric functions decreases
dramatically.
In this talk, I will survey some of the main typing disciplines and
their corresponding classes of representable functions. I will start
with so-called simple typing, characterized by Schwichtenberg and
Statman in the late 60's, and work through to some recent results of
Daniel Leivant and myself on systems of ramified polymorphism.
November 12, 1999
Speaker: Péter Komjáth
Title: Simultaneous Chromatic Number
November 5, 1999
Speaker: Chris Pollett
Title: Strengths and Weaknesses of LH Arithmetic
One way to quantify the difficulty of P = NP problem would be to
exhibit a logical theory which is capable of formalizing current
attempts at answering this question and yet which is not powerful
enough to prove or disprove this equality. Razborov has argued that
most current circuit lower bound techniques can be formalized in a
fragment of arithmetic which roughly has induction on NE-predicates.
Nevertheless, exhibiting any fragment of arithmetic which one can
demonstrate cannot prove the collapse of the polynomial hierarchy is
nontrivial. In this talk we will consider a much weaker theory than
Razborov's, but which we argue can still do some interesting
mathematics. Namely, it can "reason" about all the functions in the
log-time hierarchy, it can prove the log-time hierarchy differs from
NP, and, in fact, we give some evidence it might be able to show the
log-time hierarchy is infinite. (In the real world this is known to be
true.) On the other hand, we show this theory cannot prove the
polynomial hierarchy collapses. So, in particular, it cannot prove
P = NP, and it follows that any proof that the polynomial hierarchy
collapses, if such a proof exists, must be formalized in a stronger
fragment than ours.
October 22, 1999
No colloquium.
Fefermans at UC Irvine
October 8, 1999
Speaker: Jindrich Zapletal
Title: Open-Point Games of Transfinite Length
June 11, 1999
Speaker: Slawomir Solecki
Title: Translation Invariant Ideals on Abstract Groups
May 28, 1999
Speaker: John Steel
Title: A Mouse-Eye View of L(R)
We formulate a correctness conjecture for mice (i.e., canonical
inner models) whose iteration strategies are in L(R). We prove that
the relativized-to-a-real form of this conjecture holds for all reals
of sufficiently large Turing degree.
May 14, 1999
Speaker: Herbert Enderton
Title: Theories of Equality
The theory of equality is the set of valid sentences with no
non-logical symbols at all (so there are no function symbols,
and the only predicate symbol is equality). The first-order
theory of equality is too simple to be of interest. The
second-order theory of equality is too complex to be of interest.
This talk will focus on intermediate ground.
April 30, 1999
Speaker: Lorenz Halbeisen
Title: The Dual-Ramsey Property for Sets of Partitions
A set S of infinite subsets of N is called Ramsey iff there exists
an infinite subset of N such that each or none of its infinite
subsets belongs to S. If we replace the set of infinite subsets of
N by the set of infinite partitions of N, we get the following
notion: A set T of infinite partitions of N is called dual-Ramsey
iff there exists an infinite partition X such that each or none of the
infinite partition coarser than X belongs to T.
Even though one gets a lot of results for the dual-Ramsey property
which are symmetric to the corresponding results for the Ramsey
property, e.g. each property is equivalent to the Baire property in
some topology, there are also some asymmetries and several questions
are open.
April 23, 1999
Speaker: Johan van Benthem
Title: Guarded Quantifiers:
Renewing the Search for Decidable Fragments
Logicians have long studied decidable fragments of first-order logic.
These should preferably be well behaved in other respects too, such as
having a good model theory and proof theory. We propose a new
direction here, inspired by modal logic, using a systematic analysis of
quantifier bounds. The result are large "guarded fragments" that are
decidable, and have a nice metatheory based on suitable notions of
bisimulation. We will show how guarded analysis works, and discuss
some recent results -- as well as open questions. A useful intuition
here is that of "logical dynamics": quantifiers are actions that jump
to new states, subject to certain constraints. Undecidability then
lurks once we get to parallel, rather than just sequential, quantifier
action.
References:
(1) H. Andréka, J. van Benthem, and I. Németi,
Modal logics and bounded fragments of predicate logic,
Journal of philosophical logic,
vol. 27 no. 3, 1998, pp. 217-274.
(2) J. van Benthem, Modal logic in two Gestalts,
tutorial at LICS and invited lecture at AiML Uppsala 1998, to appear in
Advances in modal logic '98, edited by
M. de Rijke and M. Zakharyashev, Kluwer, Dordrecht.
(3) E. Grädel and I. Walukiewicz, The guarded fragment with
fixed points is decidable, RWTH Aachen and informatics Warsaw, 1999.
April 16, 1999
Speaker: Alexander Kechris
Title:
Applications of Linear Algebraic Groups to Descriptive Set Theory
March 5, 1999
Speaker: Aldo Antonelli
Title: Free Set Algebras Satisfying Systems of Equations
In this talk we introduce the notion of a set algebra S satisfying
a system E of equations. After defining a notion of freeness for such
algebras, we show that, for any system E of equations, set algebras
that are free in the class of structures satisfying E exist and are
unique up to a bisimulation. Along the way, we mention analogues of
classical set-theoretic and algebraic properties as well as connections
between the algebraic and set-theoretic viewpoints.
February 19, 1999
Speaker: Matthew Foreman
Title: Partition Relations for Successor Cardinals
The classical Ramsey's theorem says that if G is an infinite graph
then G contains either an infinite complete subgraph or an infinite
independent set. Sierpinski showed that the analogous result fails for
graphs of size omega_1.
Erdös and his coworkers investigated a weaker conjecture: If G
is a graph on an ordinal of uncountable cardinality then G has either
complete subgraphs of all countable order types or independent sets of
all countable order types. This was proved (in ZFC) in the early 70's
by Baumgartner and Hajnal using forcing.
The situation for successors of uncountable cardinals is much harder.
Baumgartner and Hajnal's proof (and its predecessors) heavily uses the
measurability of omega, leading to the conjecture that the theorem
should hold at the successor of a measurable cardinal.
The talk will survey some recent advances on the problem (done jointly
with Hajnal).
February 5, 1999
Speaker: Vaughan Pratt
Title: Chu Spaces: Subject-Predicate Interaction as an
Alternative to Relational Structures
We propose Chu spaces as a simple alternative to relational
structures having the advantage that topology and duality are not only
integral but fundamental to the approach. This application of Chu
spaces was found by accident while developing them as a model of
concurrency. Chu spaces admit both conventional first order logic and
linear logic, which can be understand as respectively their internal
and external logics. The latter has a useful overlap with process
algebra for true concurrency.
January 22, 1999
Speaker: Charly Bitton
Title: Almost Free Groups
A group G of size lambda is almost free if every subgroup of size less
than lambda is free. Our objects of study are almost free groups that
are not free. There are many questions one can ask, e.g. for which
lambda is there such an object? We will review what is known and not
known, old and new, regarding this type of question.
December 4, 1998
Speaker: Alessandro Andretta
Title: Projective Sets and Ordinary Differential Equations
Fix n > 1 and consider a Cauchy problem of dimension n, i.e., a system
of n ordinary differential equations with an initial value, namely
(dx_1/dt, ... , dx_n/dt) = F(t, x_1, ... , x_n),
x_1(t_0), ... , x_n(t_0) = a_1, ... , a_n
where F : R x R^n --> R^n is continuous. It is conventional wisdom
that it is quite hard to determine whether such a Cauchy problem admits
a global solution ( = a solution defined for all t's). A possible
explanation is that the set of all Cauchy problems that admit a global
solution is Sigma^1_1-complete. In particular it is not Borel.
Restricting the attention to the F's such that for every initial
condition there is a global solution won't help: such a set is
Pi^1_1-complete.
Finally the collection of Cauchy problems which admit a global solution
even if the initial condition is slightly perturbed yields a
Pi^1_2-complete set.
(Joint work with A. Marcone.)
November 13, 1998
Speaker: Ilijas Farah
Title: F-sigma Ideals from Tsirelson Spaces
Let X be a Banach space and let {x_n : n in N} be a "nice" (e.g.
1-unconditional) basic sequence in X which converges to 0 in norm. The
sets A of integers such that the sequence a_n = x_1 + x_2 + ... + x_n
is norm-convergent form an ideal, I(x_n). The question whether one
such ideal, I(x_n), is reducible to another, I(y_n), is related to the
question whether Y contains an isomorphic copy of X. It is still
unclear what is the relationship between a Banach space and ideals
which can be represented in it in this way, but this construction has
already led us to a better understanding of Borel ideals on the
integers and the corresponding quotient structures. We consider these
ideals in the case when X is the Banach space not containing a copy of
any of the classical spaces c_0 or ell_p (p in [1,infty)), constructed
by B. Tsirelson. The deeper understanding of this space achieved
during the recent years has led to solutions of several long-standing
open problems in Banach space theory. We use Tsirelson's space to
answer some questions of G. Hjorth, A. Kechris, and K. Mazur about the
reducibility of Borel equivalence relations.
November 6, 1998
Speaker: Thomas Scanlon
Title: One-Based Groups and Arithmetic Algebraic Geometry
The notion of a one-based theory arose from an attempt to characterize
the combinatorics of the forking dependence relation in some
well-behaved stable theories. In the 1980s Pillay and Hrushovski
observed that the hypothesis of one-basedness severely restricts the
structure of definable sets for a stable group. In particular, every
definable set is a finite boolean combination of cosets of groups. In
the early 1990s Hrushovski observed that this fact together with a
method for recognizing one-based groups deduced from the machinery of
Zariski Geometries implied positive solutions to some outstanding
conjectures in diophantine geometry.
I will speak about the development of this notion of one-basedness
from the purely logical perspective and then describe some of my
own recent work on applying the structure theory of one-based
groups to some number-theoretic problems, specifically to the inverse
rational dynamics of additive polynomials in positive characteristic
(Denis' Manin-Mumford Conjecture for Drinfeld modules).
October 23, 1998
Speaker: Mark Burgin
Title: Logical Varieties and Inconsistent Knowledge Systems
One of the main concepts of the modern logic is that of a logical
calculus. However, this construction has definite limitations in many
cases. For example, the principal condition that is demanded from any
logical calculus is its consistency. At the same time, knowledge
about big object domains (in science or in practice) is essentially
inconsistent. Consequently, when logic is used for formalization of
such knowledge, it is possible to represent only small fragments of
the object domain. Otherwise contradictions appear.
To eliminate these limitations in a logically correct way, the
concepts of a logical prevariety and variety are introduced. They
generalize in a natural way the concept of a logic calculus. Problems
of completeness are investigated for logical varieties. An
incompleteness theorem for logical varieties having finite weight is
proved. The famous Gödel incompleteness theorem is a partial case
of this result.
Besides, applications to knowledge representation and non-monotonic
inference are considered.
October 9, 1998
Speaker: Ralf Schindler
Title: Nice Sets of Reals and Choice-like Principles
In the constructible universe just the analytic sets of reals are
"nice" (are Lebesgue measurable, have the property of Baire, etc.), as
there is a Delta^1_2 well-ordering of the reals. Are there inner
models in which this situation is lifted to higher levels of the
projective hierarchy, i.e., in which the Sigma^1_n sets of reals are
nice and there is a Delta^1_{n+1} well-ordering of the reals, for
n > 1?
It is well-known that the answer is "yes" under PD. But it is also
"yes" (in a strong sense) under the weaker assumption that there is an
inner model with infinitely many strong cardinals. The constructions
of the relevant models combine "David's trick" in the presence of
strong cardinals with a heavy dose of core model theory. (This is
joint work with Sy Friedman.)
I also want to discuss recent developments on related questions
which may fall under the topic of the talk's title. For instance,
Basis(Pi^1_3(x), Delta^1_4(x)) does not imply Delta^1_2(x)-determinacy
(for many reals x), even if all projective sets of reals are nice and
there are measurable cardinals.
Finally, a comment on the status of the core model theory playing
its role here might be in order (this refers to joint work with John
Steel).
June 5, 1998
Speaker: Geoffrey Hellman
Title: Predicative Foundations of Arithmetic and Its Challenges
After reviewing the Feferman-Hellman-Aczel recovery of the natural number
structure in an Elementary Theory of Finite Sets and Classes
(conservative over PA), certain challenges concerning alleged
impredicativity of induction and circularity of the construction will be
addressed. The relevance of a structuralist viewpoint concerning number
systems will be emphasized.
May 29, 1998
Speaker: Vladimir Kanovei
Title: Nonstandard Proof of the Jordan Curve Theorem
A transparent proof of the Jordan curve theorem will be
presented.
May 15, 1998
Speaker: David Marker
Title: Logarithmic-Exponential Series
The logarithmic-exponential series provide a natural algebraic
nonstandard model of the field of real numbers with exponentiation in
which one can easily analyze asymptotic behavior of definable
functions. I will show how this model can be used to answer a problem
of Hardy's.
(This is joint work with Angus Macintyre and Lou van den Dries.)
May 8, 1998
Speaker: Sergei Starchenko
Title: On Groups Definable in o-Minimal Structures
May 1, 1998
Speaker: Itay Neeman
Title: The Iterability of K^c
I discuss some recent progress on the question of iterability for
models on the K^c construction of Steel's "The Core Model Iterability
Problem" (LNL, vol. 8). Ultimately one would like to show outright
that these models are iterable. This would allow for such theorems as:
Assume PFA and that there exists a measurable cardinal. Then there is
an inner model with a super-strong cardinal.
Our ultimate goal then is to show that if a model on the construction
fails to be iterable then 0 = 1. Unfortunately current technology
falls far short of this goal. For the time being all we can derive
from the failure of iterability are inner models with large cardinals
in the region of Woodin cardinals (presumably well below 0 = 1). Thus
current lower bounds for the consistency strength of "PFA + there
exists a measurable cardinal" correspond to those large cardinals
which can be obtained from the failure of iterability.
In my talk I'll describe the current level of large cardinals which
can be derived from the failure of iterability. The work described is
joint with John Steel, and extends results of Steel and Andretta.
April 24, 1998
Speaker: Paul Eklof
Title: Absolutely Rigid Systems
Mark Nadel asked whether there is a proper class of torsion-free
abelian groups with the property that no two are L_{\infty\omega}-
equivalent, that is, no two become isomorphic in any generic
extension of the universe.
His approach to the question involved looking at known constructions
of rigid systems (that is, there are no non-zero homomorphisms between
distinct groups) to see if they remain rigid in any generic extension of
the universe. (We call these absolutely rigid systems.) He showed that
this is the case for Fuchs' construction of a rigid system of groups
smaller than the first strongly inaccessible cardinal. But he pointed
out that other constructions, such as Fuchs' construction of a rigid
system for any cardinal less than the first measurable or Shelah's for
an arbitrary cardinal, involve non-absolute notions.
In joint work with Shelah, we give a strong affirmative answer to
Nadel's original question, but we also show that there are not
arbitrarily large absolutely rigid systems. There is an absolutely
rigid system of size kappa if and only if kappa is less than
the first omega-Erdös cardinal. On the other hand, there exists
an absolutely indecomposable group A_lambda for every cardinal
lambda, such that for lambda_1 < lambda_2, A_{lambda _1} and
A_{lambda_2} are not L_{\infty\omega}-equivalent.
April 10, 1998
Speaker: Frank Wagner
Title: Supersimple Division Rings
It had long been noted that some algebraic structures, in particular
pseudo-finite fields, show a behaviour similar to stability. This has
recently been explained by Kim and Pillay, who extended the
stability-theoretic notion of "forking" to a wider class, that of
simple theories, which includes interesting structures such as bounded
pseudo-algebraically closed (PAC) fields, or existentially closed
fields with an automorphism (in characteristic 0). While a theorem due
to Macintyre, Cherlin, and Shelah states that any stable division ring
which allows an ordinal rank (i.e., is superstable) is in fact
commutative and algebraically closed, the information in the
supersimple case is sketchy. We shall show that such a division ring
is commutative, and relate this result to the conjecture that it must
be PAC.
March 13, 1998
Speaker: Zoe Chatzidakis
Title: The Model Theory of Fields with an Automorphism
February 27, 1998
No Colloquium. Hilary Putnam is delivering the 1998 Reichenbach
lecture at 3 p.m. in Dodd 175. His title is
Mental Causation.
February 13, 1998
Speaker: Philip Scowcroft
Title: Some New Models for Intuitionistic Analysis
This talk will present new models, for intuitionistic analysis with
Kripke's schema, built with the help of techniques invented
to alter cardinalities in models of Zermelo-Fraenkel set theory.
January 30, 1998
No Colloquium, because of the
VIG '98 Logic Meeting at UCLA.
January 16, 1998
Speaker: Bruno Poizat
Title: A First Course in Mathematical French
This talk is specially designed for the logicians who do not understand
French, neither in its American form nor its European variant.
Mathematics is universal: it concerns humanity as a whole; an essential
character of humanity is the diversity of its languages. Therefore
expression of mathematics, and more generally of sciences, should not
be confiscated for the sole profit of the most powerful nation in terms
of politics, economics, and armies, and it is advisable to maintain
alive a variety of languages for scientific communication.
As we can see from the survival of various minorities in spite of
considerable pressures, human beings resent uniformity and intolerance
imposed on them. Nevertheless the right to differ is taken into
account by the American academic system -- which seldom takes effective
steps for the survival of languages other than English -- only in
folkloric or irrelevant matters, such as affirmative actions for women,
homosexual, ethnic minorities (or majorities!); by "irrelevant" I do
not deny that they express a concern for some basic and serious
diseases of the American society, but I mean that this concern is
applied in a wrong context: I hope that nobody will believe that
ability in mathematics is affected by sex, sexual behavior, color of
skin or other biological factors. Language is *relevant*, from the
obvious fact that mathematicians produce nothing but literature.
The immediate aim of my talk is an exposition of a general
model-theoretic version of the Theoreme de Borel-Tits concerning the
isomorphisms abstract between the groups algebraic simple.
Theorem 1 (un). Consider(ons) an object infinite V(K) defined in un
field algebraically closed K, and un isomorphisme f between V(K)
and W(L), another objet defini dans un corps algebriquement clos L.
Supposons that f echange les sets constructible de V(K)^n et de
W(L)^n for every n. Alors il existe un isomorphisme s entre les
corps K et L, so that f se decompose en the transport of structure
entre V(K) et V(s(K)) = V(L) induit par s et une application
L-definissable de V(L) on W(L).
Theoreme 2 (deux). Supposons que tout ensemble constructible de
V(K)^n be definable with parameters dans la structure V(K). Alors:
(i) if K is of characteristic zero, une copie de K est definissable
without parameters in V(K);
(ii) si K est de caracteristique p, une famille finie (K1, ... , Kn)
de copies de K est definissable sans parametres dans V(K) .
Corollary 1 (un cas simple de Borel-Tits). Un isomorphisme abstrait,
entre deux groupes algebriques simples sur des corps algebriquement
clos, se decompose en un transport de structure induit par un
isomorphisme entre les deux corps et un morphisme geometrique.
Corollaire 2. Dans un contexte superstable, un groupe connexe
definissable d'automorphismes d'un groupe algebrique simple, sur un
corps algebriquement clos, est forme d'automorphismes interieurs
( = inner).
December 5, 1997
Speaker: Howard Becker
Title: The Cardinal Number of the Set of Path-Components
This talk is concerned with the following question. Assume CH fails;
does there exist a compact set K in R^n such that K has exactly
aleph_1 path-components? For R^3, the answer is yes. For R^2, the
answer is no, assuming a weak large cardinal axiom. The proof of the
R^3 case will be discussed.
November 21, 1997
Speaker: Boban Velickovic
Title: Transfinite Ehrenfeucht-Fraisse Games
November 7, 1997
Speaker: Peter Komjath
Title: Consistency Theorems on Set Mappings
(with S. Shelah)
In this talk we consider set mappings of the type
f:[kappa]^n --> [kappa]^{< mu}
where n is a natural number, and the question is how large a free set
can be, i.e., a subset X of kappa with y not in f(x_1,...,x_n)
for {y,x_1,...,x_n} in [kappa]^{n+1}. Hajnal and Mate proved that
if n = 2, kappa = omega_2, and mu = omega then there are
arbitrarily large finite free sets. This was later extended by Hajnal
to n = 3, kappa = omega_3.
Theorem (S. Shelah). There are natural numbers t_m such that for
every m < omega it is consistent that there is a set mapping
f:[omega_m]^4 --> [omega_m]^{< omega}
with no free subsets of size t_m.
Theorem (P. Komjath). For every m < omega it is consistent that
there is a set mapping
f:[omega_m]^2 --> [omega_m]^{< omega}
with no infinite free subsets.
October 24, 1997
Speaker: Steven Rudich
Title: Natural Proofs
Joint work with Alexander Razborov:
One way to argue that open problems such as P =? NP are difficult is
to demonstrate that known methods are inherently too weak to
solve them. This approach was taken in Baker, Gill, and Solovay (BGS)
who used oracle separation results for many major complexity classes to
argue that relativizing proof techniques could not solve these
problems. Since relativizing proof techniques involving
diagonalization and simulation were the only available tools at the
time of their work (1975) progress along known lines was ruled out.
Instead, people started to look at these problems in terms of
Boolean complexity. Along these lines, many (non-relativizing) proof
techniques have been discovered and used to prove lower bounds. These
techniques are highly combinatorial; they exist in a much larger
variety than their recursion-theoretic predecessors. In this talk, we
do for the 90's what BGS did for the 70's.
We introduce the notion of a natural proof. We argue that
all lower bound proofs known to us in non-monotone Boolean
complexity either are natural or can be represented as natural. We
show that if a cryptographic hardness assumption is true, then no
natural proof can prove superpolynomial lower bounds for general
circuits. Furthermore, no complexity class containing good
pseudo-random function generators has a natural proof against it. This
gives a proof that the restriction methods which were sufficient to
prove the parity lower bounds of FSS, Ajtai, Yao, and Hastad are
inherently incapable of proving the bounds for AC^0[q]-circuits of
Razborov and Smolensky.
Razborov has recently found one application of the notion of natural
proof to independence. He has shown that all lower bounds in a certain
fragment of arithmetic naturalize in our sense. Thus, on a hardness
assumption the question of whether SAT has polynomial sized circuits is
independent of this fragment.
October 17, 1997
Speaker: Martin Otto
Title: The Decision Problem for some Logics with
Only Two Variables
Some recent variations on the Classical Decision Problem concern logics
in the vicinity of FO^2, the fragment of first-order logic in which
only two variable symbols are admitted. FO^2 is long known to have the
finite model property, and to be decidable. Several slight extensions
of FO^2 turn out to be highly undecidable. One very interesting
extension, allowing counting quantifiers, however, yields a much more
expressive fragment of first-order that is decidable without having the
finite model property. (Joint work with E. Grädel and E. Rosen.)
October 3, 1997
Speaker: Andras Hajnal
Title: New Results on Old Problems