Ever since Lindstom's `little' theorem: a "$-axiomatizable theory which is categorical in some infinite cardinality is model complete, there have been questions about weaker conditions on an À<sub>1</sub>-categorical theories that imply it is model complete. We will review some of the history of this problem and report the latest result: Theorem (Baldwin-Holland). The finite rank expansions of an algebraically closed field obtained by the Hrushovski construction are model complete. Moreover, this holds for such expansions of any strongly minimal set which admits `exactly k-independent formulas.

Given a finite set C of finite connected graphs, which we declare to be "forbidden graphs," we say that a graph is C-free if it contains no subgraph isomorphic to one in the set C. We ask whether there is a countable C-free graph in which all countable C-free graphs embed. This is then a "countable universal graph with (specified) forbidden subgraphs". In the graph theoretic literature one finds various cases treated, notably the case of a single forbidden graph, where results of some substantial generality have been achieved. It is reasonable to ask whether the problem as formulated here can be solved in full generality. In particular one may ask whether the problem, as a whole, is decidable or not. Both practical experience and a model theoretic analysis suggest that this problem is intimately connected with one whose combinatorial content is considerably clearer: the local finiteness of a closure operation associated with the set C. These decision problems remain open also in the case of a single constraint graph, though I would argue that in this case, at least, it should be decidable.

>From a purely model theoretic point of view, each constraint class C also determines a canonical first order theory, and the original graph theoretic problem can be reformulated in terms of the "smallness" of this theory; our more combinatorial version corresponds to À₀-categoricity of the theory. Other natural model theoretic issues, lacking a clear motivation in graph theory, have not been addressed to date.

We discuss some applications of set-theoretic methods to representation theory, in particular to tilting theory. For any R-module M, let M^{^} denote {N:Ext_R¹(M,N)=0}. A module T is called a (1-) tilting module if T^{^} is precisely the class of all homomorphic images of some direct sum of copies of T. The fact that T^{^} is closed under direct sums allows one to prove in ZFC some results which are otherwise independent. In particular, one can prove in some circumstances that T^{^} is definable, in the sense of Crawley-Boevey (joint work with S. Bazzoni and J. Trlifaj). In the talk, we focus on a key set-theoretic lemma which derives from earlier work of Shelah, Mekler and Fuchs.

This is a joint work with Andreas Blass

Hilbert and Bernays introduced the e operator that chooses an element e(X) from every nonempty set X. The necessity to choose elements from nonempty sets arises in computing but the epsilon operator doesn't fit the bill. Besides, the extension of first-order logic with the epsilon operator is complex: its expressivity equals that of the existential monadic second-order logic.

We introduce a different choice operator, d, that fits computing better. While e is a fixed choice operator, d is an independent choice operator. Different evaluations of d(X) for the same X may produce different results. Furthermore, there is no correlation between different evaluations. Somewhat surprisingly, the extension of first-order logic with delta does not increase the expressive power of first-order logic.

See details in Journal of Symbolic Logic (3) 65(2000).

The results presented here are joint work with R. Coles, G. LaForte, and R. Downey, and will appear in [1]. Let J_e(A)=A ÅW_e^A for e Î w, A Í w. We call J:2^w® 2^w a pseudojump operator if J = J_e for some e. It was shown by C. Jockusch and R. Shore in [2] that for every pseudojump operator J there is a set A such that J(A) has degree 0¢. We study what more can be said about such an A under the additional hypothesis that the pseudojump operator J is nontrivial, i.e. J(X) < _T X for all X Í w (or for all X in some specified subset of 2^w). A sample theorem is that A can be chosen to be d.c.e (i.e. of the form U - V where U, V are c.e.) and furthermore to be of non-c.e. degree. Our most surprising result is that upper cone avoidance fails, i.e. there is a pseudojump operator J and a noncomputable c.e. set C such that J(W_e) > _T W_e for all e and C £ _T A for every c.e. set A with J(A) of degree 0¢.

References

[1]

R. Coles, R. Downey, C. Jockusch and G. LaForte, Completing pseudojump operators. Ann. Pure Appl. Logic, to appear.

[2]

C. Jockusch and R. Shore, Pseudo jump operators I: The r.e. case. Trans. Amer. Math. Soc. 275(1983), 599-609.

Classification is an important goal in many branches of mathematics. The idea is to find nice invariants for a class of mathematical objects, up to isomorphism or other equivalence, or else to say, in some concrete way, that there are no nice invariants. There are results on classification in different branches of logic. I will describe some recent work in computable structure theory, which was inspired by work in descriptive set theory.

In some sense computational complexity theory is a subfield of recursion theory. In recursion theory one asks how unsolvable is a problem, while in computational complexity theory one asks how difficult, in terms of time, storage, and other measures, it is to solve a problem. In this lecture I will describe the influences that traditional recursion theory have had on computational complexity theory. Some of the topics I will cover are resource bounded reducibilities, hierarchies, complexity classes, and structural properties of sets. I will describe some of the highlights in computational complexity in the past 30 years.

