# Past UCLA Logic Colloquia

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

# Logic Colloquium: 09/1/2007 - 08/31/2014

 Friday Jun 06 2014 16:00-16:50 (MS 6627) Ward Henson (University of Illinois at Urbana-Champaign) Uncountably categorical Banach space structures Abstract. The recent progress discussed in this talk concerns new examples of uncountably categorical Banach spaces (of which there have been very few previously known). This is joint work with Yves Raynaud (Univ. of Paris 6). Model theory is applied to (unit balls of) Banach spaces (and structures based on them, such as Banach algebras or Banach lattices) using the [0,1]-valued continuous version of first order logic. During the talk a sketchy and intuitive description of this logic will be given. A theory T of such structures is said to be kappa-categorical} if $T$ has a unique model of density kappa. Work of Ben Yaacov and Shelah-Usvyatsov shows that Morley's Theorem holds in this context: if T has a countable signature and is kappa-categorical for some uncountable kappa, then T is \kappa-categorical for all uncountable kappa. Known examples of uncountably categorical such structures (including the new ones) are closely related to Hilbert space. After the speaker called attention to this phenomenon, Shelah and Usvyatsov investigated it and proved a remarkable result: if M is a nonseparable Banach space structure (with countable signature) whose theory is uncountably categorical, then M is prime over a Morley sequence that is an orthonormal Hilbert basis of length equal to the density of M. There is a wide gap between this result and verified examples of uncountably categorical Banach spaces, which leads to the question: can a stronger such result be proved, in which the connection to Hilbert space structure is clearly expressed in the geometric language of functional analysis? Here the ultimate goal would be to prove analogues for Banach space structures (or even for general metric structures) of the Baldwin-Lachlan Theorems.Hide Friday May 23 2014 16:00-16:50 (MS 6627) Richard Shore (Cornell University) The Strength of Determinacy and Turing Determinacy within Second Order Arithmetic Abstract. We analyze the strength of standard Determinacy principles as well as ones for Turing Determinacy that are provable in (subsystems of) second order arithmetic (equivalently ZFC^-). These are all at low levels of the arithmetic hierarchy. We consider three notions of strength. The first is in the sense of reverse mathematics, which asks what axioms (e.g. comprehension for Pi^1_n formulas) are needed to prove the principles. The second is more traditionally proof theoretic in that we compare principles in terms of consistency strength. The third is recursion or set theoretic in that we want to determine the existence of which ordinals (or better levels of the constructible universe L) are implied by these principles. Here the measure is in terms of levels of admissibility (in replacement) or nonprojectability (in comprehension axioms). This is joint work with Antonio Montalbán. The limits of determinacy in second order arithmetic, Proceedings of the London Mathematical Society 104 (3) (2012), 223-252. The Limits of Determinacy in Second Order Arithmetic: Consistency andComplexity Strength, Israel Journal of Mathematics, to appear. The Strength of Turing Determinacy within Second Order Arithmetic, to appear. All are available at http://www.math.cornell.edu/~shore/papers.htmlHide Friday May 09 2014 16:00-16:50 (MS 6627) Rahim Moosa (University of Waterloo) The Canonical Base Property and the Zilber Dichotomy Revisited Abstract. The truth of the Zilber dichotomy in several first-order theories of fields with additional operators was behind Hrushovski's dramatic application of model theory to diophantine geometry in the nineties. About ten years ago, abstracting from a theorem in complex-analytic geometry, Pillay introduced a new model-theoretic condition now called the canonical base property (CBP). This condition provides a direct proof of the Zilber dichotomy in various contexts, and has other strong geometric consequences. What seems to be required in establishing the CBP in any given situation is an appropriate notion of "jet space". This talk will be a largely expository introduction to, and overview of, the subject.Hide Friday Apr 25 2014 16:00-16:50 (MS 6627) James Cummings (Carnegie Mellon University) Forcing at successors of singular cardinals Abstract. Many problems about structures on a regular cardinal become especially hard when that cardinal is the successor of a singular cardinal. We will discuss this phenomenon, with a particular focus on the question of how to prove consistency results.Hide Friday Apr 11 2014 16:00-16:50 (MS 6627) Boris Zilber (Oxford University) Schemes - structures duality in geometry and logic Abstract. The well-known duality of classical algebraic geometry between affine varieties and their co-ordinate algebras has a perfect analogue in the theory of commutative C^*-algebras, which can be seen by the Gel'fand-Naimark theorem as the algebras of continuous complex-valued functions on a compact Hausdorff space. In modern geometry and physics one deals with much more complex generalisations of co-ordinate algebras, such as schemes, stacks and non-commutative C^*-algebras, where a geometric counterpart is no longer readily available and in many cases is believed impossible. We will discuss a model-theoretic project which challenges this point of view.Hide Friday Mar 07 2014 16:00-16:50 (MS 6627) Martin Hils (University of Paris 7) Valued difference fields and NTP2 Abstract. There are interesting examples of algebraic structures with some kind oftame' model-theoretic behaviour whose theory is neither simple nor NIP. The valued difference field given by the non-standard Frobenius automorphism acting on an algebraically closed valued field is such a structure. Theories without the tree property of the second kind, i.e. NTP2 theories, generalise both simple and NIP theories, and, among other things, forking has been shown to behave well in this context. It turns out that certain valued difference fields are NTP2, in particular the non-standard Frobenius example mentioned above. (Joint work with Artem Chernikov.)Hide Friday Feb 21 2014 16:00-16:50 (MS 6627) Itay Neeman (UCLA) Higher analogues of properness Abstract. Forcing axioms are strengthenings of the Baire category theorem that allow meeting a prescribed number of dense sets with filters in prescribed classes of partial orders. For example Martin's Axiom (MA) for $\kappa$ involves meeting $\kappa$ dense sets in the class of partial orders with no uncountable antichains. Another example is the Proper Forcing Axiom (PFA) which involves meeting $\aleph_1$ dense sets in the class of proper partial orders. PFA was developed in the early 1980s and has been incredibly useful, both as a starting point for consistency proofs that would otherwise require forcing iterations, and as an axiom leading to set theoretic structure theorems. In contrast with MA where $\kappa$ can be arbitrary, PFA cannot be strengthened to allow meeting more than $\aleph_1$ dense sets. However recent work of Neeman shows that there are analogues of PFA which do involve meeting more than $\aleph_1$ dense sets. The goal in developing these analogues is to obtain generalizations to higher cardinals of applications of PFA. We describe some of the analogues in the talk, and some applications that have been obtained so far.Hide Friday Feb 07 2014 16:00-16:50 (MS 6627) Spencer Unger (UCLA) Successive cardinals with the tree property Abstract. The tree property arises as the generalization of Konig's infinity lemma to an uncountable cardinal. The existence of an uncountable cardinal with the tree property has axiomatic strength beyond the axioms of ZFC. Indeed a theorem of Mitchell shows that the theory ZFC + omega_2 has the tree property" is consistent if and only if the theory ZFC + There is a weakly compact cardinal" is consistent. In the context of Mitchell's theorem, we can ask an old question in set theory: Is it consistent that every regular cardinal greater than aleph_1 has the tree property? In this talk we will survey the best known partial results towards a positive answer to this question.Hide Friday Jan 24 2014 16:00-16:50 (MS 6627) Philipp Hieronymi (University of Illinois at Urbana-Champaign) Büchi, Cantor and Diophantus of Alexandria Abstract. I will give a progress report on the following two problems I have been working on for a while now: 1) finding a Cantor set C such that the expansion of the real field by C is model theoretically tame, 2) understanding the expansion of the ordered additive group of real numbers by two predicates, one for Z and one for aZ, where Z is the set of integers and a is an irrational number. In particular, their connection to Büchi's theorem on the monadic second order theory of one successor will be discussed.Hide Friday Jan 10 2014 16:00-16:50 (MS 6627) Dima Sinapova (University of Illinois, Chicago) Square properties for successors of singular cardinals Abstract. The square property was isolated by Jensen in his fine structure analysis of L. It is an "incompacness" property, that holds in canonical inner models. Square at $\kappa$ states that there is a coherent sequence of closed unbounded subsets singularizing points $\alpha<\kappa^+$. There are various weakenings of this principle by allowing multiple guesses for each club. How much a given model satisfies square principles serves as a measure how far this model is from a canonical inner model. It is difficult to avoid the weaker square principles at successors of singulars. Doing so requires large cardinals. It is especially difficult to obtain these failures while also violating the Singular Cardinal Hypothesis (SCH). We will investigate the relationship between square properties and not SCH. Violating SCH is done via Prikry type forcing. We will discuss the impact of these type of forcings on square properties. Time permitting, we will focus on models where SCH fails at $\aleph_\omega$ and models when SCH fails at $\kappa$ while GCH holds below $\kappa$.Hide Friday Dec 06 2013 16:00-17:00 (MS 6627) Asger Tornquist (University of Copenhagen) No mad families in Solovay's model Abstract. In a 1967 paper, Mathias showed that there are no analytic infinite maximal almost disjoint (mad) families, and asked if there are infinite mad families in Solovay's model. Recently, I have found a completely elementary proof of Mathias' theorem using an ordinal analysis/derivative argument. This argument can be adapted to work under the following general assumptions: (1) That all uncountable sets of reals contain a perfect subset, and (2) that an apparent strengthening of the Open Colouring Axiom, called $OCA_\infty$, which was proposed by Ilijas Farah, holds. Since $OCA_\infty$ holds in Solovay's model, this then answers Mathias' question. The talk will focus on this result, but if time allows, I will also discuss a more general approach along these lines that allow us to answer a number of related questions, e.g., to show that there are no analytic maximal eventually different families of functions from $\omega$ to $\omega$.Hide Friday Nov 22 2013 16:00-17:00 (MS 6627) John R. Steel (University of California, Berkeley) Some recent results in inner model theory Abstract. We shall describe some recent work that extends our methods for constructing canonical inner models satisfying large cardinal hypotheses. As applications, one obtains some new consistency strength lower bounds.Hide Friday Nov 08 2013 16:00-17:00 (MS 6627) Alexander S. Kechris (California Institute of Technology) Topological dynamics and ergodic theory of automorphism groups of countable structures Abstract. I will discuss some aspects of the topological dynamics and ergodic theory of automorphism groups of countable first-order structures and their connections with logic, finite combinatorics and probability theory. This is joint work with Omer Angel and Russell Lyons.Hide Friday Oct 25 2013 16:00-17:00 (MS 6627) Damir Dzhafarov (University of Connecticut) New directions in reverse mathematics Abstract. Mathematics today benefits from having "firm foundations", by which we usually mean a system of axioms sufficient to prove the theorems we care about. But given a particular theorem, can we specify precisely which axioms are needed to derive it? This is a natural question, and also an ancient one: over 2000 years ago, the Greek mathematicians were asking it about Euclid's geometry. Reverse mathematics provides a modern approach to this kind of question. A striking fact repeatedly demonstrated in this area is that the vast majority of mathematical propositions can be classified into just five main types, according to which set-existence axioms are needed to carry out their proofs. But more recently, a growing number of principles falling outside this classification have emerged, whose logical strength is more difficult to understand. These turn out to include many important mathematical results, such as various combinatorial problems related to Ramsey's theorem, and several set-theoretic equivalents of the axiom of choice. I will discuss some of these "irregular" principles, and some new approaches that have arisen from trying to understand why their strength is so different from that of most other theorems. In particular, this investigation reveals new connections between different mathematical areas, and exposes the rich and complex combinatorial and algorithmic structure underlying mathematics as a whole.Hide Friday Oct 11 2013 16:00-17:00 (MS 6627) Theodore A. Slaman (University of California, Berkeley) On normal numbers Abstract. A real number is simply normal in base b if in its base-b expansion each digit appears with asymptotic frequency 1/b. It is normal in base b if it is simply normal in all powers of b, and absolutely normal if it is simply normal in every integer base. By a theorem of E. Borel, almost every real number is absolutely normal. We will present three main results. We will give an efficient algorithm, which runs in nearly quadratic time, to compute the binary expansion of an absolutely normal number. We will demonstrate the full logical independence between normality in one base and another. We will give a necessary and sufficient condition on a set of natural numbers M for there to exist a real number X such that X is simply normal to base b if and only if b is an element of M.Hide Friday Sep 27 2013 16:00-17:00 (MS 6627) Isaac Goldbring (University of Illinois at Chicago) A survey of the model theory of tracial von Neumann algebras Abstract. Von Neumann algebras are certain algebras of bounded operators on Hilbert spaces. In this talk I will survey some of the model theoretic results about (tracial) von Neumann algebras, focusing mainly on (in)stability, quantifier-complexity, and decidability. No prior knowledge of von Neumann algebras will be necessary. Some of the work presented is joint with Ilijas Farah, Bradd Hart, David Sherman, and Thomas Sinclair.Hide Friday May 17 2013 16:00-17:00 (MS 6627) Maryanthe Malliaris (University of Chicago) Comparing the complexity of unstable theories Abstract. Keisler's order is a large scale program of understanding model-theoretic structure from asymptotic (ultrapower) points of view. The talk will explain some very recent progress on Keisler's order, consequences for the classification of unstable theories, and related theorems on Szemeredi regularity and set theory/general topology: in particular, Malliaris and Shelah recently solved the oldest problem on cardinal invariants of the continuum, whether "p=t", using model-theoretic tools developed for the study of Keisler's order. I will assume basic familiarity with ultraproducts, Los's theorem, and saturation, and plan to give most other relevant definitions. Papers mentioned in the talk are available at http://math.uchicago.edu/~mem.Hide Friday May 10 2013 16:00-17:00 (MS 6627) D.H.J. de Jongh (University of Amsterdam) Heyting Arithmetic and Intermediate Logic Abstract. It is proved that all intermediate logics L(propositional logics between intuitionistic logic IPC and classical logic), that have the finite model property have the following maximality property: The logic of the propositional schemes valid in Heyting Arithmetic plus L is exactly L. This is generalization of the old theorem that the logic of Heyting Arithmetic is exactly intuitionistic logic. This work was in cooperation with Rineke Verbrugge and Albert Visser.Hide Friday Apr 26 2013 16:00-17:00 (MS 6627) R. Daniel Mauldin (University of North Texas) Steinhaus' tiling problem Abstract. In the 1950's Steinhaus posed the following problem: Is there a set S in R^2 which meets each isometric copy of Z^2 in exactly one point? I will describe some aspects of the positive solution that Steve Jackson and myself gave and discuss a number of unsolved related problems.Hide Friday Apr 12 2013 16:00-17:00 (MS 6627) Mingzhong Cai (University of Wisconsin) Recursive functions and provability degrees Abstract. Given a recursive function f (with a fixed algorithm), the totality of f is the Pi_2 sentence that this function f is total. Note that the totality of f depends on the algorithm for computing f. Given two recursive functions f and g with fixed algorithms, we say f is provably reducible to g if the totality of g proves the totality of f over some base theory T. Now we can consider the degree structure on recursive functions modulo provable equivalence, and investigate this proof-theoretic degree structure by recursion-theoretic methods and ideas. This is essentially Lindenbaum algebra restricted on true Pi_2 sentences, and there are two natural jump-like operators. I will present a few sample results, including density theorem, jump inversion theorem and high-low hierarchy. This is joint work with Andrews, Diamondstone, Lempp and Miller.Hide Friday Mar 15 2013 16:00-17:00 (MS 6627) Trevor Wilson (UC Irvine) A Determinacy transfer principle Abstract. The Axiom of Determinacy, AD, asserts that infinitely long two-player games on the integers are determined. Although AD contradicts the Axiom of Choice, many strong hypotheses such as large cardinal axioms imply that AD holds in some realm of "nice" sets; for example, the projective sets or the sets of reals in the inner model L(R). In some cases showing that more games are determined requires a stronger hypotheses, whereas in other cases one can get extra determinacy "for free." The latter type of result, sometimes called a determinacy transfer principle, was used by Kechris and Woodin to prove that every set of reals in L(R) is determined from a seemingly lesser determinacy hypothesis. We introduce a general determinacy transfer principle and use it to give a new proof of Woodin's theorem that given two "divergent" models of AD, their intersection satisfies a strong form of AD (namely determinacy for games on the reals.)Hide Friday Feb 15 2013 16:00-17:00 (MS 6627) Sean Walsh (UC Irvine) Basic Law V: Standard and Non-standard Models Abstract. Basic Law V was one of the crucial axioms of Frege's ultimately inconsistent system in Grundgesetze. Roughly, Basic Law V postulates an injection from the second-order part of a structure to the first-order part. In recent decades, the work of Parsons, Ferreira, Wehmeier and others has shown Basic Law V is consistent with more limited amounts of comprehension. In this talk, we describe some new model constructions of Basic Law V. On the one hand, Basic Law V allows one to define a membership relation, and so here it's natural to look for models amongst small fragments of the constructible hierarchy. On the other hand, by modifying the Ferreira-Wehmeier construction, one can ascertain which kinds of fields are compatible with the structure of Basic Law V, and as some such fields are so well-understood one is able to thus deduce that various natural statements about the induced membership relation are not provable from Basic Law V.Hide Friday Feb 08 2013 16:00-17:00 (MS 6627) Dana Bartosova (University of Toronto) Ramsey property for Boolean algebras with ideals and the Katowice problem Abstract. I will give an introduction to the theory connecting topological dynamics, Ramsey theory and model theory of countable structures developed by Kechris, Pestov and Todorcevic. I will mention how their results can be extended to uncountable structures, in particular to the Boolean algebra of all subsets of an uncountable set modulo the ideal of finite sets. This requires a generalization of the Dual Ramsey Theorem to classes of finite Boolean algebras with distinguished ideals. Considering Fraisse limits of these classes provides results in dynamics of the group of homeomorphisms of the Cantor set.Hide Friday Jan 11 2013 16:00-17:00 (MS 6627) Edward Keenan (UCLA) Boolean Type Theory for Natural Language (Eliminating the Universe) Abstract. We linguistically motivate an extensional type theory for natural language which replaces the unstructured universe of entities in which singular terms denote by a booleanly structured set P of properties in which common nouns (e.g. doctor) and one place predicates denote. Sentences denote in 2 = {0,1} as usual. Denotations of singular terms (e.g. John, individual constants) are booleanly defined in terms of properties and truth values. The full set of possible denotation sets is the closure of {P,2} under the formation of function spaces and finite products. All denotation sets are provably complete atomic boolean lattices. This boolean streamlining is shown to be linguistically enlightening and to justify the same valid arguments as classical type theory. Then we generalize our boolean type theory by relaxing the atomicity requirement on P in order to provide denotations for a class of intensional adjectives (skillful) and quantifiers (enough, too many). (If the surgeons and the lawyers happen to be the same individuals in some model it does not follow that the skillful surgeons and the skillful lawyers are the same; also it may be that not enough doctors attended some meeting even though enough (even too many) lawyers did). Our generalized boolean type theory makes extensive use of complete but non-atomic boolean lattices. We invoke no semantic novelties like "possible worlds" or structured meanings. Several open questions remain concerning generalizing boolean types to new categories of expressions (including sentences!) and the uniformity of intensions across categories. Do not modifier categories (adjectives, adverbs) behave differently from predicate-argument categories? Within a category different subclasses of adjectives seem to make different contributions to the intensions of the common noun phrases they build.Hide Friday Dec 07 2012 16:00-17:00 (MS 6627) Andrew Marks (Caltech) Structure theorems for treeable countable Borel equivalence relations Abstract. We use Borel determinacy to prove some structure theorems for treeable countable Borel equivalence relations. We show that a smooth disjoint union of continuum many non-universal treeable Borel equivalence relations is not universal treeable, that every universal treeable equivalence relation achieves its universality on a nullset, and that universality for Borel reductions and universality for Borel embeddings coincide for the class of treeable equivalence relations. Our results follow from the existence of a countably complete ultrafilter on the invariant Borel sets of a universal treeable equivalence relation for which every element of the ultrafilter is universal. Our results also generalize to some other universal K-structurable equivalence relations.Hide Friday Nov 30 2012 16:00-17:00 (MS 6627) Zlatan Damnjanovic (USC) Concatenation as a basis for set theory Abstract. We describe a direct and natural interpretation of Adjunctive Set Theory with Extensionality (AST+EXT) in a weak elementary theory of concatenation. As a consequence we establish mutual interpretability of AST+EXT and Robinson arithmetic, Q.Hide Friday Nov 09 2012 16:00-17:00 (MS 6627) James Freitag (UC Berkeley) Almost simple differential algebraic groups Abstract. We will begin by describing the setting and explaining what a differential algebraic group is and why they are of interest. After this, we will discuss a series of problems which were revealed when Cassidy and Singer proved a Jordan-Holder type theorem for differential algebraic groups. Subsequent work using model theoretic techniques and Steinberg groups has lead to a strong classification of noncommutative almost simple groups. If time allows, we will explain generalizations of this work to the superstable setting along with its relationship to Cherlin's main conjecture.Hide Friday Nov 02 2012 16:00-17:00 (MS 6627) Aleksandra Kwiatkowska (UCLA) Boolean actions of groups of isometries Abstract. I will discuss the following result: every Boolean action of an isometry group of a separable locally compact space has a point realization. This generalizes both a classical result due to Mackey for separable locally compact groups and a recent result due to Glasner, Tsirelson, and Weiss for non-archimedean Polish groups, and it covers new interesting examples. The proof of this result relies on a new characterization of groups of isometries of separable locally compact spaces. The solution to the Hilbert's fifth problem plays a crucial role in our investigations. This is a joint work with Slawek Solecki.Hide Friday Oct 19 2012 16:00-17:00 (MS 6627) Jay Williams (Caltech) Group embeddability and countable Borel quasi-orders Abstract. Descriptive set theory gives us a framework for analyzing the relative complexity of quasi-orders (i.e. reflexive transitive relations) arising in many areas of mathematics, such as Turing reducibility of sets of natural numbers or embeddability of countable groups, using the notion of a Borel reduction. I will discuss a special class of quasi-orders, the countable Borel quasi-orders, which include embeddability of finitely-generated groups. I will present a proof that embeddability of countable groups is a universal analytic quasi-order, and discuss how the ideas work in the finitely-generated case.Hide Friday Jun 08 2012 16:00-17:00 (MS 6627) Enrique Casanovas (University of Barcelona) Forking and Stable Types Abstract. I will discuss the notion of forking and its meaning in unstable theories. Next I will show how to localize to partial types properties of theories like stability, simplicity and nip. Finally, I will present some new results (obtained jointly with H. Adler) on preservation of stability of complete types under nonforking restrictions, generalizing previous theorems of A. Hasson and A. Onshuus.Hide Friday May 25 2012 16:00-17:00 (MS 6627) Simon Thomas (Rutgers University) A Descriptive View of Unitary Group Representations Abstract. Abstract: In this talk, I will discuss an ongoing attempt to understand the unitary representations of discrete countable groups from the point of view of descriptive set theory. In particular, I will explain why there are precisely two unitary duals of countably infinite amenable groups up to Borel isomorphism.Hide Friday Apr 20 2012 16:00-17:00 (MS 6627) Christophe Weiss (UC Irvine) Large Cardinal Axioms Seen Combinatorially Abstract. We will discuss certain large cardinal axioms that play an important role in contemporary set theory. We will then show how these can be seen as natural generalizations of smaller large cardinal axioms, and how this allows us to even see small cardinals as very large ones.Hide Friday Apr 13 2012 16:00-17:00 (MS 6627) David Marker (University of Illinois Chicago) Integer Parts of Real Closed Fields Abstract. An integer part of a real closed field is a discretely ordered subring where every element of the field is within distance one of an element of the ring. Sheperdson first noticed that integer parts are models of a weak fragment of arithmetic. Recently, D'Aquino, Knight and Starchenko studied the real closed fields where the integer part is a model of Peano Arithmentic and gave a complete classification in the countable case. We will survey the subject and examine some phenomena in the uncountable case.Hide Friday Apr 06 2012 16:00-17:00 (MS 6627) Ryan Williams (Stanford University) Lower Bounds in Complexity Theory via Diagonalization Abstract. The general feeling in complexity theory has been that the method of diagonalization would not be powerful enough to prove strong lower bounds, i.e., separations of complexity classes. Recent work has shown that diagonalization can be fruitfully combined with other ideas to prove interesting lower bounds, such as time-space lower bounds for the satisfiability problem and circuit size lower bounds for nondeterministic exponential time. I will survey the general ideas and thought processes that are used to prove these lower bounds. Ultimately the techniques are algorithmic in nature: one assumes that too-good-to-be-true algorithms exist, and through algorithmic thinking, one eventually derives a contradiction to the assumption via diagonalization.Hide Friday Mar 02 2012 16:00-17:00 (MS 6627) Benjamin Miller (University of Muenster) Bases, non-hyperfiniteness, and rigidity Abstract. By the Glimm-Effros dichotomy, every non-smooth countable Borel equivalence relation contains a copy of the non-smooth hyperfinite Borel equivalence relation. We will discuss how local rigidity properties of the usual action of SL_2(Z) on R^2 can be used to rule out analogous results for the class of non-measure-hyperfinite countable Borel equivalence relations. I hope to make the talk accessible to a broad audience.Hide Friday Feb 24 2012 16:00-17:00 (MS 6627) Stevo Todorcevic (University of Toronto and University of Paris VII) A set-theoretic analysis of the unconditional basic sequence problem Abstract. We investigate the density requirement on a given normed space X that guarantees the existence of an infinite unconditional basis sequence of elements of $X.$ This is a joint work with J. Lopez-Abad.Hide Friday Feb 10 2012 16:00-17:00 (MS 6627) Asger Tornquist (University of Copenhagen) The conjugacy relation on unitary representations Abstract. In a paper from 1965, Effros asked if the conjugacy relation on unitary representations of a countable discrete group (or, more generally, a locally compact second countable group) on a separable Hilbert space is a Borel equivalence relation. In this talk, I will show that the answer is yes. This is joint work with Greg Hjorth, completed in December 2010.Hide Friday Jan 13 2012 16:00-17:00 (MS 6627) Uri Andrews (University of Wisconsin) Amalgamation constructions and degrees of categorical theories with recursive models Abstract. The Hrushovski amalgamation method was originally built to generate theories with unexpected geometric properties. I will present how the Hrushovski amalgamation construction can be used to construct theories with strange recursion theoretic properties as well, answering problems in recursive model theory. In particular, we will focus on characterizing the degrees of strongly minimal and countably categorical theories all of whose countable models are recursive.Hide Friday Nov 04 2011 16:00-16:50 (MS 6627) Isaac Goldbring (UCLA) Nonstandard hulls and infinite-dimensional Lie theory Abstract. The notion of a nonstandard hull of a normed space has proven very useful in applications of nonstandard analysis to Banach space theory. Given a normed space E with nonstandard extension E*, the nonstandard hull of E is the normed space of "finite'' elements of E* quotiented by the subspace of "infinitesimal" elements of E*. If E happened to be a Banach-Lie algebra, that is, a Banach space equipped with a continuous Lie bracket, then the nonstandard hull of E is naturally a Banach-Lie algebra. Pestov used this construction to produce nonstandard hulls of Banach-Lie groups, which he then used to derive a very useful local criterion for the enlargeability of Banach-Lie algebras. In this talk, I will explain all of the relevant nonstandard analysis and Lie theory to understand the aforementioned construction and results of Pestov. Then I will discuss my own extension of Pestov's results to the wider class of locally exponential Lie groups and algebras.Hide Friday Oct 28 2011 16:00-16:50 (MS 6627) Leo Harrington (UC Berkeley) Is there a Philosophical View Already in Mathematical Logic? Abstract. This talk will suggest that a certain "view", readily available from basic ingredients of mathematical logic, bears a resemblance with views found respectively in the philosophers Parmenides, Hegel, and Heidegger. And this talk will attempt to indicate the possibility that, while staying inside mathematical logic, this view can be elaborated to maintain such a resemblance with a philosophical view found in common in the works ofthese philosophers.Hide Friday Oct 14 2011 16:00-16:50 (MS 6627) Theodore Slaman (UC Berkeley) The First Order Consequences of the Existence of an Infinite Random Sequence Abstract. We will discuss the question, "What first order statements follow from the existence of an infinite random sequence by effective means?" The answer depends on the degree of randomness in the infinite source. In one case, it isolates a mysterious subtheory of arithmetic strictly between $\Sigma_1$-Induction and $\Sigma_2$-Bounding.Hide Friday Sep 30 2011 16:00-16:50 (MS 6627) Sam Buss (UC San Diego) Bounding time-space lower bounds for satisfiability algorithms. Abstract. The NP-complete problem of Satisfiability is one of the central decision problems studied computational complexity. In this talk, we discuss alternation trading proofs that give lower bounds for sublinear space algorithms for Satisfiability. Ryan Williams proved that any deterministic algorithm for Satisfiability that uses space n^{0{1}} must have run time of at least n^c for c equal to 2\cos(\pi/7), and this result applies to many other NP complete problems. This talk discusses this result, plus how to prove that this value for c is the best that can be obtained with currently known techniques. We also present similar results for Satisfiability algorithms that use space n^e for constant values e<1. (Joint work with R. Williams.)Hide Friday Jun 10 2011 16:00-16:50 (MS 6627) Todor Tsankov (University of Paris 7) Generic Representations of Abelian Groups Friday Jun 03 2011 16:00-16:50 (MS 6627) Matthew Foreman (U.C. Irvine) Classifying Measure Preserving Diffeomorphisms of the Torus Abstract. The statistical behavior of deterministic dynamical systems can be completely random. The ergodic theorem tells us that the statistical behavior of a system carrying an invariant ergodic measure is captured by the isomorphism class of that measure. Motivated by this type of phenomenon, in 1932 von Neumann proposed the program of classifying the ergodic measure preserving systems. This talk discuss applications of the tools of descriptive set theory to show that this program is impossible. In earlier joint work with Weiss, it was shown that the isomorphism relation is "turbulent" and hence no generic class can be reduced to an S-infinity action. With Rudolph and Weiss it was shown that the isomorphism relation is a complete analytic set. But what about concrete systems: C-infinity measure preserving diffeomorphisms of the torus? Recent work with Weiss extends these results to such transformations. Finally a very recent result shows that the "graph-isomorphism problem" can be reduced to isomorphism of measure preserving diffeomorphisms. As a corollary the isomorphism relation is complete for S-infinity actions.Hide Friday May 27 2011 16:00-16:50 (MS 6627) Sam Sanders (Ghent University) Reverse Mathematics & Non-Standard Analysis: Why some theorems are more equal than others. Abstract. Reverse Mathematics is a program in foundations of mathematics initiated by Friedman ([1, 2]) and developed extensively by Simpson ([4]). Its aim is to determine which minimal axioms prove theorems of ordinary mathematics. Nonstandard Analysis plays an important role in this program ([3, 5]). We consider Reverse Mathematics where equality is replaced by the predicate $\approx$, i.e. equality up to infinitesimals from Nonstandard Analysis. A copy' of Reverse Mathematics for WKL$_0$ and ACA$_0$ is obtained in a weak system of Nonstandard Analysis. We consider possible connections with constructive analysis and recursion theory. Our results also have implications for the Philosophy of Science. In particular, we show how the very nature of Mathematics in Physics implies that real numbers are not needed in Physics (cf. the famous Quine-Putnam indispensability argument). [1] Harvey Friedman, Some systems of second order arithmetic and their use, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 1, Canad. Math. Congress, Montreal, Que., 1975, 235-242. [2] , Systems of second order arithmetic with restricted induction, I & II (Abstracts), Journal of Symbolic Logic 41 (1976), 557-559. [3] H. Jerome Keisler, Nonstandard arithmetic and reverse mathematics, Bull. Symbolic Logic 12 (2006), no. 1, 100-125. [4] Stephen G. Simpson, Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. [5] Kazuyuki Tanaka, The self-embedding theorem of WKL0 and a non-standard method, Ann. Pure Appl. Logic 84 (1997), no. 1, 41-49.Hide Friday May 13 2011 16:00-17:00 (MS 6627) John Steel (U.C. Berkeley) The Triple Helix Abstract. Many different foundational theories have been developed and studied by set theorists. Remarkably, no divergence at the level of statements about "concrete" objects (for example, natural numbers) has emerged, and indeed, these theories are linearly ordered by the inclusion order on their sets of arithmetic consequences. The place of a theory in this order is known as its consistency strength. Our methods for comparing the consistency strengths of set theories center on three intertwined canonical hierarchies of sets. In this talk we shall describe those three hierarchies in very general terms. We shall focus on the philosophical significance of the results and open questions concerning them.Hide Friday Apr 29 2011 16:00-17:00 (MS 6627) Balder ten Cate (U.C. Santa Cruz) Unary Negation Abstract. We study fragments of first-order logic and of least fixed point logic that allow only unary negation: negation of formulas with at most one free variable. These logics generalize many interesting known formalisms, including modal logic and the mu-calculus, as well as conjunctive queries and monatic Datalog. We show that satisfiability and finite satisfiability are decidable for both fragments, and we pinpoint the complexity of of satisfiability, finite satisfiability, and model checking. We also show that the unary negation fragment of first-order logic is model-theoretically very well behaved. In particular, it enjoys Craig interpolation and the Beth property. Based on joint work with Luc Segoufin (STACS 2011).Hide Friday Apr 08 2011 04:00-04:50 (ms 6627) Itay Neeman (UCLA) Forcing with Side Conditions Abstract. Iterated forcing constructions are a crucial tool in consistency proofs, and their use typically requires preservation theorems showing that the iteration does not destroy cardinals. General preservation theorems exist for several classes of forcing posets, most notably the classes of c.c.c. posets, proper posets, and semi-proper posets. Each of these theorems, used with a universal iteration, leads to a consistency proof for a forcing axiom stating that the universe is to some extent saturated under forcing with posets in the class. These axioms, most notably Martin's Axiom (c.c.c. posets), the Proper Forcing Axiom, and the Semi-Proper Forcing Axiom, are in turn used as center points for many consistency proofs. While c.c.c. posets preserve all cardinals, proper posets need only preserve $\omega_1$. This limits the level of saturation possible in the Proper Forcing Axiom. When the axiom was first introduced, some 30 years ago, it was expected that there would be a parallel of the axiom and the iteration theorem for proper posets, that works for an analogous class of posets preserving more cardinals, for example preserving both $\omega_1$ and $\omega_2$. But the naive attempt to obtain such an analog fails, and no analog had been obtained. In the talk I will show how to obtain an analog of the Proper Forcing Axiom for posets that preserve both $\omega_1$ and $\omega_2$. The analog requires a new iteration method, that combines standard iterations with uses of models as side conditions.Hide Friday Mar 04 2011 16:00-17:00 (MS 6627) Henry Wilton (USC) Conjugacy Classes of Solutions to Systems of Equations over Hyperbolic Groups Abstract. I will describe an algorithm that determines whether or not a given system of equations and inequations over a torsion-free word-hyperbolic group has infinitely many conjugacy classes of solutions. One application is to enumerate immutable' sub-groups.Hide Friday Feb 18 2011 16:00-17:00 (MS 6627) Alice Medvedev (U.C. Berkeley) The Recursive Spectrum of a Strongly Minimal Modular Theory of Groups in a Finite Language Abstract. (I will define and explain "stronly minimal," "modular," "recursive spectrum," and all other frightening words.) The recursive spectrum of a fixed strongly minimal theory T is the set of integers n such that the model of T of dimension n admits a recursive presentation. How complicated can this set be? Some interesting examples can be constructed by coding complicatedness into an infinite language, or by using Hrushovski constructions. We are working towards showing that the recursive spectrum of a strongly minimal locally modular theory in a finite language must be nothing, everything, or only the prime model. The title describes the current state of this joint work with Uri Andrews.Hide Friday Jan 28 2011 16:00-17:00 (MS 6627) Kenny Easwaran (USC) The Tarski-Godel Thesis Abstract. A distinction is standardly drawn between so-called "structural" axioms (those that define a type of mathematical structure, like a group or a field) and "foundational" axioms (those like PA or ZFC that characterize some pre-existing structure). However, some mathematicians with structuralist sympathies deny that there is such a distinction and assimilate all axioms to the "structural" type. In this talk, I will consider Godel's Completeness Theorem and show that its standard interpretation depends on a non-mathematical thesis parallel to the Church-Turing thesis in computability theory. Consideration of this thesis shows that the type of structuralist view mentioned above is untenable, since it suggests that any consistent system is equally good, but says that there is no fact of the matter about whether certain systems are consistent.Hide Friday Jan 21 2011 16:00-17:00 (MS 6627) Jack Lutz (Iowa State University) The Dimensions of Individual Points in Euclidean Space Abstract. The (constructive Hausdorff) dimension of a point x in Euclidean space is the algorithmic information density of x. Roughly speaking, this is the least real number dim(x) such that r·dim(x) bits suffice to specify x on a general-purpose computer with arbitrarily high precisions 2-r. This talk will survey the development of this notion, its geometric meaning, and its role in the analysis of several classes of fractals. The results surveyed are the work of many investigators.Hide Friday Dec 03 2010 16:00-17:00 (MS 6627) Asger Tornquist (University of Vienna) Borel Reducibility and the Classification of Separable C^*-Algebras Friday Nov 19 2010 16:00-17:00 (MS 6627) Greg Hjorth (UCLA) The Fine Structure of Orbits Abstract. In the case of continuous actions of the infinite symmetric group, the Scott analysis provides a sharp analysis of the Borel Complexity of orbits. This talk will compare the relatively well understood situation of the symmetric group with the still poorly understood situation for general Polish groups.Hide Friday Nov 05 2010 16:00-17:00 (MS 6627) Matthew Foreman (U.C. Irvine) Chang's Conjecture: Generic Elementary Embeddings and Inner Models for Huge Cardinals Abstract. The lecture describes some model theoretic transfer properties on $\omega_4$ that can be proved to be between a huge cardinal and a 2-huge cardinal in consistency strengthHide Monday Sep 27 2010 16:00-16:50 (MS 5147) Anand Pillay (University of Leeds) Measures in Model Theory (NOTE: Different day) Abstract. I will discuss the extension of stability-theoretic ideas to a broader context but with measures replacing types.Hide Friday Jun 04 2010 16:00-16:50 (MS 6627) Mia Minnes (MIT/UCSD) Linear Orders -- A Case Study in Automatic Model Theory Abstract. Computable model theorists have analysed 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, homoegeneity, 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.Hide Friday May 28 2010 16:00-16:50 (MS 6627) Joel I. Friedman (U.C. Davis) Modal Platonism is a Threat to Platonism (and to its So-Called Indispensability Principle) Abstract. See: http://www.math.ucla.edu/~hbe/joel.pdfHide Friday May 21 2010 16:00-16:50 (MS 6627) Menachem Magidor (The Hebrew University of Jerusalem) Forcing Axioms and Squares Abstract. 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.Hide Friday May 07 2010 16:00-16:50 (MS 6627) Zlatan Damnjanovic (USC) From Strings to Numbers Abstract. 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$.Hide Friday Apr 30 2010 16:00-16:50 (MS 6627) Alex Usvyaov (University of Lisbon) Generic Stability and the Forking Ideal Abstract. 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 stableHide Friday Apr 09 2010 16:00-16:50 (MS 6627) Yiannis Moschovakis (UCLA) The Axiomatic Derivation of Absolute Lower Bounds Abstract. 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 $2\log(\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.Hide Friday Mar 12 2010 16:00-17:00 (MS 6627) Inessa Epstein (Caltech) Measure Preserving Group Actions and Descriptive Set Theory Abstract. 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.Hide Friday Feb 19 2010 16:00-17:00 (MS 6627) Lou van den Dries (University of Illinois) Transseries Abstract. 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 abot the real field. This is a survey of joint work with Matthhias Aschenbrenner and Joris van der HoevenHide Friday Jan 22 2010 16:00-17:00 (MS 6627) Grigor Sargsyan (UCLA) Descriptive Inner Model Theory Abstract. It is by now a well-known theorem of Martin, Steel and Woodin that if there is a measurable cardinal above omega-many Woodin cardinals then AD holds in $L(\mathbb{R})$. Since this theorem was proved, many theorems of a similar nature have appeared in set theory. For instance, Steel recently showed that PFA, the proper forcing axiom, implies that AD holds in $L(\mathbb{R})$. Many results that followed Martin-Steel-Woodin theorem, including Steel's aforementioned result used a substantial amount of inner model theory to prove that all sets in a certain "canonical" collection of sets of reals are determined. Canonical can probably be taken to be Universally Baire though it is a conjecture whether the actual definition that will be used in the talk is equivalent to Universal Baireness. At any rate, letting $\Gamma$ be this collection of canonical sets of reals, many of the theorems that have been proven after the Martin-Steel-Woodin result are about the size of $\Gamma$, and in particular, the earlier results just show that under certain hypotheses all sets of reals in $L(\mathbb{R})$ are in $\Gamma$. Descriptive inner model theory then can be defined as the the study of the properties of $\Gamma$ in various mathematically rich extensions of ZFC, using methods from inner model theory. Inner model theory enters into the study of the properties of $\Gamma$ through a conjecture known as the Mouse Set Conjecture, which allows one to translate questions about sets of reals into questions about iteration strategies for a certain kind of mice known as hod mice. In this talk, we will explain all this terminology and will outline some of the more recent theorems, including the following. Theorem (S.) If there is a Woodin limit of Woodins then there is $\Gamma^*$ which is a subset of Gamma and such that and $L(\Gamma^*, \mathbb{R})$ satisfies $AD_{\mathbb{R}}$ + $\theta$ is regular. We will also explain some applications in calibrating lower bounds of consistency strength and in the inner model problem.Hide Friday Jan 08 2010 16:00-17:00 (MS 6627) Fernando Ferreira (University of Lisbon (visiting Stanford)) Bar-Recursive Interpretations of Classical Analysis Abstract. 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.Hide Friday Nov 06 2009 16:00-17:00 (MS 6627) Isaac Goldbring (UCLA) Hilbert's Fifth Problem for Local Groups Abstract. 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.Hide Friday Oct 23 2009 16:00-17:00 (MS 6627) Wai Yan Pong (CSU, Dominguez Hills) Locally Finite Quantifier Eliminable Graphs Abstract. We classified the class of locally finite quantifier eliminable graphs in the language of distance predicates. This is a joint work with Shawn Hedman.Hide Friday Oct 09 2009 16:00-17:00 (MS 6627) Phokion G. Kolaitis (U.C. Santa Cruz and IBM Almaden Research Center) Foundations and Applications of Schema Mappings Abstract. 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.Hide Friday May 29 2009 16:00-16:50 (MS6627) Jana Marikova (University of Illinois at Urbana-Champaign) $O$-minimal Fields, Standard Part Maps and Triangulations Friday May 22 2009 16:00-16:50 (MS6627) Johan van Benthem (University of Amsterdam and Stanford University) Modal Lindstrom Theorems and Weak Abstract Model Theory Abstract. 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".Hide Friday May 08 2009 16:00-16:50 (MS6627) Paul Larson (Miami University, Ohio) Universally Measurable Sets of Reals in Generic Extensions Thursday Apr 30 2009 Logic Center Public Symposium 18:00-19:00 (Kerckhoff Hall, Charles E. Young Grand Salon) Reception Logic Center Public Symposium 17:00-18:00 (Kerckhoff Hall, Charles E. Young Grand Salon) Michael O. Rabin (Harvard University and Google Research) Novel Concepts of Proof and their Applications Abstract. Computer scientists have created over the past thirty years new revolutionary notions of mathematical proofs. The introduction of randomness created proofs that allow for a probability of error. Zero Knowledge Proofs enable a demonstration of a mathematical truth without revealing any information beyond the claimed truth. We shall also present a new practically efficient method for ZKPs and describe applications to business transactions such as the secure and secrecy preserving conduct of auctions. The talk will be self contained and readily accessible.Hide Logic Center Public Symposium 16:30-17:00 (Kerckhoff Hall, Charles E. Young Grand Salon) Tea Break Logic Center Public Symposium 15:30-16:30 (Kerckhoff Hall, Charles E. Young Grand Salon) Martin Davis (New York University) Hilbert's Tenth Problem Abstract. I will discuss various aspects of the work that led to a proof that Hilbert's Tenth Problem (Diophantine Equations) is unsolvable. The unsolvability result is a consequence of the equivalence between two notions, one from logic/computability theory, the other, from number theory. Interesting and curious applications of this equivalence will be discussed including a universal polynomial equation, a prime representing function, and Diophantine form of famous problems.Hide Logic Center Public Symposium 15:00-15:30 (Kerckhoff Hall, Charles E. Young Grand Salon) Tea Break Logic Center Public Symposium 14:00-15:00 (Kerckhoff Hall, Charles E. Young Grand Salon) Moshe Y. Vardi (Rice University) From Aristotle to the Pentium Abstract. Logic started as a branch of philosophy, going back to Greeks in the classical period. Computers are relatively young, dating back to the middle of the 20th century. This talk tells the story of logic begat computers, tracing the path from Aristotle to the Pentium. This is a story full of both intellectual drama, as well as real-life drama, with most of the characters dying young, miserably, or both.Hide Friday Apr 24 2009 16:00-16:50 (MS6627) John Harrison (Intel Corporation) Decidability and Undecidability in Theories of Real Vector Spaces Abstract. 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.Hide Friday Apr 17 2009 16:00-16:50 (MS6627) Carl Mummert (University of Michigan) Convergent and Stationary Strategies in Choquet Games Abstract. 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.Hide Friday Apr 03 2009 16:00-16:50 (MS6627) Alain Louveau (CNRS & Universite Paris 6) Some New Results about Borel Functions Abstract. 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.Hide Friday Mar 06 2009 16:00-16:50 (MS6627) Martin Dowd A Lower Bound on the Mahlo Rank of a $\Pi_1^1$-Indescribable Cardinal Abstract. 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.Hide Friday Feb 20 2009 16:00-16:50 (MS6627) Solomon Feferman (Stanford University) Conceptual Structuralism and the Continuum Abstract. 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.Hide Sunday Feb 01 2009 VIG Conference 12:10-13:00 (MS5200) Ted Slaman (U.C. Berkeley) Degree Invariant Functions VIG Conference 11:00-11:50 (MS5200) Greg Hjorth (UCLA and Melbourne) Treeable Equivalence Relations VIG Conference 10:00-10:50 (MS5200) Itay Neeman (UCLA) Steel Forcing in Reverse Mathematics Saturday Jan 31 2009 VIG Conference 16:40-17:30 (MS5200) Penelope Maddy (UC Irvine) Thin Realism VIG Conference 15:30-16:20 (MS5200) William Mitchell (University of Florida) A Perspective on Inner Model Theory VIG Conference 14:30-15:20 (MS5200) Arnold Miller (Madison) A Dedekind Finite Borel Set VIG Conference 11:50-12:20 (MS5200) Grigor Sargsyan (UC Berkeley) Hods of Models of Determinacy VIG Conference 11:00-11:30 (MS5200) Dilip Raghavan (University of Toronto) P-Ideal Dichotomy and the Structure of Wellfounded Lattices VIG Conference 10:00-10:50 (MS5200) W. Hugh Woodin (UC Berkeley) The Inner Model Problem for One Supercompact Cardinal and the Search for the Ultimate Version of L Friday Jan 30 2009 VIG Conference 16:10-17:00 (Boelter 3400) Ben Miller (UCLA) Forceless, Ineffective, Powerless Proofs of Descriptive Set-Theoretic Dichotomy Theorems VIG Conference 15:30-16:00 (Boelter 3400) Inessa Epstein (Caltech) Equivalence Relations with Infinitely Many Ends and Percolation VIG Conference (See http:http://www.math.ucla.edu/~ineeman/Conf/SteelVIG.htm) 14:20-15:10 (Boelter 3400) Steve Simpson (Penn State University) Mass Problems Friday Jan 16 2009 16:00-16:50 (MS6627) Sean Cox (U.C. Irvine) Consistency Strength of Combinatorial Properties at Small Regular Cardinals Abstract. 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.Hide Friday Nov 21 2008 16:00-16:50 (MS 6627) Henry Towsner (MSRI and UCLA) Proof Theory and the Correspondence Between Ergodic Theory and Additive Combinatorics Abstract. 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.Hide Friday Nov 07 2008 16:00-16:50 (MS 6627) Joseph Flenner (U.C. Berkeley) The Relative Structure of Valued Fields Abstract. 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.Hide Friday Oct 24 2008 16:00-16:50 (MS6627) Alex Usvyatsov (UCLA) Minimal Stable Types Over Banach Spaces Abstract. 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).Hide Friday Oct 10 2008 16:00-16:50 (MS 6627) Benjamin Miller Forceless, Ineffective, Powerless Proofs and Generalizations of Descriptive Set-Theoretic Dichotomy Theorems Abstract. 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.Hide Friday May 30 2008 16:00-16:50 (MS6627) Eric Pacuit (Stanford University) The Tree of Knowledge in Action Abstract. 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.Hide Friday May 23 2008 16:00-16:50 (MS6627) Simon Thomas (Rutgers University) A Remark on the Higman-Neumann-Neumann Embedding Theorem Abstract. 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$.Hide Friday May 16 2008 16:00-16:50 (MS6627) Aldo Antonelli (U.C.  Irvine) Abstraction Principles in First-Order Arithmetic Abstract. 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.Hide Friday May 02 2008 16:00-16:50 (MS6627) Salma Kuhlmann (University of Saskatchewan) Fragments of Peano Arithmetic and Embeddings of Valued Fields into Power Series Fields Friday Apr 25 2008 16:00-16:50 (MS6627) Krzysztof Krupinski (University of Wrochlaw and University of Illinois) Model Theoretic Ideas in Some Topological Contexts Abstract. 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.Hide Friday Mar 14 2008 16:00-16:50 (MS6627) Su Gao (University of North Texas) A Coloring Property for Countable Groups Abstract. 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 will show that every countable group has this coloring property. This is joint work with Steve Jackson and Brandon Seward.Hide Friday Feb 15 2008 16:00-16:50 (MS6627) Joshua Sack (CSU, Long Beach) On Temporal Dynamic Epistemic Logic Abstract. 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.Hide Friday Jan 18 2008 16:00-16:50 (MS6627) Thomas Scanlon (UC Berkeley) Theories of Fields Abstract. 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.Hide Friday Nov 30 2007 16:00-16:50 (MS6627) Marcus Kracht (Linguistics Dept., UCLA) The Combinatorics of Interpreted Languages Abstract. 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.Hide Friday Nov 16 2007 16:00-16:50 (MS6627) Boban Velickovic (University of Paris 7) Maharam Algebras Abstract. A Maharam algebra is a complete Boolean algebra that 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 solved 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.Hide Friday Nov 02 2007 16:00-16:50 (MS6627) Jason Teutsch (Rand Corporation) A Short History of Shortest Programs Abstract. 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.Hide Friday Oct 19 2007 16:00-16:50 (MS6627) Andres Caicedo (Caltech) Regressive Functions on Pairs Abstract. 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.Hide

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)
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
Title: On nonstandard set theories

