In this talk, Badia will explore the following question: how weak can a logic be for Rosser's essential undecidability result to be provable for a weak arithmetical theory? It is well known that Robinson's Q is essentially undecidable in intuitionistic logic, and P. Hájek proved it in the fuzzy logic BL for Grzegorczyk's variant of Q which interprets the arithmetic operations as non-total non-functional relations. Badia will present a proof of essential undecidability in a much weaker substructural logic and for a much weaker arithmetic theory, a version of Robinson's R (with arithmetic operations also interpreted as mere relations). The result is based on a structural version of the undecidability argument introduced by Kleene and we show that it goes well beyond the scope of the Boolean, intuitionistic, or fuzzy logic.

To register for the Zoom discussion, please email Greg Lauro, gjlauro@uci.edu. A confirmation link will be sent to registrants prior to the start of the event.