Logic Seminar Archive

February 23, 2009

Do you know how much you know?

Speaker: Rebecca Weber, Dartmouth
Abstract: Kolmogorov complexity measures the information content of a finite string. We define the mutual information of two finite strings as the sum of their individual complexities minus the complexity of their encoding as a pair. When the strings are closely related, the complexity of the pair will be smaller and hence the mutual information larger. For infinite sequences there is no universally agreed-upon definition for mutual information. I'll present one contender and argue for its plausibility, and discuss ongoing work with Denis Hirschfeldt on sequences that are low for information: those that have finite mutual information with themselves. These have nice connections to K- triviality and other properties of computational weakness.

November 17, 2008

The conjugacy problem for the automorphism group of countably categorical structures

Speaker: Paul Ellis, UCONN
Abstract: It is easily seen that the conjugacy problem for the automorphism group of N is smooth. Sam Coskey, Scott Schneider and I have shown that the conjugacy problem for the automorphism group of the countable random graph is complete Borel. I will show a proof that the same is true for the automorphism group of the countable homogeneous dense linear order. Due to a curious parallel in the three proofs, we conjecture that for any countably categorical structure, the conjugacy problem for the automorphism group is either smooth (easy) or complete Borel (totally intractable). The necessary background about Borel equivalence relations will be discussed as well.

November 03, 2008

Ramsey's theorem for trees

Speaker: Jared Corduan, Dartmouth
Abstract: A partially ordered set P has the (n,k)-Ramsey property if every coloring of the n-chains of P with k colors has a monochromatic suborder isomorphic to P. In their paper Reverse mathematics, computability, and partitions of trees, Chubb, Hirst, and McNicholl analyzed the proof theoretic strength of Ramsey's theorem for the complete binary branching tree. I will talk about joint work with Marcia Groszek and Joseph Mileti on Ramsey's theorem for arbitrary trees and answers to some questions raised by Chubb, Hirst, and McNicholl.

October 06, 2008

Some model-theoretic connections between dimension groups and AF algebras

Speaker: Philip Scowcroft, Wesleyan University
Abstract: In 1976 Elliott showed that approximately finite-dimensional C*-algebras (AF algebras) could be classified up to isomorphism by certain countable partially ordered Abelian groups (dimension groups). It turns out that one of these groups is algebraically (existentially) closed in another just in case the corresponding algebras, viewed as metric structures, enjoy the same relation.

September 29, 2008

Local Computability and Uncountable Structures

Speaker: Russell Miller, Queens College/CUNY
Abstract: Computable model theory has always restricted itself to the study of countable structures. The natural numbers form the standard domain and range for partial computable functions, due to the finiteness of the programs and computations in the Turing model. In this talk we continue to use this standard model of computation, but in such a way as to allow consideration of uncountable structures. We no longer aspire to describe a structure S globally. Instead, we content ourselves with a local description; a list of the finitely-generated substructures of S, up to isomorphism. Initially we require that these substructures should be computable, and that the list of them be given effectively. If this can be done, then S is said to be locally computable. (Such an S must have only countably many finitely-generated substructures, up to isomorphism.) Then we consider more sophisticated effective descriptions of S, by naming embeddings among the substructures which reflect the inclusions in S. We will prove several theorems about locally computable structures, but since the notion of local computability is extremely new, much of this talk will be devoted to definitions and examples.

September 22, 2008

Higher-Order Reverse Topology

Speaker: James Hunter
Abstract: Traditional reverse mathematics deals with second-order objects: sets of natural numbers. This allows traditional reverse mathematics to use many techniques from computability theory and related fields. However, this also limits its ability to analyze topological statements, since all objects being discussed must be represented by second-order codes. The topological spaces examined in reverse mathematics have typically been of size continuum (so that points can be represented by sets of natural numbers) and countably-based (so that open sets can also be represented by sets of natural numbers).

Using a base theory defined in recent years by Kohlenbach, based on functionals rather than sets, once can start to perform higher-order mathematics. Extending Kohlenbachs base theory to allow topological spaces to consist of arbitrarily many atoms, one can begin to rough out the reverse-mathematical strength of certain basic topological theorems.

September 15, 2008

Small covers of semi-abelian varieties

Speaker: John Baldwin, University of Illinois at Chicago

April 28, 2008

On ordered structures of higher rank

Speaker: Charles Steinhorn, Vassar College
Abstract: It has been widely thought that o-minimal structures might lie at the first level of a hierarchy of ordered structures, in analogy with strongly minimal structures. In joint work with A. Onshuus, we develop a framework for ordered structures of finite rank. In particular, we analyze linear orders definable in o-minimal structures, and this will be the focus of the first part of the talk. This analysis appears to have an interesting application in mathematical economics---joint work with T. Brihaye, C. Michaux, and Onshuus---discussion of which is the subject of the second part of the talk.

March 24, 2008

Andrei Morozov: On countable structures Sigma-definable over R,C, and H

Speaker: Andrei Morozov, Sobolev Institute of Mathematics and Novosibirsk State University
Abstract: We give a characterization of countable structures Sigma-definable without parameters over the ordered field of reals, the field of complex numbers, and skew field of quaternions. It appears that over R, all such structures are hyperarithmetical and they can have arbitrary high hyperarithmetical complexity, although if we assume some natural restrictions on the definition, then all such structures have isomorphic computable copies.

February 25, 2008

Brooke Andersen, Strong notions of reducibility and completeness

