Dott. Sara Ugolini (Artificial Intelligence Research Institute, Spanish National Research Council (IIIA-CSIC)) will give a seminar on Wednesday 7 May 2025 at 11:30 in Sala Riunioni, DipMat.
Title: Almost natural semirings with difference.
Abstract: In this talk, we begin by considering the semiring of the natural numbers with (truncated) difference, N = (N, +, x, -, 0, 1). Its equational theory is not recursively axiomatizable, due to the fact that one can essentially encode in it the undecidability of Hilbert’s tenth problem. It is then interesting to study finitely axiomatizable varieties of semirings with difference which include the one generated by N, and are as close to it as possible. To this end, we introduce the variety of “almost natural semirings with difference”. We show that the subdirectly irreducible algebras in this variety coincide with the models of PA–, a weak form of Peano Arithmetic without induction that is an axiomatic extension of Robinson Arithmetic. Models of PA– are known to satisfy all Sigma_1 sentences true in N. This variety can be axiomatized by a few simple equations and enjoys several appealing universal-algebraic properties: it is connected to lattice-ordered rings, it is a discriminator variety, ideal determined and 0-regular —thus admitting an associated 0-assertional logic. Nevertheless, we will see that its connection to arithmetic still yields an undecidable equational theory. This talk is based on ongoing joint work with Guillermo Badia, Xavier Caicedo, and Carles Noguera.
0 Comments