Bi-Weekly Talk: Richard Wilke: The Presburger fragment of logics with multiteam semantics

Wednesday, July 15, 2020, 10:30am

Location: Online session

Speaker: Richard Wilke

 

The Presburger fragment of logics with multiteam semantics

Abstract:

Team semantics is the mathematical basis of modern logics of dependence and independence.
In contrast to classical Tarski semantics, a formula is evaluated not for a single assignment
of values to the free variables, but on a set of such assignments,  called a team.
Team semantics is appropriate for a purely logical understanding of dependency notions,
where only the presence or absence of data matters, but based on sets, it does not take into account
multiple occurrences of data values. It is therefore insufficient in scenarios where such multiplicities
matter, in particular for reasoning about probabilities and statistical independencies.

We obtain insights about the expressive power of logics with multiteam semantics by comparing
them to a variant of existential second-order logic for a specific class of metafinite structures
whose numeric sort is the standard arithmetic on natural numbers with multiset summation.
In particular, multiteam inclusion-exclusion logic is in a precise sense equivalent to the Presburger
fragment of this second-order logic, that is the fragment using only summation operators.
Further, we explore other notions of dependency in this context such as forking and independence.
Interestingly, in (set based) team semantics independence logic is equally expressive to
inclusion-exclusion logic or existential second-order logic, while in multiteam semantics any
combination of properties that are downwards closed or union closed fails to express independence.