University Seminar: Logic Across Disciplines

Spring 2019

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.