University Seminars: Logic Across Disciplines Archives

Spring 2019

Title: Cohesive Powers: Structures in General and Linear Orders
Speaker:  Rumen Dimitrov, Western Illinois University,
Date and Time:  Friday, April 19, 1:00PM-2:00PM
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  The fundamental theorem of cohesive powers establishes relationship between the satisfiability of formulas (sentences) in a computable structure and in its cohesive power. In this talk, I will survey known results about cohesive powers and will show that different computable presentations of a computable structure may have non-isomorphic (not even elementary equivalent) cohesive powers. I will then present results about cohesive powers of linear orders, which are based on recent joint work with Harizanov, Morozov, Shafer, A.Soskova, and Vatev. 

Title: The Rigour of Proof
Speaker:  Michele Friend, Philosophy Department, GWU,
Date and Time:  Friday, March 29, 12:00PM-1:00PM
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  What is a rigorous proof? When is a proof sufficiently rigorous? What is the importance of rigour in a mathematical proof? To answer the first question, we begin with a comparison between a formal proof and a rigorous proof. A rigorous proof need not be formal, but it needs to be possible, in principle, to make it formal. To answer the second, we start with the distinction between sufficiently rigorous for acceptance by other mathematicians, sufficiently rigorous to establish a result and sufficiently rigorous to elicit further questions. The importance of rigour in a proof has several answers. A realist about the ontology of mathematics might well accept a non-rigorous proof since it establishes a truth guaranteed by the ontology of mathematics, in this case rigour is of psychological or epistemological importance at best. In contrast, constructivist philosophers and mathematicians would assert that the term ‘rigorous proof’ is redundant, since for them, a proof lacking in rigour is not a proof, it is at best a purported proof. Pluralists give a third, more nuanced answer. 

Title:Measuring Complexity in Computable Structure Theory
Speaker:  Valentina Harizanov, GWU
Date and Time:  Friday, February 22, 12:00-1:00PM
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  In order to measure complexity of problems in computable structure theory, one of the main strategies is to find an optimal description of the class of structures under investigation. This often requires the use of various algebraic properties of the structures. To prove the sharpness of our description, we use the notion of many-one completeness. The complexity is often expressed using hyper-arithmetical sets or their differences. As examples of different complexity problems we will present some recent results.

Title: Computability via definability and polynomial computability
Speaker:  Sergei Goncharov, Russian Academy of Sciences
Date and Time: Wednesday, February 6, 3:45-4:45PM
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  Computability on abstract models can be based on definability via Delta _0 and Sigma formulas. We introduce computability over an abstract model M based on definability over hereditary finite subset superstructure over M or hereditary finite list-extension over M. We will consider different enrichments of our language for the notion of terms and discuss the problem of complexity of definable functions. It is a basis for constructing a logic programming language. We will construct extensions with different properties of computability.

Title: Fraisse limits, ages, and computability
Speaker:  Valentina Harizanov, GWU
Date and Time:  Friday, February 1, 12:00-1:00PM
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  Fraisse studied countable structures A through analysis of the age of A, the set of all finitely generated substructures of A. We will focus on Fraisse limits and other structures with similar automorphism extension properties, and present some recent results concerning their computability-theoretic properties.

Fall 2018

Title: Homotopy Type Theory, the confluence of logic and space
Speaker:  Tslil Clingman, Johns Hopkins University
Date and Time:  Friday, November 30, 3:30-4:30PM
Place: Phillips Hall (801 22nd Street), Room 736

Abstract:  In this talk we will learn how to express ourselves in the language of Homotopy Type Theory and see how it is represents the natural merging of logic and space. We will take some time to consider how identity types, and in particular univalence, free us from certain artificial restrictions of classical logic(s) and foundational systems and give rise to a rich and pleasing theory. Time permitting, we will discuss the role of Univalent Foundations and how Homotopy Type Theory in particular may be leveraged as a foundational system to the direct advantage of the working mathematician.

Title: Relatively C-categorical structures
Speaker:   Valentina Harizanov, GWU
Date and Time:  Friday, November 2, 1-2PM
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  For a computability-theoretic complexity class C, we say that a computable structure A is relatively C-categorical if for every isomorphic structure B, there is an isomorphism that is of complexity C using the atomic diagram of B as an oracle. This notion is more general than C-categoricity and can be expressed syntactically using nice Scott families of formulas. We will give examples from familiar classes of structures and survey recent related results.

Title:  Limit computably categorical structures
Speaker:   Valentina Harizanov, GWU

