Logic Colloquium 2024

Contributed Talk

Contributed Talks 2

Chair: Ivan Di Liberti

  Tuesday, 16:30, J330 ! Live

Time allocation: 20 minutes per speaker; 5 minutes for each changeover

Talks in this session


Nurlan Markhabatov, On Disintegrated Models

Definition 1. [1] Let \(\mathcal{T}\) be a family of theories and \(T\) be a theory such that \(T\notin \mathcal{T}\). The theory \(T\) is said to be \(\mathcal{T}\)-approximated, or approximated by the family \(\mathcal{T}\), or a pseudo-\(\mathcal{T}\)-theory, if for any formula \(\varphi \in T\) there exists \(T'\in \mathcal{T}\) for which \(\varphi \in T'\).

Definition 2. An infinite model \(\mathcal{M}\) of a \(\mathcal{T}\)-approximated theory \(T\) is called disintegrated if it is a disjoint union of models, \(\mathcal{M}=\bigsqcup_{i\in \omega} \mathcal{M}_i\), where \(\mathcal{M}_i\) is finite (possibly either \(\omega\)-categorical or minimal). Otherwise, \(\mathcal{M}\) is called integrated.

Theorem. Any disintegrated infinite model is pseudofinite.

Theorem. There is an integrated model, which is pseudofinite.

This research was funded by the Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan (Grant No. AP19677451, AP22782938).


  1. S.V. Sudoplatov, Approximations of theories, Siberian Electronic Mathematical Reports, 17, (2020), pp. 715–725. https://doi.org/10.33048/semi.2020.17.049

Katalin Bimbó, Operational semantics for positive relevance logics

The relational semantics for relevance logics that was introduced by Meyer and Routley in the 1970s, utilizes a ternary relation, although it emerged from the idea of an operational semantics (cf. [2]). A binary operation in place of the ternary relation provides a certain simplification; however, the set of prime filters (or prime theories) is not closed under the fusion operation. For an informational interpretation of the semantics, it is desirable to use operations applicable to situations that have less structure than prime theories have. In this talk, I define an operational semantics for the main positive relevance logics \(\mathbf{T_+}\), \(\mathbf{E_+}\) and \(\mathbf{R_+}\), that is, the positive fragments of the logics of ticket entailment, of entailment and of relevant implication. The operational structure for these logics is based on pieces of information and it is augmented with a topology (which is similar to the topology used in [1]). The logics are proved to be sound and complete for these operational semantics.


  1. Bimbó, Katalin, Dual gaggle semantics for entailment, Notre Dame Journal of Formal Logic, vol. 50 (2009), no. 1, pp. 23–41.
  2. Bimbó, Katalin and J. Michael Dunn, The emergence of set-theoretical semantics for relevance logicsaround 1970, Proceedings of the Third Workshop, May 16–17, 2016,Edmonton, Canada, (Bimbó, K. and J. M. Dunn, editors), special issue of the IFCoLog Journal of Logics and theirApplications, vol. 4 (2017), no. 3, pp. 557–589.

Michał Wrocławski, Punctually presentable injective structures

This presentation is based on joint research with Nikolay Bazhenov, Ivan Georgiev, Dariusz Kalociński, Luca San Mauro, and Stefan Vatev (in alphabetical order).

Punctual structure theory considers structures whose domain is \(\mathbb{N}\) and all relations and functions from their signature are uniformly primitive recursive.

In [1] it has been proved that every computable structure of each of the following classes has a punctual presentation: equivalence structures, linear orderings, Boolean algebras and some more. On the other hand, among others, computable torsion abelian groups do not always have a punctual presentation. Punctual equivalence structures were also studied in [2].

We have studied a different type of structures which we call injective structures. They are of the form \((\mathbb{N},f)\) where \(f\) is a unary injective function. An injective function can be decomposed into various orbits, each of which is either a cycle, or constitutes an \(\mathbb{N}\)-chain or a \(\mathbb{Z}\)-chain. A function which can be decomposed into cycles only is called a cyclic function.

We have shown that every computable injective structure which is not cyclic is punctually presentable. So is every computable injective structure which has some cycle length occurring infinitely many times.

When none of these cases occurs, the situation is less clear. We have constructed a computable cyclic injective structure without a punctual presentation. We have also considered the following concept. Suppose that \(f\) is a cyclic function and that \(g: \mathbb{N} \to \mathbb{N}\) is an enumeration of all cycle lengths of \(f\) in which each cycle length is repeated as many times as it appears in \(f\). We have proved several charaterizations tying punctual presentability of \((\mathbb{N},f)\) to computational properties of \(g\).

