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.
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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.) | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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.) | ||||
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. | ||||
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. | ||||
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. | ||||
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). | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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 strength | ||||
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. | ||||
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. | ||||
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.pdf | ||||
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. | ||||
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$. | ||||
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 stable | ||||
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. | ||||
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. | ||||
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 Hoeven | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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". | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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). | ||||
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. | ||||
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. | ||||
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$. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. | ||||
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. |
May 18, 2007
Speaker: John D. Clemens
Title: Subshift Isomorphism is a Universal Countable Borel Equivalence Relation
A subshift on a finite alphabet A is a closed subset of the
space A^Z of bi-infinite sequences from A which is
invariant under the shift map S, where S(x)(n) = x(n+1). Two
subshifts X and Y are isomorphic if there is a homeomorphism from X
to Y which commutes with the shift. Subshifts are a widely-studied class
of dynamical systems, and much is known about their classification up to
isomorphism.
I will show that the isomorphism relation on subshifts is a
universal countable Borel equivalence relation, i.e., it is a countable
Borel equivalence relation such that every other countable Borel
equivalence relation is Borel reducible to it. Hence this classification
problem is quite complicated. As a consequence, we see that the problem of
classifying one-dimensional subshifts up to isomorphism has the same
complexity as the problem of classifying two-dimensional (or higher
dimensional) subshifts up to isomorphism.
May 11, 2007 Note change of date!
Speaker: Joan Rand Moschovakis
Title: Brouwer's Analysis, Markov's Principle and the Church-Kleene Rule
Each of the three main schools of constructive mathematics
(Brouwer's intuitionism, Markov's recursive mathematics, and Bishop's
cautious constructivism) accepts intuitionistic (Heyting) arithmetic HA as
evident, then uses intuitionistic logic to study a (more or less restricted)
class of number-theoretic functions, eventually arriving at a characteristic
theory of real number generators. The resulting intuitionistic, recursive
and constructive analyses have acquired the acronyms INT, RUSS and BISH,
respectively. BISH can be considered as a common subset of RUSS, INT and
CLASS (classical analysis). RUSS accepts a strong form of Church's Thesis
which is inconsistent with classical first-order (Peano) arithmetic PA.
INT is consistent with PA and accepts a classically correct principle of bar
induction, but contradicts CLASS by using a strong axiom of continuous
choice ("Brouwer's Principle") which causes the intuitionistic analytical
hierarchy to collapse at the second level (an early result of Wim Veldman).
Although Brouwer and Bishop preferred to do their constructive
mathematics informally, in order to compare the three approaches -- in
particular, in order to study what can and what cannot be proved in each,
and how much of CLASS can consistently be represented in each without losing
the constructive viewpoint -- a formal treatment is evidently useful.
Heyting [1930] gave the first adequate formalization of intuitionistic
predicate logic; Kleene [1952] set the pattern for formalizing HA as a
subsystem of PA; Kleene and Vesley [1965] formalized INT and proved its
consistency; BISH can be represented (up to a point, since BISH allows the
use of constructive set theory) within Kleene and Vesley's INT by
reinterpreting the sequence variables and trimming the axioms; Troelstra and
van Dalen [1988] suggest formalizing RUSS by adding Markov's Principle and
an extension of Church's Thesis to HA. Each of these theories satisfies
Markov's Rule (which is a way of saying that the integers are standard) and
the Church-Kleene Rule (which guarantees that only recursive functions can
be proved to exist).
Douglas Bridges and his school are now working on the reverse
mathematics of BISH, and Wim Veldman is leading the study of INT from a
similar viewpoint. We give sample results of these two programs, then
discuss the consequences of adding to INT Markov's Principle and/or other
classically correct principles which preserve the Church-Kleene Rule.
April 13, 2007
Speaker: John Krueger
Title: Internally Club and Approachable
Internally approachable structures are a useful tool in set
theory. Various weakenings of internal approachability have been used and
studied; for example, internally club structures are structures which are
the union of an "epsilon-increasing" chain of models. Under some cardinal
arithmetic assumptions, these properties are all equivalent to one
another. On the other hand, it was recently discovered that these
properties are consistently distinct.
March 16, 2007
Speaker: Matthias Aschenbrenner
Title: Asymptotic Differential Algebra
This talk will be an introduction to asymptotic differential
algebra for a general mathematical audience. This subject deals with the
interplay between two approaches to the asymptotic theory of real-valued
functions: on the one hand, Hardy fields; on the other, fields of
transseries. Both have origins in the 19th century, but are closely related
with more recent developments in mathematical logic (o-minimal expansions of
the real field) and analysis (Écalle's solution of the Dulac problem).
March 9, 2007
Speaker: Julien Melleray
Title: Geometry and Dynamics in the Urysohn Space
Urysohn's universal metric space was built by P. S. Urysohn in 1924,
then essentially forgotten for 60 years. I will try to explain why this
space has attracted the attention of mathematicians in recent years; I will
discuss in particular algebraic and topological properties of the isometry
group of this space, and (if time permits) describe some open problems.
March 2, 2007
Speaker: Donald Bamber
Title:
Robust Reasoning with Rules that Have Rare Exceptions
We wish to construct one or more logics for reasoning with rules that
have rare exceptions. Such rules are statements of the type: Nearly
all As are Bs. It is assumed that an informant will assert such a
rule only if the conditional probability P(B | A) is at least 1 - e,
where the threshold parameter e is a small positive quantity whose
value is unknown to us. The approach we take is to define a
nonmonotonic form of entailment in which a conclusion is entailed by
premises if and only if, roughly speaking, nearly all probability
measures that model the premises also model the conclusion. If one
assumes that every rule in our premise set has been asserted by a
single informant, then the resulting logic is equivalent to Pearl's
System Z and Lehmann and Magidor's Rational Closure. However, if the
assumption that all premise rules have been asserted by the same
informant is not correct, then some of our conclusions may not be
justified. We consider a worst-case scenario in which each premise
rule has been asserted by a different informant and each informant
has his own personal threshold parameter, with the values of all
threshold parameters being unknown to us. The logic generated under
this scenario is equivalent to an argumentation system in which a
conclusion is entailed by premises if and only if there exists at
least one argument for the conclusion and every argument against the
conclusion is overridden by some argument for the conclusion. (Joint
work with I. R. Goodman and Hung T. Nguyen.)
February 9, 2007
Speaker: Antonio Montalbán
Title: Embeddability and Decidability in the Turing Degrees.
Computability Theory is the area of logic that studies the concept
of "being computable from." We say that a set, or a problem, is
computable from another one if there is an algorithm that decides
whether an element is in the former set, using the latter set as given
information. This allows us to measure the complexity of sets or of
mathematical problems.
We say that two problems are Turing equivalent if each one can
compute the other one. One of the main goals of computability theory is
to understand the shape of the structure of the Turing degrees. Two
common ways of studying this are by looking at structures that can be
embedded into the Turing degrees and by looking at the decidability of
the theory of this structure, varying the language or taking
substructures.
February 2, 2007
Speaker: Noam
Greenberg
Title:Strongly Jump-traceable Reals and Cost Functions
Various classes of very low degrees, such as the K-trivials, can be
constructed by using cost functions limiting the changes in the set being
approximated. It turns out that the similarity between the
construction methods yields deep connection between the various lowness
notions, as the cost function method is essentially the only way to
construct such degrees.
We give an overview and then discuss a related class, the
strongly jump-traceable reals, which is a proper sub-class of
the K-trivials. In the background lurks an attempt to characterize
lowness classes that arise from algorithmic randomness by
combinatorial means.
January 26, 2007
Speaker: Jan Reimann
Title: The Metamathematics of Algorithmic Randomness
I will discuss some recent work with Theodore Slaman (Berkeley) on the
logical structure of random reals. By relativizing Martin-Löf's test
concept to representations of measures, one can define an algorithmic
notion of randomness with respect to arbitrary (probability) measures
on Cantor space. Instead studying the properties of random reals with
respect to Lebesgue measure, we can now study a `reverse' problem: Which
properties of a real ensure randomness with respect to a reasonably
well-behaved (e.g. non-atomic) measure?
The investigation of this problem reveals interesting relations between
the logical complexity of a real and its randomness properties, for
example, strong ties to Borel determinacy. Furthermore, I will address
possible applications of algorithmic randomness to analysis.
December 1, 2006
Speaker: Jeff Remmel (at 4:00)
Title: Answer Set Programming
Answer Set Programming (ASP) is a formalism that grew out of work on
nonmonotonic logic and logic programming with negation. Recently,
a number of ASP search engines have been developed and these have been
used for various pratical applications. There are a number of variations
of ASP formalism that have led to a number of interesting theoretical
questions. We will survey some recent results in this area.
December 1, 2006
Speaker: Alain Louveau (at 2:00)
Title:The Complexity of Isomorphism between Separable Banach Spaces
It is proved that the relation of isomorphism between separable Banach
spaces is a complete analytic equivalence relation, i.e., that any
analytic equivalence relation Borel reduces to it. The, separable Banach
spaces up to isomorphism provide complete invariants for a great number
of mathematical structures up to their corresponding notion of isomorphism.
November 17, 2006
Speaker: Joan Bagaria
Generic Absoluteness and Combinatorial Properties of Projective Sets of Reals
We will present some exact equiconsistency results on the
absoluteness of the projective theory of the real numbers under some natural
classes of forcing extensions. As an application of these results we will
show, e.g., that in Solovay models the projective sets of reals enjoy
certain strong combinatorial properties.
November 3, 2006
Speaker: Alice Medvedev
Title:Model Theory of Difference Fields
A difference field is a field with a distinguished
automorphism, viewed as a structure for the language of fields with an
additional unary function symbol sigma. The theory of algebraically
closed fields with generic automorphisms, called ACFA, is
model-theoretically tractable; it is a canonical example of a
supersimple theory.
Before talking about my work, I will recall the model theory around
it. I will define and give examples of supersimple theories ,
minimal sets , combinatorial geometries (also known as a
matroid), and non-orthogonality between two minimal sets.
The basic model theory of ACFA was developed by Chatzidakis,
Hrushovski, and others over the last decade. They established the
simplicity of the theory, an analysis of finite-dimensional definable
sets in term of minimal sets, and the Zilber Trichotomy classifying
the combinatorial geometries that arise on minimal sets in ACFA. Some
fine-structure questions had been left open, although their
significance is evident by analogy with differentially closed fields.
My work explores the definability of the three cases of the Zilber
trichotomy for minimal sets defined by formulas of the form
sigma(x) = f(x) for some rational function f, and the definability of
non-orthogonality between two such sets. We show that the group-like
case of the trichotomy is definable. Since it is known that the
field-like case is definable, this makes all three cases of the
trichotomy definable. Indeed, our techniques yield definitions of each
of the three kinds of group cases -- additive, multiplicative, or
elliptic. We also show that non-orthogonality between two given
minimal sets is definable within the multiplicative case but not
within the elliptic case. A generalization of our results to all
minimal sets of sigma-degree one is a possible source of definable
classes of minimal sets closed under non-orthogonality. These would
produce new, model-theoretically interesting theories of difference
fields, in the spirit of Hrushovski and Itai's "On model complete
differential fields."
October 27, 2006
Speaker: Boban Velickovic
Title:Saturation of Aronszajn Trees and Shelah's Conjecture
Given a class of linear orderings K, a basis for K is a list K_0 of
members of K such that any member of K contains an isomorphic copy
of a member of K_0. The class of infinite linear orderings has an
obvious basis consisting of omega and its reverse omega^*. Considering
uncountable linear orderings, one can show in ZFC that any basis has to
have at least five elements. In the 1970s Shelah conjectured that it is
consistent that there be a five-element basis for the uncountable linear
orderings. This conjecture was finally confirmed by J. Moore in 2004.
However, his proof makes considerable use of large cardinals and it is
not clear if they are at all needed.
In this talk I will discuss the notion of saturation of Aronszajn trees
and show that it plays a key role in the proof of Shelah's conjecture.
This allows us to reduce dramatically the large cardinal assumptions
needed in the proof. Finally, we will discuss some open problems in
this area.
This is joint work with B. Koening, P. Larson and J. Moore.
October 6, 2006
Speaker: Pandelis Dodos
Title:A Classification of Separable Rosenthal Compacta and its Consequences
June 2, 2006
Speaker: Antonio Montalbán
Title: Equimorphism Types of Linear Orderings
We analyze the structure of equimorphism types of linear orderings
ordered by embeddability. (Two linear orderings are equimorphic if they
can be embedded in each other.) Our analysis is mainly from the
viewpoints of Computable Mathematics and Reverse Mathematics. But we
also obtain results, such as the definition of equimorphism invariants for
linear orderings, which provide a better understanding of the shape of
this structure in general.
Here are our main results: Spector proved in 1955 that every
hyperarithmetic ordinal is isomorphic to a computable one. We extend
his result and prove that every hyperarithmetic linear ordering is
equimorphic to a computable one. From the viewpoint of Reverse
Mathematics, we look at the strength of Fraisse's conjecture.
From our results, we deduce that Fraisse's conjecture is
sufficient and necessary to develop a reasonable theory of equimorphism
types of linear orderings.
May 26, 2006
Speaker: Justin Moore
Title:
Combinatorics of omega_1
In this talk I will discuss two recent results and one open
problem which concern the combinatorics of omega_1. The theorems are
the following: (1) Assume PFA. The uncountable linear orders have a
five-element basis; (2) There is a hereditarily Lindelof, non-separable
regular topological space. While these results do not overtly mention
the combinatorial properties of omega_1, they have reformulations
which are essentially Ramsey-theoretic statements about the first
uncountable cardinal.
These two theorems represent the two typical outcomes of analysis in
this area: a classification which follows from PFA and a pathological
example which can be constructed without additional axiomatic
assumptions. In this talk I will discuss the combinatorial aspects of
these problems and their relationship to each other. The talk will
finish with an open problem in the area for which the combinatorial
analysis has so far proved elusive.
May 19, 2006
Speaker: Martin Zeman
Title: Progress on Combinatorial Analysis of Extender Models
The study of combinatorial principles in extender models is a
continuation of Jensen's analysis of the combinatorial properties in
G&oml;edel's constructible universe L. Although interesting in its own
right, the knowledge of combinatorics in such models plays an
important role in applications where the constructible universe is
replaced by some extender model, which is necessary if the applications
involve large cardinals incompatible with L. Substantial progress
on developing methods for studying the combinatorics of such models was
made by Schimmerling and myself at the end of 1990's and led to the
characterization of Jensen's principle square_kappa. I will review some
results building on that characterization which were made during the
recent few years and also explain the progress on techniques used in
combinatorial analysis of extender models.
Note that on Friday, May 12, 2006 (3 p.m.), Brian Skyrms is delivering the Reichenbach Lecture at the UCLA Philosophy Department (Dodd 175).
May 5, 2006
Speaker at 4:00 in MS 6627:
Nate Segerlind
Title:On the Sizes of Propositional Proofs
Propositional logic is reasoning about true/false assertions built up from
atomic true/false assertions (variables). A propositional proof system
is an efficiently checkable method for certifying that propositional
statements evaluate to true for all assignments to the variables (that
the statement is a tautology). A fundamental question in the study of
propositional proof complexity is whether or not there is a propositional
proof system P and a constant c > 0 so that for all tautologies tau
written in n symbols there is a P-proof of tau of size at most n^c.
This problem is equivalent to the NP versus coNP problem of computational
complexity, and its negative resolution implies that P is not NP.
Motivated by this connection to computational complexity and an interest
in unconditional results for satisfiability algorithms, there has been
much interest in this problem for specific propositional proof systems.
In this talk, we will discuss results for extensions of the resolution
system. The methods of probabilistic combinatorics enter in two ways.
The first is in the construction of the tautologies which are candidates
for requiring large proofs. The second is a method of converting k-DNFs
into constant height decision trees, by the application of a random
partial assignment to the variables.
May 5, 2006
Speaker at 2:00 in MS 7608:
Stelios
Negrepontis
Title: Schreier Sets in Ramsey Theory
The lecture is based on joint work with V. Farmaki. I will describe how
classical Ramsey theory can be extended by the introduction of families
of Schreier sets for every countable ordinal. Thus Ramsey's, Hindman's,
Milliken-Taylor's theorems, and van der Waerden's, Hales-Jewett's,
Carlson's, and Furstenberg-Katznelson's theorems can be so extended.
By way of applying these results we are currently interested in two
questions, still in the area of speculation; one is a question in
mathematical logic, arising from the Paris-Harrington result, the other
a broad attempt to apply these results to Ramsey ergodic theory.
[1] V. Farmaki, Ramsey and Nash-Williams combinatorics via Schreier
families, arXiv: math FA/0404014
[2] V. Farmaki, S. Negrepontis, Block Combinatorics, Trans. A.M.S.,
January 2006.
[3] V. Farmaki, S. Negrepontis, Schreier sets in Ramsey theory, arXiv:
math.CO/0510102
Note that on Thursday, May 4, 2006 (4 p.m.), Ed Keenan is speaking at the UCLA Mathematical Linguistics Circle, on A Semantic Classification of Natural Language Quantifiers.
April 21, 2006
Speaker: Johan van Benthem
Title: Modal Logics for Space and Knowledge
Spatial interpretations for modal logics go back to Tarski's work in the 1930s.
We will explain the newly emerging interest in this area, but now with modern
modal techniques such as bisimulation games, extended languages, and product
constructions. New modal structures are emerging in topology, affine and metric
geometry, and linear algebra. Next, we cross over to epistemic interpretations,
and show how a topological viewpoint leads to a more sensitive modeling of
'common knowledge' as advocated by Barwise in the mid-1980s. The proper
setting here is fixed-point languages, but now with spatial interpretations.
References:
Marco Aiello, Johan van Benthem, & Ian Pratt-Hartmann, editors,
Handbook of Spatial Logics, Springer, Dordrecht, to appear (2006).
J. van Benthem & G. Bezhanishvili, 2006,
Modal Logics of Space.
Note that Johan van Benthem will also be speaking at the
Mathematical Linguistics Circle
on Thursday, April 20.
April 7, 2006
Speaker: Greg Hjorth
Title:Borel Equivalence Relations
We survey how the theory of Borel equivalence relations has developed
since Harrington-Kechris-Louveau at the end of the 1980's.
February 10, 2006
Speaker: Martin Davis
Title: Gödel: Missed Connections, Alternate Directions
I'll point out a number of ways in which Skolem and Gödel talked past
each other in the early 1930s. Finally, in a more speculative vein, I'll
explore a suggestion Gödel made in his Gibbs Lecture from which he
later decisively distanced himself.
Special event: February 3-5, 2006, Magidorfest at UC, Irvine.
The Day of Algebraic Logic is Tuesday, January 31, in MS 6118.
January 27, 2006
Speaker: Alain Louveau
Title:Countable Quotients for Combinatorial Structures
January 20, 2006
Speaker: Yiannis N. Moschovakis
Title: Recursion and Complexity
My aim is to explain how the faithful representation of algorithms
by systems of recursive equations can be applied to complexity
theory, specifically in the derivation of worst-case lower bounds
which hold for all algorithms from specified givens. I
will use for examples some results in [1] and related, unpublished
joint work with van den Dries on arithmetic complexity,
but, in this lecture, I will put more emphasis on the conceptual
problems which arise in this enterprise: How can you make precise
and prove that to decide R(x) from given functions
g_1, ... , g_m,
you will need at least Kh(x) "calls to the givens,"
no matter which algorithm you use?
[1] Lou van den Dries and Yiannis N. Moschovakis.
Is the Euclidean algorithm optimal among its peers?
The Bulletin of Symbolic Logic, 10: 390-418, 2004.
December 2, 2005
Speaker: Eli Gafni
Title:
Distributed Symmetry-Breaking:
Renaming is Weaker than Set Agreement!
We resolve a problem in distributed computing, open since the discovery
of the connection between distributed computing and topology, back in 1993.
Then, the problems of renaming and set agreement
were proved to be impossible
to solve wait-free in a read-write shared-memory model.
However, the proofs were very different, and the relation
between the problems was left unclear. Moreover, the renaming
impossibility proof relied on non-trivial algebraic topology
techniques.
Our main result is that renaming is strictly weaker than
set agreement.
To prove this impossibility, we design a new model of
computation, that we believe is interesting
by itself. It is the first model we know of where an easy
analysis of the topology of a protocol
that invokes other protocols can be performed, and hence for a general
setting to study reductions. To study reductions between
renaming and set agreement, we identify and study a symmetry
breaking class of tasks, where processes decide on binary
output values. We show that set agreement and renaming are just
variations of symmetry breaking.
Also, we formulate a new version of the celebrated
index lemma, that yields the first elementary
proof of the renaming impossibility proof.
Finally, by exhibiting a symmetry breaking task that is
a symmetric manifold and solves renaming, we pinpoint the difference
between set-agreement and renaming. While the former is impossible
to solve using tasks that are manifolds,
the latter cannot be solved by a task that is an orientable manifold.
Unfortunately read-write memory is an orientable manifold.
Joint work with Sergio Rajsbaum, UNAM
November 18, 2005
Speaker: Assaf Sharon
Title: Reflection of Stationary Sets and the SCH.
November 4, 2005
Speaker: Alex Usvyatsov
Title: Are Different Approaches to Model Theory of Analysis So Different?
I will describe the history of different model theoretical
approaches to studying natural classes arising in functional analysis
and topology, and recent developments showing that once generalized
appropriately, all these approaches converge to the same context.
October 21, 2005
Speaker: Moti Gitik
Title:On the General Behavior of the Power Set Function
October 7, 2005
Speaker: Jean-Yves Béziau
Title: Universal Logic: Towards a General Theory of Logics
In this talk I will outline the basic ideas of universal logic, a
general theory of logics considered as mathematical structures. I will
present the main lines of research of this field and some recent
developments.
June 10, 2005
Speaker: Dominique Lecomte
Title:
Hurewicz-like Tests for Borel Subsets of the Plane
May 27, 2005
Speaker: Stevo Todorcevic
Title:
Universally Meager Sets and Principles of Generic Continuity
and Selection in Banach Spaces
May 20, 2005
Speaker:
Matthew Foreman
Title: Automorphisms of the Measure Algebra
The measure-preserving transformations of the unit interval form a Polish
group. This group acts on the ergodic measure-preserving transformations
by conjugacy, and this action coincides with isomorphism of
measure-preserving transformations. The main result of the talk is that
this equivalence relation is complete analytic and therefore not Borel.
The argument involves randomized cut-and-stack arguments. This is joint
work with D. Rudolph and B. Weiss.
May 6, 2005
Speaker:
Phokion Kolaitis
Title: On Preservation under Homomorphisms in the Finite
Slides in postscript format.
It is well known that many classical results of mathematical logic
about all structures (finite and infinite) fail,
if only finite structures are considered.
The classical preservation-under-homomorphisms theorem asserts that
the existential positive formulas are the only first-order formulas
(up to logical equivalence) that are preserved under homomorphisms
on all structures, finite and infinite.
The aim of this talk is to present an overview of recent
results concerning the status of the preservation-under-homomorphisms
theorem on various classes of finite structures, including the class
of all finite structures over a fixed relational vocabulary
and the classes of all finite graphs of bounded treewidth.
April 22, 2005
Speaker:
Harvey Friedman
Title: Boolean Relation Theory
Boolean Relation Theory is the study of the Boolean relations between sets
and their forward images under multivariate functions. More precisely,
consider (V,K), where V is a natural set of multivariate functions and K is
a natural family of associated one dimensional sets. BRT studies statements
of the form "for all f1,...,fn in V, there exists A1,...,Am in K such that a
given Boolean relation holds between the A's and their forward images under
the f's". Experience shows that the analysis of such statements, even for
small n,m, and basic discrete (V,K), has diverse connections with various
mathematical topics, including large cardinals. We discuss the contents of
my book Boolean Relation Theory, nearing completion.
April 8, 2005
Speaker:
Leo Marcus
Title: Logical Foundations of an Adaptive Security Infrastructure:
Delegation and Response
Current distributed system security mechanisms cannot adapt adequately
to either rapidly changing, or long-term evolution of, threat
environments or system components and architectures. While substantial
effort has been expended to improve the localized adaptability of
individual security mechanisms (e.g., firewalls, network routers,
intrusion detection systems), there is little understanding of the
ramifications of the interactions of such adaptations on the larger
system. We are developing a model-theoretic framework on which to
build a semantics for an "adaptive security infrastructure" (ASI).
The goal is to be able to use this framework and associated semantics
to specify and verify ASI architectures.
Here we discuss some model-theoretic problems that result from two
central issues: "delegation" -- which yields questions of property
composition, and "response" -- which yields questions of model and
theory evolution.
Note that Kit Fine is speaking March 17 (4pm, Dodd 399) and March 18 (3pm, Dodd 161) at the Philosophy Department.
March 11, 2005
Speaker:
Marcus Kracht
Title: Semantics for Modal Predicate Logics
The semantics for modal predicate logics is standardly taken to be
the one proposed by Kripke. Whatever its philosophical merits, it is
mathematically unsatisfactory because it is incomplete. It is not even
the case that if a propositional modal logic L is complete so is its
predicate extension. The first complete semantics has been proposed by
Shehtman and Skvortsov in 1993, building on work by Ghilardi.
Subsequently, this semantics has been greatly simplified. The talk
gives a summary of the development.
March 4, 2005
Speaker:
William Mitchell
Title: Finite Forcing and I[omega_2]
February 18, 2005
Speaker: Vladimir Kanovei
Title: On nonstandard set theories
February 3-6, 2005: There will be a Very Informal Gathering of logicians at UCLA.
January 21, 2005
Speaker:
Zlatan Damnjanovic
Title: On the logical foundations of arithmetic and
the uniqueness of the natural numbers
Philosophically speaking, what is ordinary number theory about?
Does the existence of non-standard models of (first-order) arithmetic
imply that the concept of natural number is in some way indeterminate?
Recent work of Charles Parsons seeks to answer these questions based on
a first-order analysis of Dedekind's famed Categoricity Theorem. This
paper critically examines Parsons's response and outlines a novel
conception of the subject matter of arithmetic which affirms its
determinateness while denying that it is constituted by a uniquely
privileged natural number sequence.
December 10, 2004
Speaker:
Andrés Caicedo
Title: Projective well-orderings and bounded forcing axioms
We show that fine structural inner models for mild large cardinal
hypotheses but below a Woodin cardinal admit forcing extensions where
bounded forcing axioms hold and the reals are projectively well-ordered.
November 19, 2004
Speaker:
Ben Miller
Title: Automorphisms of sigma-complete Boolean algebras
The group of Borel automorphisms of the reals and the group of
non-singular Lebesgue-measurable automorphisms of the reals have a
surprising number of properties in common. One reason for this is that
many problems involving these automorphism groups can be reduced to
questions about infinite permutation groups in certain restricted
languages. This viewpoint simultaneously clarifies the combinatorial
core of the problem at hand, and allows one to see that many properties
of the groups mentioned above are in fact shared by the automorphism
groups of a very wide class of sigma-complete Boolean algebras. This
class includes all complete Boolean algebras and all sigma-algebras on
the reals which contain the Borel sets. We will examine various
examples of this phenomenon.
November 5, 2004
Speaker:
Tony Martin
Title: Gödel's Conceptual Realism.
Gödel is commonly regarded the paradigm of a platonist: of someone
who believes that mathematics is about a realm of independently
existing abstract objects. Gödel certainly is a platonist in this
sense. But his brand of platonism, which he calls "conceptual
realism," has a whole other aspect. For example, Gödel holds that
the truths of mathematics are analytic: that a true mathematical
proposition is true in virtue of the meanings of the terms occurring
in it. This aspect of Gödel's position puts concepts, rather than
objects, to the forefront. I will discuss the relation between the two
aspects of Gödel's realism, and I will try to show that the object
aspect has a smaller role than it is usually taken to have.
October 15, 2004
Speaker:
Paul Eklof
Title: On Set theory applied to Ext theory
We survey some applications of set-theory to the study of the
homological functor Ext. This includes theorems of ZFC proved using
set-theoretic methods, as well as independence results. As time permits,
topics include such ancient ones as Whitehead groups as well as more
recent ones such as the Flat Cover Conjecture and tilting theory.
June 21-25, 2004. Note that the North American Summer School in Logic, Language and Information is being held at UCLA.
June 11, 2004
Speaker:
John Steel
Title: The Proper Forcing Axiom implies determinacy in L(R)
Our most all-purpose method for producing
canonical inner models satisfying large cardinal hypotheses is
the core model induction method. In a core model induction
argument, one produces canonical inner models
which are correct for statements at a given level of complexity,
using core model theory together with the existence of models
which are correct at lower levels. We shall try to convey in
greater detail the structure of such arguments, and illustrate
them by outlining a proof of the theorem quoted in the title.
June 4, 2004. The UCLA Philosophy Department is having its Reichenbach Lecture, given by Charles Parsons, at 3:00 p.m.
May 28, 2004
Speaker: Mack Stanley
Title: The Branch Problem
Abstract in pdf format.
May 14, 2004
Speaker:
Slawomir Solecki
Title: Projective Fraisse Limits and the Pseudo-arc
The talk will be about an application of logic to topology
of indecomposable continua. A continuum is a compact connected space.
A continuum is indecomposable if it is not the union of two proper
subcontinua. The pseudo-arc is a hereditarily indecomposable
continuum, that is, all of its subcontinua are indecomposable. It is,
in a sense, the generic continuum since its homeomorphic copies form a
dense G_delta subset of the space of all continua.
We develop a dualization of the classical Fraisse limit
construction from Model Theory. The dual limit of a class of structures
is a highly homogeneous structure (in the model-theoretic sense) but it
also has a natural metric zero-dimensional topology. We show that after
appropriately moding out the model-theoretic content of the dual
Fraisse limit of a certain class of structures one obtains the
pseudo-arc. Using this connection we are able to transfer results about
automorphisms of the dual Fraisse limit to results about homeomorphisms
of the pseudo-arc. In this fashion, we obtain strengthenings of results
of Mioduszewski and of Lewis and Smith on the pseudo-arc and we
establish a new topological characterization of the pseudo-arc.
This is a joint work with T. Irwin.
May 7, 2004
Speaker:
Aldo Antonelli
Title: First-Order Quantifiers
In this talk we survey a number of results concerning
first-order quantifiers and report on some work in progress. After
briefly introducing generalized quantifiers, we identify some of their
interesting properties and address the issue of their expressive power.
Special attention is paid to a particular dyadic cardinality quantifier
and its properties. Finally, we take up the question of the sense in
which first-order quantifiers, similarly to second-order ones, might be
open to a "non-standard" interpretation.
April 30, 2004
Speaker: Vladimir Uspenskiy
Title: Four Algorithmic Faces of Randomness
Let us consider infinite sequences of zeros and ones.
The classical probability theory fails to distinguish
between random and non-random sequences. The first attempt to do that
is due to von Mises (1919) but it suffered some vagueness. The theory
of algorithms contributed new ideas to the task of defining what an
individual random sequence is.
In fact, a random sequence has at at least four faces.
First, it is stochastic; that means, the sequence
itself as well as any of its reasonable subsequences has the property
of frequency stability. Second, it is chaotic; that
means, it is disordered, i.e., the occurrences of its terms are not
governed by any reasonable rule. Third, it is
typical; that means, it belongs to any reasonable majority.
Fourth, it is unpredictable; that means, one who
gambles on it cannot win by using any reasonable strategy.
All the four formulations use the word "reasonable." In
each of four cases, the theory of algorithms allows one to fill that
word with some exact meaning. So four well-defined classes of
sequences appear. And each of them claims to be the true class of
random sequences. Some of those claims are more justified than
others.
References:
1. A. N. Kolmogorov, and V. A. Uspensky.
Algorithms and randomness.
SIAM J. Theory of Probability and Its Applications, vol. 32 (1987),
pp. 389-412.
2. V. A. Uspensky, A. L. Semenov, and A. Kh. Shen.
Can an individual sequence of zeros and ones be random?
Russian Mathematical Surveys, vol. 45 (1990), no. 1, pp. 121-189.
3. V. Uspensky, and A. Semenov.
Algorithms: Main Ideas and Applications.
Kluwer, 1991. 269 pp.
4. An. A. Muchnik, A. L. Semenov, V. A. Uspensky.
Mathematical metaphysics of randomness.
Theoretical Computer Science, vol. 207 (1998), pp. 263-317.
April 23, 2004
Speaker:
Paolo Mancosu
Title: Tarski on Models and Logical Consequence
In the last fifteen years there has been a heated debate on
exactly what is going on in Tarski's theory of logical consequence.
Since Etchemendy's publications in the eighties, contributions by,
among others, Sher, Ray, Gomez-Torrente, and Bays have provided a
much more detailed picture of Tarski's seminal 1936 paper. However,
this intense focus on the original publication has led to several
disagreements with respect to important interpretative issues related
to Tarski's contribution. One of the bones of contention, and the
only one I will treat in the talk, concerns Tarski's notion of
model, the key element of Tarski's famous definition of logical
consequence. I will argue that Tarski upheld a
fixed-domain conception of model in his 1936 paper and that he was
still propounding it in 1940. Thus, the 1936 conception of logical
consequence is both intensionally and extensionally different from
the one which is nowadays commonly accepted.
March 12, 2004
Speaker:
Ted Slaman
Title: Recursive Measures and Their Random Reals
There is a well-developed theory of effective randomness,
originating with the work of Kolmogorov (1965) [independently
Chaitin (1975)] and Martin-Löf (1966). According to Chaitin and
Kolmogorov, an infinite binary sequence X is random iff each of
its initial segments is difficult to describe. According to
Martin-Löf, X is random iff X does not belong to any effectively
presented set of measure 0. However, the two notions pick out
the same set of sequences as random, and this coincidence is
commonly cited as evidence that they identify a robust and
correct notion of randomness.
Both the Chaitin-Kolmogorov and Martin-Löf formulations of
randomness are naturally equipped with random sets: the Chaitin
Omega-numbers and the Universal Martin-Löf Tests. We will
discuss these objects and recount results of Kuchera and Slaman
(2001) and Merkle, Mihailovich and Slaman (2003) which show that
they are generic examples of random sequences with recursively
enumerable approximations.
We will end with an examination of the coincidence between
descriptive randomness (Chaitin-Kolmogorov) and measure-theoretic
randomness (Martin-Löf). By the following theorem of Reimann
and Slaman, this coincidence is not a truism.
Theorem 1 (Reimann and Slaman). There is a recursive measure mu,
necessarily discontinuous, and a sequence X such that X is
Martin-Löf random relative to mu and yet for every nondecreasing
recursive function f there is an n such that the first f(n)
values of X can be specified by a program of length less than n.
In other words, there is a mu-random sequence on which mu does
not concentrate whose information content is arbitrarily
compressible.
References
Chaitin, G. J. (1975). A theory of program size formally
identical to information theory, J. Assoc. Comput. Mach. 22:
329-340.
Kolmogorov, A. N. (1965). Three approaches to the definition of
the concept "quantity of information", Problemy Peredachi
Informacii 1(vyp. 1): 3-11.
Kuchera, A. and Slaman, T. A. (2001). Randomness and recursive
enumerability, SIAM J. Comput. 31(1): 199-211 (electronic).
Martin-Löf, P. (1966). The definition of random sequences,
Information and Control 9: 602-619.
Merkle, W., Mihailovich, N. and Slaman, T. A. (2003). Some
results on effective randomness. Preprint.
February 27, 2004
Speaker: Christian Rosendal
Title: Incomparable or Minimal Banach Spaces
Using the new methods of Ramsey theory in Banach spaces
developed by Gowers, plus additional tools of descriptive set theory,
we show that any infinite dimensional Banach space contains either a
minimal subspace or a continuum of incomparable subspaces.
February 6, 2004
Speaker: Martin Dowd
Title: Iterating Mahlo's Operation
The principle of "collecting the universe" justifies axioms asserting
the existence of large cardinals which can be "built up" by iterating
Mahlo's operation. In a previous paper, "schemes" were used to
define iterations of length up to kappa^+. This talk gives a method
for defining iterations of length up to kappa^{++}. Assuming GCH,
this is an unsurpassable limit, and the question of what ranks are
achievable is complicated. Results will be given which suggest that
weakly compact cardinals can be built up, and give an idea of their
rank. It will also be argued that the notion of "built up" cardinals
suggests, along with other evidence, that all sets are constructible.
January 23, 2004
Speaker: Itay Neeman
Title: Games of Length omega_1
The pattern of connections between determinacy and large cardinals
suggests that there should be games which capture the theory of
indiscernible Woodin cardinals. We present such games in the talk,
and establish precisely the connection between the games and
iterable models for indiscernible Woodin cardinals. We note that
this connection allows finding definable winning strategies in
closed games of length omega_1, and end with the (open) problem
of constructing such winning strategies "purely", that is using
descriptive set theory rather than large cardinals.
November 21, 2003
Speaker: Berit Givens
Title: The Bohr Topology on Various Abelian Groups
The Bohr topology on an Abelian group is the coarsest topology
that makes all homomorphisms from the group into the unit circle
continuous. In spite of this simple definition, the topology is
very slippery, and I will talk about what it looks like for some
common groups. In addition, I will discuss what is known about
comparing two groups with the Bohr topology and how techniques
from logic have been used in some of the proofs.
November 7, 2003
Speaker: Bernhard König
Title:
Fragments of Martin's Maximum in Generic Extensions
We look at the following three properties of forcing notions,
increasing in strength: weak omega_1-strategic closure (e.g.
forcing a square sequence), strong omega_1-strategic closure,
and omega_1-closure (e.g. Cohen subset of omega_2).
It turns out that each type has different impact when forcing
over a model of MM. Some new consistency results can be
obtained with this.
October 24, 2003
Speaker: Andrew Arana
Title: Degree Complexity of Models of Arithmetic
and Connections with Independence Results
In his 1958 paper, "Mathematical Significance of Consistency
Proofs", G. Kreisel asked whether model-theoretic independence proofs
for arithmetic could be made constructive by using recursive models of
arithmetic. In 1959, S. Tennenbaum gave a negative answer for
first-order Peano Arithmetic (PA), by showing that no nonstandard model
of PA is recursive. This result suggested a battery of other questions
about the Turing complexity of models and complete extensions of PA.
We will survey work in this area, from the late 1950s through today.
We will focus on a line of questioning in this area instigated by
C. Jockusch, who asked for a characterization of the degrees of models
of True Arithmetic (the theory of the standard model of PA), and of
other specific complete extensions of PA. R. Solovay answered
Jockusch's questions, in theorems made widely known by J. Knight.
Knight asked later whether Solovay's theorems could be simplified in
any of three natural ways. We discuss why these simplifications are
impossible. Our discussion rests on some independence results that are
useful here and in other contexts, so we will discuss these results as
well.
October 10, 2003
Speaker: Matthew Foreman
Title: Has the CH been Settled?
May 30, 2003
Speaker: Edward Keenan
Title: Excursions in Natural Logic
Working with generalized quantifiers (GQs) we study some novel
entailment paradigms in English determined by the "4-group" of negation
operators {identity, complement, post-complement, dual}. For example
the paradigm in (1) is novel, even cute, in that Qx.A and Qx.notA are
not logically equivalent when Q = 'for all' or 'there exists'.
(1) a. Exactly half the students passed
b. Exactly half the students didn't pass
The GQs that can replace 'exactly half the students' are just those
fixed by the post-complement operator. We characterize this set, whose
members are more numerous than (1) might suggest. The second paradigm
we study is illustrated in (2):
(2) a. More than two thirds of the students read at least as many
poems as plays
b. Less than a third of the students read
fewer poems than plays
We characterize the pairs of GQs that enter this paradigm in terms of
"Facing Negations". For both paradigms we characterize the permutation
invariant GQs in the paradigm. We note that the paradigms naturally
apply to a variety of non-first order definable quantifiers.
May 23, 2003
Speaker: Jindrich Zapletal
Title: Descriptive Set Theory and Definable Forcing
This is an overview of a book accepted to the Memoirs of the
AMS. I will show the basic ideas connecting the iterations
of definable proper forcing with descriptive set theory, and
quote and explain the main theorems of the book.
May 16, 2003. No Logic Colloquium, but note that Krister Segerberg is speaking at the Philosophy Colloquium.
May 9, 2003
Speaker: Jiri Wiedermann
Title: A Formal Model of Fuzzy Computations
Fuzzy Turing machines and fuzzy languages were introduced by Zadeh, Lee
and Santo in the 1970s. Unfortunately, it appears that from a
computability point of view, their model is too powerful -- its
nondeterministic version accepts non-recursively enumerable fuzzy
languages. Moreover, from the viewpoint of modern fuzzy logic theory,
the model is too restrictive since it is defined only for a specific
t-norm (the Gödel norm). Therefore, we propose a generalization of the
original model that is based on rigorous mathematical fundamentals of
fuzzy logic. Its acceptance criterion is modified so that the resulting
model obeys the Church-Turing Thesis. Fuzzy Turing machines then
accept exactly the enumerable languages with partially computable fuzzy
membership functions. The results open the way for simulating fuzzy
computations by any other device obeying this thesis. However, the
intended use of the model is in computability and complexity-theoretic
investigations aiming at the power, limits and efficiency of fuzzy
computations, rather than in design of efficient fuzzy algorithms.
April 25, 2003
Speaker: Martin Davis
Title: Gödel's Developing Platonism
April 18, 2003
Speaker: Johan van Benthem
Title: Rational Dynamics: the Logical Structure in Games
Logicians have used special games for a long time already
when studying expressive power or argumentation structure.
But there is also a logical structure to games in the more
general sense of game theory. Games may be analyzed as
interactive processes in dynamic, temporal, or linear
logics, linking up with concerns in computer science.
On top of that, deliberations and decisions by players
in the course of such a process can be modelled in epistemic
logics, linking up with key issues in philosophical logic.
Many of the current contacts between logic and game theory
have to do with explaining the emergence and stability of
game-theoretic equilibria in terms of epistemic assumptions,
and there are important results to this effect by authors
like Aumann and Stalnaker. In this talk, we propose a new
twist. We analyze game-theoretic equilibria as arising in
the limit from repeated announcements by players of their
rationality -- a bit like the way in which the Muddy Children
arrive at enlightenment through repeated assertion of their
status. This idea can be made precise in dynamic logics of
information update. More technically, this analysis leads
to connections between different notions of game equilibrium
and different fixed-point logics: monotonic or inflationary.
Literature
'Logic in Games', 1999 ->, electronic lecture notes
in progress, ILLC, Amsterdam: see the home pages
http://staff.science.uva.nl/~johan/Teaching/
and more general info on
http://www.illc.uva.nl/lgc/
'Extensive Games as Process Models'. Journal of Logic,
Language and Information 11 (2002), 289-313.
'Rational Dynamics and Epistemic Logic in Games',
ILLC Tech report, January 2003,
http://www.illc.uva.nl
April 4, 2003
Speaker: Wayne Richter
Title: Inductive Definability
Inductively defined sets are formed by repeatedly applying an
inductive operation until closure is reached. The study goes back to
Kleene's systems of notations for the constructive ordinals. The
general theory is concerned with the relationship between, on the one
hand the form of an inductive operator, and on the other hand the form
of the set and closure ordinal defined by that operator. Inductively
defined sets provide "recursive analogs" of small, large cardinals.
Of special interest is the relationship between monotone and
nonmonotone inductive definability.
The subject has applications in proof theory and finite model
theory. The talk should be accessible to beginning graduate students.
February 28, 2003
Speaker: Marcus Kracht
Title: Reduction Functions
The finite model property and decidability are typically shown in modal
logic via filtration of the canonical model. This method is highly
nonconstructive. Another method is the tableau method, which has the
disadvantage that completeness is difficult to show. We shall present
a third way, by means of reduction functions, which establishes in a
uniform way finite model property, decidability and interpolation
(wherever applicable). Also, the best known space complexity bounds
can be obtained with it. The core of the method is to reduce
derivability of a formula P in an axiomatic extension L to derivability
in K from a set of theorems of L that need to be found a priori on the
basis of P.
February 7, 2003
Speaker: Paul Larson
Title: The Canonical Function Game
The canonical function game is a definable game of length omega_1
indentified by Hugh Woodin which falls inside a class of games known as
Neeman games. It turns out that this game is consistently undetermined.
I will discuss this result and its relationship to some major open
questions in set theory.
January 31, 2003
Speaker: Alain Louveau
Title: Dichotomy Results for Analytic Graphs
We will present some dichotomy results about analytic
(directed and undirected) graphs, which involve the ordering of Borel
homomorphic reducibility, and generalize a dichotomy of Kechris,
Solecki, and Todorcevic about the Borel chromatic number of such
graphs.
January 24-26, 2003, there will be a Very Informal Gathering of logicians at UCLA in honor of the 65th birthday of Yiannis N. Moschovakis.
January 10, 2003
Speaker: Richard Ketchersid
Title: Comparing Boolean(Pi^0_3) Cardinals is Hard
Abstract: An early result in the theory of Borel equivalence relations
on R states that for each S included in P(omega) there is an associated
Pi^0_3 (later improved to Sigma^0_2) equivalence relation E_S such that
E_S leq E_T iff T - S is finite (under AD). This shows that the Pi^0_3
"real" cardinals are a mess, but left open the question of how
complicated the reducibility relation "leq" is among Borel
equivalence relations.
I will give Boolean(Pi^0_3) equivalence relations E and E_x (uniformly
for x in R) so that {x : E leq E_x} is complete Sigma^2_1, i.e., as
complicated as possible. All this is done under "AD^+ + V = L(P(R))."
Similar results where one restricts the notion of reduction can be
obtained using less determinacy. Moreover, it seems plausible that
Boolean(Pi^0_3) should be replaced by Pi^0_3 or even Pi^0_2, but I do
not see how to do this.
November 22, 2002
Speaker: Kai Wehmeier
Title: A Metalogical (?) Argument in Frege
In the context of the recent resurgence of interest in the logical
system of Frege's Grundgesetze der Arithmetik (1893/1903),
originating with work by George Boolos, Terence Parsons, and Peter
Schroeder-Heister in the 1980's, it has become clear that we have a
somewhat poor understanding of the exact nature of Frege's project. In
particular, there is some debate as to whether metalogic plays any
substantial role in it. Two passages in Grundgesetze
appear to lend a great deal of support to the claim that it does,
namely, section 10, containing the 'permutation argument' by means of
which Frege attempts to show that he can safely identify the truth
values with certain sets (the 'identifiability thesis'), and sections
29-32, containing an attempted proof that every begriffsschrift term
denotes. In my talk, I shall focus on the permutation argument and try
to show that the standard, metalogical interpretation is untenable. I
shall advocate a 'mathematical' interpretation, first suggested by
Thomas Ricketts, instead. This interpretation has the advantage of
allowing a consistent model-theoretic reconstruction according to which
both the permutation argument and the identifiability thesis are
valid.
November 15, 2002
Speaker: Burkhard Englert
Title: Lower Bounds on the Shared Memory Requirements
for Long-lived and Adaptive Objects
Recently, several different long-lived adaptive algorithms whose
operation step complexity is a function of the actual number of
processors running concurrently with the operation execution, have been
presented. Regardless of the type of adaptiveness and the type of
object implemented, they require Omega(N) MWMR registers in their
implementation, where N is the total number of processors that
may participate in the implementation. We show that this is a
necessity. We furthermore show that even if the maximum allowed
concurrency m is a constant and m < d, where d is the number of
MWMR registers used, that for any such d there exists n_d, such
that every long-lived adaptive read/write implementation of collect and
renaming with n_d processors must use at least d MWMR registers.
This is joint work with Eli Gafni.
November 8-9, 2002: The Philosophy Department presents the Rogers Albritton Commemoration.
November 1, 2002
Speaker: Wai Yan Pong
Title: Finiteness Principles for Monomial Ideals and their
Applications
I will present some "finiteness" results on monomial ideals. The
main tool used here is the theory of Noetherian orders. This turns out
to have some interesting applications to differential algebra. In
particular, one can derive a model theoretic rank called the
differential order which generalizes the notion of the order of a
differential equation.
October 26, 2002 (Saturday): There will be a Logical Constants workshop at UC Irvine.
October 18, 2002
Speaker: Marcus Kracht
Title: The Lattice of Modal Logics
Unlike in predicate logic, there is no simple reduction from axiomatic
extensions to the basic logic. Thus, in modal logic one must be
interested in the totality of all logics. They form a lattice, whose
structure has been studied throughout the last 25 years. A principal
tool is the notion of a splitting, which proved to be of central
importance in trying to establish not only the structure of the lattice
itself, but also in solving many genuine logical problems. In this
talk I shall give an overview of the principal results concerning the
lattice of modal logics and present some open problems.
June 7, 2002
Speaker: Michael Rathjen
Title: The Axiom of Choice in Constructive Set Theory
The axiom of choice does not have an unambiguous status in
constructive mathematics. On the one hand it is said to be an
immediate consequence of the constructive interpretation of the
quantifiers. Any proof of
forall x in a, exists y in b, phi(x,y)
must yield a function f : a --> b such that
forall x in a, phi(x,f(x)).
This is certainly the case in Martin-Löf's intuitionistic
theory of types. On the other hand, from the very earliest days, the
axiom of choice has been criticised as an excessively non-constructive
principle even for classical set theory. Moreover, it has been
observed that the full axiom of choice cannot be added to systems of
constructive set theory without yielding constructively unacceptable
cases of excluded middle. On the other hand, it has been shown by
Peter Aczel that constructive set theory has a canonical interpretation
in Martin-Löf's type theory and that this interpretation also
validates several choice principles, e.g., the axiom of countable
choice and the axiom of dependent choices. The main aim of the talk is
to present joint work with Sergei Tupailo in which we give a
characterization of a restricted class of set-theoretic statements
realizable in Martin-Löf type theory. This class contains all the
statements that figure in ordinary mathematics. The realizable
statements turn out to be those provable in an extension of CZF via the
so-called Pi-Sigma-axiom of choice.
June 1-4, 2002, the ASL meeting in Las Vegas is held.
May 31, 2002
Speaker: Lefteris M. Kirousis
Title:
Review of the Results on the Approximation of the 3-SAT Threshold
Consider the space of uniformly random 3-CNF Boolean formulas phi
with density (clauses to variables ratio) r. Computer experiments
performed by several researchers starting a decade ago suggest that
there exists a number r_3 around 4.2 such that if r < r_3 then the
probability that phi is satisfiable has limit 1, as the number
variables n becomes large, whereas this limit is 0, if r > r_3. This
0-1 or phase transition phenomenon has also been corroborated by
methods of Statistical Physics (the replica method). Mathematically,
it has been proved that there exists a sequence of intervals
I_n = 3D(a_n, b_n), whose lengths approach 0, such that the
probability of satisfiability of a random 3-CNF formula has limit 0 if
its density r < a_n and has limit 1 if r > b_n. However, the existence
of a threshold number r_3 is still an open problem. On the other
hand, increasingly larger values l_3 < 4.2 and increasingly smaller
values u_3 > 4.2 have been found such that the probability of
satisfiability is almost 1 for r < l_3 and is almost 0 for r > u_3.
Some of these upper and lower threshold-bound results will be
reviewed.
May 17, 2002
Speaker: Rosalie Iemhoff
Title: The Provability Logic of Constructive Theories
The provability predicate of an arithmetical theory T is a
predicate in the language of T which, when applied to the code of a
formula, expresses that that formula is provable in T. Already the
second incompleteness theorem by Goedel shows that T cannot prove
everything that is true about this predicate; the sentence expressing
that T is consistent is such an example. The provability logic of T
consists of all (propositional) schemes that T does prove about its
provability predicate.
On the classical side provability logics are well investigated.
A remarkable thing is their stability; many classical theories, like
for example Peano Arithmetic and set theory ZF, have the same
provability logic, the decidable modal logic GL. On the constructive
side much less is known. For example, no r.e. axiomatization of the
provability logic of Heyting Arithmetic, the constructive counterpart
of Peano Arithmetic, is known, and it is not even known if it exists.
However, over the last few years significant parts of this logic have
been characterized and for the first time there is a reasonable
conjecture what the axiomatization of this provability logic actually
might be. In the talk I will give an overview of the main results in
this area.
May 3, 2002
Speaker: Derrick DuBose
Title: Determinacy and Sharps
We shall discuss some determinacy results concerning
classes within the difference hierarchy on co-analytic sets.
April 26, 2002
Speaker: Tetsuya Ishiu
Title: Club Guessing Sequences and Filters
S. Shelah proved under ZFC that for every regular
uncountable cardinal kappa, there exists a sequence which "guesses" all
closed unbounded sets in kappa. Such a sequence is called a club
guessing sequence and has been used to prove various theorems. Also we
can construct filters naturally associated with club guessing
sequences. These filters have some interesting properties, too. In
this talk, I would like to present basic facts and new results on these
objects.
April 19, 2002. No Logic Colloquium, but note that the UCLA Philosophy Department is having its Reichenbach Lecture, given by Michael Friedman.
April 12, 2002
Speaker: Jouko Väänänen
Title: Some Results in Infinitary Logic
I will give a survey of recent work in infinitary logic based on
the use of transfinite games and set-theoretic properties of trees.
April 5, 2002
Speaker: Juliette Kennedy
Title:
Some Results in Classical Model Theory Based on Transfer Principles
We study universality of regular reduced powers of first order
structures and get positive results under GCH or just a transfer
principle. Under GCH (or less) we can also prove that regular
ultrapowers of elementary equivalent structures are isomorphic,
improving earlier results by Keisler and Shelah. This is joint
work with Saharon Shelah.
March 15, 2002. No Logic Colloquium, but Charles Parsons is speaking at the UCLA Philosophy Colloquium, 3pm.
March 8, 2002
Speaker: Albert Visser
Title: Logics for Provability and Interpretability
March 1, 2002
Speaker: Benedikt Löwe
Title: Variants of Blackwell Determinacy
February 1, 2002
Speaker: Victor W. Marek
Title:
Some Applications of Universal Algebra to Semantics of
Nonmonotonic Logics
(joint work with M. Denecker, KU Leeuven, Belgium and
M. Truszczynski, University of Kentucky)
We prove a number of results on operators in lattices. These results
are used to revisit the issue of connections between leading formalisms
in nonmonotonic reasoning: logic programming with stable semantics,
autoepistemic logic and default logic. For each logic we develop a
comprehensive semantic framework. This framework is based on a family
of operators in suitably chosen lattices. These operators represent
constructions introduced in each of these domains independently. It
turns out that all three formalisms become closely related when these
semantics are properly aligned.
Abstracting from the operators used in these formalisms, we study
approximations of operators in lattices by means of operators in the
product lattice. It turns out that, with a suitably chosen ordering,
every operator possesses a best approximation. These approximations
generalize constructions such as the 3-valued T_P operator of Fitting
and the van Gelder operator for computation of alternating fixpoint.
January 11, 2002
Speaker: Tomek Bartoszynski
Title: Perfectly Meager Sets of Reals
A set of reals is perfectly meager if it is meager inside every
perfect set. I will discuss several results concerning the properties
of these sets.
December 7, 2001
Speaker: Harvey Friedman
Title: Boolean Relation Theory
Boolean relation theory is simply the study of the Boolean relations
between one-dimensional sets and their images under multivariate
functions. This study naturally leads to a variety of statements
equivalent to the 1-consistency of Mahlo cardinals of finite order,
even in concrete settings in the integers which are subject to known
quantifier elimination. In addition, there are classifications of
large finite families of such statements (as to truth value) which can
be proved to be correct with and only with the use of Mahlo cardinals
of finite order. A complete proof of the forward direction will be
given. Ideas from the reversal will be sketched.
November 30, 2001
No colloquium, because of the
Ruthfest
at the Philosophy Department.
November 16, 2001
Speaker: Boban Velickovic
Title: Long Ehrenfeucht-Fraïssé Games and Forcing
We consider Ehrenfeucht-Fraïssé games of uncountable length
between first-order structures and relate this to the existence of
certain forcing notions which make the two structures isomorphic. In
particular, we show that it is consistent to have two structures which
are L_{\infty,\omega_1} equivalent but they cannot be made isomorphic
by a sigma-closed poset consisting of partial isomorphisms. The
construction involves a special kind of a gap-1 morass.
November 2, 2001
Speaker: James Cummings
Title: Scales and Squares
We discuss some problems in combinatorial set theory which
involve successors of singular cardinals, and show that ideas from PCF
theory are relevant to their solution. In particular we discuss the
role of two canonical stationary sets, the "good points" and the
"approachable points."
October 19, 2001
Speaker: Martin Zeman
Title: The Current State of Combinatorial Analysis
of Extender Models
October 5, 2001
Speaker: John Clemens
Title: Conjugacy of Borel Automorphisms
I will discuss the difficulty of determining when two Borel
automorphisms of a Polish space are isomorphic, i.e., conjugate via
another Borel automorphism. By using the theory of definable
equivalence relations, we can show that this is a very complicated
equivalence relation. We can also view this as showing that we can not
find "simple" invariants which completely characterize the isomorphism
class of a given Borel automorphism.
June 8, 2001
Speaker: Slawomir Solecki
Title: Descriptive Set Theory and Continua
May 25, 2001
Speaker: Peter Cholak
Title: The Latest News about the Computably Enumerable Sets
As partially suggested by the title, this talk will focus on
the latest (exciting) results of Leo Harrington and the speaker on the
computably enumerable sets.
May 4, 2001
Speaker: Steve Jackson
Title: A New Kind of Pathological Set
We answer a question posed by Steinhaus by showing that
there is a set in the plane meeting every isometric copy of the
integer lattice in exactly one point. Numerous questions remain
open.
April 20, 2001: No colloquium, due to the AMS set theory meeting in Las Vegas the next day.
April 6, 2001
Speaker: Simon Thomas
Title: Countable Borel Equivalence Relations
and the Classification Problem for
Torsion-free Abelian Groups of Finite Rank
I will discuss some recent contributions to the project
of explaining why no satisfactory system of complete invariants
has been found for the classification problem for torsion-free
abelian groups of finite rank. The talk will include a discussion
of where this problem is situated within the descriptive
set-theoretic context of countable Borel equivalence relations.
March 16, 2001
Speaker: Robert Solovay
Title: Consistency Strength of Some Variants of NFU
The system of set theory, New Foundations, proposed by Quine is still
not known to be consistent. Some years ago, Jensen formulated a slight
variant of NF, NFU, which is demonstrably consistent. I have been
computing the consistency strength of some variants of NFU and they
turn out to be surprisingly strong. One, NFUA, has the approximate
consistency strength of a Mahlo cardinal. Another, NFUB has the
approximate consistency strength of a weakly compact cardinal.
The main focus of this talk will be on a third variant, NFU*, whose
consistency strength is approximately Sigma_2-replacement.
March 2, 2001
Speaker: G. Aldo Antonelli
Title: The Second-Order Propositional Theory of Two S5 Modalities
(Joint work with Rich Thomason, University of Michigan)
After introducing and motivating a poly-modal version of S5 with
propositional quantifiers, we consider the decidability problem for
such a language. We show that the language is quite expressive, indeed
equivalent to full second-order logic (under the standard
interpretation). This is in contrast to the case of one S5 modality
with propositional quantifiers, which is decidable (as proved
independently by Kit Fine and David Kaplan).
February 16, 2001
Speaker: Richard Ketchersid
Title:
On the Strength of omega_1-Dense Ideals on omega_1
I will outline how to get non-tame mice from the existence of an ideal
on omega_1 which is slightly stronger than an omega_1-dense ideal.
This puts the consistency strength of such an ideal somewhere past
"There is a proper class of strong cardinals the least of which is a
limit of Woodin cardinals."
February 2, 2001
Speaker: Eli Gafni
Title:
Uniform Protocols and a Design Methodology for Adaptive Algorithms
We propose a new meaning that one can attach to the notion that a
sequence of tasks T_1, T_2, ... is solvable. While the celebrated
Herlihy-Shavit conditions characterize when T_i is solvable, they may
give rise to a distinct protocol Pi_i to solve each task T_i. We
introduce the notion of a uniform protocol to capture the requirement
that the whole sequence is solvable by a single protocol.
We argue that this notion captures the recently researched
notion of one-shot adaptive protocols. Adaptive protocols have been
defined via step-complexity notions. By regarding adaptive protocols
as a special case of uniform protocols, where the latter involve
computability questions rather than complexity questions, we are able
to bring to bear all the topological machinery developed for such
questions, and completely characterize when is a task solvable
uniformly or adaptively. Furthermore, we motivate a simple sufficient
conditions for a task to be solved adaptively. These sufficient
conditions result in a methodology to develop adaptive algorithms. We
employ the methodology to develop a new adaptive immediate-snapshot
algorithm of complexity O(k^2) (compared with the current best of
O(k^3)), where k is the number of processors actually active in the
protocol.
January 19, 2001
Speaker: Drew Moshier
Title: Multi-lingual Sequent Calculi: Proof Theory and Topology
We introduce Gentzen-style sequent calculi where the formulas on the
left and right of the turnstile need not come from the same logical
system. In such calculi, sequents can be seen as consequences between
different domains of reasoning. We discuss the ingredients of proof
theory needed to set up calculi generalized in this fashion. The
result is the category MLS (multi-lingual sequent calculus) in which
the morphisms are generalized calculi and objects are calculi that
capture "domain internal" reasoning.
To develop a semantic theory for MLS, we turn to spectral theory,
showing that the MLS objects give rise to spectra (spaces of prime
filters) that are, up to homeomorphism, exactly the locally compact,
strongly sober spaces (aka Nachbin spaces). Such spaces, studied first
by Nachbin in the 1940's, are arguably the natural T_0 generalizations
of compact Hausdorff spaces. The morphisms of MLS correspond to
"continuous relations" between these spaces. In turn, a continuous
relation from X to Y corresponds to a continuous function from X to the
Smyth powerdomain of Y. Thus we establish category equivalences: MLS
to N^* (the category of Nachbin spaces and continuous relations) and
MLS to the Kleisli category for the Smyth powerdomain monad on N
(Nachbin spaces and continuous functions).
Several useful topological concepts, such as the Hausdorff condition,
zero-dimensionality, functionality of a relation, and properness of a
function (f^-1 preserves the "well-below" relation on opens), have
interesting characterizations within MLS as proof-theoretic properties
of the corresponding sequent calculi. As time allows, we will discuss
some of these characterizations and demonstrate how proofs within MLS
of familiar topological results shed light on the topological concepts
involved.
December 1, 2000
Speaker: Burkhard Englert
Title: Lattice Embeddings into the Computably Enumerable Degrees
The decidability of the two-quantifier theory of the partial order of
computably enumerable degrees R is still one of the major open problems
in computability theory. Since one can easily verify that for every
finite lattice L, there is a two-quantifier sentence phi such that L
is embeddable in R if and only if phi is true in R, the
characterization of all finite lattices embeddable into R has been of
particular interest to researchers (lattice embedding problem). In
this talk we will first survey the current status of this problem. We
will then present a condition that is necessary and sufficient for the
embeddability of a finite lattice without critical triples preserving
greatest element.
November 3, 2000
Speaker: Carlos Uzcátegui
Title: Analytic Topologies over Countable Sets
I will present in this talk some results of joint work with
S. Todorcevic about analytic topologies. A topology T over the natural
numbers is said to be analytic if T as a subset of the Cantor cube is
an analytic set. Some motivations for studying analytic topologies:
(1) Descriptive set theoretic aspect: The study of analytic topologies
is a continuation of what has been done for analytic filters (or
ideals) over countable sets. For instance: complexity of topologies
and their generating families, Baire measurability.
(2) General topological aspects: Most natural examples of countable
topological spaces found in the literature are analytic. Many
questions involving convergence are frequently questions about
countable spaces with an analytic topology.
The general goal is to make the connection between descriptive set
theoretic properties and purely topological properties of a given space
more explicit.
October 13, 2000
Speaker: Michael Beeson
Title: Logic and Computation: Putting Mathematics on a Computer
Today there exist computer programs which can perform algebra and
calculus (computation), and there also exist programs which attempt to
find proofs of theorems. But the former get wrong answers because they
have no logical capabilities, and the latter can't prove anything very
interesting, because they have no computational abilities, and can't
remember what they proved yesterday.
The talk will explain a suitable theoretical framework for the
integration of logic and computation, and discuss how that framework
has been implemented in two programs: MathXpert and Weierstrass. The
former does computation without logical errors, and the latter finds
proofs involving computations.
Mathpert is a symbolic-computation program designed with education as
the primary purpose. It can produce step-by-step solutions, not just
one-line answers, and keeps track of logical conditions to ensure that
the steps, and hence the answers, are correct.
Weierstrass can prove various specific functions are continuous, such
as f(x) = x^3, sqrt(x), or sin(x). (Previously the best that
theorem-provers could do was the continuity of a linear function.) It
can also prove that e is irrational, a nontrivial theorem which might
occur in an upper-division number theory course.
June 9, 2000
Nonstandard time and room: 2:00pm, MS 7608
Speaker: Abbas Edalat
Title: Foundation of a Computable Solid Modelling
Link to gzipped paper.
Solid modelling and computational geometry are based on classical
topology and geometry in which the basic predicates and operations,
such as membership, subset inclusion, union and intersection, are not
continuous and therefore not computable. But a sound computational
framework for solids and geometry can only be built in a framework
with computable predicates and operations. In practice, correctness
of algorithms in computational geometry is usually proved using the
unrealistic Real RAM machine model of computation, which allows
comparison of real numbers, with the undesirable result that correct
algorithms, when implemented, turn into unreliable programs. Here, we
use a domain-theoretic approach to recursive analysis to develop the
basis of an effective and realistic framework for solid modelling.
This framework is equipped with a well-defined and realistic notion of
computability which reflects the observable properties of real solids.
The basic predicates and operations on solids are computable in this
model which admits regular and non-regular sets and supports a design
methodology for actual robust algorithms. Moreover, the model is able
to capture the uncertainties of input data in actual CAD situations.
May 26, 2000
Speaker: James Hardy
Title: On the Interpretation of Variables
May 5, 2000
Speaker: Alain Louveau
Title: Covering of Compact Sets
April 21, 2000
Speaker: Arnold Beckmann
Title: Model-theoretic Characterizations of
the Separation Problem of Bounded Arithmetic
Link to paper.
Bounded arithmetic is designed to characterize low complexity
computability, i.e., the polynomial hierarchy. The main open
problem for bounded arithmetic is the question if bounded
arithmetic is finitely axiomatizable, which is equivalent to
asking if the levels of bounded arithmetic S^i_2, T^i_2 collapse.
Furthermore, this question is also connected to the open
problem whether the polynomial hierarchy collapses. The
precise connection is that bounded arithmetic is finitely
axiomatized if and only if bounded arithmetic can prove that
the polynomial hierarchy collapses [Buss 1995].
In this talk we will give model-theoretic characterizations
of the separation problem of bounded arithmetic. The main
tool will be restricted consistency statements, whose
complexity is captured by a bounded analog of Pi_1. Our
characterizations will be as the following one:
Two levels of bounded arithmetic -- say S^i_2 vs. T^j_2 for
j >= i -- are separated by a bounded Pi_1 sentence if and
only if there exists a model of the smaller theory (i.e.,
S^i_2) without proper bounded-elementary extensions to a
model of the stronger theory (i.e., T^j_2).
Remark for experts: By "bounded Pi_1" we mean the universal
closure of Pi^b_1, and "bounded-elementary extensions" is the
restriction of elementary extensions to sharply bounded formulas.
April 14, 2000
Speaker: André Nies
Title: Global Properties of Degree Structures
We investigate degree structures induced by many-one reducibility and
Turing reducibility on the computably enumerable (c.e.) sets, the
arithmetical sets, and all subsets of the natural numbers. We ask
which subsets of the degree structure are automorphism bases: For
instance, the minimal degrees form an automorphism base of the c.e.
many-one degrees, but not for the other two degree structures based on
many-one reducibility. Furthermore, we discuss whether a copy of
(N,+,x) can be defined without parameters in the structure, and
whether the structure is a prime model of its theory.
April 7, 2000
Speaker: Phokion G. Kolaitis
Title: The Complexity of Minimal Satisfiability Problems
A dichotomy theorem for a class of decision problems is a result
asserting that certain problems in the class are solvable in polynomial
time, while the rest are NP-complete. The first remarkable such
dichotomy theorem was proved by T. J. Schaefer in 1978. It concerns
the class of generalized satisfiability problems SAT(S), whose input is
a CNF(S)-formula, i.e., a formula constructed from elements of a fixed
set S of generalized connectives using conjunctions and substitutions
by variables.
In this talk, we first review Schaefer's dichotomy theorem and then
present some new results concerning the class of minimal satisfiability
problems MINSAT(S), where S is a fixed set of generalized connectives.
The input to such a problem is a CNF(S)-formula and a satisfying truth
assignment; the question is to decide whether there is another
satisfying truth assignment that is strictly smaller than the given
truth assignment with respect to the coordinate-wise partial order on
truth assignments. Minimal satisfiability problems were first studied
by researchers in artificial intelligence while studying the
computational complexity of propositional circumscription. Our main
result is that a dichotomy theorem holds for the class of all MINSAT(S)
problems, where S is a finite set of generalized connectives.
Moreover, we give simple criteria that tell apart the polynomial-time
solvable cases of MINSAT(S) from the NP-complete ones.
This is joint work with Lefteris M. Kirousis of the University of Patras.
March 3, 2000
Speaker: Theodore A. Slaman
Title: Definability in the Turing Degrees
A set of natural numbers B is Turing reducible to another set A iff
there is an effective algorithm to determine which numbers belong to B
when given complete information about A. Here is a simple example:
{n : 2n is in A and 2n+1 is not in A} is recursive in A
The Turing degrees are the equivalence classes of the induced
equivalence relation, and are naturally ordered by Turing
reducibility. We use D to denote this partial ordering.
The hierarchies of definability as represented by their universal sets
and their associated collections of definable sets have natural images
in D as degrees and ideals. We will discuss the extent to which these
degrees and ideals are intrinsic to D: which are invariant under
automorphisms of D and which are first-order definable in D.
We will pay particular attention to the Turing jump, which maps the
degree x of a set X of natural numbers, to the degree x' of the halting
problem relative to X.
Theorem (Slaman-Shore, 1999)
The function x maps to x' is definable in D.
The audience will find that this theorem has a checkered past, but that
the line of inquiry has an interesting future.
Note: On Thursday February 24, Matthew Foreman will speak at the UCLA Mathematics Colloquium.
February 11, 2000
Speaker: Philip Welch
Title: On Gupta-Belnap Revision Theories of Truth
Revision Theories of Truth have been developed by Herzberger,
Belnap, and Gupta to give an alternative model to Kripke's of a theory
of truth for languages in which there is a (classically or otherwise)
defined truth predicate. In such schemes the extension of a truth
predicate is successively revised or "improved." This has been
broadened in a recent book of Belnap and Gupta to include a general
theory of circular definitions.
We classify the complexity of such concepts as stably true
or categorical in such schemes (which can be non-absolute
between different models of set theory); thereby raising some
mathematically based queries concerning their status. The discussion of
which revision rule to adopt at limit ordinals (amongst the three
theories of the authors above) is seen to be irrelevant when it comes
to revision-theoretically definable predicates -- which are seen to
include also the predicate of stable truth.
We argue that these theories are better considered
as extensions to the theory of inductive definability, rather than
actual theories of truth.
January 28, 2000
Speaker: Lajos Soukup
Title: On Weak Freese-Nation Property of Boolean Algebras
A partial ordering P has the weak Freese-Nation (wFN) property if there
is a mapping f : P -> [P]^omega such that for any p, q in P with p \le q
there is r in f(p) \cap f(q) such that p \le r \le q.
In the Cohen model, (P(omega), \subset) has the wFN-property.
We study the consequences of the wFN property of (P(omega), \subset).
Under this assumption, we prove that most of the known cardinal
invariants including all of those appearing in Cichon's diagram take
the same value as in the corresponding Cohen model.
If a cBA has the wFN property then it should satisfy the c.c.c. We
prove that GCH does not decide whether every c.c.c. cBA has the wFN
property. We also investigate the relationship between the wFN
property of different cBAs.
January 14, 2000
Speaker: Su Gao
Title: On the Classification of Countable Boolean Algebras
We consider the question: How many countable Boolean algebras
are there up to isomorphism? The best possible answer in the
terminology of 1900 is that there are continuum many. However,
with the theory of equivalence relations developed in the last
decade we can answer the question in a much stronger way.
In this talk I will survey some results about the isomorphism
relation for countable Boolean algebras and some applications
of these results to other related algebraic and topological
equivalence relations. This is joint work with R. Camerlo.
December 3, 1999
Speaker: Donald Bamber
Title:
Reasoning with Fallible Rules: A Second-Order Probability Approach
This talk describes a logic founded on two basic ideas.
First, motivated by the fact that most rules in rule-based systems
have exceptions, Adams' high-probability semantics was adopted. In
this semantics, a rule "If A then B" is interpreted as meaning that
the conditional probability of B given A is close to one.
Second, it was desired to have a logic that would produce (a) many
inferences having a small probability of error rather than (b) only a
few inferences having no possibility of error. Consequently, the
Bacchus-Grove-Halpern-Koller inference criterion was adopted. With
this criterion, a conclusion is inferred from a set of premises if,
roughly speaking, nearly all models of the premises are models of the
conclusion. To implement this quasi-Bayesian approach to inference,
Adamsian probability models were represented as vectors in Euclidean
space and a uniform prior probability distribution over models was
employed.
The resulting logic is equivalent to a logic of Lehmann and Magidor
and nearly equivalent to logics of Goldszmidt and Pearl.
November 19, 1999
Speaker: Norman Danner
Title: Capturing Function Classes with the Lambda Calculus
One of the first results regarding Church's untyped lambda calculus is
that, relative to an appropriate encoding of the natural numbers,
exactly the total recursive functions are representable. Much of the
power of the untyped calculus arises from its (intentional) failure to
distinguish between function and argument (i.e., the same term can be
used in both capacities). A typing discipline for the lambda calculus
reinstates this distinction, and when a typing discipline is imposed,
the collection of representable numeric functions decreases
dramatically.
In this talk, I will survey some of the main typing disciplines and
their corresponding classes of representable functions. I will start
with so-called simple typing, characterized by Schwichtenberg and
Statman in the late 60's, and work through to some recent results of
Daniel Leivant and myself on systems of ramified polymorphism.
November 12, 1999
Speaker: Péter Komjáth
Title: Simultaneous Chromatic Number
November 5, 1999
Speaker: Chris Pollett
Title: Strengths and Weaknesses of LH Arithmetic
One way to quantify the difficulty of P = NP problem would be to
exhibit a logical theory which is capable of formalizing current
attempts at answering this question and yet which is not powerful
enough to prove or disprove this equality. Razborov has argued that
most current circuit lower bound techniques can be formalized in a
fragment of arithmetic which roughly has induction on NE-predicates.
Nevertheless, exhibiting any fragment of arithmetic which one can
demonstrate cannot prove the collapse of the polynomial hierarchy is
nontrivial. In this talk we will consider a much weaker theory than
Razborov's, but which we argue can still do some interesting
mathematics. Namely, it can "reason" about all the functions in the
log-time hierarchy, it can prove the log-time hierarchy differs from
NP, and, in fact, we give some evidence it might be able to show the
log-time hierarchy is infinite. (In the real world this is known to be
true.) On the other hand, we show this theory cannot prove the
polynomial hierarchy collapses. So, in particular, it cannot prove
P = NP, and it follows that any proof that the polynomial hierarchy
collapses, if such a proof exists, must be formalized in a stronger
fragment than ours.
October 22, 1999
No colloquium.
Fefermans at UC Irvine
October 8, 1999
Speaker: Jindrich Zapletal
Title: Open-Point Games of Transfinite Length
June 11, 1999
Speaker: Slawomir Solecki
Title: Translation Invariant Ideals on Abstract Groups
May 28, 1999
Speaker: John Steel
Title: A Mouse-Eye View of L(R)
We formulate a correctness conjecture for mice (i.e., canonical
inner models) whose iteration strategies are in L(R). We prove that
the relativized-to-a-real form of this conjecture holds for all reals
of sufficiently large Turing degree.
May 14, 1999
Speaker: Herbert Enderton
Title: Theories of Equality
The theory of equality is the set of valid sentences with no
non-logical symbols at all (so there are no function symbols,
and the only predicate symbol is equality). The first-order
theory of equality is too simple to be of interest. The
second-order theory of equality is too complex to be of interest.
This talk will focus on intermediate ground.
April 30, 1999
Speaker: Lorenz Halbeisen
Title: The Dual-Ramsey Property for Sets of Partitions
A set S of infinite subsets of N is called Ramsey iff there exists
an infinite subset of N such that each or none of its infinite
subsets belongs to S. If we replace the set of infinite subsets of
N by the set of infinite partitions of N, we get the following
notion: A set T of infinite partitions of N is called dual-Ramsey
iff there exists an infinite partition X such that each or none of the
infinite partition coarser than X belongs to T.
Even though one gets a lot of results for the dual-Ramsey property
which are symmetric to the corresponding results for the Ramsey
property, e.g. each property is equivalent to the Baire property in
some topology, there are also some asymmetries and several questions
are open.
April 23, 1999
Speaker: Johan van Benthem
Title: Guarded Quantifiers:
Renewing the Search for Decidable Fragments
Logicians have long studied decidable fragments of first-order logic.
These should preferably be well behaved in other respects too, such as
having a good model theory and proof theory. We propose a new
direction here, inspired by modal logic, using a systematic analysis of
quantifier bounds. The result are large "guarded fragments" that are
decidable, and have a nice metatheory based on suitable notions of
bisimulation. We will show how guarded analysis works, and discuss
some recent results -- as well as open questions. A useful intuition
here is that of "logical dynamics": quantifiers are actions that jump
to new states, subject to certain constraints. Undecidability then
lurks once we get to parallel, rather than just sequential, quantifier
action.
References:
(1) H. Andréka, J. van Benthem, and I. Németi,
Modal logics and bounded fragments of predicate logic,
Journal of philosophical logic,
vol. 27 no. 3, 1998, pp. 217-274.
(2) J. van Benthem, Modal logic in two Gestalts,
tutorial at LICS and invited lecture at AiML Uppsala 1998, to appear in
Advances in modal logic '98, edited by
M. de Rijke and M. Zakharyashev, Kluwer, Dordrecht.
(3) E. Grädel and I. Walukiewicz, The guarded fragment with
fixed points is decidable, RWTH Aachen and informatics Warsaw, 1999.
April 16, 1999
Speaker: Alexander Kechris
Title:
Applications of Linear Algebraic Groups to Descriptive Set Theory
March 5, 1999
Speaker: Aldo Antonelli
Title: Free Set Algebras Satisfying Systems of Equations
In this talk we introduce the notion of a set algebra S satisfying
a system E of equations. After defining a notion of freeness for such
algebras, we show that, for any system E of equations, set algebras
that are free in the class of structures satisfying E exist and are
unique up to a bisimulation. Along the way, we mention analogues of
classical set-theoretic and algebraic properties as well as connections
between the algebraic and set-theoretic viewpoints.
February 19, 1999
Speaker: Matthew Foreman
Title: Partition Relations for Successor Cardinals
The classical Ramsey's theorem says that if G is an infinite graph
then G contains either an infinite complete subgraph or an infinite
independent set. Sierpinski showed that the analogous result fails for
graphs of size omega_1.
Erdös and his coworkers investigated a weaker conjecture: If G
is a graph on an ordinal of uncountable cardinality then G has either
complete subgraphs of all countable order types or independent sets of
all countable order types. This was proved (in ZFC) in the early 70's
by Baumgartner and Hajnal using forcing.
The situation for successors of uncountable cardinals is much harder.
Baumgartner and Hajnal's proof (and its predecessors) heavily uses the
measurability of omega, leading to the conjecture that the theorem
should hold at the successor of a measurable cardinal.
The talk will survey some recent advances on the problem (done jointly
with Hajnal).
February 5, 1999
Speaker: Vaughan Pratt
Title: Chu Spaces: Subject-Predicate Interaction as an
Alternative to Relational Structures
We propose Chu spaces as a simple alternative to relational
structures having the advantage that topology and duality are not only
integral but fundamental to the approach. This application of Chu
spaces was found by accident while developing them as a model of
concurrency. Chu spaces admit both conventional first order logic and
linear logic, which can be understand as respectively their internal
and external logics. The latter has a useful overlap with process
algebra for true concurrency.
January 22, 1999
Speaker: Charly Bitton
Title: Almost Free Groups
A group G of size lambda is almost free if every subgroup of size less
than lambda is free. Our objects of study are almost free groups that
are not free. There are many questions one can ask, e.g. for which
lambda is there such an object? We will review what is known and not
known, old and new, regarding this type of question.
December 4, 1998
Speaker: Alessandro Andretta
Title: Projective Sets and Ordinary Differential Equations
Fix n > 1 and consider a Cauchy problem of dimension n, i.e., a system
of n ordinary differential equations with an initial value, namely
November 13, 1998
Speaker: Ilijas Farah
Title: F-sigma Ideals from Tsirelson Spaces
Let X be a Banach space and let {x_n : n in N} be a "nice" (e.g.
1-unconditional) basic sequence in X which converges to 0 in norm. The
sets A of integers such that the sequence a_n = x_1 + x_2 + ... + x_n
is norm-convergent form an ideal, I(x_n). The question whether one
such ideal, I(x_n), is reducible to another, I(y_n), is related to the
question whether Y contains an isomorphic copy of X. It is still
unclear what is the relationship between a Banach space and ideals
which can be represented in it in this way, but this construction has
already led us to a better understanding of Borel ideals on the
integers and the corresponding quotient structures. We consider these
ideals in the case when X is the Banach space not containing a copy of
any of the classical spaces c_0 or ell_p (p in [1,infty)), constructed
by B. Tsirelson. The deeper understanding of this space achieved
during the recent years has led to solutions of several long-standing
open problems in Banach space theory. We use Tsirelson's space to
answer some questions of G. Hjorth, A. Kechris, and K. Mazur about the
reducibility of Borel equivalence relations.
November 6, 1998
Speaker: Thomas Scanlon
Title: One-Based Groups and Arithmetic Algebraic Geometry
The notion of a one-based theory arose from an attempt to characterize
the combinatorics of the forking dependence relation in some
well-behaved stable theories. In the 1980s Pillay and Hrushovski
observed that the hypothesis of one-basedness severely restricts the
structure of definable sets for a stable group. In particular, every
definable set is a finite boolean combination of cosets of groups. In
the early 1990s Hrushovski observed that this fact together with a
method for recognizing one-based groups deduced from the machinery of
Zariski Geometries implied positive solutions to some outstanding
conjectures in diophantine geometry.
I will speak about the development of this notion of one-basedness
from the purely logical perspective and then describe some of my
own recent work on applying the structure theory of one-based
groups to some number-theoretic problems, specifically to the inverse
rational dynamics of additive polynomials in positive characteristic
(Denis' Manin-Mumford Conjecture for Drinfeld modules).
October 23, 1998
Speaker: Mark Burgin
Title: Logical Varieties and Inconsistent Knowledge Systems
One of the main concepts of the modern logic is that of a logical
calculus. However, this construction has definite limitations in many
cases. For example, the principal condition that is demanded from any
logical calculus is its consistency. At the same time, knowledge
about big object domains (in science or in practice) is essentially
inconsistent. Consequently, when logic is used for formalization of
such knowledge, it is possible to represent only small fragments of
the object domain. Otherwise contradictions appear.
To eliminate these limitations in a logically correct way, the
concepts of a logical prevariety and variety are introduced. They
generalize in a natural way the concept of a logic calculus. Problems
of completeness are investigated for logical varieties. An
incompleteness theorem for logical varieties having finite weight is
proved. The famous Gödel incompleteness theorem is a partial case
of this result.
Besides, applications to knowledge representation and non-monotonic
inference are considered.
October 9, 1998
Speaker: Ralf Schindler
Title: Nice Sets of Reals and Choice-like Principles
In the constructible universe just the analytic sets of reals are
"nice" (are Lebesgue measurable, have the property of Baire, etc.), as
there is a Delta^1_2 well-ordering of the reals. Are there inner
models in which this situation is lifted to higher levels of the
projective hierarchy, i.e., in which the Sigma^1_n sets of reals are
nice and there is a Delta^1_{n+1} well-ordering of the reals, for
n > 1?
It is well-known that the answer is "yes" under PD. But it is also
"yes" (in a strong sense) under the weaker assumption that there is an
inner model with infinitely many strong cardinals. The constructions
of the relevant models combine "David's trick" in the presence of
strong cardinals with a heavy dose of core model theory. (This is
joint work with Sy Friedman.)
I also want to discuss recent developments on related questions
which may fall under the topic of the talk's title. For instance,
Basis(Pi^1_3(x), Delta^1_4(x)) does not imply Delta^1_2(x)-determinacy
(for many reals x), even if all projective sets of reals are nice and
there are measurable cardinals.
Finally, a comment on the status of the core model theory playing
its role here might be in order (this refers to joint work with John
Steel).
June 5, 1998
Speaker: Geoffrey Hellman
Title: Predicative Foundations of Arithmetic and Its Challenges
After reviewing the Feferman-Hellman-Aczel recovery of the natural number
structure in an Elementary Theory of Finite Sets and Classes
(conservative over PA), certain challenges concerning alleged
impredicativity of induction and circularity of the construction will be
addressed. The relevance of a structuralist viewpoint concerning number
systems will be emphasized.
May 29, 1998
Speaker: Vladimir Kanovei
Title: Nonstandard Proof of the Jordan Curve Theorem
A transparent proof of the Jordan curve theorem will be
presented.
May 15, 1998
Speaker: David Marker
Title: Logarithmic-Exponential Series
The logarithmic-exponential series provide a natural algebraic
nonstandard model of the field of real numbers with exponentiation in
which one can easily analyze asymptotic behavior of definable
functions. I will show how this model can be used to answer a problem
of Hardy's.
(This is joint work with Angus Macintyre and Lou van den Dries.)
May 8, 1998
Speaker: Sergei Starchenko
Title: On Groups Definable in o-Minimal Structures
May 1, 1998
Speaker: Itay Neeman
Title: The Iterability of K^c
I discuss some recent progress on the question of iterability for
models on the K^c construction of Steel's "The Core Model Iterability
Problem" (LNL, vol. 8). Ultimately one would like to show outright
that these models are iterable. This would allow for such theorems as:
Assume PFA and that there exists a measurable cardinal. Then there is
an inner model with a super-strong cardinal.
Our ultimate goal then is to show that if a model on the construction
fails to be iterable then 0 = 1. Unfortunately current technology
falls far short of this goal. For the time being all we can derive
from the failure of iterability are inner models with large cardinals
in the region of Woodin cardinals (presumably well below 0 = 1). Thus
current lower bounds for the consistency strength of "PFA + there
exists a measurable cardinal" correspond to those large cardinals
which can be obtained from the failure of iterability.
In my talk I'll describe the current level of large cardinals which
can be derived from the failure of iterability. The work described is
joint with John Steel, and extends results of Steel and Andretta.
April 24, 1998
Speaker: Paul Eklof
Title: Absolutely Rigid Systems
Mark Nadel asked whether there is a proper class of torsion-free
abelian groups with the property that no two are L_{\infty\omega}-
equivalent, that is, no two become isomorphic in any generic
extension of the universe.
His approach to the question involved looking at known constructions
of rigid systems (that is, there are no non-zero homomorphisms between
distinct groups) to see if they remain rigid in any generic extension of
the universe. (We call these absolutely rigid systems.) He showed that
this is the case for Fuchs' construction of a rigid system of groups
smaller than the first strongly inaccessible cardinal. But he pointed
out that other constructions, such as Fuchs' construction of a rigid
system for any cardinal less than the first measurable or Shelah's for
an arbitrary cardinal, involve non-absolute notions.
In joint work with Shelah, we give a strong affirmative answer to
Nadel's original question, but we also show that there are not
arbitrarily large absolutely rigid systems. There is an absolutely
rigid system of size kappa if and only if kappa is less than
the first omega-Erdös cardinal. On the other hand, there exists
an absolutely indecomposable group A_lambda for every cardinal
lambda, such that for lambda_1 < lambda_2, A_{lambda _1} and
A_{lambda_2} are not L_{\infty\omega}-equivalent.
April 10, 1998
Speaker: Frank Wagner
Title: Supersimple Division Rings
It had long been noted that some algebraic structures, in particular
pseudo-finite fields, show a behaviour similar to stability. This has
recently been explained by Kim and Pillay, who extended the
stability-theoretic notion of "forking" to a wider class, that of
simple theories, which includes interesting structures such as bounded
pseudo-algebraically closed (PAC) fields, or existentially closed
fields with an automorphism (in characteristic 0). While a theorem due
to Macintyre, Cherlin, and Shelah states that any stable division ring
which allows an ordinal rank (i.e., is superstable) is in fact
commutative and algebraically closed, the information in the
supersimple case is sketchy. We shall show that such a division ring
is commutative, and relate this result to the conjecture that it must
be PAC.
March 13, 1998
Speaker: Zoe Chatzidakis
Title: The Model Theory of Fields with an Automorphism
February 27, 1998
No Colloquium. Hilary Putnam is delivering the 1998 Reichenbach
lecture at 3 p.m. in Dodd 175. His title is
Mental Causation.
February 13, 1998
Speaker: Philip Scowcroft
Title: Some New Models for Intuitionistic Analysis
This talk will present new models, for intuitionistic analysis with
Kripke's schema, built with the help of techniques invented
to alter cardinalities in models of Zermelo-Fraenkel set theory.
January 30, 1998
No Colloquium, because of the
VIG '98 Logic Meeting at UCLA.
January 16, 1998
Speaker: Bruno Poizat
Title: A First Course in Mathematical French
This talk is specially designed for the logicians who do not understand
French, neither in its American form nor its European variant.
Mathematics is universal: it concerns humanity as a whole; an essential
character of humanity is the diversity of its languages. Therefore
expression of mathematics, and more generally of sciences, should not
be confiscated for the sole profit of the most powerful nation in terms
of politics, economics, and armies, and it is advisable to maintain
alive a variety of languages for scientific communication.
As we can see from the survival of various minorities in spite of
considerable pressures, human beings resent uniformity and intolerance
imposed on them. Nevertheless the right to differ is taken into
account by the American academic system -- which seldom takes effective
steps for the survival of languages other than English -- only in
folkloric or irrelevant matters, such as affirmative actions for women,
homosexual, ethnic minorities (or majorities!); by "irrelevant" I do
not deny that they express a concern for some basic and serious
diseases of the American society, but I mean that this concern is
applied in a wrong context: I hope that nobody will believe that
ability in mathematics is affected by sex, sexual behavior, color of
skin or other biological factors. Language is *relevant*, from the
obvious fact that mathematicians produce nothing but literature.
The immediate aim of my talk is an exposition of a general
model-theoretic version of the Theoreme de Borel-Tits concerning the
isomorphisms abstract between the groups algebraic simple.
Theorem 1 (un). Consider(ons) an object infinite V(K) defined in un
field algebraically closed K, and un isomorphisme f between V(K)
and W(L), another objet defini dans un corps algebriquement clos L.
Supposons that f echange les sets constructible de V(K)^n et de
W(L)^n for every n. Alors il existe un isomorphisme s entre les
corps K et L, so that f se decompose en the transport of structure
entre V(K) et V(s(K)) = V(L) induit par s et une application
L-definissable de V(L) on W(L).
Theoreme 2 (deux). Supposons que tout ensemble constructible de
V(K)^n be definable with parameters dans la structure V(K). Alors:
(i) if K is of characteristic zero, une copie de K est definissable
without parameters in V(K);
(ii) si K est de caracteristique p, une famille finie (K1, ... , Kn)
de copies de K est definissable sans parametres dans V(K) .
Corollary 1 (un cas simple de Borel-Tits). Un isomorphisme abstrait,
entre deux groupes algebriques simples sur des corps algebriquement
clos, se decompose en un transport de structure induit par un
isomorphisme entre les deux corps et un morphisme geometrique.
Corollaire 2. Dans un contexte superstable, un groupe connexe
definissable d'automorphismes d'un groupe algebrique simple, sur un
corps algebriquement clos, est forme d'automorphismes interieurs
( = inner).
December 5, 1997
Speaker: Howard Becker
Title: The Cardinal Number of the Set of Path-Components
This talk is concerned with the following question. Assume CH fails;
does there exist a compact set K in R^n such that K has exactly
aleph_1 path-components? For R^3, the answer is yes. For R^2, the
answer is no, assuming a weak large cardinal axiom. The proof of the
R^3 case will be discussed.
November 21, 1997
Speaker: Boban Velickovic
Title: Transfinite Ehrenfeucht-Fraisse Games
November 7, 1997
Speaker: Peter Komjath
Title: Consistency Theorems on Set Mappings
(with S. Shelah)
In this talk we consider set mappings of the type
f:[kappa]^n --> [kappa]^{< mu}
where n is a natural number, and the question is how large a free set
can be, i.e., a subset X of kappa with y not in f(x_1,...,x_n)
for {y,x_1,...,x_n} in [kappa]^{n+1}. Hajnal and Mate proved that
if n = 2, kappa = omega_2, and mu = omega then there are
arbitrarily large finite free sets. This was later extended by Hajnal
to n = 3, kappa = omega_3.
Theorem (S. Shelah). There are natural numbers t_m such that for
every m < omega it is consistent that there is a set mapping
f:[omega_m]^4 --> [omega_m]^{< omega}
with no free subsets of size t_m.
Theorem (P. Komjath). For every m < omega it is consistent that
there is a set mapping
f:[omega_m]^2 --> [omega_m]^{< omega}
with no infinite free subsets.
October 24, 1997
Speaker: Steven Rudich
Title: Natural Proofs
Joint work with Alexander Razborov:
One way to argue that open problems such as P =? NP are difficult is
to demonstrate that known methods are inherently too weak to
solve them. This approach was taken in Baker, Gill, and Solovay (BGS)
who used oracle separation results for many major complexity classes to
argue that relativizing proof techniques could not solve these
problems. Since relativizing proof techniques involving
diagonalization and simulation were the only available tools at the
time of their work (1975) progress along known lines was ruled out.
Instead, people started to look at these problems in terms of
Boolean complexity. Along these lines, many (non-relativizing) proof
techniques have been discovered and used to prove lower bounds. These
techniques are highly combinatorial; they exist in a much larger
variety than their recursion-theoretic predecessors. In this talk, we
do for the 90's what BGS did for the 70's.
We introduce the notion of a natural proof. We argue that
all lower bound proofs known to us in non-monotone Boolean
complexity either are natural or can be represented as natural. We
show that if a cryptographic hardness assumption is true, then no
natural proof can prove superpolynomial lower bounds for general
circuits. Furthermore, no complexity class containing good
pseudo-random function generators has a natural proof against it. This
gives a proof that the restriction methods which were sufficient to
prove the parity lower bounds of FSS, Ajtai, Yao, and Hastad are
inherently incapable of proving the bounds for AC^0[q]-circuits of
Razborov and Smolensky.
Razborov has recently found one application of the notion of natural
proof to independence. He has shown that all lower bounds in a certain
fragment of arithmetic naturalize in our sense. Thus, on a hardness
assumption the question of whether SAT has polynomial sized circuits is
independent of this fragment.
October 17, 1997
Speaker: Martin Otto
Title: The Decision Problem for some Logics with
Only Two Variables
Some recent variations on the Classical Decision Problem concern logics
in the vicinity of FO^2, the fragment of first-order logic in which
only two variable symbols are admitted. FO^2 is long known to have the
finite model property, and to be decidable. Several slight extensions
of FO^2 turn out to be highly undecidable. One very interesting
extension, allowing counting quantifiers, however, yields a much more
expressive fragment of first-order that is decidable without having the
finite model property. (Joint work with E. Grädel and E. Rosen.)
October 3, 1997
Speaker: Andras Hajnal
Title: New Results on Old Problems