On definability of team relations with k-invariant atoms

Research output: Contribution to journalArticleScientificpeer-review


We study the expressive power of logics whose truth is defined over sets of assignments, called teams, instead of single assignments. Given a team X, any k-tuple of variables in the domain of X defines a corresponding k-ary team relation. Thus the expressive power of a logic L with team semantics amounts to the set of properties of team relations which L-formulas can define. We introduce a concept of k-invariance which is a natural semantic restriction on any atomic formulae with team semantics. Then we develop a novel proof method to show that, if L is an extension of FO with any k-invariant atoms, then there are such properties of (k+1)-ary team relations which cannot be defined in L. This method can be applied e.g. for arity fragments of various logics with team semantics to prove undefinability results. In particular, we make some interesting observations on the definability of binary team relations with unary inclusion-exclusion logic.

Original languageEnglish
Article number103136
Issue number10
Early online date2022
Publication statusPublished - Dec 2022
Publication typeA1 Journal article-refereed


  • Arity fragments
  • Expressive power
  • Inclusion-exclusion logic
  • Proof techniques
  • Team semantics
  • Undefinability results

Publication forum classification

  • Publication forum level 2

ASJC Scopus subject areas

  • Logic


Dive into the research topics of 'On definability of team relations with k-invariant atoms'. Together they form a unique fingerprint.

Cite this