1. Team Logic and Second-Order Logic
- Author
-
Ville Nurmi and Juha Kontinen
- Subjects
Algebra and Number Theory ,Computer science ,Second-order logic ,010102 general mathematics ,06 humanities and the arts ,0603 philosophy, ethics and religion ,16. Peace & justice ,01 natural sciences ,Dependence logic ,Theoretical Computer Science ,Algebra ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Computational Theory and Mathematics ,Negation ,Fragment (logic) ,Computer Science::Logic in Computer Science ,060302 philosophy ,0101 mathematics ,Hardware_LOGICDESIGN ,Information Systems - Abstract
Team logic is a new logic, introduced by Vaananen [12], extending dependence logic by classical negation. Dependence logic adds to first-order logic atomic formulas expressing functional dependence of variables on each other. It is known that on the level of sentences dependence logic and team logic are equivalent with existential second-order logic and full second-order logic, respectively. In this article we show that, in a sense that we make explicit, team logic and second-order logic are also equivalent with respect to open formulas. A similar earlier result relating open formulas of dependence logic to the negative fragment of existential second-order logic was proved in [8].
- Published
- 2011
- Full Text
- View/download PDF