February 3-6, 2005: There will be a Very Informal Gathering of logicians at UCLA.

January 21, 2005
Speaker: Zlatan Damnjanovic
Title: On the logical foundations of arithmetic and the uniqueness of the natural numbers
Philosophically speaking, what is ordinary number theory about? Does the existence of non-standard models of (first-order) arithmetic imply that the concept of natural number is in some way indeterminate? Recent work of Charles Parsons seeks to answer these questions based on a first-order analysis of Dedekind's famed Categoricity Theorem. This paper critically examines Parsons's response and outlines a novel conception of the subject matter of arithmetic which affirms its determinateness while denying that it is constituted by a uniquely privileged natural number sequence.

December 10, 2004
Speaker: Andrés Caicedo
Title: Projective well-orderings and bounded forcing axioms
We show that fine structural inner models for mild large cardinal hypotheses but below a Woodin cardinal admit forcing extensions where bounded forcing axioms hold and the reals are projectively well-ordered.

November 19, 2004
Speaker: Ben Miller
Title: Automorphisms of sigma-complete Boolean algebras
The group of Borel automorphisms of the reals and the group of non-singular Lebesgue-measurable automorphisms of the reals have a surprising number of properties in common. One reason for this is that many problems involving these automorphism groups can be reduced to questions about infinite permutation groups in certain restricted languages. This viewpoint simultaneously clarifies the combinatorial core of the problem at hand, and allows one to see that many properties of the groups mentioned above are in fact shared by the automorphism groups of a very wide class of sigma-complete Boolean algebras. This class includes all complete Boolean algebras and all sigma-algebras on the reals which contain the Borel sets. We will examine various examples of this phenomenon.

