|
|
|
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 (Illinois-Chicago)
- 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 (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.
- 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
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 À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 92697-3875,
USA
Tilting toward definability
-
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:ExtR1(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.
- 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 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).
- CARL JOCKUSCH, University of Illinois at Urbana-Champaign,
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 Je(A)=A ÅWeA for e Î w, A Í w. We call J:2w® 2w a pseudojump operator if J = Je
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
2w). 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(We) > T We 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.
- 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
One-based theories and finite axiomatizability
-
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.
- DAVE MARKER, University of Illinois at Chicago
Remarks on Zilber's pseudoexponentiation
-
Zilber has found an Lw1,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,
50-384 Wroclaw, Poland
Countable coverings of groups and graphs
-
Assume G is an À0-saturated group covered by countably many
type-definable sets Xn,n < w.
Theorem 1
Some finitely many of the sets Xn 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 (À0-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.
- 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 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.
- 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 D03
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 D03 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
D03 on an appropriate substructure of A. Hence, little is
lost if we only build D03 automorphisms. The second
Cholak-Harrington 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 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 22w asymptotic
cones up to homeomorphism.
This is joint work with Linus Kramer, Saharon Shelah and Katrin Tent.
|
|