Building on a previous result for trivial, strongly minimal theories, we have recently shown that trivial, uncountably categorical theories of rank one are model complete after naming constants for a model. We will discuss the proof of this result, along with an approach for bounding the quantifier complexity of trivial, uncountably categorical theories as a function of the rank of the theory. Some of this is joint work with Alf Dolich and Alex Raichev.

In the '80s, Cherlin, Harrington and Lachlan worked out the structure of omega-stable, omega-categorical theories. One consequence they drew is that an omega-stable, omega-categorical theory is not finitely axiomatizable. What part of the full structure theory is sufficient for the non-finite axiomatizability? The key fact is that an omega-stable, omega-categorical theory is one-based. More precisely,

Theorem. Suppose T is a one-based simple omega-categorical theory. If there is a stable and stably embedded definable set in a model of T, then T is not finitely axiomatizable.

In particular, the theorem gives a new proof of the non-finite axiomatizability of omega-stable, omega-categorical theories. I will discuss the theorem and some other connections between finite axiomatizability and the property of being one-based.

Zilber has found an L_w1,w(Q) sentence axiomatizing an uncountably categorical class of algebraically closed fields of characteristic zero with exponentiation and conjectures that the complex numbers with exponentiation is a model of this theory. I will discuss some aspects of his proof and conjectures.

Assume G is an À₀-saturated group covered by countably many type-definable sets X_n,n < w.

Theorem 1 Some finitely many of the sets X_n generate the group G in at most 3 steps.

A model-theory free version is as follows. Assume G is any group and f: G®w any function. Assume X is a countable compactification of w (hence a metric space).

Theorem 2 There is a finite set Y Í X such that for every e > 0, G is generated in at most 3 steps by f^-1[B(Y,e)], where B(Y,e) is the ball around Y of radius e.

For some groups 2 steps are enough, e.g. in Theorem 1 for all stable groups, and in both theorems for all amenable groups. If a group contains a non-abelian free subgroup, then in general in Theorem 2, 3 steps are needed. Hence also in general 3 steps are needed in Theorem 1.

There are some counterparts of these results on countable colourings of types and graphs. For example, if the edges of a complete directed graph are coloured into countably many colours in a homogeneous way, then for some infinite set of colours, if we erase all edges of these colours from the graph, then what remains is still a connected graph of diameter at most 3.

In the model-theoretic (À₀-saturated) set-up (where the colours are type-definable) we can choose finitely many colours so that if we erase all the edges of the other colours, then what remains is still a connected graph of diameter at most 3.

These results involve a new notion of an open analysis of a compact space with respect to its covering. They also show some connections between measures and forking. They suggest a possibility to extend some generic types arguments to some general unstable contexts.

Some of these results are due to my student, Marcin Petrykowski.

Let F be a function from the reals into the countable ordinals. F is said to be bounded if the range of F is bounded above by a countable ordinal. A typical bounding theorem says F is bounded if F satisfies some definability condition. Some classical results and their effective counterparts are briefly reviewed. Some recently obtained extensions are outlined.

There is a well developed theory of effective randomness, originating with the work of Chaitin (1975), Kolmogorov (1965), and Martin-Löf (1966). According to Chaitin and Kolmogorov, an infinite binary sequence X is random if each of its initial segments is difficult to describe. According to Martin-Löf, X is random if 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 W-numbers and the Universal Martin-Löf Tests. We will discuss these objects and recount results of Kucera and Slaman (2001) and Merkle, Mihailovi\'c 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. There is a recursive measure m, necessarily discontinuous, and a sequence X such that X is Martin-Löf random relative to m and yet for every recursive function f there is an n such that the first f(n) values of f can be specified by a program of length less than n. In other words, there is a m-random sequence whose information content is arbitrarily compressible.

Let E denote the structure of the computably enumerable sets modulo the ideal of finite sets under inclusion. In 1967 Lachlan asked whether any two maximal sets (coatoms of E) were automorphic. Soare [1974] answered this affirmatively and introduced the Extension Theorem for building effective automorphisms, which says that under certain conditions a partial map on E can be extended to an automorphism. The Extension Theorem was used for many applications by Downey, Stob, Maass, Cholak, and others. Harrington and Soare [1996] and independently Cholak [1995] combined the Lachlan priority tree method with the Soare automorphism machinery to build D⁰₃ automorphisms rather than just effective ones. This was powerful but lacked some of the flexibility of the Extension Theorem such as putting negative restraint on the image set. Soare has just discovered a Unified Extension Theorem which combines the best features of both the original Extension Theorem and the D⁰₃ method and which supercedes these and most of the automorphism results over the last thirty years. It is also closely related to two recent remarkable results by Cholak and Harrington which show that an arbitrary automorphism mapping A to B is equivallent to one which is D⁰₃ on an appropriate substructure of A. Hence, little is lost if we only build D⁰₃ automorphisms. The second Cholak-Harrington result crucially uses the Soare Unified Extension Theorem, and indeed can be derived as a corollary of it.

Let G be a connected semisimple Lie group with at least one absolutely simple factor S such that R-rank(S) ³ 2 and let G be a uniform lattice in G.

(a) If CH holds, then G has a unique asymptotic cone up to homeomorphism.
(b) If CH fails, then G has 2^2w asymptotic cones up to homeomorphism.