LOGIC SEMINAR

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

Spring 2017

(Jointly with Math Colloquium)

Friday, April 28, 2017

10:30–11:30a.m.

Speaker: Rumen Dimitrov, Western Illinois University

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

Place: Rome Hall (801 22^nd Street), Room 204

Title: The age of cohesive powers

Abstract: Fraïssé defined the age of a structure A to be the class of all structures isomorphic to the finitely generated substructures of A. He then used this term to refer to one structure as being younger than another. In this talk, I will consider the age of the rationals Q as a dense linear ordering without endpoints and as a field, and will discuss connections with the earlier notion of the cohesive powers of Q. I will also establish different model-theoretic properties of cohesive powers. 

Wednesday, April 19, 2017

5:30–6:30p.m.

Speaker: Trang Ha, GWU

Place: Rome Hall (801 22^nd Street), Room 351

Title: Representation of the spaces of orders on computable magmas

Abstract: We consider order relations on a computable magma. We discuss how these orders are represented as infinite paths of a computable binary tree, while the Turing degrees are preserved. Using the natural topology defined on the set of orders, we investigate the topological properties of the space of orders. The lack of computable orders leads to an interesting description of the space.

Wednesday, April 12, 2017

5:30–6:30p.m.

Speaker: Hakim Walker, GWU

Place: Rome Hall (801 22^nd Street), Room 351

Title: Computable directed graphs with non-computable properties

Abstract: In 2014, Cenzer, Harizanov, and Remmel investigated computable injection structures, two-to-one structures, and (2,0):1 structures, all of which are types of infinite directed graphs derived from computable functions. In this talk, we will define a (2,1):1 structure and discuss various related computability-theoretic properties, including branching, branch isomorphisms, computable categoricity, and relative computability categoricity. 

Wednesday, April 5, 2017

5:30–6:30p.m.

Speaker: Valentina Harizanov, GWU

Place: Rome Hall (801 22^nd Street), Room 351

Title: Coding information into orders

Abstract: We will show how a set of natural numbers can be coded into an order on a group. This will allows us to realize a desired Turing degree, or even a strong degree, as the degree of an order on a structure from a large class of groups.

Thursday, March 30, 2017

4:00–5:00p.m.

Speaker: Michał Godziszewski, University of Warsaw and CUNY (Fulbright Research Scholar)

Place: Rome Hall (801 22^nd Street), Room 352

Title: Computable quotient presentations of models of arithmetic and set theory

Abstract: We will discuss two conjectures of Khoussainov and prove various extensions of Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a computably enumerable equivalence relation. No nonstandard model of arithmetic in the language {+, x, ≤} has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even of much weaker set theory has a computable quotient presentation by any equivalence relation of any complexity. Similarly, no nonstandard model of finite set theory has a computable quotient presentation. We will further discuss the difficulties of computable quotient presentations in the case of purely relational structures.

Wednesday, March 1, 2017

5:30–6:30p.m.

Speaker: Hakim Walker, GWU

Place: Rome Hall (801 22^nd Street), Room 351

Title: Diagonalizing against Scott families

Abstract: A computable structure M is computably categorical if for every computable copy C of M, there is a computable isomorphism from M to C. Furthermore, a computable structure M is relatively computably categorical if for every copy B of M, there is an isomorphism computable in the atomic diagram of B. Goncharov showed that M is relatively computably categorical if and only if M has a formally computably enumerable Scott family. Every relatively computably categorical structure is also computably categorical, but the converse does not hold. We will present the construction of a directed graph that is computably categorical but not relatively so, by demonstrating the technique of diagonalizing against Scott families.

Special Colloquium

https://math.columbian.gwu.edu/colloquia

Friday, February 24, 2017

1:30–2:30pm

Speaker: William Boney, Harvard University

Place: MPA (805 21st St NW), Room 305

Title: Making nonelementary classes more elementary

Abstract: Classification theory seeks to organize classes of structures (such as algebraically closed fields, random graphs, dense linear orders) along dividing lines that separate classes into well-behaved on one side and chaotic on the other. Since its beginning, classification theory has discovered a plethora of dividing lines for classes axiomatizable in first-order logic and has been applied to solve problems in algebraic geometry, topological dynamics, and more.

However, when looking at examining nonelementary classes (such as rank 1 valued fields or pseudoexponentiation), the lack of compactness is a serious impediment to developing this theory. In the past decade, Grossberg and VanDieren have isolated the notion of tameness. Tameness can be seen as a fragment of compactness that is strong enough to allow the construction of classification theory, but weak enough to be enjoyed by many natural examples. We will discuss the motivation for classification theory in nonelementary classes and some recent results using tameness, focusing on illuminating examples. 

Special Colloquium

https://math.columbian.gwu.edu/colloquia

Thursday, February 23, 2017

