2019/02/28 by Pietro Galliani
Computer Science · Mathematics · Psychology · #Advanced Algebra and Logic #Algebra over a field #Dependency (UML) #Description logic #Expressive power #First order #First-order logic #Logic, Reasoning, and Knowledge #Order (exchange) #Philosophy and Theoretical Science #Semantics (computer science) #math.LO
paper · pdf · doi:10.4204/eptcs.305.5
published as EPTCS 305, 2019, pp. 66-82 · In Proceedings GandALF 2019, arXiv:1909.05979
openalex created_date 2019/03/02 · openalex publication_date 2019/09/12 · arxiv created 2019/09/18 · arxiv updated 2019/09/19 · openalex updated_date 2026/08/06
Team Semantics generalizes Tarski's Semantics for First Order Logic by allowing formulas to be satisfied or not satisfied by sets of assignments rather than by single assignments. Because of this, in Team Semantics it is possible to extend the language of First Order Logic via new types of atomic formulas that express dependencies between different assignments. Some of these extensions are much more expressive than First Order Logic proper; but the problem of which atoms can instead be added to First Order Logic without increasing its expressive power is still unsolved. In this work, I provide an answer to this question under the additional assumptions (true of most atoms studied so far) that the dependency atoms are relativizable and non-jumping. Furthermore, I show that the global (or Boolean) disjunction connective can be added to any strongly first order family of dependencies without increasing the expressive power, but that the same is not true in general for non strongly first order dependencies.