2010 UCLA Logic Colloquium

The UCLA Logic Colloquium meets on alternate Fridays, at 4 p.m., in MS 6627.  
Here are links to the UCLA Logic Center, the Caltech-UCLA Logic Seminar, the Philosophy Colloquium, and the Marschak Colloquium.

For more recent colloquia, see the new website maintained by Itay Neeman.

Talks are listed here in reverse chronological order.

June 4, 2010
Speaker: Mia Minnes
Title: Linear Orders -- a Case Study in Automatic Model Theory
   Computable model theorists have analyzed many classical theorems on linear orders. A standard (and important) example is that although any infinite linear order must contain either an infinite increasing chain or an infinite decreasing chain, there is a computable linear order with no computable suborder of type omega or omega*. We will show that this theorem fails in the automatic structures setting. This pronounced difference between computable model theory and automatic model theory is the departure point for further questions about categoricity, dimension, homogeneity, and complexity of substructures. Differences between the computable and automatic context with respect to each of these will be illustrated with recent results about automatic linear orders. This is joint work with Asher Kach.

May 28, 2010
Speaker: Joel Friedman
Title: Modal Platonism is a Threat to Platonism (and to its so-called Indispensability Principle)
   Abstract in pdf format. Text of talk in pdf format.

May 21, 2010
Speaker: Menachem Magidor
Title: Forcing Axioms and Squares
   Forcing Axioms are axioms added to the usual axioms of Set Theory with the intuitive motivation of "A set that can be imagined to exist, does exist".
   These axioms, like Martin's Axiom (MA), the Proper Forcing Axiom, (PFA) Martin's Maximum (MM) and other variations turned out to be very successful in deciding many problems that are otherwise independent of Set Theory.
   The combinatorial principle square, which was introduced by Jensen, seems to hold in almost all of the canonical inner models for large cardinals constructed so far. There is a class of weakenings of the square principle, and the weakest "weak square" that holds in a given model seems to be an indication of the model's deviation from a canonical inner model.
   One of the interesting global consequences of forcing axioms stronger than Martin's Axiom is that square fails everywhere. The talk will survey the known results about the interaction of different forcing axioms like PFA and MM with weak square principles. This study may be the first step to the determination of the consistency strength of these axioms.

May 7, 2010
Speaker: Zlatan Damnjanovic
Title: From Strings to Numbers
   The talk articulates a minimal, formalist framework for the representation of mathematical reasoning. We develop basic arithmetic in an elementary theory of concatenation, simulating induction and primitive recursion without taking the standard natural numbers for granted. The concatenation theory is proved to be mutually interpretable with the well-known arithmetical theory Q.

April 30, 2010
Speaker: Alex Usvatsov
Title: Generic stability and the forking ideal
   One of the main tools that model theory offers for the analysis of structures is different abstract notions of "smallness" (such as forking). The goal of my talk is to describe the behavior of some of these notions in the context of generically stable types in dependent theories (theories without the independence property).
   First I will discuss the concept of generic stability, which allows to carry many techniques from stability theory over to theories without the independence property (such as certain valued fields). Then I will talk about the notions of forking and thorn-forking, and their meaning in this context. In particular, I will discuss the recent result (joint with D. Garcia and A. Onshuus) that all the "reasonable" notions of "smallness" coincide for realizations of generically stable types.

April 9, 2010
Speaker: Yiannis Moschovakis
Title: The axiomatic derivation of absolute lower bounds
   The ancient Euclidean algorithm computes the greatest common divisor gcd(m,n) of two natural numbers by iterating the remainder operation. It requires no more than 2log(min(m,n)) extractions of remainders to compute gcd(m,n) (for m > n > 1), and so to also check whether m and n are coprime. It is not known whether it is optimal, either for the computation of gcd(m,n) or for deciding coprimeness.
   In this lecture I will develop an axiomatic approach to the theory of algorithms in the style of abstract model theory, which makes it possible to make precise and (in some cases) derive non-trivial lower bounds for problems like the computation of gcd(x,y) or deciding coprimeness. These axiomatically derived lower bounds apply to many natural complexity measures, all known computation models and (arguably) to all algorithms from specified primitives. The method will be illustrated with some specific results on problems in arithmetic like those above which are joint with Lou van den Dries.