Date and Time:  Friday, October 26 2018, 01:00pm-02:00pm
Place: Rome Hall (801 22nd Street), Room 771

AbstractWe say that a computable structure is limit computably categorical if for every isomorphic computable structure there is an isomorphism that is computable in the halting set. This notion can be further generalized, and there is a natural connection with definability using computable infinitary formulas. We will investigate limit computably categorical structures from some familiar classes, although such characterization is not known even for linear orders, trees of finite height, equivalence structures, or abelian p-groups.

Title:  Degree Structure of Effective Boolean Algebras
Speaker:   Rumen Dimitrov, Western Illinois University
Date and Time:  Friday, October 12 2018, 01:00pm-02:00pm
Place: Rome Hall (801 22nd Street), Room 771

Abstract: We establish degree embedding results for:  (1) Subalgebras of effective Boolean algebras, and (2) Lattices of subalgebras of effective Boolean algebras. The talk is based on joint work with V. Harizanov and A. Morozov.

Title:  The Algorithmic Complexity of Detecting Group Properties
Speaker:   Iva Bilanovic, GWU, GWU
Date and Time:  Friday, September 28 2018, 01:00pm-02:00pm
Place: Rome Hall (801 22nd Street), Room 771

Abstract: We consider the question: from a “nice” description of a group, can we detect whether or not it has some property of interest? Our nice descriptions will be recursive presentations and computable atomic diagrams. We show that for classes of groups with such descriptions, the detection of a Markov property is not computable. Then we look at some specific properties of high computability theoretic complexity. This will be a more technical continuation of my previous talk, but all necessary background material will be presented. 

Title:  Decision Problems and Groups
Speaker:   Iva Bilanovic, GWU
Date and Time:  Friday, September 7 2018, 01:00pm-02:00pm
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  We will discuss decision problems, those that can be formulated as yes/no questions of the inputs, and how to determine the algorithmic complexity of a procedure that makes such decisions. Computable functions, the Kleene-Mostowski arithmetical hierarchy of sets, and other related notions and topics will be discussed at length. In the final portion of the talk, we will turn our attention to decision problems both for recursively presented and for computable groups.

Title:  Multiplying Fractions in a Topological Way
Speaker:   Jozef Przytycki, GWU -
Date and Time:  Friday, September 21 2018, 01:00pm-02:00pm
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  TBA

Spring 2018

Title:Working seminar about developing a formal system representing reasoning in chemistry
Speaker: Prof. Michele Friend, Department of Philosophy.
Date and Time:  Thursday, April 27, 2018 11:00am–12:00noon
Place: Phillips Hall (801 22nd Street), Room 736

Title:Scott Ranks of Scattered Linear Orders
Speaker: Rachael Alvir, University of Notre Dame
Date and Time:  Thursday, April 26, 2018 12:30PM-1::30 PM
Place: Rome Hall(801 22nd Street), Room 351

Abstract: The logic L(omega1, omega) is obtained from regular finitary first-order logic by closing under countable conjunctions and disjunctions. There is a kind of normal form for such sentences. The Scott rank of a countable structure A is the least complexity of a sentence A of L(omega1, omega), which describes A up to isomorphism among countable structures. Every scattered linear order is associated with an ordinal known as its Hausdorff rank. We give sharp upper bounds on the Scott rank of a scattered linear order given its Hausdorff rank, along the way calculating some of the back-and-forth relations on this class. These results generalize previously obtained results on the Scott ranks of ordinals and Hausdorff rank 1 linear orders.

Title:Detecting Nilpotence in Classes of Groups
Speaker: Iva Bilanovic, GWU
Date and Time:  Friday, March 30, 2018 11:00AM-12::00 PM
Place: Phillips Hall (801 22nd Street), Room 736

Abstract: Detecting an arbitrary Markov property is π2-hard in the class of recursively presented groups and is π1-hard in the class of computable groups. In other words, even when a computable description of a group is given we cannot algorithmically decide whether the group has some property. Certain properties attain even higher level of complexity. We will investigate nilpotence and precisely locate its undecidability in the arithmetical hierarchy.  

Title: Structural Properties of Spectra and Omega-Spectra
Speaker:Alexandra Soskova, Sofia University, Bulgaria
Date and Time: Thursday, March 22, 2018, 12:30-1:30 PM
Place: Rome Hall (801 22nd Street), Room 531

