Logic Colloquium 2022, the annual European Summer Meeting of the Association of Symbolic Logic, was held at Reykjavík University, June 27 through July 1, 2022. It was hosted by the ICE-TCS research center of the Department of Computer Science. The conference was held in a hybrid fashion with 101 participants in person and 55 participants online. ASL travel grants were awarded to 15 graduate students and recent PhDs.

Funding for the conference was provided by the Association for Symbolic Logic, the US National Science Foundation and Reykjavík University.

The success of the meeting owes a great deal to the enthusiasm and hard work of the Local Organizing Committee composed of Luca Aceto, Antonis Achilleos, Léo Exibard, Anna Ingolfsdóttir and Tarmo Uustalu as well as a number of local and guest helpers, Elli Anastasiadi, Aggeliki Chalki, Basile Gros, Eva Gunnarsdóttir, Dylan McDermott, Alexandre Nolin and Niccolò Veltri.

The Program Committee was chaired by Andrea Sorbi (University of Siena) and consisted of Antonis Achilleos (Reykjavík University), Ayşe Berkman (Mimar Sinan Fine Arts University), Zoé Chatzidakis (École Normale Supérieure), Ekaterina Fokina (Vienna University of Technology), Brice Helimi (University of Paris), Emil Jeřábek (Czech Academy of Sciences), Russell Miller (Queens College, City University of New York), Michael Rathjen (University of Leeds) and Ralph Schindler (University of Münster).

The program included two tutorial courses, twelve invited lectures, including the 33rd Annual Gödel Lecture, thirty-four invited lectures in six special sessions (computer science logic; model theory; philosophy of mathematics; proof theory and ordinal analysis; reverse mathematics and combinatorial principles; and set theory), and 76 contributed talks. The following tutorial courses were given.

Libor Barto (Charles University), Algebra and logic in the complexity of constraints.

Luca San Mauro (Sapienza University of Rome), Computable reductions of equivalence relations.

The 33rd Gödel Lecture was delivered by Patricia Blanchette.

Patricia Blanchette (University of Notre Dame), Formalism in logic.

The following invited plenary lectures were presented.

Tuna Altinel (Institut Camille Jordan), On the actions of finite permutation groups on groups of finite Morley rank.

Anton Freund (Technical University of Darmstadt), The uniform Kruskal theorem: a bridge between finite combinatorics and abstract set existence.

Gunter Fuchs (College of Staten Island and CUNY Graduate Center), Blurry HOD – a sketch of a landscape.

Paweł' M. Idziak (Jagiellonian University), Complexity of equations solving – kith and kin.

Juliette Kennedy (University of Helsinki), Do syntactic features supervene on semantic ones in foundations of mathematics? A few starting points.

Karen Lange (Wellesley College), Classification via effective lists.

Alexander G. Melnikov (Victoria University of Wellington), Primitive recursive mathematics.

Moritz Müller (University of Passau), Automating resolution is NP-hard.

Fedor Pakhomov (Ghent University), Limits of applicability of Gödel’s second incompleteness theorem.

Françoise Point (Mons University), On differential expansions of topological fields.

Andrea Vaccaro (Université Paris Cité), Games on classifiable C*-algebras.

Abstracts of invited and contributed talks given in person, remotely, or by title by members of the Association follow.

For the Program Committee

Andrea Sorbi

Abstract of the invited 33rd Annual Gödel Lecture

▸ PATRICIA BLANCHETTE, Formalism in logic.

Department of Philosophy, University of Notre Dame, USA.

E-mail: [email protected].

URL Address: http://sites.nd.edu/patricia-blanchette/.

Logic became “formal” at the end of the 19th century primarily in pursuit of deductive rigor within mathematics. But by the early 20th century, a formal treatment of logic had become essential to two new streams in the current of logic: the collection of crucial “semantic” notions surrounding the idea of categoricity, and the project of examining the tools of logic themselves, in the way that’s crucial for the treatment of completeness (in its various guises). This lecture discusses the variety of different tasks that have been assigned the notion of formalization in the recent history of logic, with an emphasis on some of the ways in which the distinct purposes of formalization are not always in harmony with one another.

Abstract of invited tutorials

▸ LIBOR BARTO, Algebra and logic in the complexity of constraints.

Department of Algebra, Faculty of Mathematics and Physics, Charles University, Czech Republic.

E-mail: [email protected].

URL Address: www.karlin.mff.cuni.cz/~barto.

What kind of mathematical structure in computational problems allows for efficient algorithms? This fundamental question now has a satisfactory answer for a rather broad class of computational problems, so called fixed-template finite-domain Constraint Satisfaction Problems (CSPs). This answer, due to Bulatov and Zhuk, stems from the interplay between algebra and logic, similar to the classical connection between permutation groups and first-order definability.

The aim of this tutorial is to explain this algebra-logic interplay, show how it is applied in CSPs, and discuss some of the major research directions.

▸ LUCA SAN MAURO, Computable reductions of equivalence relations.

Department of Mathematics, Sapienza University of Rome, Italy.

E-mail: [email protected].

The study of the complexity of equivalence relations has been a major thread of research in diverse areas of logic. A reduction of an equivalence relation $E$ on a domain $X$ to an equivalence relation $F$ on a domain $Y$ is a function $f:X\to Y$ which induces an injection on the quotient sets, ${X}_{/E}\to {Y}_{/F}$ . In the literature, there are two main definitions for this reducibility.

• • In descriptive set theory, Borel reducibility is defined by assuming that $X$ and $Y$ are Polish spaces and $f$ is Borel.

• • In computability theory, computable reducibility is defined by assuming that $X$ and $Y$ coincide with the set of natural numbers and $f$ is computable.

The theory of Borel equivalence relations is a central field of modern descriptive set theory and it shows deep connections with topology, group theory, combinatorics, model theory, and ergodic theory – to name a few. On the other hand, computable reducibility dates back to the 1970s and it found remarkable applications in a diverse collection of fields, including the theory of numberings, proof theory, computable structure theory, combinatorial algebra, and theoretical computer science.

Despite the clear analogy between the two notions, for a long time the study of Borel and computable reducibility were conducted independently. Yet, it is rapidly emerging a theory of computable reductions which blends ideas from both computability theory and descriptive set theory. This tutorial will overview such a theory. We will present computable, or computably enumerable, analogs of fundamental concepts from the Borel theory (e.g., benchmark equivalence relations, dichotomy results, orbit equivalence relations, the Friedman-Stanley jump), highlighting differences and similarities between the Borel and the computable setting. We will also report on recent progress in the abstract study of computable reducibility, focusing on both local structures of equivalence relations of given complexity and the global structure of all equivalence relations on the natural numbers.

Abstracts of invited plenary lectures

▸ TUNA ALTINEL, On the actions of finite permutation groups on groups of finite Morley rank.

Institut Camille Jordan, Université Claude Bernard Lyon 1, 43 blvd. du 11 novembre 1918, 69622, Villeurbanne cedex, France.

E-mail: [email protected].

Ever since the work of Borovik and Cherlin on permutation groups of finite Morley rank ([4]), there has been growing interest in faithful actions finite groups on various types of groups of finite Morley rank. This interest is due to various motivations: classifying highly generically transitive actions on sets ([1]), highly generically transitive representations ([2, 3]), definable actions of finite groups on groups of finite Morley rank, automorphisms of groups of finite Morley ranks. In my talk, I will give an overview of these lines of research and detail a recent result joint with Joshua Wiscons on lower bounds in the case of faithful actions of the alternating group on a nonsolvable group of finite Morley rank that does not contain involutions.

[1] Tuna Altnel and Joshua Wiscons, Recognizing ${PGL}_3$ via generic $4$ -transitivity, Journal of the European Mathematical Society , vol. 20 (2018), no. 6, pp. 1525–1559.

[2] Ayşe Berkman and Alexandre Borovik Groups of finite Morley rank with a generically sharply multiply transitive action, Journal of Algebra , vol. 368 (2012), no. X, pp. 237–250.

[3] Ayşe Berkman and Alexandre Borovik Groups of finite Morley rank with a generically multiply transitive action on an abelian group, Preprint, arXiv:2107.09997.

[4] Alexandre Borovik and Gregory Cherlin, Permutation groups of finite Morley rank, Model theory with applications to algebra and analysis. Vol. 2 (H. Dugald Macpherson, editor), Cambridge Univ. Press, Cambridge, 2008, pp. 29–124.

[5] Luis Jaime Corredor and Adrien Deloro and Joshua Wiscons, $Sym(n)$ - and $Alt(n)$ -modules with an additive dimension, eprint (2022) arXiv:2111.11498.

▸ ANTON FREUND, The uniform Kruskal theorem: a bridge between finite combinatorics and abstract set existence.

Department of Mathematics, Technical University of Darmstadt, Schlossgartenstr. 7, 64289 Darmstadt, Germany.

E-mail: [email protected].

URL Address: https://sites.google.com/view/antonfreund.

An important theorem of J. Kruskal states that any infinite sequence ${t}_0,{t}_1,\dots$ of finite trees admits $i<j$ such that ${t}_i$ embeds into ${t}_j$ . As shown by H. Friedman, this theorem – and even a ‘finitized’ corollary – is unprovable in predicative axiom systems, such as the theory ${\mathrm{ATR}}_0$ from reverse mathematics. This is one of the most convincing mathematical examples for the incompleteness phenomenon from Gödel’s theorems.

The ‘minimal bad sequence lemma’ due to C. Nash-Williams provides a particularly elegant proof of Kruskal’s theorem. By a result of A. Marcone, this lemma is equivalent to the impredicative principle of ${\Pi}_1^1$ -comprehension, over a weak base theory from reverse mathematics. Kruskal’s theorem itself cannot be equivalent to this principle, as its quantifier complexity is too low. This suggests the following question:

In which sense can we view Kruskal’s theorem as the concrete ‘shadow’ of an abstract set existence principle?

To suggest an answer, I will present joint work with M. Rathjen and A. Weiermann [4], which shows that ${\Pi}_1^1$ - comprehension is equivalent to a uniform version of Kruskal’s theorem (with general recursive data types at the place of trees). Together with the aforementioned result of Marcone, this confirms the intuition that minimal bad sequences provide ‘the’ canonical proof.

An analogous equivalence [2] has been established between ${\Pi}_1^1$ -transfinite recursion, a minimal bad sequence result of I. Kříž, and a uniform version of Friedman’s extended Kruskal theorem with ordinal labels and gap condition. The results rely on previous work [1, 3] that connects the ‘concrete’ viewpoint of ordinal analysis with the more ‘abstract’ setting of reverse mathematics.

The results and proofs will be presented on an intuitive level. Beyond the specific case of Kruskal’s theorem, the hope is to shed some light on a remarkable phenomenon in modern mathematics: that concrete statements about finite objects are sometimes proved via abstract and infinite ones.

The work of Anton Freund has been funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project number 460597863.

[1] Anton Freund, ${\Pi}_1^1$ -comprehension as a well-ordering principle, Advances in Mathematics , vol. 355 (2019), article no. 106767, 65 pp.

[2] \bysame, Reverse mathematics of a uniform Kruskal-Friedman theorem, Preprint, arXiv:2112.08727, 25 pp.

[3] Anton Freund and Michael Rathjen, Well ordering principles for iterated ${\Pi}_1^1$ -comprehension, Preprint, arXiv:2112.08005, 67 pp.

[4] Anton Freund, Michael Rathjen and Andreas Weiermann, Minimal bad sequences are necessary for a uniform Kruskal theorem, Advances in Mathematics , vol. 400 (2022), article no. 108265, 44 pp.

▸ GUNTER FUCHS, Blurry HOD – a sketch of a landscape.

Department of Mathematics, CUNY College of Staten Island and Graduate Center, USA.

E-mail: [email protected].

URL Address: www.math.csi.cuny.edu/~fuchs.

Classically, a set is ordinal definable if it is the unique object satisfying a formula with ordinal parameters. Generalizing this concept, given a cardinal $\kappa$ , I call a set $<\kappa$ -blurrily definable if it is one of less than $\kappa$ many objects satisfying a formula with ordinal parameters (called a $<\kappa$ -blurry definition). By considering the hereditary versions of this notion, one arrives at a hierarchy of inner models, one for each cardinal $\kappa$ : the collection of all hereditarily $<\kappa$ -blurrily ordinal definable sets, which I call $<\kappa$ -HOD. In a ZFC-model, this hierarchy spans the entire spectrum from HOD to V.

The special cases $\kappa =\omega$ and $\kappa ={\omega}_1$ have been previously considered, but no systematic study of the general setting has been done, it seems. One main aspect of the study is the notion of a leap, that is, a cardinal at which a new object becomes hereditarily blurrily definable. The talk splits into two parts: first, the ZFC-provable properties of blurry HOD, which are surprisingly rich, and second, the effects of forcing on the structure of blurry HOD and the achievable leap constellations.

▸ PAWEŁ M. IDZIAK, Complexity of equations solving – kith and kin.

Theoretical Computer Science Department, Jagiellonian University, Kraków, Poland.

E-mail: [email protected].

The talk is intended to present latest achievements in searching what structural algebraic conditions a finite algebra $\mathbf{A}$ has to satisfy in order to have a polynomial time algorithm that decides if an equation $\mathbf{s}\left({x}_1,\dots, {x}_n\right)=\mathbf{t}\left({x}_1,\dots, {x}_n\right)$ , where $\mathbf{s},\mathbf{t}$ are polynomials over $\mathbf{A}$ , has a solution in $\mathbf{A}$ .

Several connections to modular circuits ${CC}^0$ of constant depth will be discussed. Most of the results are obtained together with Piotr Kawałek, Jacek Krzaczkowski or Armin Weiß.

▸ JULIETTE KENNEDY, Do syntactic features supervene on semantic ones in foundations of mathematics? A few starting points.

Department of Mathematics and Statistics, Helsinki University, Gustaf Hällströminkatu 2b, Finland.

E-mail: [email protected].

URL Address: http://www.math.helsinki.fi/logic/people/juliette.kennedy/.

The practice of foundations of mathematics is built around a firm distinction between syntax and semantics. But how stable is this distinction, and is it always the case that semantically presented mathematical objects, in the form e.g. of a model class, might give rise to a “natural logic” in which the model class is definable? Can a logic without a syntax be considered a logic at all? In this talk I will investigate different scenarios from set theory and model theory in which an investigation of the notion of an implicit or internal logic or syntax becomes possible. I will close by discussing some historical issues raised by Blanchette [1], Goldfarb [2] and others having to do with the relation between having a precise syntax and the development of metamathematics, in early foundational practice.

[1] Patricia Blanchette, From Logicism to Metatheory, The Palgrave Centenary Companion to Principia Mathematica (Bernard Linsky and Nicholas Griffin, editors), Palgrave Macmillan, Basingstoke, United Kingdom, 2013, pp. 59–78.

[2] Warren Goldfarb, Logic in the Twenties: the Nature of the Quantifier, The Journal of Symbolic Logic , vol. 44 (1978), no. 3, pp. 351–368.

▸ KAREN LANGE, Classification via effective lists.

Department of Mathematics, Wellesley College, USA.

E-mail: [email protected].

URL Address: https://www.wellesley.edu/math/faculty/karen_lange.

“Classifying” natural collections of structures is a common goal in mathematics. Providing a classification can mean different things, e.g., identifying a set of invariants that settle the isomorphism problem or creating a list of all structures of a given kind without repetition of isomorphism type. Here we discuss recent work on classifications of the latter kind from the perspective of computable structure theory. We’ll consider natural classes of computable structures such as vector spaces, equivalence relations, algebraic fields, and trees to better understand the nuances of classification via effective lists and its relationship to other forms of classification in this setting.

▸ ALEXANDER G. MELNIKOV, Primitive recursive mathematics.

School of Mathematics and Statistics, Victoria University of Wellington, New Zealand.

E-mail: [email protected].

In my talk I will discuss the current state of the rapidly developing field of ‘primitive recursive’ mathematics. The subject has many different aspects. The main motivation of this framework is to understand the role of unbounded search in computable mathematics: either eliminate it when possible, or prove that without the unbounded search the result fails. Also, primitive recursion serves as a ‘bridge’ between the more abstract Turing computable mathematics and the perhaps more applicable polynomial-time and automatic algebra and analysis.

Over that past several years, investigations into this direction have uncovered many deep technical issues and results that were completely ‘invisible’ in the more general Turing computable algebra, analysis, and infinite combinatorics. Some recent results of this sort simply have no direct analogy in computable structure theory. In my talk I will emphasise those results and research directions in primitive recursive mathematics that either lead to counter-intuitive results or give new insights into other branches of effective mathematics. In particular, connections with automatic structure theory and reverse mathematics will be mentioned.

▸ MORITZ MÜLLER, Automating resolution is NP-hard.

Faculty of Computer Science and Mathematics, University of Passau, Germany.

E-mail: [email protected].

Together with Albert Atserias we showed that it is NP-hard to find a resolution refutation that is at most polynomially longer than a shortest one. The talk presents this result in its historical context.

▸ FEDOR PAKHOMOV, Limits of applicability of Gödel’s second incompleteness theorem.

Department of Mathematics, Ghent University, Krijgslaan 281, B9000 Ghent, Belgium.

E-mail: [email protected].

The celebrated Gödel’s second incompleteness theorem is the result that roughly speaking says that no strong enough consistent theory could prove its own consistency. In this talk I will first give an overview of the current state of research on the limits of applicability of the theorem. And second I will present two recent results: first is due to me [1] and the second is due to Albert Visser and me [2]. The first result is an example of a weak natural theory that proves the arithmetization of its own consistency. The second result is a general theorem with the flavor of Second Incompleteness Theorem that is applicable to arbitrary weak first-order theories rather than to extension of some base system. Namely the theorem states that no finitely axiomatizable first-order theory one-dimensionally interprets its own extension by predicative comprehension.

[1] Fedor Pakhomov, A weak set theory that proves its own consistency, Preprint, arXiv:1907.00877.

[2] Fedor Pakhomov and Albert Visser, Finitely axiomatized theories lack self-comprehension, Preprint, arXiv:2109.02548.

▸ FRANÇOISE POINT, On differential expansions of topological fields.

Department of Mathematics, Mons University, 7000 Mons, Belgium.

E-mail: [email protected].

A. Tarski, A. Robinson and A. Macintyre have described languages for which real-closed fields, algebraically closed valued fields, p-adically closed fieds admit quantifier elimination (and as a consequence one has a good understanding of definable sets in these structures). In particular, these structures are respectively o-minimal, C- minimal, p-minimal (more generally of dp-rank $1$ ). More recently one has described satisfactory languages for which the corresponding theories admit elimination of imaginaries. In his work on Shelah’s conjecture on fields with the non independence property (NIP), W. Johnson has shown that a field of dp-rank $1$ , which is not strongly minimal can be endowed with a definable field topology.

Differential expansions of (topological) fields of characteristic $0$ , where there is a priori no interactions between the derivation and the topology, have been first considered by M. Singer in the case of real-closed fields and he showed that the theory of differential ordered fields has a model companion. This was later generalized by M. Tressl in the class of large fields (a class of fields introduced by F. Pop).

In this talk, we consider the following setting. Given a large field of characteristic $0$ endowed with a definable field topology and its theory $T$ , we denote by ${T}_{\delta }$ the theory of differential expansions of models of $T$ by a derivation $\delta$ (satisfying the usual axiom: $\delta \left(x+y\right)=\delta (x)+\delta (y)\wedge \delta (xy)=\delta (x)y+ x\delta (y)$ ). Under some further conditions on definable subsets in models of $T$ , we show the following. The class of existentially closed models of ${T}_{\delta }$ is first-order axiomatisable by a theory ${T}_{\delta}^{\ast }$ . Properties such as: quantifier elimination, the NIP property, elimination of imaginaries transfer from $T$ to ${T}_{\delta}^{\ast }$ . In order to show the last result, we first prove a cell decomposition theorem for models of $T$ , applying a similar strategy as for topological fields of dp-rank $1$ due to P. Simon and E. Walsberg and then we show that there are no new open definable sets in models of ${T}_{\delta}^{\ast }$ . This approach can be applied to certain theories of pairs of models of $T$ . These results were obtained in collaboration with N. Guzy and P. Cubides Kovacsics.

Then, using that the theories $T$ we consider, are geometric theories (the topological dimension is well-behaved), we pursue our analysis to describe finite-dimensional definable groups in models of ${T}_{\delta}^{\ast }$ . We relate them to definable groups in models of $T$ , using Weil’s approach to recover an algebraic group from generic data. This last part is ongoing work with A. Pillay and K. Peterzil.

▸ ANDREA VACCARO, Games on classifiable C*-algebras.