March 12, 2010
Speaker: Inessa Epstein
Title: Measure Preserving Group Actions and Descriptive Set Theory
   We are going to consider the space of free, measure preserving, ergodic actions of a countable group on a standard probability space. This space is of high importance in functional analysis. We will consider equivalence relations on this space - in particular, the equivalence relation given by orbit equivalence - and discuss the Borel complexity of the equivalence relation. Two group actions are orbit equivalent if these is a measurable way of almost everywhere identifying the orbits given by the actions. Descriptive set theoretic aspects that are of interest will be introduced as well as recent results concerning these group actions.

February 19, 2010
Speaker: Lou van den Dries
Title: Transseries
   The differential field of Laurent series over the reals is not closed under exponentiation, but has a canonical extension to an exp-closed differential field T of ``transseries''. I will describe T and mention some of the intriguing conjectures about its model-theoretic behavior, which are analogous to the well-known model-theoretic facts about the real field. This is a survey of joint work with Matthias Aschenbrenner and Joris van der Hoeven.

January 22, 2010
Speaker: Grigor Sargsyan

January 8, 2010
Speaker: Fernando Ferreira
Title: Bar-Recursive Interpretations of Classical Analysis   Slides for talk
   We start by briefly describing Shoenfield's functional interpretation of Peano arithmetic. Tao's finitization of the infinite convergence principle can be seen as an instance of this interpretation together with a simple majorizability argument (uniformity result). In 1962, Spector gave a remarkable characterization of the provably recursive functionals of full second-order arithmetic (a.k.a. analysis). We explain what is bar-recursion and outline a direct (i.e., not via intuitionistic logic) proof of Spector's result. We note that bar-recursive functionals are majorizable and, hence, that majorizability arguments extend to analysis.
   The bounded functional interpretation was introduced in 2005 by Oliva and the present author. In its version for classical arithmetic, it is an interpretation which "injects" some non set-theoretic uniformities into Peano arithmetic. Due to its Soundness Theorem, the interpretation extracts correct uniform bounds of AE-theorems (Proof Mining). Together with Engrácia, we recently showed that the bounded functional interpretation also extends to analysis.

November 6, 2009
Isaac Goldbring
Title: Hilbert's Fifth Problem for Local Groups
   The most common version of Hilbert's Fifth Problem (H5) asks whether every locally euclidean topological group (i.e. a topological group whose identity has an open neighborhood homeomorphic to some R^n) can be given the structure of a real analytic manifold so that the group multiplication and inversion become real analytic maps; briefly, whether every locally euclidean topological group is a Lie group. A positive solution to the H5 was given by Gleason, Montgomery, and Zippin in the 1950s. Shortly after, Jacoby claimed to have proven that every locally euclidean "local group" was locally isomorphic to a Lie group. Roughly speaking, a local group is a hausdorff space which has a partial group-like operation defined on it which is continuous. However, Jacoby's proof was discovered to be flawed in the '90s, leaving some important theorems whose truth rests on this local version of the H5 on shaky foundation. By modifying techniques used by Hirschfeld in a proof of the H5 using nonstandard analysis, I was able to give a correct proof of the local H5. In this talk, I will try and sketch a part of the proof of the local H5. No background knowledge in Lie theory or nonstandard analysis will be necessary and all relevant terms will be defined.

October 23, 2009
Speaker: Wai Yan Pong
Title: Locally Finite Quantifier Eliminable Graphs
   We classified the class of locally finite quantifier eliminable graphs in the language of distance predicates.
This is a joint work with Shawn Hedman.

