Logic Colloquium 2024

Contributed Talk

Contributed Talks 14

Chair: Luca San Mauro

  Thursday, 17:30, J336 ! Live

Talks in this session


Ellen Hammatt, The punctual degrees of linear orders

In 2017, Kalimullin, Melnikov and Ng initiated the systematic study of the primitive recursive content of mathematics. The main idea of such studies is eliminating unbounded search from various abstract algorithms in computable structure theory. The main definition in the theory of punctual structures is the following. An algebraic structure is punctual (or fully primitive recursive) if its domain is the set of natural numbers and the operations and relations are represented by primitive recursive functions. An instance of this is called a punctual presentation.

In computable structure theory, computable presentations are viewed up to computable isomorphism. In the punctual setting, this is no longer straightforward due to the fact that the inverse of a primitive recursive bijection does not need to be primitive recursive. We notice that this induces a natural partial order on punctual presentation. This partial order induces a degree structure on all punctual presentations \(\mathcal{M}\) which we call the punctual degrees of \(\mathcal{M}\) and denote \(PR(\mathcal{M})\).

We study the properties of the punctual degrees for linear orders. In [1], we showed that the punctual degrees of \((\mathbb{Z},<)\) is dense. In contrast, Koh, Melnikov and Ng [2] have recently proven that the punctual degrees of \(\mathbb{Q}\) is not dense.

We study this further investigating whether we can embed the atomless Boolean algebra into the punctual degrees for linear orders. The first step towards this is to build a diamond, where we construct presentations \(A,B,C,D\) so that \(C\) and \(D\) are incomparable, \(A=\inf(C,D)\) and \(B=\sup(C,D)\). We will discuss the complications and techniques required to embed the diamond and atomless Boolean algebra in the punctual degrees of rigid linear orders and the rational numbers. All work presented is joint work with Dorzhieva.


  1. Koh, Heer Tern and Melnikov, Alexander and Ng, Keng Meng, A non-density aspect of the rationals, to appear.
  2. Dorzhieva, Marina and Downey, Rod and Hammatt, Ellen and Melnikov, Alexander and Ng, Keng Meng, Punctually presented structures II: comparing presentations, to appear.

Hsing-Chien Tsai, Atomicity under non-transitive mereology

The non-transitive mereology (NTM) to be addressed in this talk is axiomatized by the following axioms and axiom schema (\(Oxy=\exists z(Pzx\land Pzy)\)).

  • (P1: reflexivity) \(\forall xPxx\)
  • (P2: anti-symmetry) \(\forall x\forall y((Pxy\land Pyx)\to x=y)\)
  • (SSP: strong supplementation) \(\forall x\forall y(\neg Pyx\to\exists z(Pzy\land\neg Ozx))\)
  • (UF: unrestricted fusion principle) \(\exists x\alpha(x)\to\exists z\forall y(Oyz\leftrightarrow\exists x(\alpha(x)\land Oyx))\), for any formula \(\alpha(x)\) where z and y do not occur free.

Note that we will get the so-called General Extensional Mereology (GEM) if we add the transitivity axiom: \(\forall x\forall y\forall z((Pxy\land Pyz)\to Pxz)\) to the foregoing list.

In this talk, the following four definitions of atomicity will be considered where \(Atom(x)=\forall y(Pyx\to x=y)\).

  • A0(x)=\(\forall y(Pyx\to\exists u(Atom(u)\land Puy))\)
  • A1(x)=\(\forall y(Pyx\to\exists u(Atom(u)\land Puy\land Pux))\)
  • A2(x)=\(\forall y(Pyx\to(A1(y)\land\exists u(Puy\land Atom(u)\land Pux))\)
  • A3(x)=\(\forall y(Pyx\to\exists u(Atom(u)\land Puy\land\forall u((Atom(u)\land Puy)\to Pux)))\)

It is easy to see that all of these definitions are equivalent under GEM. But we will show that some pairs of them are not equivalent under NTM. Furthermore, we will also show that NTM+\(\forall xA3(x)\) is equivalent to GEM+\(\forall xA0(x)\) (hence to GEM+\(\forall xAi(x)\), where i=0 to 3). Such a result means that we won’t get any stronger atomic theory even if we define an atomicity predicate finer than A3(x).


Davide Sutto, A History of Level Theories: From Ranks to Levels.

The paper presents a comprehensive history of the formalizations of the Iterative Conception of Set. First, I show how the core idea originated, even before Zermelo’s \(V_\alpha\)s, in reflections on ranks appearing in Mirimanoff’s 1910s contributions and earlier notes by German mathematicians. Second, I emphasize the seminal role played by Tarski’s School in developing the notion of rank and further argue that the actual genesis of the conception is to be found in Tarski’s 1950s set theory seminars, later developed in [2] and [3]. Third, I focus on the crucial passage from the notion of rank to its more explicit characterization: levels. In the work of Tarski’s School we can find the first formulations of axiomatic theories of levels in purely set theoretic terms. This is relevant as I move forward to Shoenfield and Boolos, who rather outline stage theories, adopting stages as a further primitive. Finally, I close with the more recent contributions of Potter and Button, who revitalized the notion of level by making it more tractable.


  1. T. Button,Level Theory, Part 1: Axiomatizing the Bare Idea of a Cumula- tive Hierarchy of Sets,Bulletin of Symbolic Logic,vol. 27 (2022), no. 4, pp. 436–460.
  2. R. Montague, D. Scott, A. Tarski,An Axiomatic Approach to Set Theory,North Holland Publishing Co.,Unpublished [Archive Copy from the Bancroft Library: Alfred Tarski Papers, circa 1923-1985 (BANC MSS 84/69 c, Carton 4, Folder 29-30)].
  3. D. Scott,Axiomatizing Set Theory,Proceedings of Symposia in Pure Mathematics(UCLA, July 10-August 5, 1967),(Thomas J. Jech),vol. XIII, part II,American Mathematical Society,1974,pp. 207–214.

 Overview  Program