Department of Mathematics, Université Paris Cité, France.

E-mail: [email protected].

One of the major themes of research in the study of C*-algebras, over the last decades, has been Elliott’s program to classify separable nuclear C*-algebras by their tracial and K-theoretic data, customarily represented in the so- called Elliott Invariant. In this talk I will analyze some subclasses of algebras (such as approximately finite C*- algebras) which fall within the scope of Elliott Classification Program from the perspective of infinitary continuous logic. More specifically, I will discuss how the techniques developed to classify nuclear C*-algebras can be combined with metric analogues of Ehrenfeucht–Fraïssé games, allowing to reduce the study of elementary equivalence between C*-algebras to the analogous relation on the discrete structures (groups and ordered groups) composing the Elliott Invariant. I will moreover show how this reduction can be employed to build classes of approximately finite C*-algebras of arbitrarily high Scott rank.

Abstracts of invited talks in the Special Session on Computer Science Logic

▸ THORSTEN ALTENKIRCH, Should type theory replace set theory as the foundation of mathematics?

School of Computer Science, University of Nottingham, UK.

E-mail: [email protected].

Set theory in the form of Zermelo-Fraenkel’s axiomatic set theory is usually considered the standard foundation of mathematics. Type theory which is based on the static notion of types is an alternative offers many advantages: the notion of a type seems to be closer to mathematical practice, types hides implementation details which enables Voevodky’s univalence principle, and it is supported by a number of implementations providing the base for formal developments.

▸ SUSANNA F. DE REZENDE, Proofs, circuits, and total search problems.

Department of Computer Science, LTH Lund University, Sweden.

E-mail: [email protected].

Many recent results in both propositional proof complexity and boolean circuit complexity have been enabled, either directly or indirectly, by a deeper understanding of proofs and circuits as a consequence of viewing them through the lens of total search problems, and by the development of query-to-communication lifting theorems, which show that in certain scenarios query complexity lower bounds can be “lifted” to communication lower bounds. Such results include explicit strongly exponential lower bounds on monotone formula complexity, separations between the $\textsf{mon}\hbox{-} {\textsf{AC}}^i$ and the $\textsf{mon}\hbox{-} {\textsf{NC}}^i$ hierarchies, new techniques for proving lower bounds on the size of monotone circuits and of cutting planes proofs, exponential lower bounds on the size of cutting planes proofs for random CNF formulas, the resolution of the Alon- Saks-Seymour problem, and many others.

This talk will focus on characterizations of proofs and circuits using the theory of total search problems (TFNP), expanding on classical results in complexity theory such as the characterization of circuit depth by Karchmer- Wigderson games, and the equivalence between tree-like Resolution and decision trees. We will also discuss how lifting theorems and feasible interpolation provide a connection between the query and communication complexity of certain search problems, and how this perspective suggests a whole program for further research.

▸ FABIO MOGAVERO, Alternating (in)dependence-friendly logic.

Department of Electrical Engineering and Information Technology, Università degli Studi di Napoli Federico II, Italy.

E-mail: [email protected].

Informational independence is a phenomenon that emerges quite naturally in game theory, as players in a game make moves based on what they know about the state of the current play [8]. In games such as Chess or Go, both players have perfect information about the current state of the play and the moves they and their adversary have previously made. For other games, like Poker and Bridge, the players have to make decisions based only on imperfect information on the state of the play. Given the tight connection between games and logics, think for instance at game-theoretic semantics [5, 4, 1], a number of proposals have been put forward to reason with or about informational independence, most notably, Independence-Friendly Logic [2], Dependence Logic [7], and logics derived thereof.

Independence-Friendly Logic (IF) was originally introduced by Hintikka and Sandu [2], and later extensively studied, e.g., in [6], as an extension of First-Order Logic (FOL) with informational independence as first-class notion. Unlike in FOL, where quantified variables always functionally depend on all the previously quantified ones, the values for quantified variables in IF can be chosen independently of the values of specific variables quantified before in the formula. From a general game-theoretic viewpoint, however, the IF semantics exhibits some limitations. It treats the players asymmetrically, truly allowing only one of the two players to have imperfect information. In addition, sentences of the logic can only encode the existence of a uniform winning strategy for one of the two players and, as a consequence, IF does admit undetermined sentences, which are neither true nor false.

In this talk I will present an extension of IF, called Alternating (In)Dependence Friendly Logic (ADIF), tailored to overcome these limitations and that appears more adequate when reasoning about games with full imperfect information is the main concern. To this end, we introduce a novel compositional semantics, generalising Hodges’ semantics for IF based on trumps/teams [3, 7, 6], which (i) allows for restricting the two players, aiming at describing both symmetric and asymmetric imperfect information games, (ii) recovers the law of excluded middle for sentences, and (iii) grants ADIF the full descriptive power of Second Order Logic. We also provide both an equivalent Herbrand-Skolem semantics and a game-theoretic semantics for the prenex fragment of ADIF, the latter being defined in terms of a determined infinite-duration game that precisely captures the compositional semantics on finite structures.

This is joint work with Dylan Bellier, Massimo Benerecetti, and Dario Della Monica.

[1] J. Hintikka, Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic , Oxford University Press, 1973.

[2] J. Hintikka and G. Sandu, Informational Independence as a Semantical Phenomenon, ICLMPS’89 , Elsevier, 1989, pp. 571–589.

[3] W. Hodges, Compositional Semantics for a Language of Imperfect Information, Logic Journal of the IGPL , vol. 5 (1997), no. 4, pp. 539–563.

[4] K. Lorenz, Dialogspiele als semantische Grundlage von Logikkalkülen, Archiv für mathematische Logik und Grundlagenforschung , vol. 11 (1968), pp. 32–55.

[5] P. Lorenzen, Ein dialogisches Konstruktivitätskriterium, Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959 , Państwowe Wydawnictwo Nankowe, Warsaw, Poland, 1961, pp. 193–200.

[6] A. L. Mann, G. Sandu, and M. Sevenster, Independence-Friendly Logic - A Game-Theoretic Approach , Cambridge University Press, 2011.

[7] J. A. Väänänen, Dependence Logic: A New Approach to Independence Friendly Logic , London Mathematical Society Student Texts, vol. 70, Cambridge University Press, 2007.

[8] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior , Princeton University Press, 1944.

▸ JOANNA OCHREMIAK, On the power of symmetric linear programs.

University of Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence, France.

E-mail: [email protected].

We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates.

When we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs.

The talki is based on joint work with Albert Atserias and Anuj Dawar [1].

[1] Albert Atserias, Anuj Dawar, and Joanna Ochremiak, On the power of symmetric linear programs, Journal of the ACM , vol. 68 (2021), no. 4.

▸ REVANTHA RAMANAYAKE, Sequent calculi with restricted cuts for non-classical logics.

Bernoulli Institute, University of Groningen, The Netherlands.

E-mail: [email protected].

URL Address: https://www.rug.nl/staff/d.r.s.ramanayake/.

The primary motivation for cut-elimination is that it leads to a proof calculus with the subformula property. Such a proof calculus has a restricted proof search space and this is a powerful aid for investigating the properties of the logic. Unfortunately, many substructural and modal logics of interest lack a sequent calculus that supports cut-elimination. The overwhelming response since the 1960s has been to generalise the sequent calculus in a bid to regain cut- elimination. The price is that these generalised formalisms are more complicated to reason about and implement.

There is an alternative: remain with the sequent calculus by accepting weaker (but still meaningful) versions of the subformula property. We will discuss how cut-free hypersequent proofs can be transformed into sequent calculus proofs in a controlled way [2]. Combined with the quite general methodology [1] for transforming Hilbert axiomatic extensions into cut-free hypersequent calculi, this leads to an algorithm taking a Hilbert axiomatic extension to a sequent calculus with a weak subformula property.

Can we avoid this detour through the hypersequent calculus? This goes to the heart of a new programme called cut-restriction that aims to adapt Gentzen’s celebrated cut-elimination argument systematically so that cut-formulas are restricted (when elimination is not possible). We will present the early results in this programme: from arbitrary cuts to analytic cuts in the sequent calculi for bi-intuitionistic logic and $S5$ via a uniform cut-restriction argument (the results themselves are well-known).

Based on joint work with Agata Ciabattoni (TU Wien) and Timo Lang (UCL).

[1] A. Ciabattoni, N. Galatos, and K. Terui, From axioms to analytic rules in nonclassical logics, Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS) Pittsburgh, PA, USA, IEEE Computer Society, 2008, pp. 229–240.

[2] Agata Ciabattoni, Timo Lang, and Revantha Ramanayake, Bounded-analytic Sequent Calculi and Embeddings for Hypersequent Logics, The Journal of Symbolic Logic , vol. 86 (2021), no. 2, pp. 635–668.

▸ ALEXIS SAURIN, On the dynamics of cut-elimination for circular and non-wellfounded proofs.

IRIF, CNRS, Université Paris Cité & INRIA, Paris, France.

E-mail: [email protected].

In this talk, I will consider the structural proof theory of fixed-point logics and their cut-elimination theorems, focusing on their computational content.

More specifically, I will consider logics with least and greatest fixed-points, expressing inductive and coinductive properties, and proof systems for those logics admitting “circular” and non-wellfounded proofs [1, 2, 4, 5]. Those derivations are finitely branching but admit infinitely deep branches, possibly subject to some regularity conditions. Circular derivations are closely related with proofs by infinite descent [3] and shall be equipped with a global condition preventing vicious circles in proofs.

In order to unveil the computational content of those logical systems, I will concentrate on linear logic extended with least and greatest fixed points ( $\mu \mathrm{LL}$ ), that is, on the $\mu$ -calculus considered in a linear setting, where the structural rules of contraction and weakening are prohibited (or carefully controlled at least). In particular, following the spirit of structural proof-theory and of the Curry-Howard correspondence, we will be interested not only in the structure of provability but also in the structure of proofs themselves, corresponding to programs (while formulas correspond to data and codata types).

I will first introduce the non-wellfounded proof systems for $\mu \mathrm{LL}$ and for its exponential-free fragment, $\mu \mathrm{MALL}$ (that is, multiplicative and additive linear logic with least and greatest fixed points). After establishing cut-elimination for $\mu \mathrm{MALL}$ [2], I will show how to generalize the cut-elimination result to $\mu \mathrm{LL}$ (as well as to the intuitionistic and classical non-wellfounded sequent calculi). After that, I will discuss limitations of the validity condition considered above, from a computational perspective, and introduce a more flexible validity condition, called bouncing-validity [1], and establish a cut-elimination theorem for this richer system which, while proving the same theorems, admits more valid proofs that is, through the bridge of the Curry-Howard correspondence, more programs.

[1] David Baelde, Amina Doumane, Denis Kuperberg, and Alexis Saurin, Bouncing Threads for Circular and Non-wellfounded Proofs – Towards Compositionality with Circular Proofs, 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022 (Haifa, Israel), 2022, to appear.

[2] David Baelde, Amina Doumane, and Alexis Saurin, Infinitary Proof Theory: the Multiplicative Additive Case, 25th EACSL Annual Conference on Computer Science Logic, CSL 2016 (Marseille, France), Leibniz International Proceedings in Informatics, vol. 62. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 42:1–42:17.

[3] James Brotherston and Alex Simpson, Sequent Calculi for Induction and Infinite Descent, Journal of Logic and Computation , vol. 21 (2011), no. 6, pp. 1177–1216.

[4] Jérôme Fortier and Luigi Santocanale, Cuts for Circular Proofs: Semantics and Cut-elimination, Computer Science Logic 2013 (Torino, Italy), (Simona Ronchi Della Rocca, editor), Leibniz International Proceedings in Informatics, vol. 23. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013, pp. 248–262.

[5] Luigi Santocanale, A Calculus of Circular Proofs and Its Categorical Semantics, Foundations of Software Science and Computation Structures , (Mogens Nielsen and Uffe Engberg, editors), vol. 2303, Lecture Notes in Computer Science, Springer, 2002, pp. 357–371.

Abstracts of invited talks in the Special Session on Model Theory

▸ SYLVY ANSCOMBE, Henselian discretely valued fields and existential AKE principles.

Université Paris Cité and Sorbonne Université, CNRS, IMJ-PRG, F-75013 Paris, France.

E-mail: [email protected].

Ax–Kochen/Ershov (AKE) principles are known for various classes of henselian valued fields, including tame valued fields (itself including the case of equal characteristic zero) and the unramified mixed characteristic case. While the case of equal characteristic $p>0$ remains mysterious, in full generality, there has been progress in understanding the existential fragment of theories of such henselian valued fields.

In 2003, Denef and Schoutens obtained an axiomatization (and decidability) of the existential theory of ${\mathbb{F}}_p\left((t)\right)$ , expanded by a parameter for $t$ , assuming Resolution of Singularties in characteristic $p>0$ . Recently, with Dittmann and Fehm, we have shown a similar result with a weaker assumption. More generally: assuming a weak consequence of resolution of singularities, we obtain a transfer principle for the existential decidability of fields equipped with a discrete equicharacteristic henselian valuation and a distinguished uniformizer.

▸ SAMUEL BRAUNFELD AND MICHAEL C. LASKOWSKI, Monadic dividing lines and hereditary classes.

Computer Science Institute, Charles University, Malostranské nám. 25 11800 Praha 1, Czechia.

E-mail: [email protected].

Department of Mathematics, University of Maryland, College Park, 4176 Campus Dr College Park MD 20742, USA.

E-mail: [email protected].

A theory $T$ is monadically NIP if every expansion of $T$ by unary predicates is NIP. We will discuss how monadic NIP manifests in the theory $T$ itself rather than just in unary expansions, and how this can be used to produce structure or non-structure in hereditary classes. Analogous results concerning monadic stability may also be discussed.

[1] Samuel Braunfeld and Michael C. Laskowski, Characterizations of monadic NIP, Transactions of the American Mathematical Society, Series B , vol. 8 (2021), pp. 948–970.

▸ JAN DOBROWOLSKI, Tameness in positive logic.

Department of Mathematics, University of Manchester, UK.

E-mail: [email protected].

URL Address: https://www.math.uni.wroc.pl/~dobrowol.

Positive logic is a very flexible framework unifying full first-order logic with several other settings, such as Robinson’s logic (which studies existentially closed models of a possibly non-companionable first-order universal theory), hyperimaginary extensions of first-order theories (which are obtained by adding quotients by type-definable equivalence relations), and, in certain aspects, continuous logic.

The study of tameness in those contexts goes back to A. Pillay’s work on simple Robinson’s theories ([2]), and I. Ben Yaacov’s work on simple compact abstract theories ([3]). In the talk, I will present a joint work with M. Kamsma on NSOP ${}_1$ in positive logic and a joint work in progress with R. Mennuni on NIP in positive logic, discussing in particular the main motivating examples for the two projects: existentially closed exponential fields (studied before by L. Haykazyan and J. Kirby in [1]) and existentially closed ordered abelian groups with an automorphism.

[1] L. Haykazyan and J. Kirby, Existentially closed exponential fields, Israel Journal of Mathematics , vol. 241(2021), no. 1, pp. 89–117.

[2] A. Pillay, Forking in the Category of Existentially Closed Structures, Quaderni di Matematica , vol. 6 (2000), pp. 23–42.

[3] I. Ben Yaacov, Simplicity in compact abstract theories, Journal of Mathematical Logic , vol. 3 (2003), no. 2, pp. 163–191.

▸ ALEX KRUCKMAN, A new tree property.

Department of Mathematics and Computer Science, Wesleyan University, 265 Church Street, Middletown, CT 06459, USA.

E-mail: [email protected].

URL Address: https://akruckman.faculty.wesleyan.edu/.

One of the most important technical steps in the development of simplicity theory in the 1990s was a result now known as Kim’s Lemma: In a simple theory, if a formula $\varphi \left(x;b\right)$ divides over a model $M$ , then $\varphi \left(x;b\right)$ divides along every Morley sequence in $\mathrm{tp}\left(b/M\right)$ . More recently, variants of Kim’s Lemma have been shown by Chernikov, Kaplan, and Ramsey to follow from, and in fact characterize, two generalizations of simplicity in different directions: the combinatorial dividing lines ${\mathrm{NTP}}_2$ and ${\mathrm{NSOP}}_1$ . After surveying the Kim’s Lemmas of the past, I will suggest a new variant of Kim’s Lemma, and a corresponding new model-theoretic tree property, which generalizes both ${\mathrm{TP}}_2$ and ${\mathrm{SOP}}_1$ . I will also compare this new tree property with the Antichain Tree Property ( $\mathrm{ATP}$ ), another tree property generalizing both ${\mathrm{TP}}_2$ and ${\mathrm{SOP}}_1$ , which was introduced recently by Ahn and Kim. This is joint work with Nick Ramsey.

▸ MARIANA VICARÍA, Elimination of imaginaries in $\mathrm{\mathbb{C}}(({t}^{\Gamma}))$ _.

Department of Mathematics, University of California, Berkeley, Evans Hall, CA, USA.

E-mail: mariana\[email protected].

One of the most striking results in the model theory of henselian valued fields is the Ax-Kochen theorem, which roughly states that the first order theory of a finitely ramified henselian valued field is completely determined by the first order theory of the residue field and its value group.

A model theoretic principle follows from this theorem: any model theoretic question about the valued field can be reduced into a question to its residue field, its value groups and their interaction in the field.

Our leading question is: Can one obtain an Ax-Kochen style theorem to eliminate imaginaries in henselian valued fields?

Following the Ax-Kochen principle, it seems natural to look at the problem in two orthogonal directions: one can either make the residue field tame and understand the problems that the value group brings naturally to the picture, or one can assume the value group to be very tame and study the issues that the residue field would contribute to the problem. In this talk we will address the first approach. I will explain the sorts required to obtain elimination of imaginaries in henselian valued fields of equicharacteristic zero with residue field algebraically closed and more general value groups.

▸ TINGXIANG ZOU, The Elekes-Szabó problem for cubic surfaces.

Department of Mathematics, University of Münster, Germany.

E-mail: [email protected].

The Elekes-Szabó problem asks when a complex variety $V\subseteq {\prod}_{i=1}^3{W}_i$ has unexpected large intersections with Cartesian products of finite subsets ${X}_i\subseteq {W}_i$ for $1\le i\le 3$ . Under the assumption that ${X}_i$ ’s are in general position, Elekes and Szabó proved that one can always find commutative algebraic groups in this scenario. We explored the case when ${W}_i$ ’s are a fixed cubic surface $S$ in ${\mathrm{\mathbb{P}}}^3\left(\mathrm{\mathbb{C}}\right)$ and $V$ is the collinearity relation with the assumption that ${X}_i$ does not concentrate on any one-dimensional subvarieties of $S$ , which substantially weakens the general position assumption. We proved that when $S$ is a smooth quadric surface union a plane, then one cannot find such ${X}_i$ ’s. When $S$ is an irreducible smooth cubic surface, then ${X}_i$ ’s would contain a union of translates of arithmetic progressions on the family of planar cubic curves of $S$ . But the existence of such ${X}_i$ ’s is still open. This is a work-in-progress joint with Martin Bays and Jan Dobrowolski.

Abstracts of invited talks in the Special Session on Philosophy of Mathematics

▸ TIM BUTTON, MOON theory: Mathematical Objects with Ontological Neutrality.

UCL, Philosophy Department, 19 Gordon Square, London, WC1H 0AG, UK.

E-mail: [email protected].

URL Address: http://www.nottub.com/.

The iterative notion of set starts with a simple, coherent story, and yields a paradise of mathematical objects, which “provides a court of final appeal for questions of mathematical existence and proof” [5]. But it does not present an attractive mathematical ontology: it seems daft to say that every mathematical object is “really” some (pure) set. My goal, in this paper, is to explain how we can inhabit the set-theorist’s paradise of mathematical objects whilst remaining ontologically neutral.

I start by considering stories with this shape: (1) Gizmos are found in stages; every gizmo is found at some stage. (2) Each gizmo reifies (some fixed number of) relations (or functions) which are defined only over earlier-found gizmos. (3) Every gizmo has (exactly one) colour; same-coloured gizmos reify relations in the same way; same-coloured gizmos are identical iff they reify the same relations.

Such a story can be told about (iterative) sets: they are monochromatic gizmos which reify one-place properties. But we can also tell such stories about gizmos other than sets. By tidying up the general idea of such stories, I arrive at the notion of a MOON theory (for Mathematical Objects with Ontological Neutrality).

With weak assumptions, I obtain a metatheorem: all MOON theories are synonymous. Consequently, they are (all) synonymous with a theory which articulates the iterative notion of set (LT ${}_{+}$ ; see [1]). So: all MOON theories (can) deliver the set-theorist’s paradise of mathematical objects. But, since different MOON theories have different (apparent) ontologies, we attain ontological neutrality.