November 5, 2004
Speaker: Tony Martin
Title: Gödel's Conceptual Realism.
Gödel is commonly regarded the paradigm of a platonist: of someone who believes that mathematics is about a realm of independently existing abstract objects. Gödel certainly is a platonist in this sense. But his brand of platonism, which he calls "conceptual realism," has a whole other aspect. For example, Gödel holds that the truths of mathematics are analytic: that a true mathematical proposition is true in virtue of the meanings of the terms occurring in it. This aspect of Gödel's position puts concepts, rather than objects, to the forefront. I will discuss the relation between the two aspects of Gödel's realism, and I will try to show that the object aspect has a smaller role than it is usually taken to have.

October 15, 2004
Speaker: Paul Eklof
Title: On Set theory applied to Ext theory
We survey some applications of set-theory to the study of the homological functor Ext. This includes theorems of ZFC proved using set-theoretic methods, as well as independence results. As time permits, topics include such ancient ones as Whitehead groups as well as more recent ones such as the Flat Cover Conjecture and tilting theory.

June 21-25, 2004. Note that the North American Summer School in Logic, Language and Information is being held at UCLA.

June 11, 2004
Speaker: John Steel
Title: The Proper Forcing Axiom implies determinacy in L(R)
Our most all-purpose method for producing canonical inner models satisfying large cardinal hypotheses is the core model induction method. In a core model induction argument, one produces canonical inner models which are correct for statements at a given level of complexity, using core model theory together with the existence of models which are correct at lower levels. We shall try to convey in greater detail the structure of such arguments, and illustrate them by outlining a proof of the theorem quoted in the title.

