LOGIC SEMINAR

FALL 2007

 

Friday, November 16, 2007

2:003:00 p.m.

Place: Monroe Hall (2115 G Street), Room 267

Speaker: Vitezslav Svejdar, Charles University, Prague  

Title: Grzegorczyk’s Variant of Robinson Arithmetic

Abstract: Q is a theory similar to Robinson arithmetic Q, but its addition and multiplication are functions possibly non-total. The talk will briefly sketch a proof that Q is interpretable in Q and thus Q is essentially undecidable. The proof uses Solovay’s method of shortening of inductive cuts, known since 1976, but never published.

 

Friday, October 26, 2007

2:003:00 p.m.

Place: Monroe Hall (2115 G Street), Room 267

Speaker: Hunter Monroe, International Monetary Fund

Title: Are There “Natural” Problems with No Fastest Algorithm?

Abstract: Some suspect that several familiar problems such as integer multiplication and matrix multiplication have speedup, i.e., no fastest algorithm. In fact, there is no optimal Strassen-type identity for matrix multiplication (Coppersmith and Winograd). However, no natural problem—one requiring at least linear time—is known to have speedup on Turing machines. We identify several properties of problems that seem to imply speedup under two definitions (Blum's definition is not applicable). However, identifying a natural problem with speedup would imply PNP. Speedup can be seen as a weak form of non-computability, i.e., the property “has no fastest algorithm” is a weak version of “has no algorithm at all”. Therefore, computability theory might illuminate speedup and open problems.

 

Friday, October 19, 2007

2:003:00 p.m.

Speaker: Joe Mourad, Georgetown University

Place: Monroe Hall (2115 G Street), Room 267

Title: Well Founded Trees and Constructing Reals

Abstract: Throughout history, Mathematics has been characterized in some ways by the methods used to construct real numbers—from primitive geometric constructions to complicated set theoretic definitions (whose meanings may depend on exotic properties of very large sets).  In this talk we will look at trees whose branching at any one node may be infinite.  A question we can ask of such trees, a question which may determine part of the definition of a real number, is whether they have an infinite branch. If not we call such trees well founded.  How complicated can well founded trees get and how can we characterize them? We will prove a version of Gödel incompleteness in that context.  This version has an advantage that it gives undecidable propositions whose meanings are independent of the Gödel numbering.  Time permitting, additional observations will be made concerning foundations and the real numbers.

 

Friday, October 5, 2007

2:003:00 p.m.

Speaker: Michael Moses, GWU

http://home.gwu.edu/~moses/

Place: Monroe Hall (2115 G Street), Room 267

Title: Intrinsically Complete Properties in Linear Orders

Abstract: I describe two constructions that produce linear orders in which a c.e. property is forced to be as non-computable as it can be, not just in that linear order but in every member of its isomorphism type. Both constructions use an interesting strategy devised by Jockusch and Soare that harbours the possibility for other such results establishing “intrinsic completeness”.

 

Friday, September 28, 2007

2:003:00 p.m.

Speaker: Sarah Pingrey, GWU

http://home.gwu.edu/%7Espingrey/

Place: Monroe Hall (2115 G Street), Room 267

Title: Complexity of Relations on Computable Structures, Part III

Abstract: We will continue our talk from last week and also extend the main result, by showing that there exists a low computably enumerable set C not weak truth-table reducible to any initial segment of any computable scattered linear ordering. We will also discuss a sufficient and necessary condition for the truth-table degree spectrum of a relation on computable structure to contain all degrees.

 

Friday, September 21, 2007

12:00noon1:00 p.m.

Speaker: Sarah Pingrey, GWU

http://home.gwu.edu/%7Espingrey/

Place: Monroe Hall (2115 G Street), Room 267

Title: Complexity of Relations on Computable Structures: Using Interval Trees, Part II

Abstract: We will continue our talk from last week and show our main theorem, that for every limit computable set C, there is a computable linear ordering L of order type w+w* such that CT w(L) tt C. Then, we will extend our first application of interval trees to show that if we assume that C is computably enumerable, then so is w(L). We will also show that the main theorem does not hold when Turing reducibility is replaced by weak truth-table reducibility. We will also give a strengthened version of this result: that C is also not weak truth-table reducible to any computable scattered linear ordering.

 

Friday, September 14, 2007

2:003:00 p.m.

Speaker: Sarah Pingrey, GWU

http://home.gwu.edu/%7Espingrey/

Place: Monroe Hall (2115 G Street), Room 267

Title: Complexity of Relations on Computable Structures: Using Interval Trees

Abstract:  Let A be a computable structure and R be an additional relation on A. The Turing degree spectrum of R on A is the set of all Turing degrees of the images of R under all isomorphisms from A to computable models. The Turing degree spectrum of the w-part of a linear ordering of type w+w* is all of the limit computable Turing degrees. This is not the case for tt-degrees, and we will show the best possible positive result: for every limit computable set C, there is computable linear ordering L of order type w+w* such that CT w(L) tt C. We will show this result by defining a new technique of finding the interval tree of a linear ordering. This is joint work with J. Chisholm, J. Chubb, V. Harizanov, D. Hirschfeldt, C. Jockusch, and T. McNicholl.

 

Friday, September 7, 2007

2:003:00 p.m.

Speaker: Jennifer Chubb, GWU

http://home.gwu.edu/%7Ejchubb/

Place: Monroe Hall (2115 G Street), Room 267

Title: Degree Spectra of the Successor Relation

Abstract:  We consider a computable linear ordering L, and ask what Turing degrees the successor relation can have in computable copies of L (this is the degree spectrum of the successor relation of L). We show that for a large class of linear orderings, the degree spectrum of successor is closed upwards within the c.e. Turing degrees. As a consequence, we will see that every upper cone of c.e. Turing degrees is the degree spectrum of the successor relation of some computable linear ordering. This is from joint work with A. Frolov and V. Harizanov.

 

 

OTHER LOGIC TALKS

 

Conference: Knots in Washington XXV

http://home.gwu.edu/~przytyck/knots/knotsinwashington25.htm

 

Sunday, December 9, 2007

3:003:25 p.m.

Speaker: Jennifer Chubb, GWU

http://home.gwu.edu/%7Ejchubb/

Place: Media and Public Affairs Building (805 21st Street NW), Room 310

Title: Effectively Closed Sets and Orderings on Groups

Abstract: A countable group G is computable if there is an algorithm to determine membership in G as a set, and an algorithm for multiplication on the group. G is left-orderable (bi-orderable) if there is a linear ordering of the elements of the group that is left-invariant (both left- and right-invariant). I will describe how the orderings of a countable group may be viewed as infinite paths through a binary tree, and how the orderings of a computable group correspond to paths in a computable binary tree. Taking the usual topology induced on the paths, we see that these sets are closed subsets of Cantor space, and in the computable case, we can think of them as effectively closed. The effectively closed sets have been extensively studied in computability theory, and I will describe some of the computability theoretic consequences for the spaces of orderings on groups.

 

Sunday, December 9, 2007

3:303:55 p.m.

Speaker: Sarah Pingrey, GWU

http://home.gwu.edu/%7Espingrey/

Place: Media and Public Affairs Building (805 21st Street NW), Room 310

Title: Orders on Computable Torsion-Free Abelian Groups

Abstract: A countable group is computable if its domain is a computable set and its group theoretic operation is computable. We examine complexity of orders on a computable torsion-free abelian (hence orderable) group G, using Turing degrees as a complexity measure. There are continuum many Turing degrees and they form an upper semilattice under Turing reducibility. All computable sets have Turing degree zero. It is easy to see that if G is of rank 1, then G has exactly two orders and they are computable. Solomon showed that if G has a finite rank greater than 1, then G has an order in every Turing degree. On the other hand, if G is of infinite rank, then G does not necessarily have a computable order, as shown by Downey and Kurtz.

 

Mathematics Colloquium

Friday, November 9, 2007

1:002:00 p.m.

Place: Monroe Hall (2115 G Street), Room B02

Speaker: Martin Davis, Courant Institute

http://cs.nyu.edu/cs/faculty/davism/

Title: Unsolvability and Undecidability in the Diophantine Realm

Abstract: The work on the negative solution of Hilbert's 10th problem will be surveyed with emphasis on applications, recent work, and open problems.

 

 

Graduate Student Seminar

 

Thursday, December 6, 2007

2:153:15 p.m.

Place: Monroe Hall (2115 G Street), Room 267

Speaker: Michael Moses, GWU

http://home.gwu.edu/~moses/

Title: Compactness in Mathematical Logic

Abstract: Two well known mathematical languages, the classical one of Aristotelian Logic and the everyday one of First Order Logic, are ‘compact’ in that, for any (infinite) collection of sentences in these languages, if every finite sub-collection 'is satisfiable', then so is the whole collection. It is surprisingly easy to see why these languages are compact. Even more surprising are the ramifications of their compactness, in all areas of mathematics, from classical analysis to modern combinatorics and, most especially, in mathematical logic, where it has some unsettling things to say about the mathematical languages that we employ, and the mathematical proofs that we seek. I will begin this talk with an historical exploration of compactness and its connection with the corresponding topological concept from which it gets its name, follow this with examples of the use of compactness in the ‘non-standard analysis’ of Abraham Robinson and the ‘probabilistic method’ of Paul Erdos, and close with a brief discussion of what compactness says about mathematical languages and proofs.

 

Thursday, November 29, 2007

2:153:15 p.m.

Place: Monroe Hall (2115 G Street), Room 267

Speaker: Sarah Pingrey, GWU

http://home.gwu.edu/%7Espingrey/

Title: Computability and the Halting Problem

Abstract: Computability theory was invented in the 1930’s by Turing, Gödel, Church, and Kleene, among others, who gave formal definitions of a computable function. All of these definitions turned out to be equivalent. The Church-Turing Thesis, generally accepted by all computability theorists, says that the formal notion of a computable function captures the intuitive idea of a computable function. I will discuss what it means for a function, set, and relation to be computable, and computably enumerable and then define the Turing degrees. The Turing degree of a set says how uncomputable a set is. Then, we will discuss the halting problem, which is a natural example of a set that is computably enumerable but not computable. This talked is aimed at undergraduates.

 

Friday, November 16, 2007

1:002:00 p.m.

Place: Monroe Hall (2115 G Street), Room 267

Speaker: Michele Friend, Department of Philosophy, GWU

Title: An Introduction to the Realist and Constructivist Philosophies of Mathematics

Abstract: I shall be outlining the basic positions which fall under “realism” and “constructivism” in logic/mathematics. I shall also be giving a quick set of indicators, so you can tell which one you are talking to! I'll then outline some of the motivations for both positions and examine some contentious formal arguments.

 

Thursday, October 25, 2007

2:153:15 p.m.

Place: Monroe Hall (2115 G Street), Room 267

Speaker: Jennifer Chubb, GWU

http://home.gwu.edu/%7Ejchubb/

Title: An Algorithmic Approach to Linear Orderings

Abstract: Starting with first principles, I’ll talk about properties of linear orderings and relations on linear orderings in the context of computability theory. After some examples and a brief survey of research in this area, I’ll explain some new results.