October 9, 2009
Speaker: Phokion G. Kolaitis
Title: Foundations and Applications of Schema Mappings
   Schema mappings are high-level specifications, typically expressed in some logical formalism, that describe the relationship between two database schemas. Schema mappings constitute the essential building blocks in formalizing the main data inter-operability tasks, including data exchange and data integration. The aim of this talk is to present an overview of recent developments in the study of schema mappings with emphasis on the interaction of this area of research with logic and computation.

May 29, 2009
Speaker: Jana Marikova
Title: O-minimal Fields, Standard Part Maps, and Triangulations

May 22, 2009
Speaker: Johan van Benthem
Title: Modal Lindström Theorems and Weak Abstract Model Theory
   Standard abstract model theory has mainly looked at extensions of first-order logic, taking its expressive power for encoding structure for granted. And the classical Lindström Theorem analyzes what makes this base system tick at a suitable abstraction level. But small can be beautiful, too. In particular, modal languages are natural descriptions of processes and information that can be viewed as fragments of first-order logic with a nice balance between expressive power and (decidable) complexity. These, too, can be captured via Lindström theorems, but we need new proofs. Lindström's original argument breaks down at some stage, because not enough expressive power is left to encode partial isomorphisms or bisimulations with the right extension properties. We present an alternative proof, its consequences for preservation and interpolation theorems, and its upward generalizations to larger fragments. We also discuss how far Lindström's original proof extends 'downward' into fragments, as well as new open problems at the fault line between the two methods. Finally, we raise some questions about fixed-point extensions of these weaker languages: an area where so far, Lindström theorems have been famously missing. What does this mean?
J. van Benthem, 2007, A New Modal Lindström Theorem, "Logica Universalis" 1, 125-138.
J. van Benthem, B. ten Cate & J. Väänännen, 2007, Lindström Theorems for Fragments of First-order Logic, Proceedings of LICS 2007, 280-292. To appear in "Logical Methods for Computer Science".

May 8, 2009
Speaker: Paul Larson
Title: Universally Measurable Sets of Reals in Generic Extensions
   A set of reals is said to be universally measurable if it is in the domain of every complete finite Borel measure on the reals. The structure of the collection of universally measurable sets is still not well understood. We will show that consistently there are just continuum many universally measurable sets, answering a question of Dan Mauldin from 1978.
This is joint work with Saharon Shelah.

Note: On Thursday, April 30, there will be a public symposium, The Convergence of Logic, Mathematics, and Computer Science, 2:00-7:00 p.m., in Kerckhoff Hall, Charles E. Young Grand Salon.

April 24, 2009
Speaker: John Harrison
Title: Decidability and Undecidability in Theories of Real Vector Spaces    (Joint work with Robert M. Solovay and Rob Arthan)
   It's natural to formulate theories of real vector spaces using a 2-sorted first-order language with a sort for the scalars and a sort for the vectors. Introduction of coordinates reduces the theory of a vector space of a specific finite dimension to the first-order theory of the real numbers, known to be decidable since Tarski. Experience in the actual formalization of mathematics motivates an investigation into decision problems for various more general 2-sorted first-order theories of vector spaces, with or without an inner product, norm, assumption of completeness, or restriction on dimension.
   Solovay, Arthan and the speaker have carried out a systematic study of decidability for such theories. The theories of real vector spaces, inner product spaces, and Hilbert spaces turn out to be decidable and to admit quantifier elimination in a slightly expanded language. However, similar theories of normed spaces, Banach spaces and metric spaces are not even arithmetical: the theory of 2-dimensional Banach spaces, for example, has the same many-one degree as the set of truths of second-order arithmetic. However, by restricting quantifier alternations, we can arrive at some decidable fragments of these theories, a fact that has proved useful in mechanizing proofs.

April 17, 2009
Speaker: Carl Mummert
Title: Convergent and Stationary Strategies in Choquet Games
   This talk describes work with Francois Dorais on the (strong) Choquet game. We are interested in spaces where the second player has a stationary winning strategy, which only considers the previous move of the first player, or has a convergent strategy, which causes the result of any play to contain a single point. We show these properties are closely related to the structure of bases for the space. In particular, the second player has a stationary strategy on every second-countable T_1 Choquet space.

