


Model Theory and Recursion Theory / Théorie des modèles et théorie de la récursion Org: Robert Woodrow (Calgary), Bradd Hart (Fields Institute), and/et John Baldwin (IllinoisChicago)
 JOHN BALDWIN, University of Illinois at Chicago, Chicago, Illinois 60607, USA
Categoricity and model completeness

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 À_{1}categorical theories that imply it
is model complete. We will review some of the history of this problem
and report the latest result: Theorem (BaldwinHolland). 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
kindependent formulas.
 GREGORY CHERLIN, Rutgers University, Busch Campus/Piscataway, New Jersey 08854,
USA
Countable universal graphs with forbidden subgraphs: a decision
problem

Given a finite set C of finite connected graphs, which we
declare to be "forbidden graphs," we say that a graph is
Cfree if it contains no subgraph isomorphic to one in the
set C. We ask whether there is a countable
Cfree graph in which all countable Cfree
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 À_{0}categoricity of the theory. Other natural
model theoretic issues, lacking a clear motivation in graph theory,
have not been addressed to date.
 PAUL EKLOF, University of California, Irvine, Irvine, California 926973875,
USA
Tilting toward definability

We discuss some applications of settheoretic methods to representation
theory, in particular to tilting theory. For any Rmodule M, let
M^{^} denote {N:Ext_{R}^{1}(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 CrawleyBoevey (joint work with S. Bazzoni and J. Trlifaj). In the
talk, we focus on a key settheoretic lemma which derives from earlier
work of Shelah, Mekler and Fuchs.
 YURI GUREVICH, Microsoft Research
Logic of choice

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 firstorder
logic with the epsilon operator is complex: its expressivity equals
that of the existential monadic secondorder 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 firstorder logic with delta does not increase the
expressive power of firstorder logic.
See details in Journal of Symbolic Logic (3) 65(2000).
 CARL JOCKUSCH, University of Illinois at UrbanaChampaign,
Urbana, Illinois 61801, USA
Completing pseudojump operators

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 nonc.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), 599609.
 JULIA KNIGHT, University of Notre Dame, Notre Dame, Indiana, USA
Computable classification

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.
 RICHARD LADNER, University of Washington
The influence of recursion theory on computational complexity
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.
 CHRIS LASKOWSKI, University of Maryland, College Park, Maryland, USA
The complexity of trivial, uncountably categorical theories

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.
 DAVID LIPPEL, McMaster University, Hamilton, Ontario
Onebased theories and finite axiomatizability

In the '80s, Cherlin, Harrington and Lachlan worked out the structure
of omegastable, omegacategorical theories. One consequence they drew
is that an omegastable, omegacategorical theory is not finitely
axiomatizable. What part of the full structure theory is sufficient for
the nonfinite axiomatizability? The key fact is that an omegastable,
omegacategorical theory is onebased. More precisely,
Theorem. Suppose T is a onebased simple omegacategorical 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 nonfinite
axiomatizability of omegastable, omegacategorical theories. I will
discuss the theorem and some other connections between finite
axiomatizability and the property of being onebased.
 DAVE MARKER, University of Illinois at Chicago
Remarks on Zilber's pseudoexponentiation

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.
 L. NEWELSKI, Mathematical Institute, Wroclaw University,
50384 Wroclaw, Poland
Countable coverings of groups and graphs

Assume G is an À_{0}saturated group covered by countably many
typedefinable 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 modeltheory 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 nonabelian 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 modeltheoretic (À_{0}saturated) setup (where the colours
are typedefinable) 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.
 GERALD SACKS, Harvard and MIT
Bounding theorems

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.
 TED SLAMAN, University of California, Berkeley, California, USA
Random sequences and recursive measures

There is a well developed theory of effective randomness, originating
with the work of Chaitin (1975), Kolmogorov (1965), and MartinLö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 MartinLö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 ChaitinKolmogorov and MartinLöf formulations of randomness
are naturally equipped with random sets: the Chaitin Wnumbers
and the Universal MartinLö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 (ChaitinKolmogorov) and measure theoretic randomness
(MartinLö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
MartinLö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 mrandom sequence whose information content is
arbitrarily compressible.
 ROBERT SOARE, University of Chicago
Automorphisms of the computably enumerable sets

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^{0}_{3}
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^{0}_{3} 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^{0}_{3} on an appropriate substructure of A. Hence, little is
lost if we only build D^{0}_{3} automorphisms. The second
CholakHarrington result crucially uses the Soare Unified Extension
Theorem, and indeed can be derived as a corollary of it.
 SIMON THOMAS, Rutgers University, New Brunswick, New Jersey 08903, USA
Asymptotic cones of finitely presented groups

Let G be a connected semisimple Lie group with at least one
absolutely simple factor S such that Rrank(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.
This is joint work with Linus Kramer, Saharon Shelah and Katrin Tent.