We have also had success in proving some cases of a theorem which states a connection between instrinsic punctuality of an additional relation on a punctual injective structure and definability of that relation using a certain restricted class of quantifier-free formulas of first-order logic, assuming that a certain effectivness condition is satisfied. This is aimed to lead to a more general punctual version of Ash-Nerode Theorem.


  1. Iskander Kalimullin, Alexander Melnikov, Keng Meng Ng,Algebraic structures computable without delay,Theoretical Computer Science,vol. 674 (2017), pp. 73–98.
  2. Nikolay Bazhenov, Keng Meng Ng, Luca San Mauro, Andrea Sorbi,Primitive recursive equivalence relations and their primitive recursive complexity,Computability,vol. 11 (2022), pp. 187–221.

Ludovico Fusco, Multi-relation Agassiz sums of algebras

Authors: Ludovico Fusco and Francesco Paoli

Płonka sums are a simple yet powerful technique for building new algebras out of semilattice direct systems of algebras of a fixed type. First introduced by J. Płonka [2] in 1967, this construction immediately proved to be essential for the representation of algebras in regular varieties [3]. The aptness of Płonka sums to this purpose can be seen, at the same time, as a shortcoming, since this construction is of little avail outside this particular domain of application.

Remarkably, however, the literature teems with ‘Płonka-type’ constructions used for the representation of algebras in irregular varieties, or in varieties having certain properties stronger than regularity. All these constructions bear striking similarities to Płonka sums, but differ from them in some important respects. Examples include the representation of Polin algebras [4], T. Katriňák and J. Guričan’s representation of pseudocomplemented semilattices [1], or the recently introduced De Morgan-Pł,onka sums [5].

We aim at finding a convenient umbrella under which all these constructions can be subsumed. We introduce a multi-relation variant of G. Grätzer and J. Sichler’s sums over Agassiz systems of algebras (Agassiz sums) [6] that encompasses Płonka sums as a special case. We prove that the above-mentioned representations of Polin algebras and pseudocomplemented semilattices, as well as De Morgan-Płonka sums, can be recast in terms of sums over appropriate bi-relation Agassiz systems. Finally, we investigate the problem as to which identities are preserved by the construction.


  1. Katriňák, T., Guričan, J.,On a new construction of pseudocomplemented semilattices,Algebra Universalis,vol. LXXXII (2021), article no. 54.
  2. Płonka, J.,On a method of construction of abstract algebras,Fundamenta Mathematicae,vol. LXI (1967), no. II, pp. 183–189.
  3. —, On equational classes of abstract algebras defined by regular equations,Fundamenta Mathematicae,vol. LXIV (1969), no. II, pp. 241–247.
  4. Polin, S.V.,Identities in congruence lattices of universal algebras,Matematicheskie Zametki,vol. XXII (1977), no. III, pp. 443–451.
  5. Randriamahazaka, T.,De Morgan-Płonka sums,Studia Logica,forthcoming.
  6. Grätzer, G., Sichler, J.,Agassiz sums of algebras,Colloquium Mathematicum,vol. XXX (1974), no. I, pp. 57–59.

Christian Wurm, Finite Models for Non-Commutative Ambiguity Logics

We speak of ambiguity (in the linguistic sense) if one sign (word, phrase, sentence) has two or more clearly distinct meanings. Recent work on logics with an explicit representation of ambiguity (see [2,3]) has shown that there are two kinds of logics: those who are closed under transitive inference or more generally under the rule (cut), and those which are closed under uniform substitution of atoms. Having both properties (which are both basic requirements of abstract logics in the sense of Tarski) – together with the most basic properties of ambiguity – leads to triviality of the logic.

Moreover, every ambiguity logic comes in two versions: a) with commutative ambiguity (basically, readings can be conceived of as sets), and b) with non-commutative ambiguity (readings can be conceived of as an ordered list). Two ambiguity logics have received a particular interest (in both variants): DAL (introduced in [1], closed under (cut)) and and TAL (see [2], closed under uniform substitution), with their commutative variants cDAL and cTAL. From a semantic point of view, cDAL and cTAL are considerably simpler: there is a straightforward semantics for both based on finite classical models, which allows to prove two key results (for proofs see [1,3]):

  • both cDAL, cTAL are decidable (via Finite Model Property)
  • cDAL is the inner logic of cTAL (The inner logic of a non-transitive logic is roughly speaking its largest transitive fragment.)

In this talk, we pesent a sound and complete semantics with finite models for non-commutative DAL and TAL, which allows to transfer the two results to this case. The models are sets of strings with certain language-theoretic closure properties.


  1. Jan van Eijck, Jan Jaspars,Ambiguity and Reasoning,Manuscript
  2. Christian Wurm,Reasoning with Ambiguity,Journal of Logic, Language and Information,vol.30 (1), pp.139-206.
  3. Christian Wurm,The Family of Ambiguity Logics,Submitted

 Overview  Program