My metatheorem generalizes some of my work on Level Theory ([1], [2], [3]). It also delivers a partial realization of Conway’s “Mathematician’s Liberation Movement” [4, p.66].

[1] T. Button, Level Theory, Part 1: Axiomatizing the bare idea of a cumulative hierarchy of sets, The Bulletin of Symbolic Logic , vol. 27 (2021), pp. 436–460.

[2] \bysame, Level Theory, Part 2: Axiomatizing the bare idea of a potential hierarchy, The Bulletin of Symbolic Logic , vol. 27 (2021). pp. 461–484.

[3] \bysame, Level Theory, Part 3: A boolean algebra of sets arranged in well-ordered levels, The Bulletin of Symbolic Logic , vol. 28 (2022), pp. 1–26.

[4] J. Conway, On Numbers and Games , Academic Press, Inc., 1976.

[5] P. Maddy, Naturalism in Mathematics , Oxford University Press, 1997.

▸ LAURA CROSILLA, Hermann Weyl and the roots of mathematical logic.

Department of Philosophy, IFIKK, University of Oslo, Blindern, Norway.

E-mail: [email protected].

Hermann Weyl’s book Das Kontinuum [2] presents a coherent and sophisticated approach to analysis from a predicativist perspective. In the first chapter of [2], Weyl introduces a system of predicative sets, built “from the bottom up” starting from the natural numbers. He then goes on to show that large portions of 19th century analysis can be developed on that predicative basis. Das Kontinuum anticipated and inspired fundamental ideas in mathematical logic, ideas that we find in the logical analysis of predicativity of the 1950-60’s, in Solomon Feferman’s work on predicativity and in Errett Bishop’s constructive mathematics. The seeds of Das Kontinuum are already visible in the early [1], where Weyl, among other things, offers a clarification of Zermelo’s axiom schema of Separation. In this talk, I examine key intriguing ideas in [1], ideas that witness important debates among mathematicians at the beginning of the 20th century. I then argue that aspects of [1] foreshadow fundamental features of Das Kontinuum. This allows us to consider [2] under the new light offered by [1].

[1] H. Weyl, Über die Definitionen der mathematischen Grundbegriffe, Mathematisch-naturwissenschaftliche Blätter , vol. 7 (1910), pp. 93–95, 109–113.

[2] H. Weyl, Das Kontinuum. Kritische Untersuchungen über die Grundlagen der Analysis , Veit, Leipzig, 1918. Translated in English, Dover Books on Mathematics, 2003.

▸ SALVATORE FLORIO, Conceptions of absolute generality.

Department of Philosophy, University of Birmingham, UK.

E-mail: [email protected].

What is absolutely unrestricted quantification? Recent work on the possibility of absolute generality has highlighted that there are different legitimate answers to this question. Relying especially on [2], [1], and [3], I explore some of these answers, and their relations, in the context of different forms of type theory. The result is an initial analysis of different conceptions of absolute generality and of the theoretical value of the corresponding kinds of generalization.

[1] Tim Button and Robert Trueman, Against cumulative type theory, The Review of Symbolic Logic , forthcoming.

[2] Salvatore Florio and Nicholas K. Jones, Unrestricted quantification and the structure of type theory, Philosophy and Phenomenological Research , vol. 102 (2021), no. 1, pp. 44–64.

[3] \bysame, Two conceptions of absolute generality, manuscript.

▸ BRICE HALIMI, Geometrizing Kripke modal semantics.

Département d’Histoire de Philosophie des Sciences, Université Paris Cité & sphere, France.

E-mail: [email protected].

Kripke semantics for propositional modal logic is based on the notion of accessibility between possible worlds. The purpose of my talk is to take the latter notion literally, i.e., as indicating the existence of a path between two worlds, and thus to geometrize Kripke semantics by considering the space underlying the collection of all possible worlds as an important semantical feature in its own right. The resulting new modal semantics is worked out in a setting coming from Riemannian geometry, where Kripke semantics is shown to correspond to a special case (namely, the discrete one), and thus geometrization to amount to a generalization. Several completeness results, established between variants of well-known modal systems and certain geometric-metric properties, illustrate the fruitfulness of this new semantics.

Abstracts of invited talks in the Special Session on Proof Theory and Ordinal Analysis

▸ BAHAREH AFSHARI, From interpolation to proofs.

ILLC, University of Amsterdam, The Netherlands.

Department of Philosophy, Linguistics and Theory of Science, University of Gothenburg, Sweden.

E-mail: [email protected].

From a proof-theoretic perspective, the idea that interpolation is tied to provability is a natural one. Thinking about Craig interpolation, if a ‘nice’ proof of a valid implication $\phi \to \psi$ is available, one may succeed in defining an interpolant by induction on the proof-tree, starting from leaves and proceeding to the implication at the root. This method has recently been applied even to fixed point logics admitting cyclic proofs [1, 4]. In contrast, for uniform interpolation, there is no single proof to work from but a collection of proofs to accommodate: a witness to each valid implication $\phi \to \psi$ where the vocabulary of $\psi$ is constrained. Working over a set of prospective proofs and relying on the structural properties of sequent calculus is the essence of Pitts’ seminal result on uniform interpolation for intuitionistic logic [3].

In this talk we explore the opposite direction of the above endeavour, arguing that uniform interpolation can entail completeness of a proof system. We will demonstrate this in the case of propositional modal $\mu$ -calculus by showing that the uniform interpolants obtained from cyclic proofs [2] play an important role in establishing completeness for the natural Hilbert axiomatisation of this fixed point logic.

[1] Bahareh Afshari and Graham E. Leigh, Lyndon interpolation for modal mu-calculus, Language, Logic, and Computation TbiLLC 2019 , (Aybüke Özgün and Yulia Zinova, editors), vol. 13206, Lecture Notes in Computer Science, 2022, pp. 197–213.

[2] Bahareh Afshari, Graham E. Leigh and Guillermo Menédez Turata, Uniform interpolation from cyclic proofs: The case of modal mu-calculus., Automated Reasoning with Analytic Tableaux and Related Methods - 30th International Conference, TABLEAUX 2021 (Birmingham, UK), (Anupam Das and Sara Negri, editors), vol. 12842, Springer, 2021, pp. 335–353.

[3] Andrew M. Pitts, On an interpretation of second order quantification in first order intuitionistic propositional logic, The Journal of Symbolic Logic , vol. 57 (1992), no. 1, pp. 33–52.

[4] Daniyar Shamkanov, Circular Proofs for Gödel-Löb Logic , arXiv preprint arXiv:1401.4002, 2014.

▸ JUAN P. AGUILERA, The ${\Pi}_2^1$ -spectrum conjecture.

Department of Mathematics, Ghent University, Belgium.

E-mail: [email protected].

The ${\Pi}_2^1$ -soundness ordinal of a theory $T$ , denoted ${o}_2^1(T)$ , is a measure of how close $T$ is to being ${\Pi}_2^1$ -correct. The ${\Pi}_2^1$ - spectrum conjecture asserts that the possible values of ${o}_2^1(T)$ for recursively enumerable extensions of ${\mathrm{ACA}}_0$ are precisely the ${\Sigma}_1^1$ -definable epsilon numbers. In this talk, we present a proof of the following theorem, which is formalizable in weak set theories: If the ${\Pi}_2^1$ - Spectrum Conjecture fails, then Second-Order Arithmetic is consistent. This is joint work with Fedor Pakhomov.

▸ DAVID FERNÁNDEZ-DUQUE, Noetherian Gödel Logics.

ICS of the Czech Academy of Sciences, Czech Republic, and Department of Mathematics WE16, Ghent University, Belgium.

E-mail: [email protected].

Noetherian Gödel logics are many-valued logics where the set of truth values is a closed subset of $\left[0,1\right]$ without infinite ascending sequences. These logics are parametrized by countable ordinals, so that ${G}_{\alpha}^{\downarrow }$ is the logic with truth values inversely isomorphic to $\alpha +1$ . In this talk we discuss the complexity of satisfiability and validity for each Noetherian Gödel logic, strengthening and generalizing results of Baaz-Leitsch-Zach and Hájek. Specifically, we show that the complexity of satisfiability and validity in ${G}_{\alpha}^{\downarrow }$ are related to ${\Sigma}_1^1$ and ${\Pi}_1^1$ formulas, respectively, over ${({\mathbb{L}}_{\beta})}_{\beta \le \alpha }$ .

This is joint work with Juan P. Aguilera and Jan Bydzovsky.

▸ GERHARD JÄGER, The admissible extension of subsystems of second order arithmetic.

Institute of Computer Science, University of Bern, Neubrückstrasse 10, 3012 Bern, Switzerland.

E-mail: [email protected].

Given a first order structure $\mathfrak{M}$ , the next admissible $\mathrm{\mathbb{H}}{\mathrm{YP}}_{\mathfrak{M}}$ and Barwise’s cover $\mathrm{\mathbb{C}}{\mathrm{ov}}_{\mathfrak{M}}$ – provided that $\mathfrak{M}$ is a model of Kripke-Platek set theory $\mathrm{KP}$ – are examples of structures that extend $\mathfrak{M}$ to a (in some sense) larger admissible set; see his textbook “Admissible Sets and Structures”. But observe that these processes do not affect the underlying $\mathfrak{M}$ .

Now let $T$ be a a subsystem of second order arithmetic. What happens when we combine $T$ with Kripke-Platek set theory $\mathrm{KP}$ ? Let us start off from a structure $\mathfrak{M}=\left(\mathrm{\mathbb{N}},\mathbb{S},\in \right)$ of the natural numbers $\mathrm{\mathbb{N}}$ and collection of sets of natural numbers $\mathbb{S}$ that has to obey the axioms of $T$ . Then we erect a set-theoretic world with transfinite levels on top of $\mathfrak{M}$ governed by the axioms of $\mathrm{KP}$ . However, owing to the interplay of $T$ and $\mathrm{KP}$ , either theory’s axioms may force new sets of natural to exists which in turn may engender yet new sets of naturals on account of the axioms of the other. Therefore, the admissible extension of $T$ is usually not a conservative extension of $T$ .

It turns out that for many familiar theories $T$ , the second order part of the admissible extension of $T$ equates to $T$ augmented by transfinite induction over all initial segments of the Bachmann-Howard ordinal.

This is joint work with Michael Rathjen.

▸ RICHARD MATTHEWS, On the constructive Constructible Universe.

School of Mathematics, University of Leeds, Leeds LS2 9JT, UK.

E-mail: [email protected].

Gödel’s Constructible Universe, L, was introduced to show the consistency of the Axiom of Choice and the Generalized Continuum Hypothesis with the axioms of ZF and is the smallest inner model of ZF. That is, it is the minimal submodel that satisfies ZF and contains all the ordinals of the background universe. In this talk we shall see how vastly different the situation can be in constructive set theories.

Firstly, we shall investigate L over CZF. Via a proof-theoretic ordinal analysis of Power Kripke Platek combined with realizability, we shall show that it is not possible to prove that Exponentiation holds in L. Therefore, over CZF, the Constructible Universe may fail to be an inner model of full CZF. Secondly, we shall explore the concept of an ordinal in the constructive setting. We shall see that, without the law of excluded middle, ordinals need not satisfy many of the standard, expected properties and instead can have very strange behaviour. In particular, over IZF, we shall see that it is possible for there to be an ordinal which is not in the constructible universe, answering a question of Lubarsky. This is joint work with Michael Rathjen.

▸ GUNNAR WILKEN, Isominimal realizations of patterns.

Okinawa Institute of Science and Technology Graduate University, Japan.

E-mail: [email protected].

Elementary patterns of resemblance are ordinal notations that can be approached from both a combinatorial and a semantic angle. The former derives from the observation that patterns are so-called respecting forests, while the latter is tied to the existence of unique isominimal realizations in the ordinals when interpreting the edges of patterns by elementary substructurehood. For patterns of order 1 the characterization of isominimal realizations is quite perspicuous, whereas patterns of order 2 already pose challenges, some of which I will address in my talk.

Abstracts of invited talks in the Special Session on Reverse Mathematics and Combinatorial Principles

▸ CHRIS CONIDIS, The computability of the Artin-Rees Lemma and Krull Intersection Theorem.

Department of Mathematics, College of Staten Island, 2800 Victory Boulevard Staten Island NY 10314, USA.

E-mail: [email protected].

We will examine the proofs of two related algebraic theorems, namely the Artin-Rees Lemma (AR) and the Krull Intersection Theorem (KIT). These related arguments appear in many Algebra textbooks in which AR is used to prove KIT. First, we will show that AR and KIT each follow from weak König’s Lemma ( ${\mathrm{WKL}}_0$ ). We will then go on to show that, in the context of infinite sequences of rings, the uniform Artin-Rees Lemma (UAR) still follows from ${\mathrm{WKL}}_0$ , but the uniform Krull Intersection Theorem (UKIT) does not.

[1] H. Matsumura, Commutative Ring Theory , Cambridge University Press, 2006.

▸ DENIS R. HIRSCHFELDT, The strength of versions of Mycielski’s Theorem.

Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, IL 60637, USA.

E-mail: [email protected].

Mycielski’s Theorem is a Ramsey-theoretic result on the reals with versions for measure and for category. These imply respectively that there is a perfect tree whose paths are all relatively $1$ -random, and that there is a perfect tree whose paths are all relatively $1$ -generic. In fact, in relativized form, the latter two statements are equivalent to the two versions of Mycielski’s Theorem. I will discuss joint work with Carl G. Jockusch, Jr. and Paul E. Schupp on the computability-theoretic and reverse-mathematical strength of these statements.

▸ KATARZYNA W. KOWALIK, A non speed-up result for the chain-antichain principle over a weak base theory.

Faculty of Mathematics Informatics and Mechanics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland.

E-mail: [email protected].

The chain-antichain principle (CAC), a well-known consequence of Ramsey’s Theorem for pairs and two colours, says that for every partial order on $\mathrm{\mathbb{N}}$ there exists an infinite chain or antichain with respect to this order. We study the strength of this principle over the weak base theory ${\mathrm{RCA}}_0^{\ast }$ , which is obtained from ${\mathrm{RCA}}_0$ by replacing the ${\Sigma}_1^0$ -induction scheme with ${\Delta}_1^0$ -induction.

It was shown by Patey and Yokoyama in [3] that ${\mathrm{RT}}_2^2$ is ${\Pi}_3^0$ -conservative over ${\mathrm{RCA}}_0$ and from [4] it follows that ${\mathrm{RT}}_2^2$ is also ${\Pi}_3^0$ -conservative over ${\mathrm{RCA}}_0^{\ast }$ (cf. [1]). The conservativity results lead to the question whether ${\mathrm{RT}}_2^2$ has significantly shorter proofs for ${\Pi}_3^0$ -sentences. The answer depends on the choice of the base theory: it was proved in [2] that ${\mathrm{RT}}_2^2$ can be polynomially simulated by ${\mathrm{RCA}}_0$ for ${\Pi}_3^0$ - sentences but it has non-elementary speed-up over ${\mathrm{RCA}}_0^{\ast }$ for ${\Sigma}_1^0$ -sentences.

The speed-up result was obtained by the use of the exponential lower bound for the finite version of ${\mathrm{RT}}_2^2$ . However, it follows from Dilworth’s theorem that the upper bound for the finite version of CAC is polynomial. This suggests that CAC, despite being a relatively strong consequence of ${\mathrm{RT}}_2^2$ , might not have an analogous speed-up over ${\mathrm{RCA}}_0^{\ast }$ . We confirm this conjecture by constructing a two-step forcing interpretation of ${\mathrm{RCA}}_0^{\ast }+$ CAC in ${\mathrm{RCA}}_0^{\ast }$ .

[1] Leszek A. Kołodziejczyk, Katarzyna W. Kowalik, and Keita Yokoyama, How strong is Ramsey’s theorem if infinity can be weak? Submitted, arXiv:2011.02550.

[2] Leszek A. Kołodziejczyk, Tin Lok Wong, and Keita Yokoyama, Ramsey’s theorem for pairs, collection, and proof size. Submitted, arXiv:2005.06854.

[3] Ludovic Patey and Keita Yokoyama, The proof-theoretic strength of Ramsey’s theorem for pairs and two colors, Advances in Mathematics , vol. 330 (2018), pp. 1034–1070.

[4] Keita Yokoyama, On the strength of Ramsey’s theorem without ${\Sigma}_1$ -induction, Mathematical Logic Quarterly , vol. 59 (2013), no. 1-2, pp. 108–111.

▸ GIOVANNI SOLDÀ, On the strength of some first-order problems corresponding to Ramseyan principles.

Department of Mathematics: Analysis, Logic and Discrete Mathematics, Ghent University, Krijgslaan 281 S8, 9000 Ghent, Belgium.

E-mail: [email protected].

Given a represented space $X$ , we say that a problem $f$ with $\operatorname{dom}(f)\subseteq X$ is first-order if its codomain is $\mathrm{\mathbb{N}}$ . In this talk, we will study, from the point of view of Weihrauch reducibility, some first-order problems corresponding to Ramseyan combinatorial principles.

We will start by analyzing some problems that can be seen naturally as first-order: more specifically, after mentioning some well-established results due to Brattka and Rakotoniaina [1], we will proceed to study some principles whose strengths, from a reverse mathematical perspective, lie around $\mathrm{I}{\Sigma}_2^0$ , as proved mainly in [2].

We will then move to study the first-order part ${}^1f$ of problems $f$ which cannot be presented as first-order ones: intuitively speaking, ${}^1f$ corresponds the strongest first-order problem Weihrauch reducible to $f$ . The first-order part operator was introduced by Dzhafarov, Solomon and Yokoyama in unpublished work, and it has already proved to be a valuable tool to gauge the strengths of various problems according to Weihrauch reducibility. After giving some technical results on this operator, we will focus on ${}^1\left({\mathrm{RT}}_2^2\right)$ , presenting various results on the position of its degree in the Weihrauch lattice.

The results presented are joint work with Arno Pauly, Pierre Pradic, and Manlio Valenti.

[1] Vasco Brattka and Tahina Rakotoniaina, On the uniform computational content of Ramsey’s theorem, The Journal of Symbolic Logic , vol. 82 (2015), no. 4, pp. 1278–1316.

[2] Leszek A. Kolodziejczyk, Henryk Michalewski, Pierre Pradic, and Michał Skrzypczak, The logical strength of Büchi’s decidability theorem, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) (Marseille, France), (Jean-Marc Talbot and Laurent Regnier), vol. 62, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016, pp. 36:1–36:16.

▸ WEI WANG, Ackermann function and reverse mathematics.

Department of Philosophy and Institute of Logic and Cognition, Sun Yat-sen University, Guangzhou 510275, P. R. China.

E-mail: [email protected], [email protected].

In 1928, Ackermann [1] defined one of the first examples of recursive but not primitive recursive functions. Later in 1935, Rózsa Péter [5] provided a simplification, which is now known as Ackermann or Ackermann-Péter function. The totality of Ackermann-Péter function is an interesting subject in the study of fragments of first order arithmetic. Kreuzer and Yokoyama [4] prove that the totality of Ackermann-Péter function is equivalent to a ${\Sigma}_3$ -proposition called $P{\Sigma}_1$ . And $P{\Sigma}_1$ has played important roles in reverse mathematics in recent years. We will see some examples in this talk, including some joint works [2, 3] of the speaker and logicians in Singapore.

[1] Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen , 99(1):118–133, 1928.

[2] Chitat Chong, Wei Li, Wei Wang, and Yue Yang, On the strength of Ramsey’s theorem for trees, Advances in Mathematics , vol. 369 (2020), no. 107180, 39 pp.

[3] Chitat Chong, Wei Wang, and Yue Yang, Conservation Strength of The Infinite Pigeonhole Principle for Trees, Israel Journal of Mathematics , to appear, arXiv:2110.06026.

[4] Alexander P. Kreuzer and Keita Yokoyama, On principles between ${\Sigma}_1$ - and ${\Sigma}_2$ -induction, and monotone enumerations, Journal of Mathematical Logic , vol. 16 (2016), no. 1:1650004, 21 pp.

[5] Péter, Rózsa, Konstruktion nichtrekursiver Funktionen, Mathematische Annalen , vol. 111 (1935), no. 1, pp. 42–60.

▸ LIAO YUKE, Recursive coloring without ${\Delta}_3^0$ witness for Hindman theorem.

Department of Mathematics, National University of Singapore, Singapore.

E-mail: liao\[email protected].