April 3, 2009
Speaker: Alain Louveau
Title: Some New Results about Borel Functions
   Some old questions about Borel functions, in particular their generation by filter limits and generalizations of the Jayne-Rodgers result, have been studied by various people, including Debs, Saint Raymond, Motto Ross, and Semmes. I will discuss the results obtained so far and some possible conjectures.

March 6, 2009
Speaker: Martin Dowd
Title: A Lower Bound on the Mahlo Rank of a Pi_1^1-Indescribable Cardinal
   Computing the Mahlo rank of a large cardinal provides perspective on the cardinal. In particular it provides a "conservative" quantitative method for evaluating whether the existence of the cardinal should be accepted as an axiom. The Pi_1^1-indescribable cardinals are a fundamental example. Results related to this problem will be given, including a lower bound on the rank.

February 20, 2009
Speaker: Solomon Feferman
Title: Conceptual Structuralism and the Continuum
   Conceptual structuralism is a view of the nature of mathematics according to which mathematics emerges from humanly constructed, intersubjectively established, basic structural conceptions. Some of these are so clear that every problem posed in the language of the structure conceived can be said to have a definite truth value, whether or not that can be determined. Other conceptions may contain an inherently vague aspect, so that truth is only partial in them and not every problem can be asserted to have a definite truth value. In particular, this is behind my view that the Continuum Hypothesis is not a definite mathematical problem.

February 13, 2009: No Logic Colloquium, but note that Moshe Vardi is speaking at the CS Seminar at Caltech, 74 Jorgensen, 4:00.
Title: From Philosophical to Industrial Logics
    One of the surprising developments in the area of program verification is how several ideas introduced by logicians in the first part of the 20th century ended up yielding at the start of the 21st century industry-standard property-specification languages called PSL and SVA. This development was enabled by the equally unlikely transformation of the mathematical machinery of automata on infinite words, introduced in the early 1960s for second-order arithmetics, into effective algorithms for industrial model-checking tools. This talk attempts to trace the tangled threads of this development.

January 30 to February 1, 2009
There will be a Very Informal Gathering of logicians at UCLA.

January 16, 2009
Speaker: Sean Cox
Title: Consistency Strength of Combinatorial Properties at Small Regular Cardinals
    I will present some consistency results about the following combinatorial properties at small regular cardinals: stationary set reflection, existence of nonregular ultrafilters, and variants of Chang's Conjecture.

November 21, 2008
Speaker: Henry Towsner
Title: Proof Theory and the Correspondence Between Ergodic Theory and Additive Combinatorics
    In the last decade there has been a renewed interest in the Furstenberg correspondence, a technique for relating problems in additive combinatorics. We discuss how methods from mathematical logic apply to this correspondence and can be used to expand the class of problems the correspondence applies to.

November 7, 2008
Speaker: Joseph Flenner
Title: The Relative Structure of Valued Fields
    The idea of the model theory of a valued field being controlled by the residue field and value group has been a common thread since the theorem of Ax and Kochen, and recently has found a new level of sophistication in work of Haskell, Hrushovski, and Macpherson. We give an overview, and then describe an ongoing attempt to consolidate this through a general analysis of characteristic-0 henselian fields relative to the leading terms. The talk should be broadly accessible.

October 24, 2008
Speaker: Alex Usvyatsov
Title: Minimal Stable Types over Banach Spaces.
   I will describe analysis of minimal stable wide types over Banach spaces, which in particular leads to the solution of Henson's conjecture on categorical classes of Banach spaces. The proofs are quite elementary, and I will define all the basic concepts, so this talk will require virtually no background in model theory (or logic in general).

October 10, 2008
Speaker: Benjamin Miller
Title: Forceless, Ineffective, Powerless Proofs and Generalizations of Descriptive Set-Theoretic Dichotomy Theorems
   Over the last 30 years, a great variety of dichotomy theorems concerning Borel structures in Polish spaces have been discovered. Despite the fact that these results only deal with classical notions, many of their proofs require somewhat advanced ideas from logic, e.g., recursion theory and forcing. We will discuss an approach to giving classical proofs of these theorems which utilizes ideas from graph theory.