June 4, 2004. The UCLA Philosophy Department is having its Reichenbach Lecture, given by Charles Parsons, at 3:00 p.m.

May 28, 2004
Speaker: Mack Stanley
Title: The Branch Problem
Abstract in pdf format.

May 14, 2004
Speaker: Slawomir Solecki
Title: Projective Fraisse Limits and the Pseudo-arc
The talk will be about an application of logic to topology of indecomposable continua. A continuum is a compact connected space. A continuum is indecomposable if it is not the union of two proper subcontinua. The pseudo-arc is a hereditarily indecomposable continuum, that is, all of its subcontinua are indecomposable. It is, in a sense, the generic continuum since its homeomorphic copies form a dense G_delta subset of the space of all continua.
We develop a dualization of the classical Fraisse limit construction from Model Theory. The dual limit of a class of structures is a highly homogeneous structure (in the model-theoretic sense) but it also has a natural metric zero-dimensional topology. We show that after appropriately moding out the model-theoretic content of the dual Fraisse limit of a certain class of structures one obtains the pseudo-arc. Using this connection we are able to transfer results about automorphisms of the dual Fraisse limit to results about homeomorphisms of the pseudo-arc. In this fashion, we obtain strengthenings of results of Mioduszewski and of Lewis and Smith on the pseudo-arc and we establish a new topological characterization of the pseudo-arc.
This is a joint work with T. Irwin.

May 7, 2004
Speaker: Aldo Antonelli
Title: First-Order Quantifiers
In this talk we survey a number of results concerning first-order quantifiers and report on some work in progress. After briefly introducing generalized quantifiers, we identify some of their interesting properties and address the issue of their expressive power. Special attention is paid to a particular dyadic cardinality quantifier and its properties. Finally, we take up the question of the sense in which first-order quantifiers, similarly to second-order ones, might be open to a "non-standard" interpretation.

April 30, 2004
Title: Four Algorithmic Faces of Randomness
Let us consider infinite sequences of zeros and ones.
The classical probability theory fails to distinguish between random and non-random sequences. The first attempt to do that is due to von Mises (1919) but it suffered some vagueness. The theory of algorithms contributed new ideas to the task of defining what an individual random sequence is.
In fact, a random sequence has at at least four faces. First, it is stochastic; that means, the sequence itself as well as any of its reasonable subsequences has the property of frequency stability. Second, it is chaotic; that means, it is disordered, i.e., the occurrences of its terms are not governed by any reasonable rule. Third, it is typical; that means, it belongs to any reasonable majority. Fourth, it is unpredictable; that means, one who gambles on it cannot win by using any reasonable strategy.
All the four formulations use the word "reasonable." In each of four cases, the theory of algorithms allows one to fill that word with some exact meaning. So four well-defined classes of sequences appear. And each of them claims to be the true class of random sequences. Some of those claims are more justified than others.
References:
1. A. N. Kolmogorov, and V. A. Uspensky. Algorithms and randomness. SIAM J. Theory of Probability and Its Applications, vol. 32 (1987), pp. 389-412.
2. V. A. Uspensky, A. L. Semenov, and A. Kh. Shen. Can an individual sequence of zeros and ones be random? Russian Mathematical Surveys, vol. 45 (1990), no. 1, pp. 121-189.
3. V. Uspensky, and A. Semenov. Algorithms: Main Ideas and Applications. Kluwer, 1991. 269 pp.
4. An. A. Muchnik, A. L. Semenov, V. A. Uspensky. Mathematical metaphysics of randomness. Theoretical Computer Science, vol. 207 (1998), pp. 263-317.

April 23, 2004
Speaker: Paolo Mancosu
Title: Tarski on Models and Logical Consequence
In the last fifteen years there has been a heated debate on exactly what is going on in Tarski's theory of logical consequence. Since Etchemendy's publications in the eighties, contributions by, among others, Sher, Ray, Gomez-Torrente, and Bays have provided a much more detailed picture of Tarski's seminal 1936 paper. However, this intense focus on the original publication has led to several disagreements with respect to important interpretative issues related to Tarski's contribution. One of the bones of contention, and the only one I will treat in the talk, concerns Tarski's notion of model, the key element of Tarski's famous definition of logical consequence. I will argue that Tarski upheld a fixed-domain conception of model in his 1936 paper and that he was still propounding it in 1940. Thus, the 1936 conception of logical consequence is both intensionally and extensionally different from the one which is nowadays commonly accepted.

March 12, 2004
Speaker: Ted Slaman
Title: Recursive Measures and Their Random Reals
There is a well-developed theory of effective randomness, originating with the work of Kolmogorov (1965) [independently Chaitin (1975)] and Martin-Löf (1966). According to Chaitin and Kolmogorov, an infinite binary sequence X is random iff each of its initial segments is difficult to describe. According to Martin-Löf, X is random iff X does not belong to any effectively presented set of measure 0. However, the two notions pick out the same set of sequences as random, and this coincidence is commonly cited as evidence that they identify a robust and correct notion of randomness.
Both the Chaitin-Kolmogorov and Martin-Löf formulations of randomness are naturally equipped with random sets: the Chaitin Omega-numbers and the Universal Martin-Löf Tests. We will discuss these objects and recount results of Kuchera and Slaman (2001) and Merkle, Mihailovich and Slaman (2003) which show that they are generic examples of random sequences with recursively enumerable approximations.
We will end with an examination of the coincidence between descriptive randomness (Chaitin-Kolmogorov) and measure-theoretic randomness (Martin-Löf). By the following theorem of Reimann and Slaman, this coincidence is not a truism.
Theorem 1 (Reimann and Slaman). There is a recursive measure mu, necessarily discontinuous, and a sequence X such that X is Martin-Löf random relative to mu and yet for every nondecreasing recursive function f there is an n such that the first f(n) values of X can be specified by a program of length less than n.
In other words, there is a mu-random sequence on which mu does not concentrate whose information content is arbitrarily compressible.
References
Chaitin, G. J. (1975). A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22: 329-340.
Kolmogorov, A. N. (1965). Three approaches to the definition of the concept "quantity of information", Problemy Peredachi Informacii 1(vyp. 1): 3-11.
Kuchera, A. and Slaman, T. A. (2001). Randomness and recursive enumerability, SIAM J. Comput. 31(1): 199-211 (electronic).
Martin-Löf, P. (1966). The definition of random sequences, Information and Control 9: 602-619.
Merkle, W., Mihailovich, N. and Slaman, T. A. (2003). Some results on effective randomness. Preprint.