We give an example of a recursive coloring of integers which has no ${\Delta}_3^0$ witness for Hindman theorem and an example of a recursive coloring of integers such that any ${\Pi}_3^0$ set of integers whose any two elements are apart is not a witness for Hindman theorem.

[1] Andreas R. Blass, Jeffry L. Hirst, and Stephen G. Simpson, Logical analysis of some theorems of combinatorics and topological dynamics, Contemporary Mathematics , vol. 65 (1987), pp. 125–156.

Abstracts of invited talks in the Special Session on Set Theory

▸ BEN DE BONDT, Some remarks on Namba-type forcings.

Institut de Mathématiques de Jussieu (IMJ-PRG), Université Paris Cité, Bâtiment Sophie Germain, 8 Place Aurélie Nemours, 75013 Paris, France.

E-mail: [email protected].

For the purpose of this abstract, let “a Namba-type forcing” be any forcing that forces ${\omega}_2$ to get cofinality $\omega$ and doesn’t collapse ${\omega}_1.$ It is well known that the existence of a semiproper Namba-type forcing is equivalent to a Strong Chang’s Conjecture, but that instead the existence of a stationary set preserving Namba-type forcing is provable in plain $\mathrm{ZFC}.$ However, in the context of questions on iterated-forcing-using-side- conditions, it is natural to ask whether one can demand more than mere stationary set preservation and get provably in $\mathrm{ZFC}$ a Namba-type forcing that allows many (but not necessarily club many) models for which there exist sufficient semi-generic conditions. In this talk I will discuss a “side-condition version” $\mathrm{\mathbb{P}}$ of Namba forcing and explain that there exists a very natural projective stationary family of countable elementary submodels of ${H}_{\theta }$ such that $\mathrm{\mathbb{P}}$ is semiproper with respect to these models. In fact, we can consider a notion of strong semiproperness, in analogy to the notion of strong properness and verify that $\mathrm{\mathbb{P}}$ satisfies it, again with respect to these distinguished models.

As an application of this approach towards Namba forcing, we discuss a particularly natural presentation of an “ersatz iterated Namba forcing” which, given an increasing sequence $\left({\kappa}_{\alpha }:\alpha <\gamma \right)$ of regular cardinals $\ge {\omega}_2,$ adds for every $\alpha <\gamma$ a countable cofinal subset of ${\kappa}_{\alpha }$ , while at the same time preserving stationarity of stationary subsets of ${\omega}_1.$ In the proof, we will make strong use of a technique involving labelled trees and games played on such trees that appears in [1].

Finally, we will mention closely related ongoing work and remaining questions. This talk is based on joint work with my thesis supervisor Boban Veličković.

[1] Matthew Foreman and Menachem Magidor, Mutually stationary sequences of sets and the non-saturation of the non-stationary ideal on ${P}_{\kappa}\left(\lambda \right)$ , Acta Mathematica , vol. 186 (2001), no. 2, pp. 271–300.

[2] Saharon Shelah, Proper and Improper Forcing , Perspectives in Logic, vol. 5, Cambridge University Press, 1998.

▸ DIANA CAROLINA MONTOYA, Independence for uncountable cardinals.

Fakultät für Mathematik, Universität Wien, Vienna, Austria.

E-mail: [email protected].

In this talk, we will discuss the concept of maximal independent families for uncountable cardinals. First, we will mention a summary of results regarding the existence of such families in the case of an uncountable regular cardinal. Specifically, we will focus on joint work with Vera Fischer regarding the existence of an indestructible maximal independent family, which turns out to be indestructible after forcing with generalized Sacks forcing.

In the second part, we will focus on the singular case and present two results obtained in joint work with Omer Ben-Neria. Finally, I will mention some open questions and future paths of research.

▸ THOMAS GILTON, MAXWELL LEVINE, AND ŠÁRKA STEJSKALOVÁ, Club stationary reflection and consequences of square principles.

Department of Mathematics. The Dietrich School of Arts and Sciences, 301 Thackeray Hall, Pittsburgh, PA 15260, USA.

Albert-Ludwigs-Universität Freiburg, Freiburg, Germany

Charles University, Prague, Czech Republic.

E-mail: [email protected].

E-mail: [email protected].

E-mail: [email protected].

The square principle ${\square}_{\mu }$ , for a cardinal $\mu$ , exerts a tremendous influence on the combinatorics of ${\mu}^{+}$ implying, for example, that on ${\mu}^{+}$ stationary reflection and the tree property fail, but that the approachability property holds. In [3], the authors showed that these three consequences of ${\square}_{\mu }$ are mutually independent, in the sense that any of their eight Boolean combinations are consistent, from large cardinals, at ${\kappa}^{++}$ , where $\kappa$ is either singular or regular.

Recently Levine, Stejskalová, and I ([1]) have continued this line of research, showing how to obtain Club Stationary Reflection together with a variety of other combinatorics at a double successor of a regular. Moreover, Stejskalová and I have recently shown ([2]) how to fold Prikry-type forcings into these arguments to obtain similar results at the double successor of a cofinality $\omega$ singular.

In this talk, we will briefly review the impact that ${\square}_{\mu }$ has on the combinatorics at ${\mu}^{+}$ , and then sketch the main ideas for a number of our theorems, both in the regular and singular cases. In particular, we will discuss how we use weakly compact Laver diamonds to build our focings, and we will discuss new preservation theorems for club stationary reflection. If time permits, we will also discuss current work which involves Magidor forcing and uncountable cofinality singulars.

[1] Thomas Gilton, Maxwell Levine, and Šárka Stejskalová, Trees and Stationary Reflection at Double Successors of Regular Cardinals, The Journal of Symbolic Logic , to appear.

[2] Thomas Gilton and Šárka Stejskalová, Compactness Principles at ${\aleph}_{\omega +2}$ , In preparation.

[3] James Cummings, Sy-David Friedman, Menachem Magidor, Assaf Rinot, and Dima Sinapova, The Eightfold Way, The Journal of Symbolic Logic , vol. 83 (2018) no. 1, pp. 349–371.

▸ SANDRA MÜLLER, A stationary-tower-free proof of $\textsf{Sealing}$ from a supercompact.

Institute of Discrete Mathematics and Geometry, TU Wien, Wiedner Hauptstrasse 8-10/104, 1040 Vienna, Austria.

E-mail: [email protected].

URL Address: https://dmg.tuwien.ac.at/sandramueller/.

$\textsf{Sealing}$ is a generic absoluteness principle for the theory of the universally Baire sets of reals introduced by Woodin. It is deeply connected to the Inner Model Program and plays a prominent role in recent advances in inner model theory. Woodin showed in his famous Sealing Theorem that in the presence of a proper class of Woodin cardinals $\textsf{Sealing}$ holds after collapsing a supercompact cardinal. I will outline the importance of $\textsf{Sealing}$ and discuss a new and stationary-tower-free proof of Woodin’s Sealing Theorem that is based on Sargsyan’s and Trang’s proof of $\textsf{Sealing}$ from iterability. This is joint work with Grigor Sargsyan and Bartosz Wcisło.

▸ DAMIAN SOBOTA, P-measures in random extensions.

Kurt Gödel Research Center, Department of Mathematics, Vienna University, Vienna, Austria.

E-mail: [email protected].

Let $\mu$ be a finitely additive probability measure on $\omega$ which vanishes on points, that is, $\mu \left(\left\{n\right\}\right)=0$ for every $n\in \omega$ . It follows immediately that $\mu$ is not $\sigma$ -additive, however it may be almost $\sigma$ -additive in the following weak sense. We say that $\mu$ is a P- measure if for every decreasing sequence $\left({A}_n\right)$ of subsets of $\omega$ there is a subset $A$ such that $A\backslash {A}_n$ is finite for every $n$ and $\mu (A)={\lim}_n\mu \left({A}_n\right)$ . P-measures can be thought of as generalizations of P-points and similarly as in the case of P-points the existence of P-measures is independent of ZFC.

During my talk I will discuss basic properties of P-measures and show, at least briefly, that using old ideas of Solovay and Kunen one can obtain a non-atomic P-measure in the random model. The latter result implies that in this model ${\omega}^{\ast }$ contains a closed nowhere dense ccc P-set, which may be treated as a (weak) partial answer to the open question asking whether there are P-points in the random model.

This is a joint work with Piotr Borodulin-Nadzieja.

▸ JING ZHANG, Making the diamond principle fail at an inaccessible cardinal.

Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel.

E-mail: [email protected].

It is a well-known theorem by Shelah that for any infinite cardinal $\lambda >{\aleph}_0$ , ${2}^{\lambda}={\lambda}^{+}$ is equivalent to $\diamondsuit({\lambda}^{+})$ . However, the situation at inaccessible cardinals is different. Woodin produced a model where the diamond principle fails at a (greatly) Mahlo cardinal, based on the analysis of the Radin forcing. We will discuss the advantage and the limitation of such method. Furthermore, we demonstrate a new method giving rise to the failure of the diamond principle at an inaccessible cardinal, fundamentally different from Woodin’s method. The differences from the previous method will be highlighted. Joint work with Omer Ben-Neria.

Abstract of Contributed Talks

▸ LUCA ACETO, ANTONIS ACHILLEOS, DUNCAN PAUL ATTARD, LÉO EXIBARD, ADRIAN FRANCALANZA, KAROLIINA LEHTINEN, Runtime monitoring for Hennessy-Milner logic with recursion over systems with data.

ICE-TCS, Reykjavík University, Menntavegur 1, Iceland.

E-mail: [email protected].

Runtime verification consists in checking whether a program satisfies a given specification by observing the trace it produces during its execution. In the regular setting, Hennessy-Milner logic with recursion (recHML), a variant of the modal $\mu$ -calculus, provides a versatile back-end for expressing linear- and branching-time specifications. In this paper, we study an extension of this logic [2] that allows to express properties over data values (i.e. values from an infinite domain) and examine which fragments can be verified at runtime. Data values are manipulated through first-order formulas over the underlying theory in modalities and through first-order quantification outside of them. They can also be stored using parameterised recursion variables.

Assuming decidability of the underlying first-order theory, we study how to generalise the classification known in the regular case. We further observe that restricting quantifier-free formulas in the modalities yields a logic that corresponds to register automata with non-deterministic reassignment, allowing us to ground our monitor synthesis algorithms, in the spirit of, and to derive impossibility results. In particular, contrary to the regular case, restricting to deterministic monitors strictly reduces the set of monitorable properties. We also note that further limiting quantifications to immediate bindings, we get recHML^d [1], a logic previously introduced for monitoring events that carry data.

[1] Luca Aceto, Ian Cassar, Adrian Francalanza and Anna Ingólfsdóttir, On Runtime Enforcement via Suppressions, Proceedings of the 29th International Conference on Concurrency Theory, CONCUR 2018 , (Beijing, China), (Sven Schewe and Lijun Zhang, editors), vol. 118 (34), LIPIcs, pp. 1–17.

[2] Jan Friso Groote and Radu Mateescu, Verification of Temporal Properties of Processes in a Setting with Data, Proceedings of Algebraic Methodology and Software Technology, 7th International Conference, AMAST ’98 , (Amazonia, Brazil), (Armando Martin Haeberer, editor), vol. 1548, Lecture Notes in Computer Science, 1998, pp. 74–90.

▸ ANTONIS ACHILLEOS, ELENI BAKALI, AGGELIKI CHALKI, ARIS PAGOURTZIS, Descriptive complexity for hard counting problems with an easy decision version.

Department of Computer Science, Reykjavik University, Menntavegur 1, IS-102, Reykjavík, Iceland.

School of Electrical and Computer Engineering, National Technical University of Athens, Iroon Polytechniou 9, 15780, Athens, Greece.

E-mail: [email protected].

The class # $\textsf{P}$ is the class of functions that count the number of solutions to problems in $\textsf{NP}$ . Since very few counting problems can be exactly computed in polynomial time (e.g. counting spanning trees), the interest of the community has turned to the complexity of approximating them. To this end, the class # $\textsf{PE}$ of problems in # $\textsf{P}$ the decision version of which is in $\textsf{P}$ is of great significance.

We focus on a subclass of # $\textsf{PE}$ , namely $\textsf{TotP}$ , the class of functions that count the total number of paths of NPTMs. $\textsf{TotP}$ contains all self-reducible # $\textsf{PE}$ functions and it is robust, in the sense that it has natural complete problems and it is closed under addition, multiplication and subtraction by one.

We present logical characterizations of $\textsf{TotP}$ and two other robust subclasses of this class, building upon two seminal works on descriptive complexity for classes of counting problems [2, 1]. In specific, to capture $\textsf{TotP}$ , we use recursion on functions over second-order variables which, we believe, is of independent interest.

This work has been partially funded by the Basic Research Program PEVE 2020 of the National Technical University of Athens, and the project “MoVeMnt: Mode(l)s of Verification and Monitorability” (grant no 217987) of the Icelandic Research Fund.

[1] M. Arenas, M. Muñoz, and C. Riveros, Descriptive Complexity for Counting Complexity Classes, Logical Methods in Computer Science , vol. 16 (2020), no. 1.

[2] S. Saluja, K. V. Subrahmanyam, and M. N. Thakur, Descriptive Complexity of #P Functions, Journal of Computer and System Sciences , vol. 50 (1995), no. 3, pp. 493–505.

▸ GUILLERMO BADIA, XAVIER CAICEDO, AND CARLES NOGUERA, Frame definability in finitely-valued modal logic.

School of Historical and Philosophical Inquiry, University of Queensland, Brisbane, Australia.

E-mail: [email protected].

URL Address: https://sites.google.com/site/guillermobadialogic/home.

Departamento de Matemáticas, Universidad de los Andes, Bogotá, Colombia.

E-mail: [email protected].

URL Address: https://math.uniandes.edu.co/webxcaicedo/.

Department of Information Engineering and Mathematics, University of Siena, Siena, Italy.

E-mail: [email protected].

URL Address: https://sites.google.com/view/carlesnoguera/bio-cv.

In this paper we study frame definability in finitely-valued modal logics and establish two main results via suitable translations: (1) in finitely-valued modal logics one cannot define more classes of frames than are already definable in classical modal logic (cf. [4, Thm. 8]), and (2) a large family of finitely- valued modal logics define exactly the same classes of frames as classical modal logic (including modal logics based on finite Heyting and MV-algebras). In this way one may observe, for example, that the celebrated Goldblatt–Thomason theorem applies immediately to these logics. In particular, we obtain the central result from [3] with a much simpler proof and answer one of the open questions left in that paper. Moreover, the proposed translations allow us to determine the computational complexity of a big class of finitely-valued modal logics. Finally, we show that the first translation we offer (from finitely-valued modal logic into two-valued modal logic) yields a 0-1 law over models for the former (cf. [1]) as a corollary of W. Oberschelp’s generalization [2] of Fagin’s 0-1 law. In particular, one can show that, over Kripke models for finitely-valued modal logics based on finite frames, for every modal formula there is a truth-value that it takes almost surely at all worlds.

[1] J. Y. Halpern and B. M. Kapron, Zero-one laws for modal logic, Annals of Pure and Applied Logic , vol. 69 (1994), pp. 157–193.

[2] Walter Oberschelp, Asymptotic 0-1 laws in combinatorics, Combinatorial theory, Lecture Notes in Mathematics , (D. Jungnickel, editor), Springer, 1982, vol. 969, pp. 276–292.

[3] B. Teheux, Modal definability for Łukasiewicz validity relations, Studia Logica , vol. 104 (2016), no. 2, pp. 343–363.

[4] S. K. Thomason, Possible worlds and many truth values, Studia Logica vol. 37 (1978), pp. 195–204.

▸ KATALIN BIMBÓ, Relational semantics for some classical relevance logics.

Department of Philosophy, University of Alberta, 2–40 Assiniboia Hall, Edmonton, AB T6G2E7, Canada.

URL Address: www.ualberta.ca/~bimbo.

The framework called generalized Galois logics (or gaggle theory, for short) was introduced in [2] to encompass Kripke’s semantics for modal and intuitionistic logics, Jónsson & Tarski’s representation of BAO’s and the Meyer–Routley semantics for relevance logics among others. In some cases, gaggle theory gives exactly the semantics defined earlier for a logic; in other cases, the semantics differ (cf. [3], [1]). Relational semantics for classical relevance logics such as $\mathbf{CR}$ and $\mathbf{CB}$ are usually defined as a modification of the Meyer–Routley semantics for ${\mathbf{R}}_{+}$ and ${\mathbf{B}}_{+}$ , respectively (cf. [4]). In this talk, I compare the existing semantics for $\mathbf{CB}$ and $\mathbf{CR}$ to the semantics that results as an application of gaggle theory.

[1] Bimbó, Katalin and J. Michael Dunn, Generalized Galois Logics: Relational Semantics of Nonclassical Logical Calculi , (CSLI Lecture Notes vol. 188), CSLI Publications, Stanford, CA, 2008.

[2] Dunn, J. Michael, Gaggle theory: An abstraction of Galois connections and residuation, with applications to negation, implication, and various logical operators, Logics in AI: European Workshop JELIA ‘90 , (J. van Eijck, editor), Lecture Notes in Computer Science vol. 478, Springer, Berlin, 1991, pp. 31–51.

[3] \bysame, Gaggle theory applied to intuitionistic, modal and relevance logics, Logik und Mathematik. Frege-Kolloquium Jena 1993 , (I. Max and W. Stelzner, editors), W. de Gruyter, Berlin, 1995, pp. 335–368.

[4] Meyer, Robert K., Ternary relations and relevant semantics, Annals of Pure and Applied Logic , vol. 127 (2004), pp. 195–217.

▸ JASON BLOCK, Categoricity ordinals and models of Presburger arithmetic.

Department of Mathematics, City University of New York, 365 5th Avenue, New York, NY 10016, USA.

E-mail: [email protected].

The categoricity ordinal of a structure $\mathrm{\mathcal{M}}$ is a measure of how hard it is to compute isomorphisms between copies of $\mathrm{\mathcal{M}}$ . Presburger arithmetic is the theory of $\left(\mathrm{\mathbb{Z}},+,<\right)$ . We will precisely define categoricity ordinals, explore computability-theoretic properties of Presburger arithmetic, and examine which ordinals can be the categoricity ordinal for a model of Presburger arithmetic.

▸ VITTORIO CIPRIANI, Equivalence relations and learning of algebraic structures.

Dipartimento di informatica, scienze matematiche e fisiche, Università degli studi di Udine, Via delle Scienze 206, Udine (UD), Italy.

E-mail: [email protected].

In this talk we present some results related to algorithmic learning of algebraic structures. In a series of papers [4, 2, 3] the authors developed a framework in which a learner receives larger and larger pieces of an arbitrary copy of a computable structure and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if the conjectures eventually stabilize to a correct guess. Borrowing ideas from descriptive set theory, we aim to calibrate the complexity of nonlearnable families, offering a new hierarchy based on reducibility between equivalence relations. To do so, we define the notion of $E$ -learnability.

Definition 1. A family of structures $\mathfrak{K}$ is $E$ -learnable if there is function $\Gamma :{2}^{\omega}\to {2}^{\omega }$ which continuously reduce $\mathrm{LD}{\left(\mathfrak{K}\right)}_{/\cong }$ to $E$ , where $\mathrm{LD}\left(\mathfrak{K}\right)$ is the collection of all copies of the structures from $\mathfrak{K}$ .

For example, we show that the paradigm introduced at the beginning coincides with ${E}_0$ -learnability, where ${E}_0$ is the eventual agreement on reals. We then focus on the learning power of well-known benchmark Borel equivalence relations differentiating between learnability of finite and countably infinite families.

This is a joint work with Nikolay Bazhenov and Luca San Mauro, and some of the results discussed here can be found in [1].

[1] Nikolay Bazhenov, Vittorio Ciprani, and Luca San Mauro, Learning algebraic structures with the help of Borel equivalence relations, Preprint, arxiv.2110.14512.

[2] Nikolay Bazhenov, Ekaterina Fokina, and Luca San Mauro, Learning families of algebraic structures from informant, Information and Computation , vol. 275 (2020), no. 104590.

[3] Nikolay Bazhenov and Luca San Mauro, On the Turing complexity of learning finite families of algebraic structures, Journal of Logic and Computation , Preprint, 2021, arXiv:2106.14515.

[4] Ekaterina Fokina, Timo Kötzing, and Luca San Mauro, Limit learning equivalence structures, Proceedings of the 30th International Conference on Algorithmic Learning Theory , (Aurélien Garivier and Satyen Kale, editors), Proceedings of Machine Learning Research, vol. 98 (2019), pp. 383–403.

▸ TONICHA CROOK, JAY MORGAN, MARKUS ROGGENBACH AND ARNO PAULY, A computability perspective on verified machine learning.