May 30, 2008
Speaker: Eric Pacuit
Title: The Tree of Knowledge in Action
   Many logical systems today describe intelligent interacting agents over time. This talk will survey various approaches to modeling rational interaction and the questions that arise when comparing them.

May 23, 2008
Speaker: Simon Thomas
Title: A Remark on the Higman-Neumann-Neumann Embedding Theorem
   The Higman-Neumann-Neumann Embedding Theorem states that every countable group G can be embedded into a 2-generator group K. In this talk, using the theory of Borel equivalence relations, I will explain why there does not exist an explicit choice of the group K which has the property that isomorphic groups G are assigned isomorphic groups K.

May 16, 2008
Speaker: Aldo Antonelli
Title: Abstraction Principles in First-Order Arithmetic
   Formalizations of arithmetic ordinarily proceed along one of the three avenues: (1) as a first-order theory in which numbers are taken as primitive and their properties laid down by means of particular extra-logical axioms; (2) as a second-order theory in the manner of Frege and Russell, in which numbers are naturally identified with classes of (extensions of) equinumerous concepts, and their properties derived from such a characterization; or (3) as a first-order theory embedded within a set-theoretic apparatus, in the manner of Zermelo or von Neumann, selecting particular representatives for the equivalence classes (with respect to equinumerosity). None of these options is completely satisfying in every respect. Option (1) leaves the nature of number unexplained, and option (3) does not seem general enough, in that the connection of numbers with their cardinal properties (i.e., ultimately, with the act of counting) is lost. Option (2) is perhaps the most conceptually satisfying, in that the characterization of numbers as equivalence classes is well-motivated and completely general. Unfortunately, option (2) also takes us into the hostile landscape of second-order logic.
   In this talk we show how to overcome these shortcomings. After looking at abstraction principles in general, and with the aid of a non-standard (but still first-order) cardinality quantifier and an extra-logical operator representing numerical abstraction, we propose a formalization of arithmetic at the first order, in which numbers are abstracta of the equinumerosity relation, their properties derived from those of the cardinality quantifier and the abstraction operator.

May 2, 2008
Speaker: Salma Kuhlmann
Title:Fragments of Peano Arithmetic and Embeddings of Valued Fields into Power Series Fields
   An integer part (IP for short) Z of an ordered field F is a discretely ordered subring, with 1 as the least positive element, and such that for every x in F, there is a z in Z such that z <= x < z+1. The interest in studying these rings originates from Shepherdson's work in [S] who showed that IP's of real closed fields are precisely the models of a fragment of Peano Arithmetic called Open Induction. On the other hand, in [M-R], the authors establish the existence of an IP for any real closed field R. The key idea of their proof is to show that there is a "truncation closed" embedding of R in the field of generalized power series R((G)) (G := v(R), the value group). We studied in [B-K-K] the arithmetic properties of such rings, and consider in [F-K-K] necessary and sufficient conditions for a valued field K with value group G and residue field k (with char K = char k) to admit a truncation-closed embedding in the field of generalized power series k((G,f)) (with factor set f). We show that this is equivalent to the existence of a family (tower of complements) of k-subspaces of K which are complements of the (possibly fractional) ideals of the valuation ring. We construct such towers if K is a Henselian field of characteristic 0 or, more generally, an algebraically maximal Kaplansky field. Hence our results complement Kaplansky's embedding theorem [Kap].
   [B-K-K] Biljakovic, Darko; Kotchetov, Mikhail; Kuhlmann, Salma: Primes and irreducibles in truncation integer parts of real closed fields, in Logic, Algebra and Arithmetic, Lecture Notes in Logic 26, A K Peters (2006), 42-65.
   [F-K-K] Fornasiero, A.; Kuhlmann, F.-V.; Kuhlmann, S.: Towers of complements and truncation closed embeddings of valued fields, submitted (2008), 41 pp.
   [Kap] Kaplansky, I.: Maximal fields with valuations I, Duke Math J. 9 (1942), 303-321.
   [M-R] Mourgues, Marie-H\'el\`ene; Ressayre, Jean-Pierre: Every real closed field has an integer part, J. Symbolic Logic 58 (1993), 641-647.
   [S] Shepherdson, J. C.: A non-standard model for a free variable fragment of number theory, Bulletin de l'Academie Polonaise des Sciences 12 (1964), 79-86.