Abstract: We consider the degree spectrum of a structure from the point of view of enumeration reducibility and omega-enumeration reducibility. We will give an overview of several structural properties of degree spectra and their co-spectra, such as a minimal pair theorem and the existence of quasi-minimal degrees for degree spectra and receive as a corollary some fundamental theorems in enumeration degrees. We will show that every countable ideal of enumeration degrees is a co-spectrum of a structure and if a degree spectrum has a countable base then it has a least enumeration degree. Next we investigate the omega-enumeration co-spectra and show that not every countable ideal of omega-enumeration degrees is an omega-co-spectrum of a structure.

TitleTransforming Machine Learning Heuristics into Provable Algorithms: Classical, Stochastic, and Neural
Speaker: Cheng Tang, GWU, Computer Science
Date and Time: Friday February 23, 11:00-12:00 noon
Place: Phillips Hall (801 22nd Street), Room 736

Abstract: A recurring pattern in many areas of machine learning is the empirical success of a handful of “heuristics”, i.e., any simple learning procedure favored by practitioners. Many of these heuristic techniques lack formal theoretical justification. For unsupervised learning, Lloyd's k-means algorithm, while provably exponentially slow in the worst-case, remains popular for clustering problems arising from different applications. For supervised learning, random forest is another example of a winning heuristic with many variants and applications. But the most prominent example is perhaps the blossoming field of deep learning, which is almost entirely composed of heuristics; the practical success of a deep learning algorithm usually relies on an experienced user skillfully and creatively combining heuristics. In this talk, I will discuss some of my thesis work in advancing the theoretical understanding of some of the most widely used machine learning heuristics.

Title: Effective Ultraproducts and Their Applications
Speaker: Rumen Dimitrov, Western Illinois University
Date and Time: Thursday February 8, 12:30-1:30
Place: Phillips Hall (801 22nd Street), Room 730

Abstract: We use cohesive (effectively indecomposable) sets to build nonstandard versions of the field of rational numbers. We study the isomorphism types of these models when the complements of the cohesive sets are computably enumerable. Using Koenigsmann’s work on Hilbert's Tenth Problem we give a new proof that these fields are rigid.

Title:  Topological Spaces of Orderings of Algebraic Structures
Speaker:   Jennifer Chubb, University of San Francisco and GWU
Date and Time:  Friday, February 2 2018 11:00 am-12 noon
Place: Phillips Hall (801 22nd Street), Room 736

Abstract: A left- or bi- partial ordering of an algebraic structure is a partial ordering of the elements of the structure that is invariant under the structure acting on itself on the left or, respectively, both on the left and on the right.  In this talk, we will consider the spaces of total left and bi-orderings of a group, how these spaces can be visualized as the paths of binary trees, and their computational and topological properties.

Title:  Encoding Noncomputable Sets into Orders on Computable Structures
Speaker:   Valentina Harizanov, GWU
Date and Time:  Friday, January 26, 2018 11:00 am-12 noon
Place: Phillips 736

Abstract: We consider a structure with a binary operation, which admits orders that are invariant under the operation. The space of these orders is compact under a natural topology, and in many cases homeomorphic to the Cantor set. For such computable structures, including many groups, we show when it is possible to encode an arbitrary set into an order so that their Turing degrees are preserved.

Fall 2017

Title:   An intuitive description of toposes, toposes as a description of intuitionism

Speaker:    Tslil Clingman, Johns Hopkins University

Date and Time: Thursday, November 30,  2017, 2:30pm-3:30pm

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

Abstract:   In this talk we will begin by examining, by way of example, the notion of a topos, a category exhibiting certain structural properties satisfied in particular by the familiar category of sets and functions but many strange and wonderful examples besides. We will then observe how the presence of certain structural properties naturally equips a topos with `internal' and `external' models intuitionistic propositional logic. From here we will explore the `Mitchell-Bènabou' language of a topos -- a framework which will allow us to redevelop much of the usual language of set theory internal to any topos. That is, we will see how we may make sense of forming objects of a topos via comprehensions, quantifiers and many other appropriate tools as in the case of "surjections(X,Y) = {f  Y^X | yxX [f(x)=y]}" for the (object of) surjections from X to Y. That objects defined in this manner are in factthe ones we desired depends further on the semantics of internal language, the so termed Kripke-Joyal semantics of a topos. Time allowing we will develop this more fully and explore the relation this bears to the forcing arguments of Cohen.

Title:   Gödel Index Sets of Computable Structures

Speaker:  Valentina Harizanov, GWU