Computational Foundry, Swansea University, Swansea, UK.

E-mail: [email protected].

We approach the idea of verified machine learning from the perspective of computable analysis. By using the language of computable analysis, particularly that of represented spaces, we can formalize various verification questions of relevance for the machine learning community. These formulations involve function spaces, as well as the spaces of open subsets, overt subsets and compact subsets. We can then show that as long as the appropriate notions of subsets are chosen, and as long as we use ternary logic including an undetermined truth value, these verification questions do become computable.

[1] Tonicha Crook, Jay Morgan, Markus Roggenbach, and Arno Pauly, Computability Perspective on (Verified) Machine Learning, arXiv 2102.06585.

▸ ANUPAM DAS AND AVGERINOS DELKOS, Proof complexity of monotone branching programs.

School of Computer Science, University of Birmingham, B15 2TT, UK.

E-mail: [email protected].

E-mail: [email protected].

We investigate the proof complexity of systems based on positive branching programs, i.e. non-deterministic branching programs (NBPs) where, for any 0- transition between two nodes, there is also a 1-transition. Positive NBPs compute monotone Boolean functions, like negation-free circuits or formulas, but constitute a positive version of (non-uniform) NL, rather than P or ${\mathbf{NC}}^1$ , respectively.

The proof complexity of NBPs was investigated in previous work by Buss, Das and Knop, using extension variables to represent the dag-structure, over a language of (non-deterministic) decision trees, yielding the system $\mathrm{eLNDT}$ . Our system ${\mathrm{eLNDT}}^{+}$ is obtained by restricting their systems to a positive syntax, similarly to how the ‘monotone sequent calculus’ $\mathrm{MLK}$ is obtained from the usual sequent calculus $\mathrm{LK}$ by restricting to negation-free formulas.

Our main result is that ${\mathrm{eLNDT}}^{+}$ polynomially simulates $\mathrm{eLNDT}$ over positive sequents. Our proof method is inspired by a similar result for $\mathrm{MLK}$ by Atserias, Galesi and Pudlák, that was recently improved to a bona fide polynomial simulation via works of Jeřábek and Buss, Kabanets, Kolokolova and Koucký. Along the way we formalise several properties of counting functions within ${\mathrm{eLNDT}}^{+}$ by polynomial-size proofs and, as a case study, give explicit polynomial-size poofs of the propositional pigeonhole principle.

▸ PABLO DOPICO, Truth-theoretic determinacy revisited.

Department of Philosophy, King’s College London, Strand, London, UK.

E-mail: [email protected].

Despite being highly successful, Saul Kripke’s theory of truth (1975), based on the so-called fixed-point semantics, has been criticised on the basis of its incapacity to formulate the semantic status of paradoxical sentences such as the Liar. In other words, Kripke’s theory treats that and similar sentences as being neither true nor false, but the object language lacks the resources to speak about the gappy character of the Liar. From Burge (1979) to Field (2008), the tradition has suggested that this gappy character can be best understood as the idea that the Liar is not determinate or not determinately true. As a result, the main aim of this paper is to explore what being determinate in relation to a truth predicate could mean. We hence propose three different understandings of such notion in the form of three determinacy predicates and offer philosophical motivations for each of them. After that, we test different theories of truth against the background of those three understanding of truth-theoretic determinacy. In particular, we assess Kripke’s theory of truth, as well as Solomon Feferman’s well-known axiomatization of it (the so-called KF) (Halbach 2014), and Vann McGee’s theory of definite truth (1991). Our results suggest that there could be a trade-off between the semantic expressibility of a theory of truth, understood as its ability to capture the semantic status of the Liar, and the logical strength of the theory.

[1] Tyler Burge, Semantical paradox, The Journal of Philosophy , vol. 76 (1979), no. 4, pp. 169–198.

[2] Hartry Field, Saving truth from paradox , Oxford University Press, 2008.

[3] Volker Halbach, Axiomatic theories of truth , Cambridge University Press, 2014.

[4] Saul Kripke, Outline of a theory of truth, The Journal of Philosophy , vol. 72 (1975), no. 19, pp. 690–716.

[5] Vann McGee, Truth, vagueness, and paradox: An essay on the logic of truth , Hackett Publishing, 1991.

▸ FREDRIK ENGSTRÖM, Foundations of team semantics.

Department of Philosophy, Linguistics and Theory of Science, University of Gothenburg, Sweden.

E-mail: [email protected].

Dependence logic, see [3], and its relatives are defined using team semantics, in which formulas are satisfied by sets of assignments, teams, rather than single assignments. The team semantics construction is widely applicable and can be used to understand notions from many different areas; model theory, game theory, database theory, probabilistic reasoning and program verification, to name a few.

The denotatiton of a first-order formula in classical Tarskian semantics is the set of assignments satisfying the formula, . In team semantics it is the set of teams satisfying the formula, i.e., a set of sets of assignments, . The standard team semantic construction is via the flatness principle according to which .

This construction can, at least partially, be described using the free functor from the category of partially ordered monoids to the category of quantales, i.e., partially ordered monoids equipped with a complete semilattice structure, see [1]. This functor maps the space of Tarskian denotations, $\mathcal{P}({X}^V)$ , where $X$ is the domain and $V$ a set of variables, into the space $\mathrm{\mathscr{H}}(\mathcal{P}({X}^V))$ , the set of downwards-closed subsets of $\mathcal{P}({X}^V)$ . The embedding is based on the flatness principle in that .

However, the space of downwards-closed sets can not be used as the space of denotations for some logics: One example is the well-studied Independence logic, which isn’t downward-closed; another is a logic constructed to handle branching of non-monotone generalized quantifiers, which isn’t based on the flatness principle. I will in this talk revisit the description of the team semantic construction as the free functor from a more general perspective that also includes these logics.

[1] Samson Abramsky and Jouko Väänänen, From IF to BI, Synthese , vol. 167 (2009), pp. 207–230.

[2] Fredrik Engström, Generalized quantifiers in Dependence logic, Journal of Logic, Language and Information , vol. 21 (2012), pp. 299–324.

[3] Jouko Väänänen, Dependence logic. A new approach to independence friendly logic , London Mathematical Society Student Texts, Cambridge University Press, 2007.

▸ DAVID FERNÁNDEZ-DUQUE, ORIOLA GJETAJ, ANDREAS WEIERMANN, Intermediate Goodstein principles.

Institute for Analysis, Logic and Discrete Mathematics, Ghent University, Krijgslaan 281 S8, 9000 Ghent, Belgium.

E-mail: [email protected].

E-mail: [email protected].

E-mail: [email protected].

The Goodstein principle is a natural number-theoretic theorem which is unprovable in Peano arithmetic.The original process proceeds by writing natural numbers in nested exponential k-base normal form, then successively raising the base to k + 1 and subtracting one from the end result. Such sequences always reach zero, but this fact is unprovable in Peano arithmetic.

In this talk, we will consider canonical representations of natural numbers using Ackermann function and the function of Grzegorczyk hierarchy. These representations give a natural Goodstein process for which we obtain independence from different theories of reverse mathematics.

This is a joint ongoing work with A. Weiermann and D. Fernández-Duque on exploring normal form notations for the Goodstein principle.

[1] D.Fernández-Duque, O.Gjetaj, and A. Weiermann, Intermediate Goodstein principles, Mathematics for Computation(M4C) , 2023, Accepted.

[2] D. Fernández-Duque and A. Weiermann, Ackermannian Goodstein Sequences of Intermediate Growth, Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020 (Marcella Anselmo, Gianluca Della Vedova, Florin Manea, and Arno Pauly, editors), Springer, (2020), pp. 163–174.

[3] T. Arai, D. Fernández-Duque, S. Wainer, and A. Weiermann, Predicatively Unprovable Termination of the Ackermannian Goodstein Principle, Proceedings of the American Mathematical Society , vol. 148 (2019), pp. 3567–3582.

[4] R.L. Goodstein, On the restricted ordinal theorem, Journal of Symbolic Logic , vol 9. (1944), pp. 33–41.

[5] L. Kirby and J. Paris., On the restricted ordinal theorem, Bulletin of The London Mathematical Society , vol 14. (1982), no. 4, pp. 285–293.

[6] A.Weiermann, Ackermannian Goodstein principles for first order Peano arithmetic, Sets and Computations , Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 33, WorldScientific Publications, Hackensack, NJ (2018), pp. 157–181.

▸ DAVID FERNÁNDEZ-DUQUE, JOOST J. JOOSTEN, AND KONSTANTINOS PAPAFILIPPOU, Hyperarithmetical worm battles.

Department of Mathematics WE16, Ghent University, Ghent, Belgium.

E-mail: [email protected].

E-mail: [email protected].

Department of Philosophy, University of Barcelona, Spain.

E-mail: [email protected].

Japaridze’s provability logic $\mathrm{GLP}$ has one modality $\left[n\right]$ for each natural number and has been used by Beklemishev for a proof theoretic analysis of Peano aritmetic ( $\mathrm{PA}$ ) and related theories. In his analysis, he interprets $\mathrm{GLP}$ in arithmetic by interpreting each modality $\left\langle n\right\rangle$ as ${\Sigma}_n$ - $\mathrm{RFN}(T):= \left\{{\square}_T\phi \to \phi :\phi\;\mathrm{is}\;\mathrm{a}\;{\Sigma}_n\mathrm{formula}\right\}$ , for some given theory $T$ and with ${\square}_T\phi$ standing for the formula: “ $\phi$ is provable in $T$ “. He examines what he calls worms, which is the set $W$ of formulas in $\mathrm{GLP}$ defined as:

• • $T\in W$ ;

• • if $A\in W$ and $n$ is a natural number, then $\left\langle n\right\rangle A\in W$ .

Among other benefits, this analysis yields [1] the so-called Every Worm Dies ( $\mathrm{EWD}$ ) principle, a natural combinatorial statement that is similar in spirit to the hercules hydra battle and a bit more closely connected to the assertion of the totality of Hardy functions ${H}_{\alpha }$ on ordinals $\alpha <{15}_0$ . He had then proven that $\mathrm{EWD}$ is equivalent over $\mathrm{EA}:= I{\Delta}_0+\mathit{\exp}$ to the ${\Sigma}_1$ - $\mathrm{RFN}\left(\mathrm{PA}\right)$ and hence it is also independent of $\mathrm{PA}$ . Recently, Beklemishev and Pakhomov [2] have studied notions of provability corresponding to transfinite modalities in $\mathrm{GLP}$ and they have looked into their connection to some theories of second order arithmetic. We show [3] that indeed the natural transfinite extension of $\mathrm{GLP}$ is sound for this interpretation, and yields similarly an equivalence to the ${\Sigma}_1$ -reflection of the second order theory $\mathrm{ACA}$ of arithmetical comprehension with full induction. We also provide restricted versions of $\mathrm{EWD}$ related to the fragments $I{\Sigma}_n$ of Peano arithmetic.

[1] Lev D. Beklemishev, Reflection principles and provability algebras in formal arithmetic, Russian Mathematical Surveys , vol. 60 (2005), no. 2, pp. 197–268.

[2] Lev D. Beklemishev and Fedor N. Pakhomov, Reflection algebras and conservation results for theories of iterated truth, Annals of Pure and Applied Logic , vol. 173 (2022), no. 5.

[3] David Fernández-Duque, Joost J. Joosten, and Konstantinos Papafilippou, Hyperarithmetical Worm Battles, Logical Foundations of Computer Science , (Artemov Sergei and Nerode Anil, editors), Springer International Publishing, 2022, pp. 52–69.

▸ FRANCESCO GALLINARO, Exponential sums equations and tropical geometry.

School of Mathematics, University of East Anglia, NR4 7TJ, UK.

E-mail: [email protected].

In the late 1990s, Boris Zilber made a conjecture on the model theory of the exponential function, the Quasiminimality Conjecture (see [2], [3]). This predicts that all subsets of the complex numbers that are definable using the language of rings and the exponential function are either countable or cocountable. He then proved that the conjecture would follow if the complex exponential field were a model of a certain theory in an infinitary logic. Building on Zilber’s work, Bays and Kirby have proved in [1] that the Quasiminimality Conjecture would follow from just one of Zilber’s axioms, the Exponential-Algebraic Closedness Conjecture, which predicts sufficient conditions for systems of equations in polynomials and exponentials to have complex solutions. In this talk, I will give an introduction to this topic before presenting some recent work which solves the conjecture for a class of algebraic varieties which corresponds to systems of exponential sums. This turns out to be closely related to tropical geometry, a “combinatorial shadow” of algebraic geometry which reduces some questions about algebraic varieties to questions about polyhedral objects.

[1] Martin Bays and Jonathan Kirby, Pseudo-exponential maps, variants, and quasiminimality, Algebra & Number Theory , vol. 12 (2018), no. 3, pp. 493–549.

[2] Boris Zilber, Analytic and pseudo-analytic structure, Logic Colloquium 2000, Paris , (Rene Cori, Alexander Razborov, Stevo Todorčević, and Carol Wood, editors), Lecture Notes in Logic, vol. 19, Cambridge University Press, 2005, pp. 392–408.

[3] \bysame, Pseudo-exponentiation on algebraically closed fields, Annals of Pure and Applied Logic , vol. 132 (2005), no. 1, pp. 67–95.

▸ MATTIAS GRANBERG OLSSON AND GRAHAM E. LEIGH, Almost negative truth and fixpoints in intuitionistic logic.

Department of Philosophy, Linguistics and Theory of Science, University of Gothenburg, PO Box 200 SE405 30 Göteborg, Sweden.

E-mail: [email protected].

E-mail: [email protected].

We present work in progress on the relationship between the theory of transfinitely iterated strictly positive fixpoints and axiomatic theories of compositional and disquotational truth for almost negative formulae in intuitionistic logic. The starting point is the result of Cantini [1] and Feferman [2] (extended to the transfinite by Fujimoto [3]) that the (classical) theory of positive fixpoints ${\widehat{\mathrm{ID}}}_1$ , the Kripke-Feferman compositional theory of partial truth $\mathrm{KF}$ , and the uniformly disquotational theory for truth-positive formulae $\mathrm{PUTB}$ are mutually interpretable. We obtain similar results for the theories of transfinite iterations of strictly positive fixpoints (as in [106]) for almost negative operators, and disquotation for almost negative strictly truth-positive formulae, in intuitionistic logic (which we call ${\widehat{\mathrm{ID}}}_{\alpha}^{\mathrm{i}}\left(\Lambda \right)$ and $\mathrm{P}\Lambda {\mathrm{UTB}}_{\alpha}^{\mathrm{i}}$ respectively):

• • First, ${\widehat{\mathrm{ID}}}_{\alpha}^{\mathrm{i}}\left(\Lambda \right)$ is interpretable in $\mathrm{P}\Lambda {\mathrm{UTB}}_{\alpha}^{\mathrm{i}}$ by mimicking the classical proof.

• • Second, $\mathrm{P}\Lambda {\mathrm{UTB}}_{\alpha}^{\mathrm{i}}$ is interpretable (via a compositional theory) in ${\widehat{\mathrm{ID}}}_{\omega \cdot \alpha}^{\mathrm{i}}\left(\Lambda \right)$ for limit $\alpha$ . This is achieved by using the extra ‘spacing’ between the levels, given by the multiplication by $\omega$ , to keep track of the nestings of implications in formulae.

[1] Andrea Cantini, Notes on formal theories of truth, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , vol. 35 (1989), no. 2, pp. 97–130.

[2] Solomon Feferman, Reflecting on incompleteness, The Journal of Symbolic Logic , vol. 56 (1991), no. 1, pp. 1–49.

[3] Kentaro Fujimoto, Autonomous progression and transfinite iteration of self-applicable truth, The Journal of Symbolic Logic , vol. 76 (2011), no. 3, pp. 914–945.

[4] Christian Rüede and Thomas Strahm, Intuitionistic fixed point theories for strictly positive operators, Mathematical Logic Quarterly , vol. 48 (2002), no. 2, pp. 195–202.

▸ LAURI HELLA, KERKKO LUOSTO, AND JOUKO VÄÄNÄNEN, Dimension in team semantics.

Faculty of Information Technology and Communication Sciences, Tampere University, Finland.

E-mail: [email protected].

E-mail: [email protected].

Department of Mathematics and Statistics, University of Helsinki, Finland.

E-mail: [email protected].

We introduce three measures of complexity for families of sets. Each of the three measures, that we call dimensions, is defined in terms of the minimal number of convex subfamilies that are needed for covering the given family: for upper dimension, the subfamilies are required to contain a unique maximal set, for dual upper dimension a unique minimal set, and for cylindrical dimension both a unique maximal and a unique minimal set. In addition to considering dimensions of particular families of sets we study the behaviour of dimensions under operators that map families of sets to new families of sets. We identify natural sufficient criteria for such operators to preserve the growth class of the dimensions.

We apply the theory of our dimensions for proving new hierarchy results for logics with team semantics. First, we show that the standard logical operators preserve the growth classes of the families arising from the semantics of formulas in such logics. Second, we show that the upper dimension of $k+1$ -ary dependence, inclusion, independence, anonymity, and exclusion atoms is in a strictly higher growth class than that of any $k$ -ary atoms, whence the $k+1$ -ary atoms are not definable in terms of any atoms of smaller arity.

Related and earlier work:

[1] Ivano Ciardelli, Inquisitive semantics and intermediate logics, Master’s thesis, University of Amsterdam, 2009.

[2] Lauri Hella, Kerkko Luosto, Katsuhiko Sano, and Jonni Virtema, The expressive power of modal dependence logic, Advances in modal logic (Rajeev Goré, Barteld Kooi, and Agi Kurucz, editors), College Publications, 2014, pp. 294–312.

[3] Lauri Hella and Johanna Stumpf, The expressive power of modal logic with inclusion atoms, Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification , vol. 193, Electronic Proceedings in Theoretical Computer Science (EPTCS), 2015, pp. 129–143.

[4] Martin Lück and Miikka Vilander, On the succinctness of atoms of dependency, Logical Methods in Computer Science , vol. 15 (2019), no. 3.

▸ MAIRA KASSYMETOVA, NAZGUL SHAMATAYEVA, OLGA ULBRIKHT AND AIBAT YESHKEYEV, Properties of lattices of existential formulas of Jonsson beautiful pairs.

Faculty of Mathematics and Information Technologies, Karaganda Buketov University, University str., 28, Building 2, Kazakhstan.

E-mail: [email protected].

E-mail: [email protected].

E-mail: [email protected].

E-mail: [email protected].

Let $T$ be a convex $\exists$ -complete perfect Jonsson theory of a countable language $L$ , $C$ is its semantic model, ${T}^{\ast}= Th(C)$ is the center of theory $T$ , $M=\cap {M}_i$ , where ${M}_i\in {E}_T$ , ${M}_i\subseteq C$ and ${E}_T$ is the class of existentially closed models of the theory $T$ .

Definition 1. Let $N,M\in {E}_T$ and $M{\preccurlyeq}_{\exists_1}N$ . We will call a pair $\left(N,M\right)$ a $J$ -beautiful pair if it satisfies the following conditions:

1) $M$ is ${\left|T\right|}^{+}$ - ${\exists}_1$ -saturated;

2) for each tuple $\overline{b}$ extracted from $N$ , each $\exists$ -type over $M\cup \big\{\overline{b}\big\}$ is realized in $N$ .

Let class $K=\big\{\left({M}_i,M\right)\mid {M}_i{\preccurlyeq}_{\exists_1}C\ \mathrm{and}\ \left({M}_i,M\right)\mathrm{is}$ J $- \textrm{beautiful\ pair}\big\}$ . Consider the Jonsson spectrum of the class $K$ :

It is easy to see that the cosemanticness relation on the set of Jonsson theories is an equivalence relation. Then we can consider the $JSp(K){/}_{\bowtie}$ , which is the factor set of the Jonsson spectrum of the class $K$ with respect to $\bowtie$ .

Let $\left[\Delta \right]\in JSp(K){/}_{\bowtie }$ and ${E}_n\left(\left[\Delta \right]\right)$ be the distributive lattice of equivalence classes of ${\varphi}^{\left[\Delta \right]}=\left\{\psi \in {E}_n(L)|{\left[\Delta \right]}^{\ast}\models \varphi \leftrightarrow \psi, \varphi \in {E}_n(L)\right\}$ .

Definition 2. Let $T$ be an arbitrary Jonsson theory, then a $\#$ -companion of a theory $T$ is a theory ${T}^{\#}$ of the same signature if it satisfies the following conditions:

