2013/05/31 by Pietro Galliani
Mathematics · Computer Science · #math.LO #cs.LO
paper · pdf · doi:10.4204/eptcs.119.10
published as EPTCS 119, 2013, pp. 93-106 · In Proceedings GandALF 2013, arXiv:1307.4162
arxiv created 2013/07/17 · arxiv updated 2013/07/18
We prove that adding upwards closed first-order dependency atoms to first-order logic with team semantics does not increase its expressive power (with respect to sentences), and that the same remains true if we also add constancy atoms. As a consequence, the negations of functional dependence, conditional independence, inclusion and exclusion atoms can all be added to first-order logic without increasing its expressive power. Furthermore, we define a class of bounded upwards closed dependencies and we prove that unbounded dependencies cannot be defined in terms of bounded ones.