April 25, 2008
Speaker: Krzysztof Krupinski
Title: Model Theoretic Ideas in Some Topological Contexts
   The notion of forking independence, introduced by Shelah, turned out to be the main tool in the study of stable and, more generally, simple theories. This notion generalizes classical notions of independence, e.g. linear independence in vector spaces and algebraic independence in algebraically closed fields. The powerfulness of forking independence in stable and simple theories comes from the fact that it satisfies the long list of nice properties (such as symmetry or transitivity), which actually determine this notion.
   The main motivation for what I am going to discuss is to apply various ideas from geometric stability theory to purely topological (or descriptive set theoretic) objects. The point is that we can use a certain notion of independence defined in a purely topological way, even if we do not work in a first-order context.
   I will discuss topological notions of profinite structure and m-independence introduced by Newelski in the late 90's. Examples, conjectures and some structural theorems about profinite groups regarded as profinite structures, proved by Newelski and Wagner, will be given. Then I will concentrate on a more general notion of Polish structure and non-meager independence that I have introduced and been investigating for about two years.
   A Polish structure is a pair (X,G) where G is a Polish group acting (faithfully) on a set X so that the stabilizers of all singletons are closed. Profinite structures are particular cases of Polish structures for X and G profinite and the action of G on X continuous. Polish G-spaces and, more generally, Borel G-spaces are also examples of Polish structures. We say that a Polish structure (X,G) is small if for every n in omega there are countably many orbits on X^n under G.
   Newelski has introduced the topological notion of m-independence in profinite structures which, under the assumption of smallness, satisfies nice properties and allows us to prove counterparts of some deep results from stability theory. However, it is not easy to find many explicit examples of small profinite structures (e.g. I have proved that abelian profinite groups of finite exponent being inverse limits of countable systems are such examples). In contrast, there are many examples of small Polish structures. A simple non-profinite example is the unit circle with the full group of homeomorphisms. More complicated examples are Hilbert cube and the pseudo-arc with the full group of homeomorphisms.
   I will discuss a purely topological notion of independence, called non-meager independence, that satisfies some nice properties (e.g. symmetry, transitivity, existence of independent extensions) in small Polish structures, and so allows us to introduce basic stability-theoretic concepts and to prove fundamental results about them (e.g. Lascar inequalities). In profinite structures this notion of independence coincides with m-independence introduced by Newelski. If time permits, I will also discuss some examples and results describing the structure of small compact G-groups, i.e., small Polish structures (X,G) where X is a compact group and G acts continuously on X as a group of automorphisms.

March 14, 2008
Speaker: Su Gao
Title: A Coloring Property for Countable Groups
   I will talk about a combinatorial coloring property for countable groups that is equivalent to the existence of compact free subflows of the Bernoulli flow. We show that every countable group has this coloring property. This is joint work with Steve Jackson and Brandon Seward.

February 15, 2008
Speaker: Joshua Sack
Title: On Temporal Dynamic Epistemic Logic
   Epistemic logic is a modal logic that expresses knowledge and belief of agents. We obtain dynamic epistemic logic (DEL) by adding to epistemic logic expressions that assert that certain actions result in certain new beliefs. In this talk, I will discuss one of several languages that add temporal logic to DEL, focusing on the addition of a previous time operator to DEL.

On February 1 - 3, 2008, there will be a Very Informal Gathering of logicians at UCLA. The invited speakers are Jeremy Avigad, Deirdre Haskell, Marcus Kracht, Justin Moore, Chris Pollett, Jan Reimann, and Christian Rosendal.

