University Seminar: Logic Across Disciplines

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.