Monday, September 22, 2008
04:45 pm
Higher-Order Reverse Topology
Speaker: James Hunter<br>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.
Exley Science Center - ESC 618
Monday, September 29, 2008
04:45 pm
Local Computability and Uncountable Structures
Speaker: Russell Miller, Queens College/CUNY<br>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.
Exley Science Center - ESC 618
Monday, October 06, 2008
04:45 pm
Some model-theoretic connections between dimension groups and AF algebras
Speaker: Philip Scowcroft, Wesleyan University<br>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.
Exley Science Center - ESC 618
Monday, November 03, 2008
04:45 pm
Ramsey's theorem for trees
Speaker: Jared Corduan, Dartmouth<br>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.
Exley Science Center - ESC 618
Monday, November 17, 2008
04:45 pm
The conjugacy problem for the automorphism group of countably categorical structures
Speaker: Paul Ellis, UCONN<br>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.
Exley Science Center - ESC 618
Monday, February 23, 2009
04:45 pm
Do you know how much you know?
Speaker: Rebecca Weber, Dartmouth<br>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.
Exley Science Center - ESC 618
Monday, May 03, 2010
04:00 pm
- 06:00 pm
The Conjugacy Problem for $GL_{\infty}(q)$
Speaker: Scott SchneiderAbstract: When are two invertible linear operators on a countably-infinite dimensional vector space over a finite field conjugate? We will discuss this problem and the Borel complexity of its solution in the context of a larger project of investigating the Borel complexities of the conjugacy relations on the automorphism groups of various countably categorical structures.
ESC 638
Monday, September 13, 2010
04:45 pm
- 06:30 pm
Existentially Closed Dimension Groups
Speaker: Philip ScowcroftAbstract: A dimension is a special kind of partially ordered Abelian group first studied in connection with operator algebras. Existentially closed dimension groups are to dimension groups as algebraically closed fields are to fields. This talk will explain all the terms in its title and characterize the existentially closed dimension groups.
ESC 638
Monday, September 20, 2010
04:45 pm
- 06:30 pm
Finitely Generic Dimension Groups
Speaker: Philip Scowcroft, Wesleyan UniversityAbstract: Finitely generic dimension groups form a subclass of the existentially closed dimension groups. After outlining the method of model-theoretic forcing used to produce finitely generic dimension groups, this talk will describe algebraic and recursion-theoretic properties distinguishing these groups from arbitrary existentially closed dimension groups.
ESC 638
Monday, October 11, 2010
04:05 pm
- 05:00 pm
Geometric Model Theory in Efficient Computability
Speaker: Cameron HillAbstract: This talk will consist of a sketch of the proof of a single main result linking geometric ideas from the first-order model theory of infinite structures with complexity-theoretic analyses of problems over classes of finite structures. To remove any suspense, the statement of the theorem is as follows:Theorem:Let K = fin[T^G], where T is a complete k-variable theory with infinitely many finite models up to isomorphism.I. If T is constructible, then K is rosy.II. T is efficiently constructible if and only if K is super-rosy.Obviously, a great number of definitions are needed (regardless of the reader's background, most likely) to make sense of these assertions. For the time being, it should be understood as a shadow of the ``main current'' of first-order model theory -- namely, Shelah's Classification theory. I take ``efficiently constructible'' -- meaning that models of T can be efficiently recovered from elementary diagrams of subsets -- to be a reasonable substitute for ``classifiable'' in the classical theory. We then seek a hierarchy of structural properties culminating in efficient constructibility in analogy with the stability-theoretic hierarchy, Stable properly contains Super-stable properly contains Classifiable=Super-stable+NDOP. In the classical scenario, any non-trivial bound on the number of models of the theory in each cardinality imposes stability, which already supports the rudimentary notion of geometry known as non-forking independence. In the scenario of this study, the hypothesis of constructibility by an algorithm cursorily imitating that of an efficient algorithm in form (meaning, an essentially inflationary program which isn't necessarily efficient) is sufficient to impose another rudimentary notion of geometry on the class of models -- in this case, known as thorn-independence in a rosy class; this is the content of I of the Theorem. The further requirement of efficiency -- polynomially-bounded running times -- induces a further guarantee of good behavior in the geometry of thorn-independence, and the "only if" portion of II of the theorem amounts to just this fact. It turns out, then, that this additional tractability in the geometry gives enough purchase to devise an efficient algorithm, initially disguised as a weak model-theoretic coordinatization result, for the class of the theory's finite models.
ESC 638
Monday, October 11, 2010
05:10 pm
- 06:00 pm
Computable Fields and the Bounded Turing Reduction
Speaker: Rebecca SteinerAbstract: For a computable field F, the splitting set S_F of F is the set of polynomials with coefficients in F which factor over F, and the root set R_F of F is the set of polynomials with coefficients in F which have a root in F.Results of Frohlich and Shepherdson from 1956 imply that for a computable field F, the splitting set S_F and the root set R_F are Turing-equivalent. Much more recently, R. G. Miller showed that for algebraic fields, the root set actually has slightly higher complexity: for algebraic fields F, it is always the case that S_F 1-reduces to R_F, but there are algebraic fields F where we have R_F not 1-reducible to S_F.Here we compare the splitting set and the root set of a computable algebraic field under a different reduction: the bounded Turing reduction. We construct a computable algebraic field for which R_F does not bT-reduce to S_F.We also define a Rabin embedding g of a field into its algebraic closure, and for a computable algebraic field F, we compare the relative complexities of R_F, S_F, and g(F) under m-reducibility and under bT-reducibility.
ESC 638
Monday, October 25, 2010
04:15 pm
- 06:00 pm
AT UCONN Definability and Automorphisms of the C.E. Sets
Speaker: Rachel Epstein, Harvard UniversityAbstract: Definability is one of the fundamental themes of computability theory. We examine the structure of the computably enumerable (c.e.) sets under set inclusion. The problem of which classes of degrees are definable in this structure has been an important topic of study in computability theory. In particular, it has been shown that all upward-closed jump classes (such as high, nonlow2, etc.) are definable except for the nonlow degrees, which are not definable. To show that the nonlow degrees are not definable, we use automorphisms, which we build on trees of strategies. We will discuss the history of the problem and some of the ideas of the proof.
ESC 638
Monday, December 06, 2010
04:15 pm
- 06:00 pm
Cardinal Invariant Properties of Countable Borel Equivalence Relations
Speaker: Scott Schneider, Wesleyan UniversityAbstract: Boykin and Jackson have shown that the bounding number, b, can be used to define a property of countable Borel equivalence relations that is relevant to the unions problem for hyperfinite relations. In fact, many other cardinal invariants of the continuum can be used in an analogous manner to define "Borel cardinal invariant" properties of countable Borel equivalence relations. In this talk, we introduce these new properties and examine some of the basic relationships that hold between them, thus linking the study of countable Borel equivalence relations with that of cardinal invariants of the continuum. In particular, we show that the property corresponding to the splitting number s is equivalent to smoothness..NOTE: The CT logic seminar will NOT meet on Monday Nov 29th. Our next seminar meeting, and the last of the fall semester, will be on Monday December 6, 2010.
ESC 638
Monday, April 04, 2011
04:45 pm
- 06:00 pm
End-Extensions
Speaker: Philip Rothmaler, CUNYAbstract: I will explain a new and simple proof of the fact that every (colored) linear ordering has a proper elementary end-extension (unless it obviously cannot). The proof has in large parts very little to do with orderings. It is based on a simple idea of how to get Vaughtian pairs (i.e. extend a model without extending a certain infinite definable set) via what is known as weak orthogonality. Though this term stems from stability theory, it is completely elementary, and I will explain everything from scratch. A new result using the same proof yields proper elementary branch-end-extensions of (colored) trees.
ESC 638
Monday, April 11, 2011
04:15 pm
- 06:00 pm
Computability of Integer Parts
Speaker: Karen Lange, Notre DameAbstract: An integer part of a real closed eld R is a discrete ordered subringI containing 1 such that for all r 2 R there exists a unique i 2 I withi r < i + 1. Mourgues and Ressayre [1] showed that every real closedeld R has an integer part. They do this by building an embeddingof R into the eld of generalized power series khhGii, where k is theresidue eld of R and G is the value group of R. For a countable realclosed eld R, we showed that the integer part obtained by the pro-cedure of Mourgues and Ressayre is 0!! (R) by bounding the lengthsof the power series in the image of this embedding. We would like toknow whether there exists a construction that yields a computation-ally simpler integer part, perhaps one that is 02 (R). All integer partsare Z-rings, discretely ordered rings that have the euclidean algorithmfor dividing by integers. By a result of Wilkie [2], any Z-ring can beextended to an integer part for some real closed eld. We show thatwe can compute a maximal Z-ring I for any real closed eld R that is02(R), and we then examine whether this I must serve as an integerpart for R. We also show that certain subclasses of 02(R) are notsucient to produce integer parts for R. This is joint work with PaolaD'Aquino and Julia Knight.References[1] M. H. Mourgues and J.-P. Ressayre, \Every real closed eld has an integerpart," J. Symb. Logic, vol. 58 (1993), pp. 641-647.[2] Alex Wilkie, \Some results and problems on weak systems of Arithmetic", inLogic Colloquium '77, North Holland.
ESC 638
Monday, April 25, 2011
04:15 pm
- 06:00 pm
Solutions to Linear Equations in Valued D-Fields
Speaker: Meghan Anderson, UC BerkeleyAbstract: A theory of D-henselian fields was developed by Scanlon in his 1997 thesis. In this theory, valued fields are endowed with a derivative like operator D, interacting strongly with the valuation. The operator specializes to a derivative in the residue field, but in the valued field is interdefinable with a nontrivial automorphism. The theory has good model theoretic properties, most notably quantifier elimination. This should allow for some analysis of the difference field in terms of the differential structure. However, the theory also presents its own challenges, even in the relatively simple setting of solution spaces to linear equations. I will discuss some of these challenges, and progress towards a model theoretic Galois theory in this setting.
ESC 638
Monday, May 09, 2011
04:15 pm
- 06:00 pm
Integration in T-convex theories
Speaker: Yimu Yin, PittsburghAbstract: I will first briefly explain Hrushovski-Kazhdan style motivic integration and then outline how to construct such an integration in T-convex theories. Since this is an ongoing project and not all the details have been checked, I will focus more on the motivation, which is related to motivic multiplicative characters, than the technical details.
ESC 638
![[Wesleyan University]](/common/_internal/files/logo.png "Wesleyan University front door"){kind=logo}
![[Wesleyan University shield]](http://www.wesleyan.edu/common/_internal/files/shield_44x50_dddddd.png){kind=small}