Dimension in team semantics

Lauri Hella, Kerkko Luosto, Jouko Väänänen

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We introduce three measures of complexity for families of sets. Each of the three measures, which 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 behavior 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. To this end we associate each atom with a natural notion or arity. 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.

Original languageEnglish
JournalMATHEMATICAL STRUCTURES IN COMPUTER SCIENCE
DOIs
Publication statusE-pub ahead of print - 2024
Publication typeA1 Journal article-refereed

Keywords

  • dependence logic
  • dimension
  • growth class
  • team semantics

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Mathematics (miscellaneous)
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Dimension in team semantics'. Together they form a unique fingerprint.

Cite this