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

Title: *
*

January 8, 2010

Speaker: **
Fernando Ferreira**

Title: * Bar-Recursive Interpretations of Classical Analysis *

We start by briefly describing Shoenfield's functional interpretation of
Peano arithmetic. Tao's finitization of the infinite convergence principle
can be seen as an instance of this interpretation together with a simple
majorizability argument (uniformity result). In 1962, Spector gave a
remarkable characterization of the provably recursive functionals of full
second-order arithmetic (a.k.a. analysis). We explain what is bar-recursion
and outline a direct (i.e., not via intuitionistic logic) proof of Spector's
result. We note that bar-recursive functionals are majorizable and, hence,
that majorizability arguments extend to analysis.

The bounded functional interpretation was introduced in 2005 by Oliva and
the present author. In its version for classical arithmetic, it is an
interpretation which "injects" some non set-theoretic uniformities into
Peano arithmetic. Due to its Soundness Theorem, the interpretation extracts
correct uniform bounds of AE-theorems (Proof Mining). Together with
Engrácia, we recently showed that the bounded functional interpretation also
extends to analysis.

November 6, 2009

Speaker: **
Isaac Goldbring**

Title: *
Hilbert's Fifth Problem for Local Groups*

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

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?

References

J. van Benthem, 2007, A New Modal Lindström Theorem,
"Logica Universalis" 1, 125-138.

J. van Benthem, B. ten Cate & J. Väänännen, 2007,
Lindström Theorems for
Fragments of First-order Logic, Proceedings of LICS 2007, 280-292.
To appear in "Logical Methods for Computer Science".

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.

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