January 18, 2008
Speaker: Thomas Scanlon
Title: Theories of Fields
   Motivated by a conjecture of Florian Pop, we show that for each finitely generated field K, there is a sentence in the language of rings so that for any finitely generated field L, the sentence is true in L if and only if L is isomorphic to K. In this talk, we will outline some of the key steps involved in connecting algebra and logic and then discuss some related questions about commutative rings.

November 30, 2007
Speaker: Marcus Kracht
Title: The Combinatorics of Interpreted Languages
   Formal language theory likes to deal with languages as sets of strings. But clearly, languages are sets of signs, which in turn are (at least) pairs consisting of a string and some meaning. A mathematical theory of such objects is so far missing.
  In this talk I shall outline the beginnings of such a theory, and give some results as well as open problems. For example, we shall show that it is possible to define a notion of strong generative capacity that does not assume structure to begin with and yet is provably different from weak generative capacity normally studied in formal language theory.

November 16, 2007
Speaker: Boban Velickovic
Title: Maharam Algebras
   A Maharam algebra is a complete Boolean algebra which carries a strictly positive continuous submeasure. In 1947 Maharam asked if every such algebra is in fact a measure algebra. This problem, which was also known as the Control Measure Problem, was finally resolved by Talagrand in 2005 who provided a counterexample. In this talk we will survey some recent work on characterizations and combinatorial properties of Maharam algebras and discuss some open questions.

November 2, 2007
Speaker: Jason Teutsch
Title: A Short History of Shortest Programs
  Since the fourteenth century and certainly not before then, mankind has demonstrated a universal preference for simplicity. This principle, known as Ockham's Razor, still manifests itself today: humans love short computer programs. Not surprisingly, we have a short description for the set of shortest programs:
     MIN = {e : for no j < e is phi_j = phi_e}.
I will survey the history of this set, from Cold War Russia to modern-day Chicago.
  The only thing better than a Turing machine which tells you whether or not your program code is the shortest possible would be a machine that does this correctly. But if your friend can do this correctly, then she is not a Turing machine. Even an oracle machine which completely knows the halting set will be clueless when it comes to shortest programs. More precisely, the set of shortest programs is Turing equivalent to 0'', the halting set of the halting set.
  Recently, Stephan and Teutsch have characterized the canonical Turing degrees 0', 0'', 0''', ... in terms of shortest programs. This should be viewed as a generalization of the above theorem by Meyer. Our characterization gives a partial solution to the most tantalizing problem in all of computability theory, Schaefer's so-called MIN* problem. The problem is this. Replace "=" in the definition for MIN by "=*" (equal except for a finite set), and call the new set MIN*. Schaefer himself showed that MIN* join 0' was Turing equivalent to 0''', leaving open the question whether or not the halting set itself might be computable from MIN*. Our answer is that this reduction holds for all Kolmogorov numberings. For Gödel numberings in general I'm still unsure.

October 19, 2007
Speaker: Andrés Caicedo
Title: Regressive Functions on Pairs
  Let k be a positive integer. A function f : [N]^k --> N is called regressive iff f(u) < min(u) whenever min(u) > 0. A subset B of N is min-homogeneous for f iff f(u) = f(v) whenever u and v are in [B]^k and 0 < min(u) = min(v). Kanamori and McAloon showed that any regressive function admits an infinite min-homogeneous set, but this is not provable in Peano Arithmetic. For k = 2, this translates into the corresponding regressive Ramsey numbers having Ackermannian rate of growth. We present a combinatorial proof of this result that considerably improves the previous bounds.

October 6, 2007   Saturday
A special logic colloquium in honor of Matthew Foreman's 50th birthday.
11:00 a.m.:   Menachem Magidor.
1:30 p.m.:   András Hajnal,   More Rainbow Ramsey Theorems.
2:30 p.m.:   James Cummings,   Full Reflection.
4:00 p.m.:   Matthew Foreman.

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.
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.

Click here to see the announcements for older Logic Colloquia.