(i) ${\big({T}^{\#}\big)}_{\forall}={T}_{\forall }$ ;

(ii) if ${T}_{\forall}={T}_{\forall}^{\hbox{'}}$ , then ${T}^{\#}={\big({T}^{\prime}\big)}^{\#}$ ;

(iii) ${T}_{\forall \exists}\subseteq {T}^{\#}$ .

The natural interpretations of the companion ${T}^{\#}$ are ${T}^{\ast }$ , ${T}^f$ , ${T}^M$ , ${T}^e$ , ${T}^0$ , where ${T}^{\ast }$ is the center of Jonsson theory $T$ , ${T}^f$ is the forcing companion of Jonsson theory $T$ , ${T}^M$ is the model companion of the theory $T$ , ${T}^e= Th({E}_T)$ , ${T}^0={Th}_{\forall \exists }C$ .

Theorem 3. Let $\left[\Delta \right]\in JSp(K){/}_{\bowtie }$ be a perfect class, then the following conditions are equivalent:

(i) ${\left[\Delta \right]}^{\#}$ is complete theory;

(ii) ${\left[\Delta \right]}^{\#}$ is model complete theory.

Theorem 4. Let $\left[\Delta \right]\in JSp(K){/}_{\bowtie }$ be a complete for $\exists$ -sentences class. Then the following conditions are equivalent:

(i) $\left[\Delta \right]$ is perfect;

(ii) ${\left[\Delta \right]}^{\ast }$ is model-complete theory;

(iii) ${E}_n\left(\left[\Delta \right]\right)$ is a Boolean algebra.

Theorem 5. Let $\left[\Delta \right]\in JSp(K){/}_{\bowtie }$ be a perfect $\forall \exists$ -complete convex class, ${\left[\Delta \right]}^{\#}$ be its $\#$ -companion. Then theory ${\left[\Delta \right]}^{\#}$ is $\omega$ -categorical iff the class $\left[\Delta \right]$ is $\omega$ -categorical.

All necessary concepts that are not defined in this thesis can be extracted from [1].

This research is funded by the Science Committee of the Ministry of Education and Science of the Republic of Kazakhstan (Grant No. AP09260237).

[1] M.T. Kassymetova and A.R. Yeshkeyev, Jonsson theories and their classes of models , Monograph, Karaganda, KSU, 2016.

▸ KRZYSZTOF KRUPIŃSKI AND ADRIÁN PORTILLO, On stable quotients.

University of Wroclaw, pl. Grunwaldzki 2/4 50-384 Wrocław, Poland.

E-mail: [email protected].

E-mail: [email protected].

We solve two problems from Haskel and Pillay [1], which concern maximal stable quotients of groups type-definable in NIP theories. The first result says that if $G$ is a type-definable group in a distal theory, then ${G}^{st}={G}^{00}$ (where ${G}^{st}$ is the smallest type-definable subgroup with $G/{G}^{st}$ stable, and ${G}^{00}$ is the smallest type-definable subgroup of bounded index). In order to get it, we prove that distality is preserved under passing from $T$ to the hyperimaginary expansion ${T}^{heq}$ . The second result is an example of a group $G$ definable in a non-distal, NIP theory for which $G={G}^{00}$ but ${G}^{st}$ is not an intersection of definable groups. Our example is a saturated extension of $\left(\mathrm{\mathbb{R}},+,\left[0,1\right]\right)$ . Moreover, we make some observations on the question whether there is such an example which is a group of finite exponent. We also take the opportunity and give several characterizations of stability of hyperdefinable sets, involving continuous logic.

[1] Mike Haskel and Anand Pillay, On maximal stable quotients of definable groups in $NIP$ theories, The Journal of Symbolic Logic , vol. 83 (2018), no. 1, pp. 117–122.

▸ BEIBUT KULPESHOV AND SERGEY SUDOPLATOV, On theories of dense spherical orders.

Kazakh-British Technical University, Almaty, Kazakhstan.

E-mail: [email protected].

Sobolev Institute of Mathematics, Novosibirsk State Technical University, Novosibirsk State University, Novosibirsk, Russia.

E-mail: [email protected].

We study properties of theories of $n$ -spherical orders ${K}_n$ [4, 5] which naturally generalize linear orders ${K}_2$ and circular orders ${K}_3$ [3, 1, 2].

A $n$ -spherical order relation, for $n\ge 2$ , is described by a $n$ -ary relation ${K}_n$ satisfying the following conditions: (nso1) $\forall {x}_1,\dots, {x}_n({K}_n({x}_1,{x}_2,\dots, {x}_n)\to {K}_n({x}_2,\dots, {x}_n,{x}_1));$ (nso2) $\forall {x}_1,\dots, {x}_n(({K}_n({x}_1,\dots, {x}_i,\dots, {x}_j,\dots, {x}_n)\wedge$ ${K}_n({x}_1,\dots, {x}_j,\dots, {x}_i,\dots, {x}_n))$ $\leftrightarrow \underset{1\le k<l\le n}{\vee }{x}_k\approx {x}_l)$ for any $1\le i<j\le n$ ; (nso3) $\forall {x}_1,\dots, {x}_n({K}_n({x}_1,\dots, {x}_n)\to$ $\forall t(\underset{i=1}{\overset{n}{\vee }}{K}_n({x}_1,\dots, {x}_{i-1},t,{x}_{i+1},\dots, {x}_n)));$ (nso4) $\forall {x}_1,\dots, {x}_n({K}_n({x}_1,\dots, {x}_i,$ $\dots,$ ${x}_j,\dots, {x}_n)\vee \vee {K}_n({x}_1,\dots, {x}_j,\dots, {x}_i,\dots, {x}_n)),1\le i<j\le n.$

Structures $\mathcal{A}=\left\langle A,{K}_n\right\rangle$ with $n$ -spherical orders are called $n$ -spherical orders, too.

A $n$ -spherical order ${K}_n$ is called dense if it contains at least two elements and for each $\left({a}_1,{a}_2,{a}_3,\dots, {a}_n\right)\in {K}_n$ with ${a}_1\ne {a}_2$ there is $b\notin \left\{{a}_1,{a}_2,\dots, {a}_n\right\}$ with $\models {K}_n\left({a}_1,b,{a}_3,\dots, {a}_n\right)\wedge {K}_n\left(b,{a}_2,{a}_3,\dots, {a}_n\right)\!.$

Theorem 1. If $\mathcal{A}$ and $\mathrm{\mathcal{B}}$ are countable dense $n$ -spherical orders, $n\ge 2$ , without endpoints for $n=2$ , then $\mathcal{A}\simeq \mathrm{\mathcal{B}}$ .

Theorem 2. For any natural $n\ge 2$ the theory ${T}_n$ of dense $n$ -spherical order is decidable.

The research is supported by Committee of Science in Education and Science Ministry of the Republic of Kazakhstan, Grant No. AP08855544 and Russian Scientific Foundation, Project No. 22-21-00044. The work of the second author was carried out in the framework of the State Contract of the Sobolev Institute of Mathematics, Project No. FWNF-2022-0012.

[1] A. B. Altaeva, and B. Sh. Kulpeshov, On almost binary weakly circularly minimal structures, Bulletin of Karaganda University, Mathematics , vol. 78 (2015), no. 2, pp. 74–82.

[2] B. Sh. Kulpeshov, On almost binarity in weakly circularly minimal structures, Eurasian Mathematical Journal , vol. 7 (2016), no. 2, pp. 38–49.

[3] B. Sh. Kulpeshov and H. D. Macpherson, Minimality conditions on circularly ordered structures, Mathematical Logic Quarterly , vol. 51 (2005), no. 4, pp. 377–399.

[4] S. V. Sudoplatov, Arities and aritizabilities of first-order theories, Preprint, 2021, arXiv:2112.09593v1.

[5] \bysame, Almost $n$ -ary and almost $n$ -aritizable theories, Preprint, 2021, arXiv:2112.10330v1.

▸ BEIBUT KULPESHOV AND SERGEY SUDOPLATOV, On algebras of binary formulas for weakly circularly minimal theories.

Kazakh-British Technical University, Almaty, Kazakhstan.

E-mail: [email protected].

Sobolev Institute of Mathematics, Novosibirsk State Technical University, Novosibirsk State University, Novosibirsk, Russia.

E-mail: [email protected].

Algebras of binary formulas are a tool for describing relationships between elements of the sets of realizations of 1-types at binary level with respect to superpositions of binary definable sets. We consider algebras of binary isolating formulas originally studied in [4, 3], where under a binary isolating formula we understand a formula of the form $\varphi \left(x,y\right)$ , without parameters, such that for some parameter $a$ the formula $\varphi \left(a,y\right)$ isolates some complete type from ${S}_1\left(\left\{a\right\}\right)$ .

The notion of weak circular minimality was originally studied in [2]. A weakly circularly minimal structure is a circularly ordered structure $M=\left\langle M,{K}_3,\dots \right\rangle$ such that any definable (with parameters) subset of $M$ is a union of finitely many convex sets in $M$ . In [1] countably categorical 1-transitive non-primitive weakly circularly minimal structures of convexity rank 1 with non-trivial definable closure have been described up to binarity.

Here we discuss algebras of binary isolating formulas for these structures and give the following criterion for commutability of such algebras:

Theorem 1. Let $M$ be a countably categorical $1$ -transitive non-primitive weakly circularly minimal structure of convexity rank $1$ with $\mathrm{dcl}(a)\ne \left\{a\right\}$ for some $a\in M$ . Then the algebra ${\mathfrak{P}}_M$ of binary isolating formulas is commutable iff there exists an $\varnothing$ -definable non-trivial monotonic-to-right bijection on $M$ .

This research has been funded by Science Committee of Ministry of Education and Science of the Republic of Kazakhstan (Grant No. AP08855544), and by Russian Scientific Foundation (Project No. 22-21-00044).

[1] B. Sh. Kulpeshov, On ${\aleph}_0$ -categorical weakly circularly minimal structures, Mathematical Logic Quarterly , vol. 52 (2006), no. 6, pp. 555–574.

[2] B. Sh. Kulpeshov and H. D. Macpherson, Minimality conditions on circularly ordered structures, Mathematical Logic Quarterly , vol. 51 (2005), no. 4, pp. 377–399.

[3] I. V. Shulepov and S. V. Sudoplatov, Algebras of distributions for isolating formulas of a complete theory, Siberian Electronic Mathematical Reports , vol. 11 (2014), pp. 362–389.

[4] S. V. Sudoplatov, Classification of countable models of complete theories , Novosibirsk, Edition of NSTU, 2018.

▸ JOSÉ M. MÉNDEZ, GEMMA ROBLES AND FRANCISCO SALTO, A class of implicative expansions of Belnap-Dunn logic in whose elements a Boolean negation is definable.

Universidad de Salamanca. Edificio FES, Campus Unamuno, 37007, Salamanca, Spain.

E-mail: [email protected].

URL Address: http://sites.google.com/site/sefusmendez.

Dpto. de Psicología, Sociología y Filosofía, Universidad de León, Campus Vegazana, s/n, 24071, León, Spain.

E-mail: [email protected].

URL Address: https://gemmarobles.github.io.

E-mail: [email protected].

Let B’ be the result of restricting Routley and Meyer basic relevant logic B (cf. [3]) as follows: (1) Restrict all axioms of B to rule form, except the self-identity axiom (i.e., $A\to A$ ), the distributive and the double negation axioms. (2) Restrict the rules Suffixing and Prefixing to the rule Transitivity. Then, we define the class of all C-extending implicative expansions containing B’ of the well-known Belnap-Dunn logic in whose elements a Boolean negation is definable. We note that, apart from classical logic, in each one of these expansions the strong logic PŁ 4 is definable. PŁ 4 is equivalent to De and Omori’s logic BD ${}_{+}$ , Zaitzev’s paraconsistent logic FDEP and Béziau’s 4-valued modal logic PM4N, according to [1] (cf. [2] and references therein).

Acknowledgements. Work supported by research project PID2020-116502GB-I00, financed by the Spanish Ministry of Science and Innovation (MCIN/AEI/10.13039/501100011033).

[1] M. De and H. Omori, Classical Negation and Expansions of Belnap–Dunn Logic, Studia Logica , vol. 103 (2015), no. 4, pp. 825–851.

[2] G. Robles and J. M. Méndez, A 2 set-up Routley-Meyer semantics for the 4-valued logic PŁ4, Journal of Applied Logics , vol. 8 (2021), no. 10, pp. 2435–2446.

[3] R. Routley, R. K. Meyer, V. Plumwood, and R. T. Brady, Relevant Logics and their Rivals , vol. 1 Atascadero, CA: Ridgeview Publishing Co., 1982

▸ ANTONIO MONTALBÁN AND DINO ROSSEGGER, The structural complexity of models of arithmetic.

Department of Mathematics, University of California, Berkeley.

E-mail: [email protected].

Department of Mathematics, University of California, Berkeley and Institut of Discrete Mathematics and Geometry, Technische Universität Wien, Austria.

E-mail: [email protected].

The Scott rank of a countable structure is the least ordinal $\alpha$ such that all automorphism orbits of the structure are definable by infinitary ${\Sigma}_{\alpha }$ formulas. Montalbán showed that the Scott rank of a structure is a robust measure of its structural and computational complexity by showing that various different measures are equivalent. For example, a structure has Scott rank $\alpha$ if and only if it has a ${\Pi}_{\alpha +1}$ Scott sentence if and only if it is uniformly ${{\Delta}}_{\alpha}^0$ categorical. In this talk we present results on the Scott rank of models of Peano arithmetic. We show that non-standard models of PA have Scott rank at least $\omega$ and that the models of PA that have Scott rank $\omega$ are precisely the prime models. We also give reductions via bi-interpretability of the class of linear orders to completions $T$ of $PA$ . This allows us to exhibit models of $T$ of Scott rank $\alpha$ for every $\omega \le \alpha \le {\omega}_1$ .

▸ NAZERKE MUSSINA, OLGA ULBRIKHT, AND AIBAT YESHKEYEV, Syntactic and semantic similarities of hybrids of classes of the Jonsson spectrum of Jonsson quasivariety of the class $K$ .

Faculty of Mathematics and Information Technologies, Karaganda Buketov University, University str., 28, building 2, Kazakhstan.

E-mail: [email protected].

E-mail: [email protected].

E-mail: [email protected].

Let $K$ be the class of structures of countable signature $\sigma$ . Let’s introduce the notation:

Definition 1. A variety (quasivariety) of structures $K$ is called a Jonsson variety (quasivariety) if $\forall \exists (K)$ is a Jonsson theory.

Consider the $JSpV(K)$ be Jonsson spectrum of the Jonsson variety of class $K$ , where $K$ is the Jonsson variety:

Then $JSpV(K){/}_{\bowtie }$ is denoting the factor set of the Jonsson spectrum of Jonsson quasivariety of the class $K$ by the relation $\bowtie$ .

Similarly, we define the Jonsson spectrum of $JSpQV(K)$ quasivariety:

Then $JSpQV(K){/}_{\bowtie }$ denotes the factor set of the Jonsson spectrum of Jonsson quasivariety of the class $K$ by the relation $\bowtie$ .

Definition 2. Let $K$ be some Jonsson quasivariety of structures of signature $\sigma$ , $\left[{T}_1\right],\left[{T}_2\right]\in JSpQV(K){/}_{\bowtie }$ . The hybrid (of the first type) $H\left(\left[{T}_1\right],\left[{T}_2\right]\right)$ of the classes $\left[{T}_1\right]$ and $\left[{T}_2\right]$ is the theory ${Th}_{\forall \exists}\left({C}_1\diamond {C}_2\right)$ if it is Jonsson theory in language of the signature $\sigma$ , where ${C}_i$ are semantic models of the classes $\left[{T}_i\right]$ , $i=1,2$ respectively and $\diamond \in \{\times, +,\oplus, \prod \limits_F,\prod \limits_U\}$ , where $\times$ is cartesian product $, +$ is the sum, $\oplus$ is the direct sum, $\prod \limits_F$ is reduced product and $\prod \limits_U$ is the ultraproduct of models.

The following fact will be necessary for the proof of Theorem 1

Fact 1. ([1], p. 48) For any complete for $\exists$ -sentences Jonsson theory $T$ the following conditions are equivalent:

1) ${T}^{\ast }$ is model complete;

2) for each $n<\omega$ , ${E}_n(T)$ is Boolean algebra, where ${E}_n(T)$ is a lattice of $\exists$ -formulas with $n$ free variables.

And in the frame above mentioned notions we have the following result.

Theorem 1. Let $K$ be some Jonsson quasivariety of structures of signature $\sigma$ , $\left[{T}_1\right],\left[{T}_2\right]$ , $\left[{T}_3\right],\left[{T}_4\right]\in JSpQV(K){/}_{\bowtie }$ , ${H}_1=H\left(\left[{T}_1\right],\left[{T}_2\right]\right)$ and ${H}_2=H\left(\left[{T}_3\right],\left[{T}_4\right]\right)$ are complete for existential sentences perfect hybrids, then following conditions are equivalent:

1. ${H}_1\overset{S}{\sim }{H}_2$ ;

2. ${H}_1^{\ast}\overset{S}{\approx }{H}_2^{\ast }$ .

All additional information regarding Jonsson theories can be found in [1].

This work was supported by the Science Committee of the Ministry of Education and Science of the Republic of Kazakhstan (grand AP09260237).

[1] M. T. Kassymetova and A. R. Yeshkeyev, Jonsson theories and their classes of models , Monograph, KSU, 2016.

▸ LUIZ CARLOS PEREIRA AND ELAINE PIMENTEL, On an ecumenical natural deduction with stoup.

Department of Philosophy, PUC-Rio/UERJ, Rio de Janeiro, Brazil.

E-mail: [email protected].

Department of Computer Science, UCL, London, UK.

E-mail: [email protected].

Natural deduction systems, as proposed by Gentzen [1] and further studied by Prawitz [3], is one of the most well known proof-theoretical frameworks. Part of its success is based on the fact that natural deduction rules present a simple characterization of logical constants, especially in the case of intuitionistic logic. However, there has been a lot of criticism on extensions of the intuitionistic set of rules in order to deal with classical logic. Indeed, most of such extensions add, to the usual introduction and elimination rules, extra rules governing negation. As a consequence, several meta-logical properties, the most prominent one being harmony, are lost.

In [4], Dag Prawitz proposed a natural deduction ecumenical system, where classical logic and intuitionistic logic are codified in the same system. In this system, the classical logician and the intuitionistic logician would share the universal quantifier, conjunction, negation and the constant for the absurd, but they would each have their own existential quantifier, disjunction and implication, with different meanings. Prawitz’ main idea is that these different meanings are given by a semantical framework that can be accepted by both parties.

In this talk, we propose a different approach adapting, to the natural deduction framework, Girard’s mechanism of stoup [2]. This will allow the definition of a pure harmonic natural deduction system ( ${\mathrm{\mathcal{LE}}}_p$ ) for the propositional fragment of Prawitz’ ecumenical logic.

[1] Gerhard Gentzen, The Collected Papers of Gerhard Gentzen , North-Holland Publishing Company, 1969.

[2] Jean-Yves Girard, A new constructive logic: Classical logic, Mathematical Structures in Computer Science , vol. 1 (1991), no. 3, pp. 255–296.

[3] Dag Prawitz, Natural Deduction , Stockholm St, Almqvist and Wiksell, 1965.

[4] Dag Prawitz, Classical versus intuitionistic logic, Why is this a Proof?, Festschrift for Luiz Carlos Pereira (Edward Hermann Haeusler, Bruno Lopes, and Wagner de Campos Sanz, editors), College Publications, 2015, pp. 15–32.

▸ IOSIF PETRAKIS, Positive negation in constructive mathematics.

Mathematisches Institut, Ludwig-Maximilians-Universität München, Theresienstrasse 39, D-80333 Munich, Germany.

E-mail: [email protected].

In standard constructive logic negation is treated as in classical logic in a negativistic and weak way. This is in contrast to the use of a positive and strong “or” and “exists”. In constructive mathematics [1] however, we often find a positive and strong approach to negatively defined concepts, like that of inequality.This fact motivates a clear distinction between a positive and strong negation and the standard weak negation. Bringing together older ideas of Griss and Nelson and recent work of Shulman [3] and ours [2], we investigate the role of a positive and strong negation in Bishop-style constructive mathematics $\mathrm{BISH}$ . We define the positive negation of a formula in $\mathrm{BISH}$ , we determine the formulas of $\mathrm{BISH}$ that are used to define the equality of a Bishop set, and we define the canonical inequality of a Bishop set through positive negation of its given equality formula. Consequently, many seemingly ad hoc definitions of concepts of $\mathrm{BISH}$ , such as the complement of a subset, the empty subset, complemented subsets, and the $F$ -complement of a closed set, are canonical definitions through positive negation.

[1] E. Bishop and D. Bridges, Constructive Analysis , Springer-Verlag, 1985.

[2] I. Petrakis, Families of Sets in Bishop Set Theory, 2021, arXiv:2109.04183v1.

[3] M. Shulman, Affine Logic for Constructive Mathematics, 2021, arXiv:1805.07518v2.

▸ JONI PULJUJÄRVI AND DAVIDE EMILIO QUADRELLARO ${}^{\ast }$ , Compactness and types in logics of dependence.

Department of Mathematics and Statistics, University of Helsinki, Finland.

E-mail: [email protected].

E-mail: [email protected].

In first-order logic, the following formulations of the compactness theorem can be easily proved from one another:

• (i) Every set of sentences that is finitely satisfiable is satisfiable;

• (ii) Every set of formulas that is finitely satisfiable is satisfiable.

For dependence logic, the first version of compactness is a well-known result and was proved by Väänänen in [3] using the translation between dependence logic and ${\Sigma}_1^1$ . However, in the context of dependence logic, one cannot derive (ii) from (i) by replacing variables with constants, as it is the case for first order logic.

The second version of compactness (ii) has been recently considered by Kontinen and Yang in [1], who used the translation from dependence logic to ${\Sigma}_1^1$ to show that “every set of formulas with countably many free variables that is finitely satisfiable is satisfiable”. In our talk, we provide a proof of the second version of compactness (ii) for arbitrary sets of formulas by adapting ultraproducts to the context of team semantics, analogously to [2].

Finally, we briefly touch upon the issue of types in dependence logic, and we see how to obtain a compact space of suitable type.

[1] Juha Kontinen and Fan Yang, Complete logics for elementary team properties, arXiv1904.08695.

[2] Martin Lück, Team Logic Axioms, Expressiveness, Complexity , PhD thesis, University of Hannover, 2020.

[3] Jouko Väänänen, Dependence Logic: A New Approach to Independence Friendly Logic , Cambridge University Press, 2007.

▸ GEMMA ROBLES, The logic E-Mingle and its Routley-Meyer semantics.

Departamento de Psicología, Sociología y Filosofía, Universidad de León, Campus Vegazana, s/n, 24071, León, Spain.

E-mail: [email protected].

URL Address: https://gemmarobles.github.io.

The logic R-Mingle (RM) is axiomatized when adding the “mingle axiom” (M: $A\to \left(A\to A\right)$ ) to Anderson and Belnap’s logic of the relevant implication R. The logic E-Mingle (EM) is the result of adding the “restricted mingle axiom” (Mr: $\left(A\to B\right)\to \left[\left(A\to B\right)\to \left(A\to B\right)\right]$ ) to Anderson and Belnap’s logic of entailment E (cf. [1]).

Contrary to what is the case with RM and its extensions, thoroughly investigated logics since the beginning of the “relevance enterprise” (cf. [1]), practically everything is ignored about EM. In particular, this logic lacks a semantics whatsoever. The aim of this paper is to remedy this deficiency by providing a Routley-Meyer semantics for EM, despite the fact that the creators of this semantics think that it is no possible to interpret Mr in it (cf. [2, §4.9]). EM is endowed with a Routley-Meyer semantics by giving it a Hilbert-style formulation in which Mr does not appear.

Acknowledgements. Work supported by research project PID2020-116502GB-I00, financed by the Spanish Ministry of Science and Innovation (MCIN/AEI/10.13039/501100011033).

[1] A. R. Anderson and N. D. Belnap, Entailment. The Logic of Relevance and Necessity , vol. I, Princeton University Press, 1975.

[2] R. Routley, R. K. Meyer, V. Plumwood, and R. T. Brady, Relevant Logics and their Rivals , vol. 1, Ridgeview Publishing Co., Atascadero, CA. 1982.

▸ TAPIO SAARINEN, The categoricity of complete theories in second-order logic.

Department of Mathematics and Statistics, University of Helsinki, Finland.

E-mail: [email protected].

A complete theory is said to be categorical, if it has a unique model up to isomorphism. Due to the upwards and downwards Löwenheim-Skolem theorems, complete first-order theories with infinite models are never categorical, as they have models in all infinite cardinalities. In contrast, the second-order versions of many familiar theories (such as second-order Peano Arithmetic, or the second-order theory of the real numbers as a complete ordered field) are categorical. One therefore wonders about the extent of this phenomenon: given an arbitrary complete second-order theory, is it categorical? As non- categorical complete second-order theories exist by a cardinality argument, it is reasonable to require that the theory is tractable in some sense (such as finitely axiomatizable, recursively axiomatizable, or that it has a model of size $\kappa$ for some particular cardinal $\kappa$ ). It turns out that for many classes of theories, the answer is independent of ZFC.

In this talk we present some new results in this area.

▸ D. GIHANEE SENADHEERA, Effective concept classes of PAC and PACi incomparable degrees and jump structure.

School of Mathematics and Statistical Sciences, Southern Illinois University, 1245 Lincoln Drive, Mail Code 4408, Carbondale IL, USA.

E-mail: [email protected].

The Probably Approximately Correct (PAC) learning model is a machine learning model introduced by Leslie Valiant in 1984. Similar to Turing reducibility there is a reducibility to this learning model as well. The PACi means a less restricted version of PAC reducibility. Here i refers to the independence of the size and the computation time of the PAC reducibility. The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples. We recursively construct two effective concept classes of incomparable PACi degrees to show that there exist incomparable PACi degrees. Similarly, we can construct for PAC degrees which is analogous to incomparable Turing degrees. The priority construction method is used to construct the two concept classes, which was used by Friedburg and Muchnik in their proof of incomparable Turing degrees. It was necessary to deal with the size of an effective concept class thus we propose to compute the size of the effective concept class using Kolmogorov complexity. Furthermore, we explore the jump structure of effective concept classes similar to the Turing jump and progress toward embedding $1$ degrees.

[1] Wesley Calvert, PAC Learning, VC Dimension, and The Arithmetic Hierarchy, Archive for Mathematical Logic , vol. 54 (2015), no.7-8, pp. 871–883.

[2] \bysame, Mathematical Logic and Probability , preprint.

[3] M. J. Kearns and U.V. Vazirani, An Introduction to Computational Learning Theory , MIT Press, 1994.

[4] Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications , Springer, Switzerland, 2019.

[5] Robert Soare, Recursively Enumerable Sets and Degrees , Springer-Verlag, New York, 1987.

▸ SEBASTIAN G.W. SPEITEL, Arithmetic via Carnap-categoricity.

Institute of Philosophy, University of Bonn, Germany.

E-mail: [email protected].

The existence of non-standard models of first-order Peano-arithmetic (PA) has long been taken to undermine the claim of the mathematical realist that determinate reference to the natural number structure is possible in a non-mysterious, naturalistically acceptable way. The use of logics stronger that FOL to achieve a categorical theory of arithmetic and resolve this referential indeterminacy has been criticised as merely pushing the issue ‘one level up’ into the meta-theory of these logics. This, the model-theoretic sceptic claims, is due to the fact that the resources needed to formulate these logics are just as much in need of justification as reference to the natural number structure itself.

In [1] we outlined and defended a novel criterion of logicality based on the idea that logical notions must be formal (invariant under isomorphisms) as well as categorical (uniquely determinable by inference). A notion satisfying this criterion was termed Carnap- categorical. In this talk, I want to show that our criterion offers an attractive and well-motivated answer to the sceptical challenge advanced against the mathematical realist. The reply is based on the Carnap-categoricity of the generalised quantifier “there are infinitely many” ( ${\mathcal{Q}}_0$ ). It is this property of ${\mathcal{Q}}_0$ which allows us to successfully mitigate the objection that the indeterminacy affecting reference to the natural number structure simply re-arises at the level of the meta-theory of the logic used to provide a categorical axiomatization of that structure.

I compare this approach with other attempts to justify the move to stronger logics found in the literature and argue that the proposal based on Carnap- categoricity is more robust and thus preferable. I conclude by reflecting on the scope of the response to the sceptical challenge and the remaining sources of indeterminacy.

[1] D. Bonnay and S. G. W. Speitel, The Ways of Logicality: Invariance and Categoricity, The Semantic Conception of Logic. Essays on Consequence, Invariance, and Meaning (G. Sagi and J. Woods, editors), Cambridge University Press, 2021, pp. 55–79.

▸ TINKO TINCHEV, Decidability of modal definability problem on the class of quasilinear frames.

Faculty of Mathematics and Informatics, Sofia University St. Kliment Ohridski, Blvd. James Bourchier 5, Sofia 1164, Bulgaria.

E-mail: [email protected].

Let $\mathcal{K}$ be the class of all quasilinear Kripke frames, i.e. the accesibility relation is reflexive, transitive and total (linear). Denote by ${\mathcal{K}}^{\mathrm{fin}}$ and by ${\mathcal{K}}^{\le \omega }$ the classes of frames from ${\mathcal{K}}^{\mathrm{fin}}$ having finetely many, resp. at most countably many, clusters. Our goal is to study the modal definability problem on these three classes. Remind that a sentence $A$ from the first-order language with equality and one binary predicate symbol is modally definable with respect to some class of frames if there is a modal formula $\varphi$ from the classical propositional modal language such that $A$ and $\varphi$ are valid in the same frames from the class. Modal definability problem ask whether there exists an algorithm that recognizes modally definable sentences.

In this talk we make a heavy use of decidability of Rabin’s $S2S$ theory to prove the following.

Theorem 1. The modal definability problem is decidable with respect to the classes ${\mathcal{K}}^{\mathrm{fin}}$ and ${\mathcal{K}}^{\le \omega }$ .

Theorem 2. For any sentence $A$ , $A$ is modally definable with respect to $\mathcal{K}$ if and only if $A$ is modally definable with respect to ${\mathcal{K}}^{\le \omega }$ . Therefore, the modal definability problem with respect to $\mathcal{K}$ is decidable.

Theorem 3. 1. There is an algorithm which for any sentence $A$ gives a modal definition of $A$ on ${\mathcal{K}}^{\mathrm{fin}}$ , if such modal formula exists.

2. There is an algorithm which for any sentence $A$ gives a modal definition of $A$ on $\mathcal{K}$ , if such modal formula exists.

▸ CHENG-SYUAN WAN, Proof theory of skew non-commutative $\mathrm{MILL}$ _.

Department of Software Science, Tallinn University of Technology, Estonia.

E-mail: [email protected].

Monoidal closed categories are models of non-commutative multiplicative intuitionistic linear logic ( $\mathrm{NMILL}$ ). Skew monoidal closed categories are weak variants of monoidal closed categories [2]. In the skew cases, three natural isomorphisms $\lambda :\mathrm{I}\otimes A\cong A$ , $\rho :A\cong A\otimes \mathrm{I}$ , and $\alpha :\left(A\otimes B\right)\otimes C\cong A\otimes \left(B\otimes C\right)$ are merely natural transformations with a specific orientation. In previous works by Uustalu et al. [3] [4], proof theoretical analysis on skew monoidal categories and skew closed categories are investigated. In particular, the sequent calculus systems modelled by skew monoidal and skew closed categories are respectively constructed. Moreover, proof theoretical semantics of each system is provided according to Jean-Marc Andreoli’s focusing technique [1].

Following the results above, a question arises: is it possible to construct a sequent calculus system naturally modelled by skew monoidal closed categories? We answer the question positively by constructing a cut-free system ${\mathrm{NMILL}}^s$ , a skew version of $\mathrm{NMILL}$ . Furthermore, we study the proof theoretical semantics of ${\mathrm{NMILL}}^s$ . The inspiration also originates from focusing, but we peculiarly employ tag annotations to keep tracking new formulae occurring in antecedent and reducing non-deterministic choices in bottom-up proof search. Focusing solves the coherence problem of skew monoidal closed categories by providing a decision procedure to determine equality of maps in the free skew monoidal closed category.

This is joint work with Tarmo Uustalu (Reykjavik University) and Niccolò Veltri (Tallinn University of Technology).

[1] Jean-Marc Andreoli, Logic Programming with Focusing Proofs in Linear Logic, Journal of Logic and Computation , vol. 2 (1992), no. 3, pp. 297–347.

[2] Ross Street, Skew-Closed Categories, Journal of Pure and Applied Algebra , vol. 217 (2012), no. 6, pp. 973–988.

[3] Tarmo Uustalu, Niccolò Veltri, and Noam Zeilberger, Deductive Systems and Coherence for Skew Prounital Closed Categories, Eletronic Proceedings in Theoretical Computer Science , vol. 332 (2021), pp. 35–53.

[4] ———, The Sequent Calculus of Skew Monoidal Categories, Joachim Lambek: The Interplay of Mathematics, Logic, and Linguistics , (Claudia Casadio and Philip J. Scott, editors), Outstanding Contributions to Logic, Springer, 2021, pp. 377–406.

▸ ANDREAS WEIERMANN, The phase transition for Harvey Friedman’s monotone Bolzano Weierstrass principle.

Department of Mathematics WE16, Krijgslaan 281 S8, 9000 Ghent, Belgium.

E-mail: [email protected].

Let $f$ be a weakly monotone and unbounded number-theoretic function. Harvey Friedman’s monotone Bolzano Weierstrass principle with respect to $f$ is the following assertion ( ${MBW}_f$ ). $\forall K\ge 3\exists M\forall {x}_1,\dots, {x}_M\in \left[0,1\right]\big({x}_1<\dots <{x}_M\to \exists {k}_1,\dots, {k}_K\big({k}_1<\dots < {k}_K\wedge \forall L\le K-2|{x}_{k_{l+1}}-{x}_{k_{l+2}}|<\frac{1}{f\big({k}_l\big)}\big)\big)$ . Friedman has shown that ${MBW}_f$ is true (by an application of the compactness of the Hilbert cube). Morever Friedman has shown that for $f(x)={2}^x$ the principle ${MBW}_f$ is provable from $I{\Sigma}_1+\forall x\exists yA\left(x,0\right)=y$ where $A$ is the Ackermann function. In our talk we will approximate the phase transition for ${MBW}_f$ and for this we will apply classical results by Abel (and its refinement by Elstrodt and Fischer) on the convergence of logarithmic series. In particular we will show that $I{\Sigma}_1\vdash {MBW}_f$ for $f(i)=i\cdot \log (i)\cdot \dots \cdot {\log}_{\log^{\ast }(i)}(i)$ where ${\log}^{\ast }(i)$ is the functional inverse of the tower function.

Abstract of talk presented by title

▸ JOACHIM MUELLER-THEYS, The inhomogeneity of concepts.

Independent researcher, Heidelberg, Germany.

E-mail: [email protected].

We may think of $P,Q,\dots \subseteq M$ as properties or concepts. For $a,b,\dots \in M$ , $P(a)$ :iff $a\in P$ . $P$ is total :iff $P=M$ , $P$ vacuous :iff $-P$ total, $P$ real :iff $P$ not vacuous. We naturally call $P$ extreme :iff $P$ is vacuous or total iff. $P$ real implies $P$ total. $P$ singular :iff $\mid P\mid =1$ . We naturally call $P$ genuine iff $P$ is neither vacuous nor singular.

We have defined $P$ -similarity $a{\sim}_Pb$ by $P(a)\&P(b)$ and $P$ -equality $a{\equiv}_Pb$ by $P(a)\iff P(b)$ . The basic connection is ${\sim}_P\subseteq {\equiv}_P$ ; the converse is not true in general.

We say that $Q$ differentiates $P$ :iff $P(a)$ , $P(b)$ , but $ a \not\equiv _Q b $ for some $a$ , $b$ . For example, evil differentiates human, transuranic differentiates element. We call $P$ inhomogeneous iff there exists $Q$ such that $Q$ differentiates $P$ . Accordingly, human and element are inhomogeneous. We have found that, in general, all genuine concepts are inhomogeneous: Let $P$ be genuine, whence $\mid P\mid \ge 2$ , whereby $P(a)$ , $P(b)$ for some $a\ne b$ . Now let $Q:= P\backslash \left\{b\right\}$ , whence $Q(a)$ , but non $Q(b)$ , whereby $ a \not\equiv _Q b $ . Thus ${\mathrm{Diff}}_Q(P)$ , whence $\mathrm{Inhom}(P)$ .

$\mathrm{Inhom}(P)$ may be seen as formalisation of sayings of the form “ $P$ is not $P$ ”, like human is not human, element is not element. Phrases of the form “ $P$ is $P$ “, like “human is human”, may be precisefied by $a{\equiv}_Pb$ for all $a,b\in P$ , which is a special case of “all $P$ are $Q$ -equal”: ${\mathrm{AllEq}}_Q(P)$ iff $\mathrm{non}$ ${\mathrm{Diff}}_Q(P)$ . ${Dicho}_Q(P)$ $:=$ $P\subseteq Q$ $\mathrm{or}$ $P,Q$ disjoint. We had found and proven the Dichotomy Theorem: ${\mathrm{AllEq}}_Q(P)$ iff ${\mathrm{Dicho}}_Q(P)$ .

Since $P\subseteq\kern0.5pt -\kern0.5pt {Q}$ iff $P\cap Q=\varnothing$ , ${Hom}_Q(P)$ $:=$ $P\subseteq Q$ $\mathrm{or}$ $P\subseteq -Q$ iff ${\mathrm{Dicho}}_Q(P)$ , whence ${\mathrm{AllEq}}_Q(P)$ iff ${\mathrm{Hom}}_Q(P)$ . Now as corollaries, ${\mathrm{AllEq}}_P(M)$ iff Extr( $P$ ), whereby human beings are equal only with respect to human, and $\mathrm{Inhom}(P)$ iff there is $Q$ with ${\mathrm{Inhom}}_Q(P)$ . Moreover, ${\mathrm{Inhom}}_Q(P)$ coincides with heterogeneity ${Het}_Q(P)$ $:=$ $P\cap Q\ne \varnothing$ $\&$ $P\cap -Q\ne \varnothing$ .

A sophisticated formal interpretation of “ $P$ is $P$ “ may now be $\forall Q$ : ${\mathrm{Hom}}_Q(P)$ $\Rightarrow$ ${\mathrm{AllEq}}_Q(P)$ (“all $P$ are equal with respect to all homogeneous $Q$ “). It is curious that “ $P$ is $P$ “ and “ $P$ is not $P$ if $P$ is genuine” are tautologies both then.

Joint work with Wilfried Buchholz. For related achievements and acknowledgments, see “Similarity and equality” (talk at the 2021 North American Annual Meeting of the Association for Symbolic Logic, The Bulletin of Symbolic Logic vol. 27 (2021), pp. 329), “Mathematical theorems on equality and unequality” (The Bulletin of Symbolic Logic vol. 28 (2022), pp. 317–318), “Equivalence” (2022 ASL Annual Meeting).

▸ ALEXEJ PYNKO, Minimally $n$ -valued maximally paraconsistent expansions of $LP$ . Cybernetics Institute, Glushkov p. 40, Kiev, 03680, Ukraine.

E-mail: [email protected].

Given any propositional language $L$ (viz., a set of propositional connectives, treated as operation symbols, when dealing with $L$ -algebras), a propositional $L$ -logic $C$ (viz., a structural closure operator over the carrier ${\mathrm{Fm}}_L$ of the absolutely-free $L$ -algebra ${\mathfrak{Fm}}_L$ freely-generated by the set $V\triangleq {\left\{{x}_i\right\}}_{i\in \omega }$ of propositional variables $\langle$ as usual, natural numbers, including $0$ , are treated as sets of lesser ones, the set of all them being denoted by $\omega \rangle$ ) is said to be [{uniformly/axiomatically} minimally/maximally] “ $\lfloor$ singularly $\rfloor$ $\lceil$ no-more-than- $\rceil n$ -valued”/ $\neg$ -paraconsisent, where “ $n\in (\omega \backslash \left(1\left[+1\right]\right)$ “/” $\neg \in L$ is unary”, provided “ $C$ is defined by a $\lfloor$ one-element $\rfloor$ class $\mathrm{M}$ of $\lceil$ no-more-than- $\rceil n$ -valued $L$ -matrices (viz., pairs of $L$ -algebras and their subsets) — i.e., $\{{h}^{-1}\left[D\right]|\left\langle \mathfrak{A},D\right\rangle \in \mathrm{M},h\in \hom \left({\mathfrak{Fm}}_L,\mathfrak{A}\right)\}$ is a closure basis of $\mathrm{img}C$ — [but is not {singularly} no-more-than- $\left(n-1\right)$ -valued]”/” $x_1\not\in C(\{x_0,\neg x_0\})$ [and $C$ has no $\neg$ -paraconsistent extension ${C}^{\prime }$ (viz., an $L$ -logic with $\left(\mathrm{img}{C}^{\prime}\right)\subseteq \left(\mathrm{img}C\right)$ ) such that ${C}^{\prime}\left\{\left(\varnothing \right)\right\}\ne C\left\{\left(\varnothing \right)\right\}$ ]”, an $L$ -matrix being said to be $\neg$ -paraconsistent, whenever its (viz., defined by it) logic is so. Then, a model of $C$ is any $L$ -matrix defining an extension of $C$ .

Let $n\in \left(\omega \backslash 3\right)$ , ${L}_{+\left[-\right]}\triangleq \left\{\wedge, \vee \left[,\neg \right]\right\}$ the propositional language with binary connectives [other than the unary one $\neg$ ], ${N}_{n\left[-\right]}\triangleq \left\{i\in \left(\left(n-1\right)\backslash 1\right)|\left(2\cdot i\right)\in \left(n\left[-1\right]\right)\ni \left(4\left[-3\right]\right)\right\}$ , ${L}_n\triangleq \left({L}_{+-}\cup \left\{{\partial}_i|i\in {N}_{n-}\right\}\cup \left\{{\nabla}_j|j\in {N}_n\right\}\right)$ the propositional language with unary connectives other than those in ${L}_{+}$ , ${\mathfrak{A}}_n$ the ${L}_n$ -algebra with ${L}_{+-}$ -reduct being the Kleene chain lattice under the natural ordering on the carrier $n$ of ${\mathfrak{A}}_n$ as well as operations ${\partial}_i^{{\mathfrak{A}}_n}\triangleq \left(\left(\left(i+1\right)\times \left\{0\right\}\right)\cup \left(\left(n\backslash \left(i+1\right)\right)\times \left\{n-1\right\}\right)\right)$ , where $i\in {N}_{-n}$ , and ${\nabla}_j^{{\mathfrak{A}}_n}\triangleq \left(\left(\left(\left(n-1\right)\backslash 1\right)\times \left\{j\right\}\right)\cup \left\{\left\langle 0,0\right\rangle, \left\langle n-1,n-1\right\rangle \right\}\right)$ , where $j\in {N}_n$ , while ${\mathcal{A}}_n\triangleq \left\langle {\mathfrak{A}}_n,{D}_n\right\rangle$ the ${L}_n$ -matrix with ${D}_n\triangleq \left(n\backslash 1\right)$ , whereas ${C}_n$ the logic of ${\mathcal{A}}_n$ . in which case this is $\neg$ -paraconsistent, while ${\left(L|C\right)}_3=\left({L}_{+-}| LP\right)$ $\mid$ (viz., the logic of paradox), whereas $\left(\left(\left(\left(n-1\right)\backslash 1\right)\times \left\{1\right\}\right)\cup \left\{\left\langle 0,0\right\rangle, \left\langle n-1,n-1\right\rangle \right\}\right)\in \hom \left({\mathcal{A}}_n\upharpoonright {L}_3,{\mathcal{A}}_3\right)$ is both strict and surjective, and so ${C}_n$ is an $n$ -valued expansion of $LP$ (in particular, $LP$ is [non-minimally] $n$ -valued [unless $n=3$ ], the ${L}_{+}$ -fragment of ${C}_n$ being that of $LP$ {i.e., that of $PC$ }).

Lemma 1. For any $\neg$ -paraconsistent model $\left\langle \mathfrak{A},D\right\rangle$ of ${C}_n$ , there are some subalgebra $\mathfrak{B}$ of $\mathfrak{A}$ with carrier $B$ and some surjective $h\in \hom \left(\mathfrak{B},{\mathfrak{A}}_n\right)$ with $\left(B\cap D\right)={h}^{-1}\left[{D}_n\right]$ .

As any $L$ -logic is defined by the class of all its models, Lemma 1 immediately yields:

Theorem 2. ${C}_n$ is both minimally $n$ -valued and maximally $\neg$ -paraconsistent.

On the other hand, elimination of any connective in ${L}_n\backslash {L}_{+-}$ results in a fragment of ${C}_n$ that is either not (even uniformly) minimally $n$ -valued or not (even axiomatically) maximally $\neg$ -paraconsistent. More precisely, we have:

Theorem 3. The ${L}^{\prime }$ -fragment ${C}^{\prime }$ of ${C}_n$ with ${L}^{\prime}\subseteq \mid =\left({L}_n\backslash \left\{{\left(\partial /\nabla \right)}_i\right\}\right)$ , $i\in {N}_{\left(n-\right)\mid n}$ , is not uniformly $\mid$ axiomatically minimally $\mid$ maximally $n$ -valued $\mid \neg$ -paraconsistent.

Theorem 4. Let ${C}_n^{\mathrm{NP}/\mathrm{PC}}$ be the ${L}_n$ -logic defined by “the direct product of ${\mathcal{A}}_n$ and”/ $\left\langle {\mathfrak{A}}_n\upharpoonright \left\{0,n-1\right\},\left\{n-1\right\}\right\rangle$ . Then, these are the only proper $\lceil$ viz., distinct from $C_n\rceil$ consistent $\lfloor$ viz., not defined by $\varnothing\rfloor$ extensions of ${C}_n$ , while the former/latter is /”a proper extension of the former as well as” the least non- $\neg$ -paraconsistent/ extension / ${C}^{\prime }$ of ${C}_n$ /”such that $\left({x}_1\left[|\neg {x}_0\supset \left({x}_0\supset {x}_1\right)\right]\right)\in {C}^{\prime}\left(\left\{{x}_0\left\{\vee {x}_1\right\},\neg {x}_0\vee {x}_1\right\}\left[|\varnothing \right]\right)$ [whenever $4\in n$ , where $\left({x}_0\supset {x}_1\right)\triangleq \left({\partial}_1{\nabla}_1\neg {x}_0\vee {x}_1\right)$ ]”, whereas ${C}_n^{\mathrm{NP}}\left(\varnothing \right)={C}_n\left(\varnothing \right)(={C}_n^{\mathrm{PC}}\left(\varnothing \right)$ iff $4\not\in n$ ).

▸ ALEXEJ PYNKO ${}^{\ast }$ AND GNAT RUBKO, Paraconsistent extensions of three-valued logics.

Cybernetics Institute, Glushkov p. 40, Kiev, 03680, Ukraine.

E-mail: [email protected].

Given any propositional language $L$ (viz., a set of connectives, treated as operation symbols, when dealing with $L$ -algebras), an $L$ -logic $C$ (viz., a structural closure operator over the set ${\mathrm{Fm}}_L$ of $L$ -formulas with variables in ${\left\{{x}_i\right\}}_{i\in \omega }$ $\langle$ natural numbers, including $0$ , are treated as sets of lesser ones, the set of all them being denoted by $\omega \rangle$ ; pairs of the form $\Gamma \vdash \varphi$ , where $\Gamma \subseteq {\mathrm{Fm}}_L\ni \varphi$ , being called $L$ -rules) is said to “satisfy an $L$ -rule $\Gamma \vdash \varphi$ “/”be [({almost} pre-)maximally] $\langle \neg$ -para $\rangle$ consisent $\langle$ where $\neg \in L$ is unary $\rangle$ “, if “ $\varphi \in C\left(\Gamma \right)$ “/” $C$ does not satisfy $\left(\left\langle \left\{{x}_0,\neg {x}_0\right\}\cup \right\rangle \varnothing \right)\vdash {x}_1$ [and has no (more than $1\left\{+1\right\}$ ) $\langle \neg$ -para $\rangle$ consistent proper — viz., distinct from $C$ – extension — viz., an $L$ -logic satisfying all $L$ -rules $C$ satisfies], an $L$ -matrix defining such a logic being said to do/be so too”. Likewise, $C$ is said to be weakly $\wedge$ -conjunctive/ $\vee$ -disjunctive, where $\wedge /\vee$ is a binary connective of $L$ (possibly, a secondary one; viz., an $L$ -formula with at most two variables ${x}_0$ and ${x}_1$ ), if $C({x}_{0\mid 1})\subseteq /\supseteq C\left({x}_0\left(\wedge /\vee \right){x}_1\right)$ , an $L$ -matrix defining such a logic being said to be so too. Then, a theorem/model of $C$ is any “element of $C\left(\varnothing \right)$ “/” $L$ -matrix defining an extension of $C$ “. Likewise, the least extension ${C}^R$ of $C$ satisfying an $L$ -rule $R$ is said to be relatively axiomatized by $R$ . Finally, two-valued $L$ -matrices with single distinguished value and operation $\neg$ permuting their unique distinguished and non-distinguished values are said to be $\neg$ -classical, [any sublogic of — viz., an $L$ -logic with an extension being — any of] their logics being called $\neg$ -[sub]classical. Let $\mathcal{A}=\left\langle \mathfrak{A},D\right\rangle$ be a $\neg$ -paraconsistent $L$ -matrix with carrier $A\triangleq (2\cup \{\frac{1}{2}\})$ and $({\neg}^{\mathfrak{A}}\upharpoonright 2)=({2}^2\backslash {\Delta}_2)$ , where ${\Delta}_S\triangleq \left\{\left\langle s,s\right\rangle |s\in S\right\}$ , for any set $S$ , as well as $D\triangleq \left(A\backslash 1\right)$ , ${\mathcal{A}}_{\frac{1}{2}}\triangleq \langle \mathfrak{A},\left\{\frac{1}{2}\right\}\rangle$ and ${C}_{\left[\frac{1}{2}\right]}$ the logic of ${\mathcal{A}}_{\left[\frac{1}{2}\right]}$ .

Theorem 1. $C$ is not maximally $\neg$ -paraconsistent iff $({\neg}^{\mathfrak{A}}\cup \{\langle \frac{1}{2},\frac{1}{2}\rangle \})\in \mathbf{S}{\mathfrak{A}}^2$ iff ${\neg}^{\mathfrak{A}}$ is an automorphism of $\mathfrak{A}$ iff ${\left(C/\mathcal{A}\right)}_{\frac{1}{2}}$ is a $\neg$ -paraconsistent extension/model of $C$ iff $C$ has a $\neg$ -paraconsistent model with single distinguished value iff $\langle \mathfrak{A},\{0,\frac{1}{2}\}\rangle$ is a $\neg$ -paraconsistent/defining model of $C$ iff the extension of $C$ relatively axiomatized by ${R}^{\left[+\right]}\triangleq \left(\left\{\left[{x}_0,\neg {x}_0,\right]{x}_1\right\}\vdash \neg {x}_1\right)$ is $\neg$ -paraconsistent, in which case proper $\mid \neg$ -paraconsistent extensions of $C$ are exactly extensions $\mid$ sublogics of ${C}^{R^{+\mid }}\subseteq \mid ={C}_{\frac{1}{2}}\left[\left(\varnothing \right)=C\left(\varnothing \right)\right]$ , while $C$ is not pre-maximally $\neg$ -paraconsistent iff ${C}_{\left[\frac{1}{2}\right]}$ has no theorem iff $C$ is not weakly disjunctive iff $2\in \mathbf{S}\mathfrak{A}$ iff ${C}^{\left[{R}^{+}\right]}$ “is $\neg$ -subclassical”/”has a consistent non- $\neg$ -paraconsistent extension” iff ${C}_{\frac{1}{2}\mid }$ is not maximally $\mid$ pre-maximally consistent iff ${C}_{\frac{1}{2}}\ne {C}^{R^{+}}$ iff ${C}_{\frac{1}{2}}$ is not the only proper [ $\neg$ -para]consistent extension of $C$ , in which case proper $\neg$ -paraconsistent both extensions/sublogics of ${C}_{/\frac{1}{2}}$ are exactly $\mid$ “ $\neg$ -subclassical $\neg$ -paraconsistent” extensions of ${C}^{R^{+}}$ “with models $\mathcal{A}\upharpoonright 2$ and ${\mathcal{A}}_{\frac{1}{2}}$ “ $\mid$ , whereas $C$ is almost pre-maximally $\neg$ -paraconsistent iff ${C}^{R^{+}}\parallel$ there is a unique proper “both $\neg$ -paraconsistent/-subclassical extension” $\mid$ “ $\neg$ -paraconsistent both extension/sublogic” of ${C}_{\mid /\frac{1}{2}}$ iff proper $\neg$ -paraconsistent extensions of $C$ are exactly ${C}^{R^{\left[+\right]}}$ iff ${C}^{R^{+}}$ is defined by $\{(\mathcal{A}\upharpoonright 2),{\mathcal{A}}_{\frac{1}{2}}\}$ iff $({\Delta}_A\cup (\{\frac{1}{2}\}\times 2))\in \mathbf{S}{\mathfrak{A}}^2$ and there is no secondary binary connective $\beta$ of $L$ such that $\forall a\in D,\forall b\in \left(2\cdot a\right):{\beta}^{\mathfrak{A}}\left(a,b\right)=\left(1-\left(a\cdot \left(1-b\right)\right)\right)$ , and so $C$ is [/pre-]maximally $\neg$ -paraconsistent, whenever it is weakly conjunctive/”disjunctive (i.e., has a theorem) and [not] $\wr$ -subclassical”.

▸ ALEXEJ PYNKO AND IRA SIRKO, Extensions of paraconsistent three-valued chain logics.

Cybernetics Institute, Glushkov p. 40, Kiev, 03680, Ukraine.

E-mail: [email protected].

Given any propositional language $L$ (viz., a set of primary connectives, treated as operation symbols, when dealing with $L$ -algebras), an $L$ -rule is any expression of the form $\mathrm{\mathcal{R}}=\left(\left[\Gamma \vdash \right]\varphi \right)$ , where $\left[\Gamma \subseteq \right]{\mathrm{Fm}}_L\ni \varphi$ , whereas ${\mathrm{Fm}}_L$ is the set of $L$ -formulas with variables in $V={\left\{{x}_i\right\}}_{i\in \omega }$ — viz. the carrier of the absolutely-free $L$ -algebra ${\mathfrak{Fm}}_L$ freely-generated by $V$ , natural numbers, including $0$ , being treated as sets of lesser ones, the set of all them being denoted by $\omega$ , while $\neg \mid \wedge /\vee \supset$ is a $\left(1|2\right)$ -ary prefix $\mid$ infix connective of $L$ (possibly, a secondary one — viz., an $L$ -formula with variables in ${\left\{{x}_j\right\}}_{j\in \left(1|2\right)}$ ). Then, an $L$ -logic $C$ (viz., a structural closure operator over ${\mathrm{Fm}}_L$ — i.e., with $\mathrm{img}C$ closed under inverse endomorphisms of ${\mathfrak{Fm}}_L$ ) is said to “satisfy $\mathrm{\mathcal{R}}$ “ $\mid$ “be [ $\neg$ -para]consistent”, if $(\varphi|x_1)\in|\not\in C(\varnothing[\cup(\Gamma|\{x_0,\neg x_0\})])$ , an extension of $C$ (viz., an $L$ -logic ${C}^{\prime }$ with $\left(\mathrm{img}{C}^{\prime}\right)\subseteq \left(\mathrm{img}C\right)$ ) being said to be proper/”relatively axiomatized by $\mathrm{\mathcal{R}}$ “, if it is “distinct from $C$ “/”the least extension of $C$ satisfying $\mathrm{\mathcal{R}}$ “. Likewise, any $L$ -matrix (viz., a pair $\mathcal{A}=\left\langle \mathfrak{A},D\right\rangle$ , constituted by its underlying $L$ -algebra $\mathfrak{A}$ with carrier $A$ , consisting of its values, and the set $D\subseteq A$ of its distinguished values) defines its logic ${\mathrm{Cn}}_{\mathcal{A}}$ such that $\{{h}^{-1}\left[D\right]|h\in \hom \left({\mathfrak{Fm}}_L,\mathfrak{A}\right)\}$ is a closure basis of ${\mathrm{imgCn}}_{\mathcal{A}}$ , as well as said to be $\neg$ -classical $\mid\ \supset$ -implicative, if “it has exactly $2\left[-1\right]$ [distinguished] values, while ${\neg}^{\mathfrak{A}}$ permutes its unique distinguished and non-distinguished values” $\mid \forall a,b\in A:\left(\left(a\in D\right)\Rightarrow \left(b\in D\right)\right)\iff ((a{\supset}^{\mathfrak{A}}b)\in D)$ . Then, $C$ is said to be $\neg$ -classical $\mid\ \supset$ -implicative, if “it is defined by a $\neg$ -classical $L$ -matrix, in which case it is consistent but not $\neg$ -paraconsistent” $\mid \forall \Delta \subseteq {\mathrm{Fm}}_L,\forall \phi, \psi \in {\mathrm{Fm}}_L:\left(\psi \in C\left(\Delta \cup \left\{\phi \right\}\right)\right)\iff \left(\left(\phi \supset \psi \right)\in C\left(\Delta \right)\right)$ , $L$ -logics with $\neg$ -classical extensions being referred to as $\neg$ -subclassical.

Theorem 1. Let $\mathfrak{A}$ be an $L$ -algebra with carrier $A\triangleq (2\cup \{\frac{1}{2}\})$ , $a\triangleq {\neg}^{\mathfrak{A}}\frac{1}{2}$ , $b\in \left\{a,1\right\}$ , $D\subseteq \left(A\backslash 1\right)$ and $\mathcal{A}\triangleq \left\langle \mathfrak{A},D\right\rangle$ . Suppose $1\in D$ , while [the least subalgebra of] $\langle A,{\wedge}^{\mathfrak{A}},{\vee}^{\mathfrak{A}},0,b[+\left(1-b\right),{\neg}^{\mathfrak{A}}]\rangle$ is a [complemented] bounded lattice, whereas ${\mathrm{Cn}}_{\mathcal{A}}$ is both $\neg$ -paraconsistent (i.e., $\{\frac{1}{2},a\}\subseteq D$ ) and {not} non- $\neg$ -subclassical (i.e., the subalgebra of $\mathfrak{A}$ generated by $2$ does {not} contain $\frac{1}{2}$ ) $\langle$ as well as $\supset$ -implicative (i.e., $\mathcal{A}$ is so) $\rangle$ . Then, ${\mathrm{Cn}}_{\mathcal{A}}$ has no consistent proper extension {other than ${\mathrm{Cn}}_{\left(\mathcal{A}\upharpoonright 2\right)/\left(\mathcal{A}\times \left(\mathcal{A}\upharpoonright 2\right)\right)}$ relatively axiomatized by $(((\{x_0\lceil\lor x_1\rceil,\ \neg x_0\lor x_1\}|\{x_0\lor x_1,\ \neg x_0\})/\{x_0,\neg x_0\})\ {\vdash}\ ([\neg\neg x_0\lor] x_1)/([\lfloor x_1\lor\rfloor\neg\neg] x_{1[-1]}))\langle\| \neg x_0\supset|||\vdash(x_0\supset([\neg\neg] x_{1[-1]}))/\rangle$ [unless $a=\frac{1}{2}$ ], in which case the former is a $\neg$ -classical proper extension of the latter, and so the latter is not $\neg$ -classical, while ${\mathrm{Cn}}_{\mathcal{A}}\left(\varnothing \right)={\mathrm{Cn}}_{\mathcal{A}\times \left(\mathcal{A}\upharpoonright 2\right)}\left(\varnothing \right)$ , whereas ${\mathrm{Cn}}_{\mathcal{A}}\left(\varnothing \right)\ne {\mathrm{Cn}}_{\mathcal{A}\upharpoonright 2}\left(\varnothing \right)$ iff $\mathcal{A}//{\mathrm{Cn}}_{\mathcal{A}}$ is implicative iff $\left\{\left\langle i,i\right\rangle |i\in 2\right\}\cup \left(\left\{\frac{1}{2}\right\}\times \left(\frac{1}{a}\right)\right)$ does not form a subalgebra of ${\mathfrak{A}}^2$ iff either $b=\frac{1}{2}$ or $\mathfrak{A}$ has a (dual) discriminator}.

This covers arbitrary three-valued expansions of “the logic of paradox $LP$ ”/“Hałkowska-Zajac’ logic $HZ$ ” (with $a=\frac{1}{2}$ and $b=\left(1/\frac{1}{2}\right)$ /“as well as secondary binary connectives $\neg {x}_0\left(\vee |\wedge \right)\neg {x}_1$ for primary ones $\wedge \mid \vee$ ”) and the $\neg$ -paraconsistent counterpart of the implication-less fragment of Gödel’s three-valued logic resulted from leaving non-distinguished $0$ alone and taking dual pseudo-complement for pseudo-complement, in which case $\left(a|b\right)=1$ , thus subsuming results originally proved by Pynko ad hoc.