Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, November 5, 2018 - 3:30pm

James Walsh

UC Berkeley

Location

University of Pennsylvania

4C8

 It is a well-known empirical phenomenon that natural axiomatic theories are well-ordered by consistency strength. Without a definition of "natural," it is difficult to state this precisely, much less to prove it. We approach this problem by studying computable order-preserving functions on the Lindenbaum algebra of a suitable base theory. We show that (i) no such function sends every consistent sentence A to a sentence with deductive strength strictly between A and A+Con(A) and (ii) for any such function f, if there is an iterate of Con that bounds f everywhere, then f must be somewhere equal to an iterate of Con. This is joint work with Antonio Montalbán.