1:30–2:30pm

Speaker: James Freitag, University of Illinois at Chicago

Place: Phillips Hall (801 22^nd Street), Room 217

Title: Model theory and Painlevé equations

Abstract: The Painlevé equations are six families of nonlinear order two differential equations with complex parameters. Around the start of the last century, the equations were isolated for foundational reasons in analysis, but the equations have since arisen naturally in various mathematical contexts. In this talk, we will discuss how to use model theory, a part of mathematical logic, to answer several open questions about Painlevé equations. We will also describe several other applications of model theory and differential algebraic equations to number theory. 

Wednesday, February 15, 2017

5:30–6:30p.m.

Speaker: Valentina Harizanov, GWU

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

Place: Rome Hall (801 22^nd Street), Room 351

Title: Diagonal method and tree strategies

Abstract: We will continue with more sophisticated diagonal arguments in computability theory and how they can be presented on a tree.

Wednesday, February 8, 2017

5:30–6:30p.m.

Speaker: Valentina Harizanov, GWU

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

Place: Rome Hall (801 22^nd Street), Room 351

Title: Diagonal method in computability theory

Abstract: We will show how Cantor’s diagonal method is generalized and used in computability theory to construct mathematical objects with various non-computable properties.

Fall 2016

Thursday, December 8, 2016

5:20–6:20p.m.

Speaker: Wesley Calvert, Southern Illinois University

http://math.siu.edu/faculty-staff/faculty/calvert.php

Place: Rome Hall (801 22^nd Street), Room 205

Title: Strong jump inversion for structures

Abstract: Consider the set of Turing degrees in which a fixed structure A has an isomorphic copy. For some classes of structures (such as Boolean algebras), there is a “forbidden region” for the least elements of this set: if there is a low copy, there must also be a computable copy. For other classes of structures, any spectrum is possible. Characterizing structures with this forbidden region seems difficult and is so far unsolved. The present talk will present a partial solution.

Thursday, November 10, 2016

5:20–6:20p.m.

Speaker: Timothy McNicholl, Iowa State University

https://sites.google.com/site/timothymcnicholl/

Place: Rome Hall (801 22^nd Street), Room 205

Title: Coarse computability

Abstract: It is well known that many algorithms that have very bad worst-case behavior work well in practice.  This has lead to the consideration of average-case behavior.  However, average-case behavior is often very difficult to calculate.  This has led to the consideration of efficient algorithms that fail only on a set of asymptotic density 0; such an algorithm is said to compute coarsely.  Recently, coarse computability has been a topic of study in computability theory, and a number of interesting connections to important computability-theoretic concepts such as algorithmic randomness and genericity have been discovered.  I will discuss the basic definitions and results as well as some open problems.

Math Colloquium

Friday, November 11, 2016

1:00–2:00pm

Speaker: Timothy McNicholl, Iowa State University

https://sites.google.com/site/timothymcnicholl/

Place: Rome Hall (801 22^nd Street), Room 206

Title: Structural Computable Analysis

Abstract: Computability theory is the mathematical study of the limits and potentialities of discrete computing devices. Computable analysis is the theory of computing with continuous data such as real numbers. Computable structure theory examines which computability-theoretic properties are possessed by the structures in various classes such as partial orders, Abelian groups, and Boolean algebras. Until recently computable structure theory has focused on classes of countable algebraic structures and has neglected the uncountable structures that occur in analysis such as metric spaces and Banach spaces. However, a program has now emerged to use computable analysis to broaden the purview of computable structure theory so as to include analytic structures. The solutions of some of the resulting problems have involved a delicate blend of methods from functional analysis and classical computability theory. We will discuss progress so far on metric spaces and Banach spaces, in particular $ell^p$ spaces, as well as open problems and new areas for investigation.

Graduate Student Seminar

Friday, October 14, 2016

3:00–4:00p.m.

Speaker: Iva Bilanovic, GWU

Place: Philips Hall (801 22^nd Street), Room 736

Title: Computable free groups and their bases

Abstract: W will consider the computability-theoretic complexity of finding a basis for a computable free group of infinite rank. We will use basic properties of free groups to build a computable sequence of computable infinitary π-2 formulas expressing the property of membership in a basis. The relativized limit lemma and these formulas will lead us to a π-2 basis. 

Logic-Topology Seminar

Wednesday, September 7, 2016

5:30–6:30p.m.

Speaker: Jozef Przytycki, GWU

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

Place: Rome Hall (801 22^nd Street), Room 771

Title: Playing with homotopy: Does Khovanov lead to bouquets of spheres in a polynomial time?

Abstract: The motivation for my talk and related research comes from the confluence of two fascinating recent developments: Khovanov homology in knot theory
and homological algebra and pseudo-knots in RNA folding theory in computational biology.