Projects

Current

Structural complexity measures for foundational theories.

Project type: WEAVE-Unisono

Project duration: 06.2025-05.2029

Principal Investigator: Mateusz Łełyk (PL), Dino Rossegger (AU)

Funding organization: National Science Centre (NCN), Poland

Host institutions: University of Warsaw, Faculty of Philosophy, Technical University of Vienna

Project description:

Formalizing observations and behavior is an integral part of science that allows us to use scientific methods to study natural phenomena. In mathematics, this is done by formulating axioms in suitable logics, such as first- order logic, which should capture the behavior of a structure or operation one wants to study. However, early results in mathematical logic tell us that this endeavor is bound to fail. It follows from Gödel’s completeness theorem that all but the most trivial axiomatizations, or theories, will have models besides the intended model whose behavior we set out to capture. Consider, for example, Peano arithmetic, the theory supposed to capture mathematics on the natural numbers; It has models with infinite numbers.

How complicated are these models? Can we easily distinguish them from our intended model? Moreover, how complicated is it to describe the elements of the model which exhibit non-intended properties? The novel idea behind our project is to use Scott analysis, which provides a robust mea- sure of structural complexity and is an established tool in descriptive set theory and computable structure theory, to answer such questions formally. The idea behind Scott analysis is to look at formulae in infinitary logic, which uniquely describe the given countable model (up to isomorphism). The complexity of the model is the least rank of a formula which is such an unambiguous character- ization. While Scott analysis has seen much use in the past, it has barely been used in the context of "foundational theories", theories that formalize large parts of everyday mathematics, such as Peano arithmetic, second-order arithmetic, or set theories such as Kripke-Platek or Zermelo-Fraenkel set theory.

This project aims to obtain a thorough analysis of the structural complexity of foundational theo- ries. Special focus will be put on whether foundational theories have "intended" models and how this intendedness can appear. We want to do Scott analysis of theories with foundational character and investigate whether Scott analysis and the use of infinitary logic are suitable to detect the intend- edness of models or other interesting properties of foundational theories. In order to approach this phenomenon at the right level of generality, we introduce the notion of a Scott function which mea- sures how many models of a given complexity the given theory has. Determining the Scott functions for foundational theories is one of the main scientific goals of the project.

Investigations of the questions outlined here will enable us to isolate new properties of first-order theories, such as for example the simplest model property, that will give new meaningful means for classifying foundational and other theories.