Midwest
Computability Seminar
VI
The Midwest Computability Seminar
meets twice in the fall and twice in the spring at University of
Chicago. Researchers in computability theory and their students
and postdocs from University of Chicago, University of Notre Dame, and
University of Wisconsin-Madison plus some others throughout the area
regularly attend. Normally we have two half hour talks and two 1-hour
talks and a few hours
to talk and collaborate with each other. The seminar started in
the fall of 2008.
DATE: Tuesday, January 26th, 2010.
PLACE: Ryerson, University of
Chicago.
1100 East 58th Street, Chicago, IL 60637.
Speakers:
- Sara Quinn - Northwestern U.
- John Wallbaum - U. of Notre Dame.
- Steffen Lempp - U. of Wisconsin.
- Reed Solomon - U. of Connecticut.
Schedule:
- 12:00 - 1:00: Lunch. (the Barn Ry 352)
- 1:00 - 1:25: Sara Quinn (the Barn Ry 352).
- 1:35 - 2:00: John Wallbaum (the Barn Ry 352).
- 2:00 - 2:30: Coffee break
- 2:30 - 3:20: Steffen Lempp (the Barn Ry 352).
- 3:30 - 4:10: Coffee break.
- 4:10 - 5:00: Reed Solomon (Ry 358).
- 6pm: Dinner. Lao Sze Chuan, 2172
South Archer Ave.
Abstracts:
Sara
Quinn.
Title: Turing Computable
Embedding
Abstract: The notion of a
Turing computable embedding is an effective analogue of the Borel
embeddings used in descriptive set theory to compare classes of
countable structures. The partial ordering that arises from this
embedding notion allow us to order the complexity of the classification
problem for various classes of structures. In this talk I will
discuss the background behind the notion, some interesting examples of
embedding and non-embedding results, and some possible future
directions of inquiry using this embedding.
John Wallbaum.
Title: Primitive elements of
free groups
Abstract: In this talk I will
describe how Charlie McCoy and I were able to use recent results in
group theory to show that the index set for F_{\infty}, the countably
generated free group, is m-complete Pi^0_4. I will also mention our
result that there is a computable copy of F_{\infty} with no Sigma^0_2
basis, which is sharp since every computable copy has a Pi^0_2 basis.
Steffen Lempp.
Title: Comparing effective notions of categoricity.
Abstract: We compare computable
categoricity and (relativized notions
of) relative
computable categoricity. It is easy to see that any relatively
computably
categorical model is computably categorical. Goncharov, using effective
versions of Scott families, showed that the converse holds for
2-decidable
models. On the other hand, Kudinov showed that the converse fails even
for 1-decidable models.
We extend these results by showing that (1) any 1-decidable
computably categorical model is relatively
Δ02-computably
categorical; and
(2) there is a computably categorical model which is not
relatively arithmetically categorical.
It is not hard to see, using Goncharov's characterization of
relative computable categoricity and a simple construction, that this
notion is
Σ03-complete.
The characterization of the complexity of computable
categoricity remains open, and appears very hard in light of the second
part of
the above theorem; in fact, while it is trivially
Π11, and
Π04-hard by White,
it is not even known whether computable categoricity is
arithmetical or not.
This is joint work with Downey, Kach and Turetsky.
Reed Solomon.
Title: Self-embeddings of computable
trees
Abstract: We present
results concerning the complexity of self-embeddings for computable
trees motivated by similar computability theoretic work in the context
of the Dushnik-Miller Theorem for linear orders. This work is joint
with Stephen Binns, Bjoern Kjos-Hanssen, Manny Lerman and Jim Schmerl.
2009/2010 Seminars:
- Sept 29th 2009. Carl Jockusch -
Rachel Epstein - Rebecca Weber
- Jan 26th 2010. Sara Quinn - John Wallbaum - Steffen Lempp - Reed
Solomon
- May 2010.
2008/2009 Seminars:
If you haven't been
receiving the announcements, and you would like to be included in the
list, send me an email to antonio at uchicago.edu.