Past UCLA Logic Colloquia

The UCLA Logic Colloquium typically meets on alternate weeks, at 4 p.m., in MS 6627. This page includes a listing of older talks. Talks are listed here in reverse chronological order. The Colloquium Webpage includes a listing of recent talks.

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

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