Location

University of Bern,
UniS, Room A -119,
Schanzeneckstrasse 1,
3012, Bern.

Schedule

Tuesday May 28

09:30 - 12:00   Tommaso Moraschini: Universal classes and decidability
12:00 - 14:00   Lunch
14:00 - 16:30   Sara Ugolini: Structural and universal completeness in quasivarieties of logic
16:30 - 16:40   Closing ceremony

Abstracts

Universal classes and decidability
Tommaso Moraschini - University of Barcelona
Abstract: Ultraproducts are a tool for constructing nonstandard models of mathematical theories. We will instantiate this idea by reviewing the classical Łoś's theorem and the ultraproduct-based proof of the compactness theorem of first order logic. Notably, ultraproducts play also a central role in embeddability theorems. More precisely, a formula of first order logic is said to be universal when it consists of a block of universal quantifiers followed by a quantifier-free formula. Similarly, a class of mathematical structures is said to be universal when it can be axiomatized by universal formulas. We will use the ultraproducts construction to show that a class of structures is universal iff it is closed under the formation of isomorphic copies, substructures, and ultraproducts. The idea underlying this proof is that a structure A embeds into an ultraproduct of structures in a class K iff every finite partial subalgebra of A can be embedded into a member of K. We will combine this idea with a calculus for handling derivations between universal formulas to show that for many classes of algebras K there exists an algorithm that determines whether a given universal sentence is true in K. Examples from classical algebra as well as from modal and intuitionistic logics will be discussed throughout the talk and, perhaps, some exercises will be assigned.

Structural and universal completeness in quasivarieties of logic
Sara Ugolini - Artificial Intelligence Research Institute of the Spanish National Research Council (IIIA – CSIC)
Abstract: In this talk we will explore some connections between algebra and logic; mainly, we will talk about some bridge theorems. A bridge theorem is a statement connecting logical (and mostly syntactic) features of deductive systems and properties of classes of algebras; this connection is usually performed using the tools of general algebra and the rich theory that is behind it. The context of the talk is that of algebraizable logics in the sense of Blok-Pigozzi, where the consequence relation of the logic is fully and faithfully represented by the semantical consequence relation of the quasivariety of algebras that is its equivalent algebraic semantics.

In particular, we will talk about the notions of structural and universal completeness, from the algebraic and logical point of view. For a logic, being structurally complete means that each of its proper extensions admits new theorems; this notion can be formalized also using the concept of admissible rule. A rule is admissible in a logic if, whenever there is a substitution making its premises a theorem, such substitution also makes the conclusion a theorem. A logic is then structurally complete if all its admissible rules are derivable in the system. Structural completeness extends to the notion of universal completeness if multiple-conclusion rules are considered instead. We will recall the seminal results by Bergman, and show some recent new results about the weaker notions of active and passive structural and universal completeness. In a nutshell, we will see how the notions of structural and universal completeness are translated into properties of the quasiequational or universal theory of the countably generated free algebra in the considered quasivariety, and the connection with finitely presented and projective algebras in the quasivariety. Finally, we will discuss applications of the general results to quasivarieties related to substructural logics.