Intuitionistic Implication in Elementary Team Logics

Abstract

The logic FOT is a team-based logic whose expressive power coincides with first-order logic at the level of both sentences and open formulas. In contrast to dependence and independence logics, which can define stronger second-order team properties, FOT is designed to capture exactly elementary team properties, modulo the empty team. In this paper we consider two modifications of FOT. First, we investigate essentially the inclusion atom free fragment of FOT. Our main result establishes quantifier elimination for the fragment in the empty signature. Second, we study an extension of FOT by the intuitionistic implication. The main conclusion is that adding this single connective increases the expressive strength so that every second-order sentence can be encoded by an open formula evaluated on the full team. Consequently, validity of formulas is equivalent to validity of full second-order logic.