Reconciling first-order logic to algebra

  • Walter Carnielli
  • Hugo Luiz Mariano
  • Mariana Matulovic


Starting from the algebraic method of theorem-proving based on the translation of logic formulasinto polynomials over nite elds, and by adapting the case of  rst-order formulas by employingcertain rings equipped with in nitary operations, this paper de nes the notion of  M-ring, a kind of polynomial ring de ned for each rst-order structure, by means of generators and relations. The notion of M-ring allows us to operate with some kind of in nitary version of Boolean sums and products, in this way expressing algebraically rst-order logic with a new gist. We then show how this polynomial representation of rst-order sentences could be seen as a legitimate algebraic semantics for first-order logic, alternative to cylindric and polyadic algebras an with a higher degree of naturalness. We brie y discuss how the method and their generalizations could be successfully lifted to n-valued logics and to other non-classical logics helping to reconcile some lost ties between algebra and logic.