UCLA Logic Colloquium

The UCLA Logic Colloquium meets on alternate Fridays, at 4 p.m., in MS 6627. The Logic Colloquium chairman is Herbert Enderton . Click here for some other colloquia at UCLA, or the Caltech-UCLA logic seminar. Click here for more about logic at UCLA and the UCLA Logic Center.

Talks are listed here in reverse chronological order.

May 30, 2008
Speaker: Eric Pacuit
Title:
  

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

Click here to see the announcements for older Logic Colloquia.