February 27, 2004
Speaker: Christian Rosendal
Title: Incomparable or Minimal Banach Spaces
Using the new methods of Ramsey theory in Banach spaces developed by Gowers, plus additional tools of descriptive set theory, we show that any infinite dimensional Banach space contains either a minimal subspace or a continuum of incomparable subspaces.

February 6, 2004
Speaker: Martin Dowd
Title: Iterating Mahlo's Operation
The principle of "collecting the universe" justifies axioms asserting the existence of large cardinals which can be "built up" by iterating Mahlo's operation. In a previous paper, "schemes" were used to define iterations of length up to kappa^+. This talk gives a method for defining iterations of length up to kappa^{++}. Assuming GCH, this is an unsurpassable limit, and the question of what ranks are achievable is complicated. Results will be given which suggest that weakly compact cardinals can be built up, and give an idea of their rank. It will also be argued that the notion of "built up" cardinals suggests, along with other evidence, that all sets are constructible.

January 23, 2004
Speaker: Itay Neeman
Title: Games of Length omega_1
The pattern of connections between determinacy and large cardinals suggests that there should be games which capture the theory of indiscernible Woodin cardinals. We present such games in the talk, and establish precisely the connection between the games and iterable models for indiscernible Woodin cardinals. We note that this connection allows finding definable winning strategies in closed games of length omega_1, and end with the (open) problem of constructing such winning strategies "purely", that is using descriptive set theory rather than large cardinals.

November 21, 2003
Speaker: Berit Givens
Title: The Bohr Topology on Various Abelian Groups
The Bohr topology on an Abelian group is the coarsest topology that makes all homomorphisms from the group into the unit circle continuous. In spite of this simple definition, the topology is very slippery, and I will talk about what it looks like for some common groups. In addition, I will discuss what is known about comparing two groups with the Bohr topology and how techniques from logic have been used in some of the proofs.

November 7, 2003
Speaker: Bernhard König
Title: Fragments of Martin's Maximum in Generic Extensions
We look at the following three properties of forcing notions, increasing in strength: weak omega_1-strategic closure (e.g. forcing a square sequence), strong omega_1-strategic closure, and omega_1-closure (e.g. Cohen subset of omega_2). It turns out that each type has different impact when forcing over a model of MM. Some new consistency results can be obtained with this.

October 24, 2003
Speaker: Andrew Arana
Title: Degree Complexity of Models of Arithmetic and Connections with Independence Results
In his 1958 paper, "Mathematical Significance of Consistency Proofs", G. Kreisel asked whether model-theoretic independence proofs for arithmetic could be made constructive by using recursive models of arithmetic. In 1959, S. Tennenbaum gave a negative answer for first-order Peano Arithmetic (PA), by showing that no nonstandard model of PA is recursive. This result suggested a battery of other questions about the Turing complexity of models and complete extensions of PA. We will survey work in this area, from the late 1950s through today.
We will focus on a line of questioning in this area instigated by C. Jockusch, who asked for a characterization of the degrees of models of True Arithmetic (the theory of the standard model of PA), and of other specific complete extensions of PA. R. Solovay answered Jockusch's questions, in theorems made widely known by J. Knight. Knight asked later whether Solovay's theorems could be simplified in any of three natural ways. We discuss why these simplifications are impossible. Our discussion rests on some independence results that are useful here and in other contexts, so we will discuss these results as well.

October 10, 2003
Speaker: Matthew Foreman
Title: Has the CH been Settled?

May 30, 2003
Speaker: Edward Keenan
Title: Excursions in Natural Logic
Working with generalized quantifiers (GQs) we study some novel entailment paradigms in English determined by the "4-group" of negation operators {identity, complement, post-complement, dual}. For example the paradigm in (1) is novel, even cute, in that Qx.A and Qx.notA are not logically equivalent when Q = 'for all' or 'there exists'.
(1) a. Exactly half the students passed
b. Exactly half the students didn't pass
The GQs that can replace 'exactly half the students' are just those fixed by the post-complement operator. We characterize this set, whose members are more numerous than (1) might suggest. The second paradigm we study is illustrated in (2):
(2) a. More than two thirds of the students read at least as many poems as plays
b. Less than a third of the students read fewer poems than plays
We characterize the pairs of GQs that enter this paradigm in terms of "Facing Negations". For both paradigms we characterize the permutation invariant GQs in the paradigm. We note that the paradigms naturally apply to a variety of non-first order definable quantifiers.

May 23, 2003
Speaker: Jindrich Zapletal
Title: Descriptive Set Theory and Definable Forcing
This is an overview of a book accepted to the Memoirs of the AMS. I will show the basic ideas connecting the iterations of definable proper forcing with descriptive set theory, and quote and explain the main theorems of the book.

May 16, 2003. No Logic Colloquium, but note that Krister Segerberg is speaking at the Philosophy Colloquium.

May 9, 2003
Speaker: Jiri Wiedermann
Title: A Formal Model of Fuzzy Computations
Fuzzy Turing machines and fuzzy languages were introduced by Zadeh, Lee and Santo in the 1970s. Unfortunately, it appears that from a computability point of view, their model is too powerful -- its nondeterministic version accepts non-recursively enumerable fuzzy languages. Moreover, from the viewpoint of modern fuzzy logic theory, the model is too restrictive since it is defined only for a specific t-norm (the Gödel norm). Therefore, we propose a generalization of the original model that is based on rigorous mathematical fundamentals of fuzzy logic. Its acceptance criterion is modified so that the resulting model obeys the Church-Turing Thesis. Fuzzy Turing machines then accept exactly the enumerable languages with partially computable fuzzy membership functions. The results open the way for simulating fuzzy computations by any other device obeying this thesis. However, the intended use of the model is in computability and complexity-theoretic investigations aiming at the power, limits and efficiency of fuzzy computations, rather than in design of efficient fuzzy algorithms.

April 25, 2003
Speaker: Martin Davis
Title: Gödel's Developing Platonism

April 18, 2003
Speaker: Johan van Benthem
Title: Rational Dynamics: the Logical Structure in Games
Logicians have used special games for a long time already when studying expressive power or argumentation structure. But there is also a logical structure to games in the more general sense of game theory. Games may be analyzed as interactive processes in dynamic, temporal, or linear logics, linking up with concerns in computer science. On top of that, deliberations and decisions by players in the course of such a process can be modelled in epistemic logics, linking up with key issues in philosophical logic.
Many of the current contacts between logic and game theory have to do with explaining the emergence and stability of game-theoretic equilibria in terms of epistemic assumptions, and there are important results to this effect by authors like Aumann and Stalnaker. In this talk, we propose a new twist. We analyze game-theoretic equilibria as arising in the limit from repeated announcements by players of their rationality -- a bit like the way in which the Muddy Children arrive at enlightenment through repeated assertion of their status. This idea can be made precise in dynamic logics of information update. More technically, this analysis leads to connections between different notions of game equilibrium and different fixed-point logics: monotonic or inflationary.
Literature
'Logic in Games', 1999 ->, electronic lecture notes in progress, ILLC, Amsterdam: see the home pages http://staff.science.uva.nl/~johan/Teaching/ and more general info on http://www.illc.uva.nl/lgc/
'Extensive Games as Process Models'. Journal of Logic, Language and Information 11 (2002), 289-313.
'Rational Dynamics and Epistemic Logic in Games', ILLC Tech report, January 2003, http://www.illc.uva.nl

April 4, 2003
Speaker: Wayne Richter
Title: Inductive Definability
Inductively defined sets are formed by repeatedly applying an inductive operation until closure is reached. The study goes back to Kleene's systems of notations for the constructive ordinals. The general theory is concerned with the relationship between, on the one hand the form of an inductive operator, and on the other hand the form of the set and closure ordinal defined by that operator. Inductively defined sets provide "recursive analogs" of small, large cardinals. Of special interest is the relationship between monotone and nonmonotone inductive definability.
The subject has applications in proof theory and finite model theory. The talk should be accessible to beginning graduate students.

February 28, 2003
Speaker: Marcus Kracht
Title: Reduction Functions
The finite model property and decidability are typically shown in modal logic via filtration of the canonical model. This method is highly nonconstructive. Another method is the tableau method, which has the disadvantage that completeness is difficult to show. We shall present a third way, by means of reduction functions, which establishes in a uniform way finite model property, decidability and interpolation (wherever applicable). Also, the best known space complexity bounds can be obtained with it. The core of the method is to reduce derivability of a formula P in an axiomatic extension L to derivability in K from a set of theorems of L that need to be found a priori on the basis of P.

February 7, 2003
Speaker: Paul Larson
Title: The Canonical Function Game
The canonical function game is a definable game of length omega_1 indentified by Hugh Woodin which falls inside a class of games known as Neeman games. It turns out that this game is consistently undetermined. I will discuss this result and its relationship to some major open questions in set theory.

January 31, 2003
Speaker: Alain Louveau
Title: Dichotomy Results for Analytic Graphs
We will present some dichotomy results about analytic (directed and undirected) graphs, which involve the ordering of Borel homomorphic reducibility, and generalize a dichotomy of Kechris, Solecki, and Todorcevic about the Borel chromatic number of such graphs.

January 24-26, 2003, there will be a Very Informal Gathering of logicians at UCLA in honor of the 65th birthday of Yiannis N. Moschovakis.

January 10, 2003
Speaker: Richard Ketchersid
Title: Comparing Boolean(Pi^0_3) Cardinals is Hard
Abstract: An early result in the theory of Borel equivalence relations on R states that for each S included in P(omega) there is an associated Pi^0_3 (later improved to Sigma^0_2) equivalence relation E_S such that E_S leq E_T iff T - S is finite (under AD). This shows that the Pi^0_3 "real" cardinals are a mess, but left open the question of how complicated the reducibility relation "leq" is among Borel equivalence relations.
I will give Boolean(Pi^0_3) equivalence relations E and E_x (uniformly for x in R) so that {x : E leq E_x} is complete Sigma^2_1, i.e., as complicated as possible. All this is done under "AD^+ + V = L(P(R))." Similar results where one restricts the notion of reduction can be obtained using less determinacy. Moreover, it seems plausible that Boolean(Pi^0_3) should be replaced by Pi^0_3 or even Pi^0_2, but I do not see how to do this.

November 22, 2002
Speaker: Kai Wehmeier
Title: A Metalogical (?) Argument in Frege
In the context of the recent resurgence of interest in the logical system of Frege's Grundgesetze der Arithmetik (1893/1903), originating with work by George Boolos, Terence Parsons, and Peter Schroeder-Heister in the 1980's, it has become clear that we have a somewhat poor understanding of the exact nature of Frege's project. In particular, there is some debate as to whether metalogic plays any substantial role in it. Two passages in Grundgesetze appear to lend a great deal of support to the claim that it does, namely, section 10, containing the 'permutation argument' by means of which Frege attempts to show that he can safely identify the truth values with certain sets (the 'identifiability thesis'), and sections 29-32, containing an attempted proof that every begriffsschrift term denotes. In my talk, I shall focus on the permutation argument and try to show that the standard, metalogical interpretation is untenable. I shall advocate a 'mathematical' interpretation, first suggested by Thomas Ricketts, instead. This interpretation has the advantage of allowing a consistent model-theoretic reconstruction according to which both the permutation argument and the identifiability thesis are valid.

November 15, 2002
Speaker: Burkhard Englert
Title: Lower Bounds on the Shared Memory Requirements for Long-lived and Adaptive Objects
Recently, several different long-lived adaptive algorithms whose operation step complexity is a function of the actual number of processors running concurrently with the operation execution, have been presented. Regardless of the type of adaptiveness and the type of object implemented, they require Omega(N) MWMR registers in their implementation, where N is the total number of processors that may participate in the implementation. We show that this is a necessity. We furthermore show that even if the maximum allowed concurrency m is a constant and m < d, where d is the number of MWMR registers used, that for any such d there exists n_d, such that every long-lived adaptive read/write implementation of collect and renaming with n_d processors must use at least d MWMR registers.
This is joint work with Eli Gafni.

November 8-9, 2002: The Philosophy Department presents the Rogers Albritton Commemoration.

November 1, 2002
Speaker: Wai Yan Pong
Title: Finiteness Principles for Monomial Ideals and their Applications
I will present some "finiteness" results on monomial ideals. The main tool used here is the theory of Noetherian orders. This turns out to have some interesting applications to differential algebra. In particular, one can derive a model theoretic rank called the differential order which generalizes the notion of the order of a differential equation.

October 26, 2002 (Saturday): There will be a Logical Constants workshop at UC Irvine.

October 18, 2002
Speaker: Marcus Kracht
Title: The Lattice of Modal Logics
Unlike in predicate logic, there is no simple reduction from axiomatic extensions to the basic logic. Thus, in modal logic one must be interested in the totality of all logics. They form a lattice, whose structure has been studied throughout the last 25 years. A principal tool is the notion of a splitting, which proved to be of central importance in trying to establish not only the structure of the lattice itself, but also in solving many genuine logical problems. In this talk I shall give an overview of the principal results concerning the lattice of modal logics and present some open problems.

June 7, 2002
Speaker: Michael Rathjen
Title: The Axiom of Choice in Constructive Set Theory
The axiom of choice does not have an unambiguous status in constructive mathematics. On the one hand it is said to be an immediate consequence of the constructive interpretation of the quantifiers. Any proof of
forall x in a, exists y in b, phi(x,y)
must yield a function f : a --> b such that
forall x in a, phi(x,f(x)).
This is certainly the case in Martin-Löf's intuitionistic theory of types. On the other hand, from the very earliest days, the axiom of choice has been criticised as an excessively non-constructive principle even for classical set theory. Moreover, it has been observed that the full axiom of choice cannot be added to systems of constructive set theory without yielding constructively unacceptable cases of excluded middle. On the other hand, it has been shown by Peter Aczel that constructive set theory has a canonical interpretation in Martin-Löf's type theory and that this interpretation also validates several choice principles, e.g., the axiom of countable choice and the axiom of dependent choices. The main aim of the talk is to present joint work with Sergei Tupailo in which we give a characterization of a restricted class of set-theoretic statements realizable in Martin-Löf type theory. This class contains all the statements that figure in ordinary mathematics. The realizable statements turn out to be those provable in an extension of CZF via the so-called Pi-Sigma-axiom of choice.

June 1-4, 2002, the ASL meeting in Las Vegas is held.

