LOGIC SEMINAR

http://home.gwu.edu/~harizanv/Logic%20Seminar%20F09.html

 

Spring 2015

 

Friday, May 22, 2015

1:002:00p.m.

Speaker: Rumen Dimitrov, Western Illinois University

http://www.wiu.edu/users/rdd104/home.htm

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

Title: Automorphism bases for the lattice of computably enumerable vector spaces

Abstract: The lattice L of computably enumerable vector spaces and its factor lattice modulo finite dimension, L*, have been extensively studied. Both lattices have complemented elements, also called decidable spaces. Ash and Downey showed that every computably enumerable vector space is a direct sum of two decidable spaces. Hence every automorphism of L is completely determined by its action on the decidable spaces. We will talk about other classes of computably enumerable vector spaces with this property.

 

Friday, April 3, 2015

1:002:00p.m.

Speaker: Scott Aaronson, MIT

http://scottaaronson.com/

Place: Government Hall, Room 101

Title: How Pervasive Is Incompleteness?

Abstract: I was asked to give a “speculative” math talk. So, I'll discuss the question of just how much “normal, finitary” math the Gödel incompleteness phenomenon might infest. I’ll first survey the types of independence and undecidability results that are known, and explain why in my view, none of them give a fully satisfactory answer. I’ll then speculate about the question, which I’m often asked, of whether the P vs. NP problem might turn out to be formally undecidable. Finally, I’ll discuss the Busy Beaver function, and its amazing ability to “concretize” questions of mathematical logic. I’ll mention some ongoing work with Adam Yedidia that aims to construct a small Turing machine whose (non-)halting is provably independent of the ZFC axioms.

 

 

At the American Math Society Meeting at Georgetown University, Washington, DC, March 7–8, 2015, there will be a Special Session on Computable Structure Theory. Speakers include: W. Calvert, J. Chubb, B. Csima, D. Cenzer, D. Dzhafarov, K. Fokina, S. Goncharov, J. Knight, K. Lange, C. Laskowski, A. Montalban, A. Morozov, R. Solomon, A. Shlapentokh, A. Soskova, M. Soskova.

Plenary Special Session talk will be given by:
Sergey Goncharov, Russian Academy of Sciences and Novosibirsk State U.

Definability and index sets of computable models.

Saturday, March 7

2:00–3:00 p.m.

Healy Hall (37th and O St.), Room 103

 

Friday, February 20, 2015

2:303:30p.m.

Speaker: Hakim Walker GWU

Place: Government Hall, Room 101

Title: Computable categoricity of a class of graphs

Abstract: We will discuss some computability-theoretic properties of graphs. Two computable graphs are said to be computably isomorphic if there is a computable isomorphism between them, and a computable graph is called computably categorical if every two computable presentations of the graph are computably isomorphic. We will discuss a characterization of the strongly locally finite graphs that are computably categorical, and present some examples. 

 

Friday, February 13, 2015

2:303:30p.m.

Speaker: Trang Ha, GWU

Place: Government Hall, Room 101

Title: Orderable but not computably orderable groups

Abstract: An order (also called a bi-order) on a group is a total ordering of the elements of its domain, which is both left-invariant and right-invariant with respect to the group operation. We will present a construction of a computable orderable group, which does not have a computable order.

 

Friday, February 6, 2015

2:303:30p.m.

Speaker: Leah Marshall, GWU

Place: Government Hall, Room 101

Title: Complexity of relations and the arithmetical hierarchy

Abstract: One way of examining computability-theoretic complexity of various natural properties (relations) of computable structures is to examine the complexity of the formulas that define the properties. In this talk, we will discuss some examples of the arithmetical complexity of various objects, pulling from the more standard and classic examples, as well as describing some examples from current research. We will review arithmetical hierarchy. The talk will be accessible to all graduate students.

 

Friday, January 23, 2015

2:303:30p.m.

Speaker: Andrew Hirsch, Cornell University

http://www.cs.cornell.edu/~akhirsch/

Place: Government Hall, Room 101

Title: Strictness, laziness, and effects
Abstract: Computer scientists want to be able to write down programs and have them correspond to a single computation. Sadly, most programming languages don't allow this: a single program might be read multiple ways. The standard strategies for fixing this, strictness and laziness, have been used since the 1930s, but continue to be poorly understood. The questions of why most languages have multiple readings, and why strictness and laziness are the natural solutions, remain mostly unanswered. We still lack even a formal definition of laziness that is not language-dependent.