Date and Time: Thursday, November 16 2017, 02:30pm-03:30pm

Place: Rome Hall 771

Abstract:  For a computable structure, we define its index set to be the set of all Gödel codes for computable isomorphic copies. We will show how to calculate precisely the complexity of the index sets for some familiar algebraic structures. We will further discuss the most recent results in this area.

Title:   Classification and measure for algebraic fields

Speaker:    Russell Miller, City University of New York

Date and Time: Friday, November 10, 2017, 03:00pm-04:00pm

Place: Rome Hall 771

Abstract:  The algebraic fields of characteristic 0 are precisely the subfields of the algebraic closure of the rationals, up to isomorphism.  We describe a way to classify them effectively, via a computable homeomorphism onto Cantor space.  This homeomorphism makes it natural to transfer Lebesgue measure from Cantor space onto the class of these fields, although there is another probability measure on the same class, which seems in some ways more natural than Lebesgue measure.  We will discuss how certain properties of these fields – notably, relative computable categoricity – interact with these measures:  the basic result is that only measure-0-many of these fields fail to be relatively computably categorical.  (The work on computable categoricity is joint with Johanna Franklin.)

Title:   Computable Classification Problem

Speaker:    Valentina Harizanov, GWU

Date and Time: Thursday, November 2, 2017, 02:30pm-03:30pm

Place: Rome Hall 771

Abstract:  The Scott Isomorphism Theorem says that for any countable structure M there is a sentence, in countable infinitary language, the countable models of which are exactly the isomorphic copies of M. Here, we consider a computable structure A and define its index set to be the set of all Gödel codes for computable isomorphic copies of AWe will present evidence for the following thesis. To calculate the precise complexity of the index set of A, we need a good description of A, using computable infinitary language, and once we have an optimal description, the exact complexity within a computability-theoretic hierarchy will match that of the description.

Title:   Trees of orderings

Speaker:   Jennifer Chubb, University of San Francisco

Date and Time: Friday, October 27, 2017, 04:15am-05:15pm

Place: Rome Hall 771

Abstract:  An ordering of an algebraic structure with identity can be often identified with the corresponding set of positive elements.  For a given algebraic structure, we can organize the cones of all the admitted orderings on a tree.  When the structure is computable, the tree can be constructed in an effective way.  Topological properties of this space of orderings can provide insight into algorithmic properties of the orderings, and vice versa.  In this talk, we will see how to construct these trees and what they can tell us.

Title:  Orderings of algebraic structures

Speaker:   Jennifer Chubb, University of San Francisco

Date and Time:  Thursday, October 19, 2017, 2:30pm-3:30pm

Place: Rome 771

Abstract:  A left- or bi- partial ordering of an algebraic structure is a partial ordering of the elements of the structure that is invariant under the structure acting on itself on the left or, respectively, both on the left and on the right. I will discuss algorithmic properties of the orderings admitted by a computable structures and their general properties, and describe some open problems.

Logic-Topology Seminar

Title:   Mathathon II: Search for Interesting Torsion in Khovanov Homology

Speaker:    Jozef Przytycki, GWU
Date and Time: Thursday, October 5, 2017, 2:30-3:30pm

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

Abstract:  We will describe the work of our Mathathon group (Sujoy Mukherjee, Marithania Silvero, Zhao Wang, Seung Yeop Yang), Dec. 2016–Jan. 2017, on torsion in Khovanov homology different from Z_2. Khovanov homology, one of the most important constructions at the end of XX century, has been computed for many links. However, computation is NP-hard and we are limited to generic knots of up to 35 crossings with only some families with larger number of crossings. The experimental data suggest that there is abundance of Z_2-torsion but other torsion seems to be rather rear phenomenon. The first Z_4 torsion appears in 15 crossing torus knot T(4,5), and the first Z_3 and Z_5 torsion in the torus knot T(5,6). Generally, calculations by Bar-Nathan, Shumakovitch, and Lewark suggest Z_p^k torsion in the torus knot T(p^k,p^k+1), p^k >3, but this has not yet been proven. We show, with Mathathoners, the existence of Z_n-torsion, n>3, for some infinite family of knots.  The simplest of them is obtained by deforming the torus knot T(5,7) by a t_2k-moves. We also prove the existence of knots with other torsion, the largest being Z_2^23, so the cyclic group of over 8 millions elements. We combine computer calculations (and struggle with NP hardness) with homological algebra technique.

The talk will be elementary and all needed notions will be defined.