May 31, 2002
Speaker: Lefteris M. Kirousis
Title: Review of the Results on the Approximation of the 3-SAT Threshold
Consider the space of uniformly random 3-CNF Boolean formulas phi with density (clauses to variables ratio) r. Computer experiments performed by several researchers starting a decade ago suggest that there exists a number r_3 around 4.2 such that if r < r_3 then the probability that phi is satisfiable has limit 1, as the number variables n becomes large, whereas this limit is 0, if r > r_3. This 0-1 or phase transition phenomenon has also been corroborated by methods of Statistical Physics (the replica method). Mathematically, it has been proved that there exists a sequence of intervals I_n = 3D(a_n, b_n), whose lengths approach 0, such that the probability of satisfiability of a random 3-CNF formula has limit 0 if its density r < a_n and has limit 1 if r > b_n. However, the existence of a threshold number r_3 is still an open problem. On the other hand, increasingly larger values l_3 < 4.2 and increasingly smaller values u_3 > 4.2 have been found such that the probability of satisfiability is almost 1 for r < l_3 and is almost 0 for r > u_3. Some of these upper and lower threshold-bound results will be reviewed.

May 17, 2002
Speaker: Rosalie Iemhoff
Title: The Provability Logic of Constructive Theories
The provability predicate of an arithmetical theory T is a predicate in the language of T which, when applied to the code of a formula, expresses that that formula is provable in T. Already the second incompleteness theorem by Goedel shows that T cannot prove everything that is true about this predicate; the sentence expressing that T is consistent is such an example. The provability logic of T consists of all (propositional) schemes that T does prove about its provability predicate.
On the classical side provability logics are well investigated. A remarkable thing is their stability; many classical theories, like for example Peano Arithmetic and set theory ZF, have the same provability logic, the decidable modal logic GL. On the constructive side much less is known. For example, no r.e. axiomatization of the provability logic of Heyting Arithmetic, the constructive counterpart of Peano Arithmetic, is known, and it is not even known if it exists. However, over the last few years significant parts of this logic have been characterized and for the first time there is a reasonable conjecture what the axiomatization of this provability logic actually might be. In the talk I will give an overview of the main results in this area.

May 3, 2002
Speaker: Derrick DuBose
Title: Determinacy and Sharps
We shall discuss some determinacy results concerning classes within the difference hierarchy on co-analytic sets.

April 26, 2002
Speaker: Tetsuya Ishiu
Title: Club Guessing Sequences and Filters
S. Shelah proved under ZFC that for every regular uncountable cardinal kappa, there exists a sequence which "guesses" all closed unbounded sets in kappa. Such a sequence is called a club guessing sequence and has been used to prove various theorems. Also we can construct filters naturally associated with club guessing sequences. These filters have some interesting properties, too. In this talk, I would like to present basic facts and new results on these objects.

April 19, 2002. No Logic Colloquium, but note that the UCLA Philosophy Department is having its Reichenbach Lecture, given by Michael Friedman.

April 12, 2002
Speaker: Jouko Väänänen
Title: Some Results in Infinitary Logic
I will give a survey of recent work in infinitary logic based on the use of transfinite games and set-theoretic properties of trees.

April 5, 2002
Speaker: Juliette Kennedy
Title: Some Results in Classical Model Theory Based on Transfer Principles
We study universality of regular reduced powers of first order structures and get positive results under GCH or just a transfer principle. Under GCH (or less) we can also prove that regular ultrapowers of elementary equivalent structures are isomorphic, improving earlier results by Keisler and Shelah. This is joint work with Saharon Shelah.

March 15, 2002. No Logic Colloquium, but Charles Parsons is speaking at the UCLA Philosophy Colloquium, 3pm.

March 8, 2002
Speaker: Albert Visser
Title: Logics for Provability and Interpretability

March 1, 2002
Speaker: Benedikt Löwe
Title: Variants of Blackwell Determinacy

February 1, 2002
Speaker: Victor W. Marek
Title: Some Applications of Universal Algebra to Semantics of Nonmonotonic Logics
(joint work with M. Denecker, KU Leeuven, Belgium and M. Truszczynski, University of Kentucky)
We prove a number of results on operators in lattices. These results are used to revisit the issue of connections between leading formalisms in nonmonotonic reasoning: logic programming with stable semantics, autoepistemic logic and default logic. For each logic we develop a comprehensive semantic framework. This framework is based on a family of operators in suitably chosen lattices. These operators represent constructions introduced in each of these domains independently. It turns out that all three formalisms become closely related when these semantics are properly aligned.
Abstracting from the operators used in these formalisms, we study approximations of operators in lattices by means of operators in the product lattice. It turns out that, with a suitably chosen ordering, every operator possesses a best approximation. These approximations generalize constructions such as the 3-valued T_P operator of Fitting and the van Gelder operator for computation of alternating fixpoint.

January 11, 2002
Speaker: Tomek Bartoszynski
Title: Perfectly Meager Sets of Reals
A set of reals is perfectly meager if it is meager inside every perfect set. I will discuss several results concerning the properties of these sets.

December 7, 2001
Speaker: Harvey Friedman
Title: Boolean Relation Theory
Boolean relation theory is simply the study of the Boolean relations between one-dimensional sets and their images under multivariate functions. This study naturally leads to a variety of statements equivalent to the 1-consistency of Mahlo cardinals of finite order, even in concrete settings in the integers which are subject to known quantifier elimination. In addition, there are classifications of large finite families of such statements (as to truth value) which can be proved to be correct with and only with the use of Mahlo cardinals of finite order. A complete proof of the forward direction will be given. Ideas from the reversal will be sketched.

November 30, 2001
No colloquium, because of the Ruthfest at the Philosophy Department.

November 16, 2001
Speaker: Boban Velickovic
Title: Long Ehrenfeucht-Fraïssé Games and Forcing
We consider Ehrenfeucht-Fraïssé games of uncountable length between first-order structures and relate this to the existence of certain forcing notions which make the two structures isomorphic. In particular, we show that it is consistent to have two structures which are L_{\infty,\omega_1} equivalent but they cannot be made isomorphic by a sigma-closed poset consisting of partial isomorphisms. The construction involves a special kind of a gap-1 morass.

November 2, 2001
Speaker: James Cummings
Title: Scales and Squares
We discuss some problems in combinatorial set theory which involve successors of singular cardinals, and show that ideas from PCF theory are relevant to their solution. In particular we discuss the role of two canonical stationary sets, the "good points" and the "approachable points."

October 19, 2001
Speaker: Martin Zeman
Title: The Current State of Combinatorial Analysis of Extender Models

October 5, 2001
Speaker: John Clemens
Title: Conjugacy of Borel Automorphisms
I will discuss the difficulty of determining when two Borel automorphisms of a Polish space are isomorphic, i.e., conjugate via another Borel automorphism. By using the theory of definable equivalence relations, we can show that this is a very complicated equivalence relation. We can also view this as showing that we can not find "simple" invariants which completely characterize the isomorphism class of a given Borel automorphism.

June 8, 2001
Speaker: Slawomir Solecki
Title: Descriptive Set Theory and Continua

May 25, 2001
Speaker: Peter Cholak
Title: The Latest News about the Computably Enumerable Sets
As partially suggested by the title, this talk will focus on the latest (exciting) results of Leo Harrington and the speaker on the computably enumerable sets.

May 4, 2001
Speaker: Steve Jackson
Title: A New Kind of Pathological Set
We answer a question posed by Steinhaus by showing that there is a set in the plane meeting every isometric copy of the integer lattice in exactly one point. Numerous questions remain open.

April 20, 2001: No colloquium, due to the AMS set theory meeting in Las Vegas the next day.

April 6, 2001
Speaker: Simon Thomas
Title: Countable Borel Equivalence Relations and the Classification Problem for Torsion-free Abelian Groups of Finite Rank
I will discuss some recent contributions to the project of explaining why no satisfactory system of complete invariants has been found for the classification problem for torsion-free abelian groups of finite rank. The talk will include a discussion of where this problem is situated within the descriptive set-theoretic context of countable Borel equivalence relations.

March 16, 2001
Speaker: Robert Solovay
Title: Consistency Strength of Some Variants of NFU
The system of set theory, New Foundations, proposed by Quine is still not known to be consistent. Some years ago, Jensen formulated a slight variant of NF, NFU, which is demonstrably consistent. I have been computing the consistency strength of some variants of NFU and they turn out to be surprisingly strong. One, NFUA, has the approximate consistency strength of a Mahlo cardinal. Another, NFUB has the approximate consistency strength of a weakly compact cardinal.
The main focus of this talk will be on a third variant, NFU*, whose consistency strength is approximately Sigma_2-replacement.

March 2, 2001
Speaker: G. Aldo Antonelli
Title: The Second-Order Propositional Theory of Two S5 Modalities
(Joint work with Rich Thomason, University of Michigan)
After introducing and motivating a poly-modal version of S5 with propositional quantifiers, we consider the decidability problem for such a language. We show that the language is quite expressive, indeed equivalent to full second-order logic (under the standard interpretation). This is in contrast to the case of one S5 modality with propositional quantifiers, which is decidable (as proved independently by Kit Fine and David Kaplan).

February 16, 2001
Speaker: Richard Ketchersid
Title: On the Strength of omega_1-Dense Ideals on omega_1
I will outline how to get non-tame mice from the existence of an ideal on omega_1 which is slightly stronger than an omega_1-dense ideal. This puts the consistency strength of such an ideal somewhere past "There is a proper class of strong cardinals the least of which is a limit of Woodin cardinals."

February 2, 2001
Speaker: Eli Gafni
Title: Uniform Protocols and a Design Methodology for Adaptive Algorithms
We propose a new meaning that one can attach to the notion that a sequence of tasks T_1, T_2, ... is solvable. While the celebrated Herlihy-Shavit conditions characterize when T_i is solvable, they may give rise to a distinct protocol Pi_i to solve each task T_i. We introduce the notion of a uniform protocol to capture the requirement that the whole sequence is solvable by a single protocol.
We argue that this notion captures the recently researched notion of one-shot adaptive protocols. Adaptive protocols have been defined via step-complexity notions. By regarding adaptive protocols as a special case of uniform protocols, where the latter involve computability questions rather than complexity questions, we are able to bring to bear all the topological machinery developed for such questions, and completely characterize when is a task solvable uniformly or adaptively. Furthermore, we motivate a simple sufficient conditions for a task to be solved adaptively. These sufficient conditions result in a methodology to develop adaptive algorithms. We employ the methodology to develop a new adaptive immediate-snapshot algorithm of complexity O(k^2) (compared with the current best of O(k^3)), where k is the number of processors actually active in the protocol.

January 19, 2001
Speaker: Drew Moshier
Title: Multi-lingual Sequent Calculi: Proof Theory and Topology
We introduce Gentzen-style sequent calculi where the formulas on the left and right of the turnstile need not come from the same logical system. In such calculi, sequents can be seen as consequences between different domains of reasoning. We discuss the ingredients of proof theory needed to set up calculi generalized in this fashion. The result is the category MLS (multi-lingual sequent calculus) in which the morphisms are generalized calculi and objects are calculi that capture "domain internal" reasoning.
To develop a semantic theory for MLS, we turn to spectral theory, showing that the MLS objects give rise to spectra (spaces of prime filters) that are, up to homeomorphism, exactly the locally compact, strongly sober spaces (aka Nachbin spaces). Such spaces, studied first by Nachbin in the 1940's, are arguably the natural T_0 generalizations of compact Hausdorff spaces. The morphisms of MLS correspond to "continuous relations" between these spaces. In turn, a continuous relation from X to Y corresponds to a continuous function from X to the Smyth powerdomain of Y. Thus we establish category equivalences: MLS to N^* (the category of Nachbin spaces and continuous relations) and MLS to the Kleisli category for the Smyth powerdomain monad on N (Nachbin spaces and continuous functions).
Several useful topological concepts, such as the Hausdorff condition, zero-dimensionality, functionality of a relation, and properness of a function (f^-1 preserves the "well-below" relation on opens), have interesting characterizations within MLS as proof-theoretic properties of the corresponding sequent calculi. As time allows, we will discuss some of these characterizations and demonstrate how proofs within MLS of familiar topological results shed light on the topological concepts involved.

December 1, 2000
Speaker: Burkhard Englert
Title: Lattice Embeddings into the Computably Enumerable Degrees
The decidability of the two-quantifier theory of the partial order of computably enumerable degrees R is still one of the major open problems in computability theory. Since one can easily verify that for every finite lattice L, there is a two-quantifier sentence phi such that L is embeddable in R if and only if phi is true in R, the characterization of all finite lattices embeddable into R has been of particular interest to researchers (lattice embedding problem). In this talk we will first survey the current status of this problem. We will then present a condition that is necessary and sufficient for the embeddability of a finite lattice without critical triples preserving greatest element.

November 3, 2000
Speaker: Carlos Uzcátegui
Title: Analytic Topologies over Countable Sets
I will present in this talk some results of joint work with S. Todorcevic about analytic topologies. A topology T over the natural numbers is said to be analytic if T as a subset of the Cantor cube is an analytic set. Some motivations for studying analytic topologies:
(1) Descriptive set theoretic aspect: The study of analytic topologies is a continuation of what has been done for analytic filters (or ideals) over countable sets. For instance: complexity of topologies and their generating families, Baire measurability.
(2) General topological aspects: Most natural examples of countable topological spaces found in the literature are analytic. Many questions involving convergence are frequently questions about countable spaces with an analytic topology.
The general goal is to make the connection between descriptive set theoretic properties and purely topological properties of a given space more explicit.

October 13, 2000
Speaker: Michael Beeson
Title: Logic and Computation: Putting Mathematics on a Computer
Today there exist computer programs which can perform algebra and calculus (computation), and there also exist programs which attempt to find proofs of theorems. But the former get wrong answers because they have no logical capabilities, and the latter can't prove anything very interesting, because they have no computational abilities, and can't remember what they proved yesterday.
The talk will explain a suitable theoretical framework for the integration of logic and computation, and discuss how that framework has been implemented in two programs: MathXpert and Weierstrass. The former does computation without logical errors, and the latter finds proofs involving computations.
Mathpert is a symbolic-computation program designed with education as the primary purpose. It can produce step-by-step solutions, not just one-line answers, and keeps track of logical conditions to ensure that the steps, and hence the answers, are correct.
Weierstrass can prove various specific functions are continuous, such as f(x) = x^3, sqrt(x), or sin(x). (Previously the best that theorem-provers could do was the continuity of a linear function.) It can also prove that e is irrational, a nontrivial theorem which might occur in an upper-division number theory course.

June 9, 2000
Nonstandard time and room: 2:00pm, MS 7608
Speaker: Abbas Edalat
Title: Foundation of a Computable Solid Modelling
Solid modelling and computational geometry are based on classical topology and geometry in which the basic predicates and operations, such as membership, subset inclusion, union and intersection, are not continuous and therefore not computable. But a sound computational framework for solids and geometry can only be built in a framework with computable predicates and operations. In practice, correctness of algorithms in computational geometry is usually proved using the unrealistic Real RAM machine model of computation, which allows comparison of real numbers, with the undesirable result that correct algorithms, when implemented, turn into unreliable programs. Here, we use a domain-theoretic approach to recursive analysis to develop the basis of an effective and realistic framework for solid modelling. This framework is equipped with a well-defined and realistic notion of computability which reflects the observable properties of real solids. The basic predicates and operations on solids are computable in this model which admits regular and non-regular sets and supports a design methodology for actual robust algorithms. Moreover, the model is able to capture the uncertainties of input data in actual CAD situations.