This talk focuses on recent work that attempts to provide a formal definition and answer these questions. We achieve this by looking through the lens of effects, which allow us to classify computations in input-independent ways.

 

Colloquium

Friday, January 16, 2015

1:002:00p.m.

Speaker: Rumen Dimitrov, Western Illinois University

http://www.wiu.edu/users/rdd104/home.htm

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

Title: The rich structure of modular lattices arising from computably enumerable vector spaces
Abstract: Post’s problem in computability theory, dating back to 1944, is whether there exist a computably enumerable (c.e.) Turing degree that is neither computable nor the degree of the halting problem. His strategy was to find a non-computable co-infinite c.e. set with a “thin” complement. The original notion of thinness was called“simplicity.” A c.e. set the complement of which is infinite but has no infinite c.e. subset is called simple. Different, ever-stronger, notions of thinness were defined, but none of them gave a solution to Post’s problem. These notions, however, revealed some fascinating structural properties of the lattice E of c.e. sets under inclusion, and its factor lattice E* (E modulo finite sets). In the talk we will introduce the lattice L of c.e. subspaces of the fully algorithmic infinite dimensional vector space and its factor lattice L* (L modulo finite dimension). We will explore some important similarities and differences between E* and L*.

 

Thursday, January 15, 2015

3:455:00p.m.

Speaker: Rumen Dimitrov, Western Illinois University

Place: Duqués Hall, Room 362

Title: Standard and nonstandard ways of constructing nonstandard structures

Abstract: In this talk we will start with some standard ways of obtaining nonstandard structures. We will then introduce the notion of cohesive power B of a computable structure A (see [1]) over a cohesive set R. We will prove certain connections between satisfaction of different formulas and sentences in the original model A and its cohesive power B.

[1] R. D. Dimitrov, Cohesive powers of computable structures, Annuaire de l’Université de Sofia “St. Kliment Ohridski,” Faculté de Mathématiques et Informatique 99 (2009), pp. 193201.

 

 

Fall 2014

 

Friday, September 26, 2014

2:303:30p.m.

Speaker: Russell Miller, City University of New York

http://qcpages.qc.cuny.edu/~rmiller/

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

Title: Effective classification of computable structures

Abstract: Many classes of computable structures can be enumerated computably. For example, one readily gives a uniformly computable list of all computable linear orders, simply by enumerating the c.e. subsets of a single computable dense linear order. Of course, this list includes infinitely many computable copies of each computable linear order. To give a computable classification (up to isomorphism) of these linear orders would require computing such a list so that no two linear orders on the list are (classically) isomorphic to each other. This is known to be impossible.

The paradigm of a computable classification was given by Friedberg, who produced a uniformly computable listing of all c.e. sets, with no set appearing more than once in the listing. That is, he gave a computable classification of the c.e. sets up to equality.  We apply his method to yield a computable classification of the computable algebraic fields, up to (classical) isomorphism. We also follow Goncharov and Knight in showing that certain other classes have no computable classification.

Finally, we give a 0'-computable classification of the computable equivalence structures. This result, which extends (and uses) more work of Goncharov and Knight, means that there is a uniformly 0'-computable listing of all computably presentable equivalence structures, with no isomorphisms between any two distinct structures on the list; however, the structures on the list are only 0'-computable, not necessarily computable.  We conjecture that there is no computable classification of the computable equivalence structures.

 

Friday, September 19, 2014

2:303:30p.m.

Speaker: Leah Marshall, GWU

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

Title: Computable isomorphisms between partial computable injection structures

Abstract: A partial computable injection structure is a mathematical structure consisting of a computable set of natural numbers and a partial computable, injective (1-1) function.  The “shape” of these structures is determined by the orbits of the elements; that is, what happens when we apply our function to an element repeatedly.  These structures can therefore be completely classified up to isomorphism by the numbers, types, and sizes of their orbits. However, we know that isomorphisms alone do not necessarily preserve the computability-theoretic properties of mathematical structures.  We examine partial computable injection structures with computable isomorphisms, and we explain what goes wrong in structures without such computable isomorphisms.  Additionally, we do the same for partial computable injection structures under Δ2-isomorphisms and Δ3-isomorphisms.

 

Logic-Topology Seminar

Friday, September 12, 2014

2:303:30p.m.

Speaker: Jozef Przytycki, GWU

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

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

Title:   Simplicial modules, quantum plane and q-polynomial of rooted trees

Abstract: For the 30th anniversary of the Homflypt polynomial of links, I propose a new polynomial invariant of rooted trees. I will relate this to the Kauffman bracket (version of the Jones polynomial) and to (pre)simplicial categories.