Absoluteness, stability, and quantifier complexity in model theory

拉斯科夫斯基正在继续他的模型理论研究，这是数理逻辑的一个分支。国际和平研究所的研究有三个方面。众所周知，几乎所有一阶模型理论的基本概念都是绝对的，也就是说，它们的解释不会随着人们所使用的集合论模型而改变。众所周知，对于无限语言中的类似概念，情况要复杂得多，在这些语言中，即使是像权力中的直接性这样的简单概念也不可能是绝对的，即使对于基数保持强制也是如此。几年前，人们注意到，如果一个人对一个理论施加了极强的稳定性理论条件，那么这些条件就限制了该理论任何模型的基本图的量词复杂性。这些界限立即给出了此类理论的可定义子集的可计算复杂性的上界。有限集上类型可定义性的模型理论概念与计算学习理论中的压缩方案概念密切相关。这种联系在两个方向上都取得了丰硕成果。已经确定了许多假设压缩方案的概念类的例子，相反，这种联系导致了对依赖理论的更深层次的模型理论的理解。模型理论关注的是理论之间的相互作用，即非常形式化语言中的句子集，以及满足这些句子的代数结构(模型)的类。有一个完善的理论分类，它基于某些元素配置在理论模型中的可嵌入性或不可嵌入性。Laskowski已经确定了与数据压缩和计算学习理论的局限性有直接联系的某些理论类别，并将继续他对这些理论的检验。

Laskowski is continuing his research in model theory, which is a branch of mathematical logic. The PI's research is in three areas. It is well known that almost all of the basic notions of first-order model theory are absolute, i.e., their interpretation does not change depending on the model of set theory one is working in. The situation is known to be much more complicated for similar concepts in infinitary languages, where even simple concepts such as categoricity in power can fail to be absolute, even for cardinal preserving forcings. A few years ago, it was noted that if one places extremely strong stability theoretic conditions on a theory, then these conditions limit the quantifier complexity of the elementary diagram of any model of the theory. These bounds immediately give upper bounds on the computable complexity of definable subsets of such a theory. The model theoretic notion of definability of types over finite sets is intimately related to the notion of a compression scheme in computational learning theory. This connection has beein fruitful in both directions. A number of examples of concept classes that posess compression schemes have been identified, and conversely this connection has led to a deeper model theoretic understanding of dependent theories.Model theory is concerned with the interplay between theories, i.e., sets of sentences in a very formal language, and the classes of algebraic structures (models) that satisfy these sentences. There is a well established taxonomy of theories, which is based on the embeddability or non-embeddability of certain configurations of elements into models of the theory. Laskowski has identified certain classes of theories that have direct connections to limitations on data compression and computational learning theory, and will continue his examination of these theories.