May 26, 2000
Speaker: James Hardy
Title: On the Interpretation of Variables

May 5, 2000
Speaker: Alain Louveau
Title: Covering of Compact Sets

April 21, 2000
Speaker: Arnold Beckmann
Title: Model-theoretic Characterizations of the Separation Problem of Bounded Arithmetic
Bounded arithmetic is designed to characterize low complexity computability, i.e., the polynomial hierarchy. The main open problem for bounded arithmetic is the question if bounded arithmetic is finitely axiomatizable, which is equivalent to asking if the levels of bounded arithmetic S^i_2, T^i_2 collapse. Furthermore, this question is also connected to the open problem whether the polynomial hierarchy collapses. The precise connection is that bounded arithmetic is finitely axiomatized if and only if bounded arithmetic can prove that the polynomial hierarchy collapses [Buss 1995].
In this talk we will give model-theoretic characterizations of the separation problem of bounded arithmetic. The main tool will be restricted consistency statements, whose complexity is captured by a bounded analog of Pi_1. Our characterizations will be as the following one:
Two levels of bounded arithmetic -- say S^i_2 vs. T^j_2 for j >= i -- are separated by a bounded Pi_1 sentence if and only if there exists a model of the smaller theory (i.e., S^i_2) without proper bounded-elementary extensions to a model of the stronger theory (i.e., T^j_2).
Remark for experts: By "bounded Pi_1" we mean the universal closure of Pi^b_1, and "bounded-elementary extensions" is the restriction of elementary extensions to sharply bounded formulas.

April 14, 2000
Speaker: André Nies
Title: Global Properties of Degree Structures
We investigate degree structures induced by many-one reducibility and Turing reducibility on the computably enumerable (c.e.) sets, the arithmetical sets, and all subsets of the natural numbers. We ask which subsets of the degree structure are automorphism bases: For instance, the minimal degrees form an automorphism base of the c.e. many-one degrees, but not for the other two degree structures based on many-one reducibility. Furthermore, we discuss whether a copy of (N,+,x) can be defined without parameters in the structure, and whether the structure is a prime model of its theory.

April 7, 2000
Speaker: Phokion G. Kolaitis
Title: The Complexity of Minimal Satisfiability Problems
A dichotomy theorem for a class of decision problems is a result asserting that certain problems in the class are solvable in polynomial time, while the rest are NP-complete. The first remarkable such dichotomy theorem was proved by T. J. Schaefer in 1978. It concerns the class of generalized satisfiability problems SAT(S), whose input is a CNF(S)-formula, i.e., a formula constructed from elements of a fixed set S of generalized connectives using conjunctions and substitutions by variables.
In this talk, we first review Schaefer's dichotomy theorem and then present some new results concerning the class of minimal satisfiability problems MINSAT(S), where S is a fixed set of generalized connectives. The input to such a problem is a CNF(S)-formula and a satisfying truth assignment; the question is to decide whether there is another satisfying truth assignment that is strictly smaller than the given truth assignment with respect to the coordinate-wise partial order on truth assignments. Minimal satisfiability problems were first studied by researchers in artificial intelligence while studying the computational complexity of propositional circumscription. Our main result is that a dichotomy theorem holds for the class of all MINSAT(S) problems, where S is a finite set of generalized connectives. Moreover, we give simple criteria that tell apart the polynomial-time solvable cases of MINSAT(S) from the NP-complete ones.
This is joint work with Lefteris M. Kirousis of the University of Patras.

March 3, 2000
Speaker: Theodore A. Slaman
Title: Definability in the Turing Degrees
A set of natural numbers B is Turing reducible to another set A iff there is an effective algorithm to determine which numbers belong to B when given complete information about A. Here is a simple example:
{n : 2n is in A and 2n+1 is not in A} is recursive in A
The Turing degrees are the equivalence classes of the induced equivalence relation, and are naturally ordered by Turing reducibility. We use D to denote this partial ordering.
The hierarchies of definability as represented by their universal sets and their associated collections of definable sets have natural images in D as degrees and ideals. We will discuss the extent to which these degrees and ideals are intrinsic to D: which are invariant under automorphisms of D and which are first-order definable in D.
We will pay particular attention to the Turing jump, which maps the degree x of a set X of natural numbers, to the degree x' of the halting problem relative to X.
Theorem (Slaman-Shore, 1999)   The function x maps to x' is definable in D.
The audience will find that this theorem has a checkered past, but that the line of inquiry has an interesting future.

Note: On Thursday February 24, Matthew Foreman will speak at the UCLA Mathematics Colloquium.

February 11, 2000
Speaker: Philip Welch
Title: On Gupta-Belnap Revision Theories of Truth
Revision Theories of Truth have been developed by Herzberger, Belnap, and Gupta to give an alternative model to Kripke's of a theory of truth for languages in which there is a (classically or otherwise) defined truth predicate. In such schemes the extension of a truth predicate is successively revised or "improved." This has been broadened in a recent book of Belnap and Gupta to include a general theory of circular definitions.
We classify the complexity of such concepts as stably true or categorical in such schemes (which can be non-absolute between different models of set theory); thereby raising some mathematically based queries concerning their status. The discussion of which revision rule to adopt at limit ordinals (amongst the three theories of the authors above) is seen to be irrelevant when it comes to revision-theoretically definable predicates -- which are seen to include also the predicate of stable truth.
We argue that these theories are better considered as extensions to the theory of inductive definability, rather than actual theories of truth.

January 28, 2000
Speaker: Lajos Soukup
Title: On Weak Freese-Nation Property of Boolean Algebras
A partial ordering P has the weak Freese-Nation (wFN) property if there is a mapping f : P -> [P]^omega such that for any p, q in P with p \le q there is r in f(p) \cap f(q) such that p \le r \le q.
In the Cohen model, (P(omega), \subset) has the wFN-property.
We study the consequences of the wFN property of (P(omega), \subset). Under this assumption, we prove that most of the known cardinal invariants including all of those appearing in Cichon's diagram take the same value as in the corresponding Cohen model.
If a cBA has the wFN property then it should satisfy the c.c.c. We prove that GCH does not decide whether every c.c.c. cBA has the wFN property. We also investigate the relationship between the wFN property of different cBAs.

January 14, 2000
Speaker: Su Gao
Title: On the Classification of Countable Boolean Algebras
We consider the question: How many countable Boolean algebras are there up to isomorphism? The best possible answer in the terminology of 1900 is that there are continuum many. However, with the theory of equivalence relations developed in the last decade we can answer the question in a much stronger way. In this talk I will survey some results about the isomorphism relation for countable Boolean algebras and some applications of these results to other related algebraic and topological equivalence relations. This is joint work with R. Camerlo.

December 3, 1999
Speaker: Donald Bamber
Title: Reasoning with Fallible Rules: A Second-Order Probability Approach
This talk describes a logic founded on two basic ideas.
First, motivated by the fact that most rules in rule-based systems have exceptions, Adams' high-probability semantics was adopted. In this semantics, a rule "If A then B" is interpreted as meaning that the conditional probability of B given A is close to one.
Second, it was desired to have a logic that would produce (a) many inferences having a small probability of error rather than (b) only a few inferences having no possibility of error. Consequently, the Bacchus-Grove-Halpern-Koller inference criterion was adopted. With this criterion, a conclusion is inferred from a set of premises if, roughly speaking, nearly all models of the premises are models of the conclusion. To implement this quasi-Bayesian approach to inference, Adamsian probability models were represented as vectors in Euclidean space and a uniform prior probability distribution over models was employed.
The resulting logic is equivalent to a logic of Lehmann and Magidor and nearly equivalent to logics of Goldszmidt and Pearl.

November 19, 1999
Speaker: Norman Danner
Title: Capturing Function Classes with the Lambda Calculus
One of the first results regarding Church's untyped lambda calculus is that, relative to an appropriate encoding of the natural numbers, exactly the total recursive functions are representable. Much of the power of the untyped calculus arises from its (intentional) failure to distinguish between function and argument (i.e., the same term can be used in both capacities). A typing discipline for the lambda calculus reinstates this distinction, and when a typing discipline is imposed, the collection of representable numeric functions decreases dramatically.
In this talk, I will survey some of the main typing disciplines and their corresponding classes of representable functions. I will start with so-called simple typing, characterized by Schwichtenberg and Statman in the late 60's, and work through to some recent results of Daniel Leivant and myself on systems of ramified polymorphism.

November 12, 1999
Speaker: Péter Komjáth
Title: Simultaneous Chromatic Number

November 5, 1999
Speaker: Chris Pollett
Title: Strengths and Weaknesses of LH Arithmetic
One way to quantify the difficulty of P = NP problem would be to exhibit a logical theory which is capable of formalizing current attempts at answering this question and yet which is not powerful enough to prove or disprove this equality. Razborov has argued that most current circuit lower bound techniques can be formalized in a fragment of arithmetic which roughly has induction on NE-predicates. Nevertheless, exhibiting any fragment of arithmetic which one can demonstrate cannot prove the collapse of the polynomial hierarchy is nontrivial. In this talk we will consider a much weaker theory than Razborov's, but which we argue can still do some interesting mathematics. Namely, it can "reason" about all the functions in the log-time hierarchy, it can prove the log-time hierarchy differs from NP, and, in fact, we give some evidence it might be able to show the log-time hierarchy is infinite. (In the real world this is known to be true.) On the other hand, we show this theory cannot prove the polynomial hierarchy collapses. So, in particular, it cannot prove P = NP, and it follows that any proof that the polynomial hierarchy collapses, if such a proof exists, must be formalized in a stronger fragment than ours.

October 22, 1999
No colloquium. Fefermans at UC Irvine

October 8, 1999
Speaker: Jindrich Zapletal
Title: Open-Point Games of Transfinite Length

June 11, 1999
Speaker: Slawomir Solecki
Title: Translation Invariant Ideals on Abstract Groups

May 28, 1999
Speaker: John Steel
Title: A Mouse-Eye View of L(R)
We formulate a correctness conjecture for mice (i.e., canonical inner models) whose iteration strategies are in L(R). We prove that the relativized-to-a-real form of this conjecture holds for all reals of sufficiently large Turing degree.

May 14, 1999
Speaker: Herbert Enderton
Title: Theories of Equality
The theory of equality is the set of valid sentences with no non-logical symbols at all (so there are no function symbols, and the only predicate symbol is equality). The first-order theory of equality is too simple to be of interest. The second-order theory of equality is too complex to be of interest. This talk will focus on intermediate ground.

April 30, 1999
Speaker: Lorenz Halbeisen
Title: The Dual-Ramsey Property for Sets of Partitions
A set S of infinite subsets of N is called Ramsey iff there exists an infinite subset of N such that each or none of its infinite subsets belongs to S. If we replace the set of infinite subsets of N by the set of infinite partitions of N, we get the following notion: A set T of infinite partitions of N is called dual-Ramsey iff there exists an infinite partition X such that each or none of the infinite partition coarser than X belongs to T.
Even though one gets a lot of results for the dual-Ramsey property which are symmetric to the corresponding results for the Ramsey property, e.g. each property is equivalent to the Baire property in some topology, there are also some asymmetries and several questions are open.

April 23, 1999
Speaker: Johan van Benthem
Title: Guarded Quantifiers: Renewing the Search for Decidable Fragments
Logicians have long studied decidable fragments of first-order logic. These should preferably be well behaved in other respects too, such as having a good model theory and proof theory. We propose a new direction here, inspired by modal logic, using a systematic analysis of quantifier bounds. The result are large "guarded fragments" that are decidable, and have a nice metatheory based on suitable notions of bisimulation. We will show how guarded analysis works, and discuss some recent results -- as well as open questions. A useful intuition here is that of "logical dynamics": quantifiers are actions that jump to new states, subject to certain constraints. Undecidability then lurks once we get to parallel, rather than just sequential, quantifier action.
References: (1) H. Andréka, J. van Benthem, and I. Németi, Modal logics and bounded fragments of predicate logic, Journal of philosophical logic, vol. 27 no. 3, 1998, pp. 217-274. (2) J. van Benthem, Modal logic in two Gestalts, tutorial at LICS and invited lecture at AiML Uppsala 1998, to appear in Advances in modal logic '98, edited by M. de Rijke and M. Zakharyashev, Kluwer, Dordrecht. (3) E. Grädel and I. Walukiewicz, The guarded fragment with fixed points is decidable, RWTH Aachen and informatics Warsaw, 1999.

April 16, 1999
Speaker: Alexander Kechris
Title: Applications of Linear Algebraic Groups to Descriptive Set Theory

March 5, 1999
Speaker: Aldo Antonelli
Title: Free Set Algebras Satisfying Systems of Equations
In this talk we introduce the notion of a set algebra S satisfying a system E of equations. After defining a notion of freeness for such algebras, we show that, for any system E of equations, set algebras that are free in the class of structures satisfying E exist and are unique up to a bisimulation. Along the way, we mention analogues of classical set-theoretic and algebraic properties as well as connections between the algebraic and set-theoretic viewpoints.

February 19, 1999
Speaker: Matthew Foreman
Title: Partition Relations for Successor Cardinals
The classical Ramsey's theorem says that if G is an infinite graph then G contains either an infinite complete subgraph or an infinite independent set. Sierpinski showed that the analogous result fails for graphs of size omega_1.
Erdös and his coworkers investigated a weaker conjecture: If G is a graph on an ordinal of uncountable cardinality then G has either complete subgraphs of all countable order types or independent sets of all countable order types. This was proved (in ZFC) in the early 70's by Baumgartner and Hajnal using forcing.
The situation for successors of uncountable cardinals is much harder. Baumgartner and Hajnal's proof (and its predecessors) heavily uses the measurability of omega, leading to the conjecture that the theorem should hold at the successor of a measurable cardinal.
The talk will survey some recent advances on the problem (done jointly with Hajnal).

February 5, 1999
Speaker: Vaughan Pratt
Title: Chu Spaces: Subject-Predicate Interaction as an Alternative to Relational Structures
We propose Chu spaces as a simple alternative to relational structures having the advantage that topology and duality are not only integral but fundamental to the approach. This application of Chu spaces was found by accident while developing them as a model of concurrency. Chu spaces admit both conventional first order logic and linear logic, which can be understand as respectively their internal and external logics. The latter has a useful overlap with process algebra for true concurrency.

January 22, 1999
Speaker: Charly Bitton
Title: Almost Free Groups
A group G of size lambda is almost free if every subgroup of size less than lambda is free. Our objects of study are almost free groups that are not free. There are many questions one can ask, e.g. for which lambda is there such an object? We will review what is known and not known, old and new, regarding this type of question.

December 4, 1998
Speaker: Alessandro Andretta
Title: Projective Sets and Ordinary Differential Equations
Fix n > 1 and consider a Cauchy problem of dimension n, i.e., a system of n ordinary differential equations with an initial value, namely