Speaker: Brooke Andersen, Dartmouth College
Abstract: We consider a notion of Turing reducibility which is always total on recursively enumerable oracles. This notion of reducibility is implied by truth-table reducibility, but is different from truth-table, weak truth-table, bounded search and Turing reducibilities on r.e. sets. Moreover, it is not transitive. We add a condition, called positivity, to make this notion transitive and see that this is still different from other strong notions of reducibility. I will show how we can use complete sets to distinguish this reducibility from other notions. This is work for my thesis. This reducibility was first studied by Marcia Groszek, Rebecca Weber and Pete Winkler.

February 18, 2008

Asher Kach: Invariants of Boolean Algebras (Part 2)

Speaker: Asher Kach
Abstract: The first part will be mostly expository. After reviewing Ershov-Tarski invariants (characterizing BAs up to elementary equivalence), well spend a significant amount of time discussing Ketonen invariants (characterizing BAs up to isomorphism). In particular, well make the transitions from BAs to linear orders, to rank functions, to measures, to derived monoids.

The second part of my talk will emphasize recent research. After giving explicit constructions of the depth zero measures, well characterize the computable depth zero, rank \omega BAs. Well also discuss rank one BAs and depth one BAs. As time permits, work (joint with Denis Hirschfeldt and Antonio Montalban) on the Feiner hierarchy and its implications to computable BAs will be presented.

November 19, 2007

Gareth Jones, Model completeness and o-minimality

Speaker: Gareth Jones, McMaster University
Title: Model completeness and o-minimality
Abstract: Proving model completeness is one of the main ways of showing that a structure is o-minimal. There have also been some results in the other direction, that is, deriving model completeness from o-minimality (and some other assumptions). I shall give some examples of this type of result, and say why they are useful.

November 07, 2007

Philipp Rothmaler, Bronx CC-CUNY

Date: Monday, November 5, 2007 Speaker: Philipp Rothmaler, Bronx CC-CUNY Title: Quasi versus pseudo: Two elementary clases generated by flat modules Time & Place: 4:45 P.M., Room 618SC

October 22, 2007

Philip Scowcroft: Halfspaces in dimension groups

Speaker: Philip Scowcroft, Wesleyan University
Abstract: Over an ordered field the class of finite intersections of halfspaces is closed under projection. By generalizing the notion of halfspace one may prove analogous results for arbitrary subgroups of the reals, and the dense subgroups obey a stronger result. I will explain how these projection theorems, both for the integers and for dense subgroups of the reals, extend to dimension groups and so to arbitrary ordered or lattice-ordered Abelian groups.

October 01, 2007

Angus Macintyre: Combining Real Exponentiation and Weierstrass Elliptic Functions - Decidability and Model Completeness

Speaker: Angus Macintyre, Queen Mary, University of London

September 24, 2007

Noam Greenberg: Admissible recursion theory and linear orderings of size $\aleph_1$

Speaker: Noam Greenberg, Victoria University, Wellington, New Zealand

Abstract: Under simplifying assumptions (namely $\mathbb R \subset L$) we use the concepts of admissible recursion (computability) theory regarding effectiveness on the ordinal $\omega_1$ to define and investigate computable model theory for structures of size $\aleph_1$. In particular, we examine computable categoricity and degree spectra of linear orderings. The theme is to examine what it is about true finiteness that enables some classical constructions in computable model theory, and which constructions are sufficiently robust to generalise (and what the correct generalisations can reveal about the classical case). I will describe the basic concepts in detail so to enable understanding of some of the constructions.

September 17, 2007

John Baldwin: WGCH and Martin's Axiom

Speaker: John Baldwin, University of Illinois Chicago

Abstract: We will describe the contrast between model theoretic consequences of Martin's axiom and WGCH ($2^n < 2^{n+1}$). Here are two results of Shelah.

Theorem 1. (WGCH) If an AEC has few models in power $\aleph_1$ it is $\omega$-stable and has the amalgamation property in $\aleph_0$.

Theorem 2. (Martin's Axiom) There is a sentence of $L_{\omega_1,\omega}$ that is $\aleph_1$-categorical but fails amalgamation in $\aleph_0$ and is not $\omega$-stable.

We will sketch the proof of the second result.

September 10, 2007

Mia Minnes: Model theoretic properties of automatic structures

Speaker: Mia Minnes, Cornell University

Abstract: Automatic structures are structures whose domain and relations are all presented by finite automata. This class of structures is a restriction of the class of computable structures, and is natural when we consider the case of comptuation with fixed finite resources. All automatic structures have decidable first order theory. This might suggest that they are simple, and perhaps uninteresting as structures. However, we use certain model theoretic measures of complexity to show that automatic structures are as complicated as possible. One such measure is Scott Rank, which measures the automorphism orbits of the structure. We show that for each ordinal less than or equal to \omega_1^CK+1, there is an automatic structures whose Scott Rank is that ordinal. This is the same result one sees in the larger class of computable structures. The proof in the automatic structures case uses embeddings of computable structures via configuration space of the corresponding Turing machines. A similar technique can be used to show that there are automatic trees with Cantor-Bendixson rank at any computable ordinal. Again, this result is surprising in that it matches that for computable structures.

This is joint work with B. Khoussainov.

April 16, 2007

Logic Seminar - Yun Lu, Wesleyan University

Title: Reducts of countably categorical graphs

Abstract: Let M be a countably categorical structure, homogeneous for a finite relational language. A reduct of M corresponds, up to bi-interpretability, to a closed subgroup of Sym(M) containing Aut(M). In this talk, I will describe classifications of reducts given by Higman, Thomas, and Bennett. I will also present my own results classifying reducts of the random bipartite graph and the random bipartite graph having more than two cross types.