Logic Seminar Archive

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

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

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

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

Combining Real Exponentiation and Weierstrass Elliptic Functions - Decidability and Model Completeness

Speaker: Angus Macintyre, Queen Mary, University of London

September 24, 2007

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

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

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.