(dx_1/dt, ... , dx_n/dt) = F(t, x_1, ... , x_n),
x_1(t_0), ... , x_n(t_0) = a_1, ... , a_n
where F : R x R^n --> R^n is continuous. It is conventional wisdom that it is quite hard to determine whether such a Cauchy problem admits a global solution ( = a solution defined for all t's). A possible explanation is that the set of all Cauchy problems that admit a global solution is Sigma^1_1-complete. In particular it is not Borel.
Restricting the attention to the F's such that for every initial condition there is a global solution won't help: such a set is Pi^1_1-complete.
Finally the collection of Cauchy problems which admit a global solution even if the initial condition is slightly perturbed yields a Pi^1_2-complete set.
(Joint work with A. Marcone.)

November 13, 1998
Speaker: Ilijas Farah
Title: F-sigma Ideals from Tsirelson Spaces
Let X be a Banach space and let {x_n : n in N} be a "nice" (e.g. 1-unconditional) basic sequence in X which converges to 0 in norm. The sets A of integers such that the sequence a_n = x_1 + x_2 + ... + x_n is norm-convergent form an ideal, I(x_n). The question whether one such ideal, I(x_n), is reducible to another, I(y_n), is related to the question whether Y contains an isomorphic copy of X. It is still unclear what is the relationship between a Banach space and ideals which can be represented in it in this way, but this construction has already led us to a better understanding of Borel ideals on the integers and the corresponding quotient structures. We consider these ideals in the case when X is the Banach space not containing a copy of any of the classical spaces c_0 or ell_p (p in [1,infty)), constructed by B. Tsirelson. The deeper understanding of this space achieved during the recent years has led to solutions of several long-standing open problems in Banach space theory. We use Tsirelson's space to answer some questions of G. Hjorth, A. Kechris, and K. Mazur about the reducibility of Borel equivalence relations.

November 6, 1998
Speaker: Thomas Scanlon
Title: One-Based Groups and Arithmetic Algebraic Geometry
The notion of a one-based theory arose from an attempt to characterize the combinatorics of the forking dependence relation in some well-behaved stable theories. In the 1980s Pillay and Hrushovski observed that the hypothesis of one-basedness severely restricts the structure of definable sets for a stable group. In particular, every definable set is a finite boolean combination of cosets of groups. In the early 1990s Hrushovski observed that this fact together with a method for recognizing one-based groups deduced from the machinery of Zariski Geometries implied positive solutions to some outstanding conjectures in diophantine geometry.
I will speak about the development of this notion of one-basedness from the purely logical perspective and then describe some of my own recent work on applying the structure theory of one-based groups to some number-theoretic problems, specifically to the inverse rational dynamics of additive polynomials in positive characteristic (Denis' Manin-Mumford Conjecture for Drinfeld modules).

October 23, 1998
Speaker: Mark Burgin
Title: Logical Varieties and Inconsistent Knowledge Systems
One of the main concepts of the modern logic is that of a logical calculus. However, this construction has definite limitations in many cases. For example, the principal condition that is demanded from any logical calculus is its consistency. At the same time, knowledge about big object domains (in science or in practice) is essentially inconsistent. Consequently, when logic is used for formalization of such knowledge, it is possible to represent only small fragments of the object domain. Otherwise contradictions appear.
To eliminate these limitations in a logically correct way, the concepts of a logical prevariety and variety are introduced. They generalize in a natural way the concept of a logic calculus. Problems of completeness are investigated for logical varieties. An incompleteness theorem for logical varieties having finite weight is proved. The famous Gödel incompleteness theorem is a partial case of this result.
Besides, applications to knowledge representation and non-monotonic inference are considered.

October 9, 1998
Speaker: Ralf Schindler
Title: Nice Sets of Reals and Choice-like Principles
In the constructible universe just the analytic sets of reals are "nice" (are Lebesgue measurable, have the property of Baire, etc.), as there is a Delta^1_2 well-ordering of the reals. Are there inner models in which this situation is lifted to higher levels of the projective hierarchy, i.e., in which the Sigma^1_n sets of reals are nice and there is a Delta^1_{n+1} well-ordering of the reals, for n > 1?
It is well-known that the answer is "yes" under PD. But it is also "yes" (in a strong sense) under the weaker assumption that there is an inner model with infinitely many strong cardinals. The constructions of the relevant models combine "David's trick" in the presence of strong cardinals with a heavy dose of core model theory. (This is joint work with Sy Friedman.)
I also want to discuss recent developments on related questions which may fall under the topic of the talk's title. For instance, Basis(Pi^1_3(x), Delta^1_4(x)) does not imply Delta^1_2(x)-determinacy (for many reals x), even if all projective sets of reals are nice and there are measurable cardinals.
Finally, a comment on the status of the core model theory playing its role here might be in order (this refers to joint work with John Steel).

June 5, 1998
Speaker: Geoffrey Hellman
Title: Predicative Foundations of Arithmetic and Its Challenges
After reviewing the Feferman-Hellman-Aczel recovery of the natural number structure in an Elementary Theory of Finite Sets and Classes (conservative over PA), certain challenges concerning alleged impredicativity of induction and circularity of the construction will be addressed. The relevance of a structuralist viewpoint concerning number systems will be emphasized.

May 29, 1998
Title: Nonstandard Proof of the Jordan Curve Theorem
A transparent proof of the Jordan curve theorem will be presented.

May 15, 1998
Speaker: David Marker
Title: Logarithmic-Exponential Series
The logarithmic-exponential series provide a natural algebraic nonstandard model of the field of real numbers with exponentiation in which one can easily analyze asymptotic behavior of definable functions. I will show how this model can be used to answer a problem of Hardy's. (This is joint work with Angus Macintyre and Lou van den Dries.)

May 8, 1998
Speaker: Sergei Starchenko
Title: On Groups Definable in o-Minimal Structures

May 1, 1998
Speaker: Itay Neeman
Title: The Iterability of K^c
I discuss some recent progress on the question of iterability for models on the K^c construction of Steel's "The Core Model Iterability Problem" (LNL, vol. 8). Ultimately one would like to show outright that these models are iterable. This would allow for such theorems as: Assume PFA and that there exists a measurable cardinal. Then there is an inner model with a super-strong cardinal.
Our ultimate goal then is to show that if a model on the construction fails to be iterable then 0 = 1. Unfortunately current technology falls far short of this goal. For the time being all we can derive from the failure of iterability are inner models with large cardinals in the region of Woodin cardinals (presumably well below 0 = 1). Thus current lower bounds for the consistency strength of "PFA + there exists a measurable cardinal" correspond to those large cardinals which can be obtained from the failure of iterability.
In my talk I'll describe the current level of large cardinals which can be derived from the failure of iterability. The work described is joint with John Steel, and extends results of Steel and Andretta.

April 24, 1998
Speaker: Paul Eklof
Title: Absolutely Rigid Systems
Mark Nadel asked whether there is a proper class of torsion-free abelian groups with the property that no two are L_{\infty\omega}- equivalent, that is, no two become isomorphic in any generic extension of the universe.
His approach to the question involved looking at known constructions of rigid systems (that is, there are no non-zero homomorphisms between distinct groups) to see if they remain rigid in any generic extension of the universe. (We call these absolutely rigid systems.) He showed that this is the case for Fuchs' construction of a rigid system of groups smaller than the first strongly inaccessible cardinal. But he pointed out that other constructions, such as Fuchs' construction of a rigid system for any cardinal less than the first measurable or Shelah's for an arbitrary cardinal, involve non-absolute notions.
In joint work with Shelah, we give a strong affirmative answer to Nadel's original question, but we also show that there are not arbitrarily large absolutely rigid systems. There is an absolutely rigid system of size kappa if and only if kappa is less than the first omega-Erdös cardinal. On the other hand, there exists an absolutely indecomposable group A_lambda for every cardinal lambda, such that for lambda_1 < lambda_2, A_{lambda _1} and A_{lambda_2} are not L_{\infty\omega}-equivalent.

April 10, 1998
Speaker: Frank Wagner
Title: Supersimple Division Rings
It had long been noted that some algebraic structures, in particular pseudo-finite fields, show a behaviour similar to stability. This has recently been explained by Kim and Pillay, who extended the stability-theoretic notion of "forking" to a wider class, that of simple theories, which includes interesting structures such as bounded pseudo-algebraically closed (PAC) fields, or existentially closed fields with an automorphism (in characteristic 0). While a theorem due to Macintyre, Cherlin, and Shelah states that any stable division ring which allows an ordinal rank (i.e., is superstable) is in fact commutative and algebraically closed, the information in the supersimple case is sketchy. We shall show that such a division ring is commutative, and relate this result to the conjecture that it must be PAC.

March 13, 1998
Speaker: Zoe Chatzidakis
Title: The Model Theory of Fields with an Automorphism

February 27, 1998
No Colloquium. Hilary Putnam is delivering the 1998 Reichenbach lecture at 3 p.m. in Dodd 175. His title is Mental Causation.

February 13, 1998
Speaker: Philip Scowcroft
Title: Some New Models for Intuitionistic Analysis
This talk will present new models, for intuitionistic analysis with Kripke's schema, built with the help of techniques invented to alter cardinalities in models of Zermelo-Fraenkel set theory.

January 30, 1998
No Colloquium, because of the VIG '98 Logic Meeting at UCLA.

January 16, 1998
Speaker: Bruno Poizat
Title: A First Course in Mathematical French
This talk is specially designed for the logicians who do not understand French, neither in its American form nor its European variant.
Mathematics is universal: it concerns humanity as a whole; an essential character of humanity is the diversity of its languages. Therefore expression of mathematics, and more generally of sciences, should not be confiscated for the sole profit of the most powerful nation in terms of politics, economics, and armies, and it is advisable to maintain alive a variety of languages for scientific communication.
As we can see from the survival of various minorities in spite of considerable pressures, human beings resent uniformity and intolerance imposed on them. Nevertheless the right to differ is taken into account by the American academic system -- which seldom takes effective steps for the survival of languages other than English -- only in folkloric or irrelevant matters, such as affirmative actions for women, homosexual, ethnic minorities (or majorities!); by "irrelevant" I do not deny that they express a concern for some basic and serious diseases of the American society, but I mean that this concern is applied in a wrong context: I hope that nobody will believe that ability in mathematics is affected by sex, sexual behavior, color of skin or other biological factors. Language is *relevant*, from the obvious fact that mathematicians produce nothing but literature.
The immediate aim of my talk is an exposition of a general model-theoretic version of the Theoreme de Borel-Tits concerning the isomorphisms abstract between the groups algebraic simple.
Theorem 1 (un). Consider(ons) an object infinite V(K) defined in un field algebraically closed K, and un isomorphisme f between V(K) and W(L), another objet defini dans un corps algebriquement clos L. Supposons that f echange les sets constructible de V(K)^n et de W(L)^n for every n. Alors il existe un isomorphisme s entre les corps K et L, so that f se decompose en the transport of structure entre V(K) et V(s(K)) = V(L) induit par s et une application L-definissable de V(L) on W(L).
Theoreme 2 (deux). Supposons que tout ensemble constructible de V(K)^n be definable with parameters dans la structure V(K). Alors: (i) if K is of characteristic zero, une copie de K est definissable without parameters in V(K); (ii) si K est de caracteristique p, une famille finie (K1, ... , Kn) de copies de K est definissable sans parametres dans V(K) .
Corollary 1 (un cas simple de Borel-Tits). Un isomorphisme abstrait, entre deux groupes algebriques simples sur des corps algebriquement clos, se decompose en un transport de structure induit par un isomorphisme entre les deux corps et un morphisme geometrique.
Corollaire 2. Dans un contexte superstable, un groupe connexe definissable d'automorphismes d'un groupe algebrique simple, sur un corps algebriquement clos, est forme d'automorphismes interieurs ( = inner).

December 5, 1997
Speaker: Howard Becker
Title: The Cardinal Number of the Set of Path-Components
This talk is concerned with the following question. Assume CH fails; does there exist a compact set K in R^n such that K has exactly aleph_1 path-components? For R^3, the answer is yes. For R^2, the answer is no, assuming a weak large cardinal axiom. The proof of the R^3 case will be discussed.

November 21, 1997
Speaker: Boban Velickovic
Title: Transfinite Ehrenfeucht-Fraisse Games

November 7, 1997
Speaker: Peter Komjath
Title: Consistency Theorems on Set Mappings (with S. Shelah)
In this talk we consider set mappings of the type f:[kappa]^n --> [kappa]^{< mu} where n is a natural number, and the question is how large a free set can be, i.e., a subset X of kappa with y not in f(x_1,...,x_n) for {y,x_1,...,x_n} in [kappa]^{n+1}. Hajnal and Mate proved that if n = 2, kappa = omega_2, and mu = omega then there are arbitrarily large finite free sets. This was later extended by Hajnal to n = 3, kappa = omega_3.
Theorem (S. Shelah). There are natural numbers t_m such that for every m < omega it is consistent that there is a set mapping f:[omega_m]^4 --> [omega_m]^{< omega} with no free subsets of size t_m.
Theorem (P. Komjath). For every m < omega it is consistent that there is a set mapping f:[omega_m]^2 --> [omega_m]^{< omega} with no infinite free subsets.

October 24, 1997
Speaker: Steven Rudich
Title: Natural Proofs
Joint work with Alexander Razborov:
One way to argue that open problems such as P =? NP are difficult is to demonstrate that known methods are inherently too weak to solve them. This approach was taken in Baker, Gill, and Solovay (BGS) who used oracle separation results for many major complexity classes to argue that relativizing proof techniques could not solve these problems. Since relativizing proof techniques involving diagonalization and simulation were the only available tools at the time of their work (1975) progress along known lines was ruled out.
Instead, people started to look at these problems in terms of Boolean complexity. Along these lines, many (non-relativizing) proof techniques have been discovered and used to prove lower bounds. These techniques are highly combinatorial; they exist in a much larger variety than their recursion-theoretic predecessors. In this talk, we do for the 90's what BGS did for the 70's.
We introduce the notion of a natural proof. We argue that all lower bound proofs known to us in non-monotone Boolean complexity either are natural or can be represented as natural. We show that if a cryptographic hardness assumption is true, then no natural proof can prove superpolynomial lower bounds for general circuits. Furthermore, no complexity class containing good pseudo-random function generators has a natural proof against it. This gives a proof that the restriction methods which were sufficient to prove the parity lower bounds of FSS, Ajtai, Yao, and Hastad are inherently incapable of proving the bounds for AC^0[q]-circuits of Razborov and Smolensky.
Razborov has recently found one application of the notion of natural proof to independence. He has shown that all lower bounds in a certain fragment of arithmetic naturalize in our sense. Thus, on a hardness assumption the question of whether SAT has polynomial sized circuits is independent of this fragment.

October 17, 1997
Speaker: Martin Otto
Title: The Decision Problem for some Logics with Only Two Variables
Some recent variations on the Classical Decision Problem concern logics in the vicinity of FO^2, the fragment of first-order logic in which only two variable symbols are admitted. FO^2 is long known to have the finite model property, and to be decidable. Several slight extensions of FO^2 turn out to be highly undecidable. One very interesting extension, allowing counting quantifiers, however, yields a much more expressive fragment of first-order that is decidable without having the finite model property. (Joint work with E. Grädel and E. Rosen.)

October 3, 1997
Speaker: Andras Hajnal
Title: New Results on Old Problems