Abstract

Independence-friendly logic is a conservative extension of first-order logic that has the same expressive power as existential second-order logic. We attempt to algebraize IF logic in the same spirit as cylindric algebra. We define independence-friendly cylindric set algebras and investigate to what extent they satisfy the axioms of cylindric algebra. We ask whether the equational theory of IF algebras is finitely axiomatizable, and prove two partial results. First, every IF algebra over a structure is an expansion of a Kleene algebra. Moreover, the class of such Kleene algebras generates the variety of all Kleene algebras. Second, every one-dimensional IF algebra over a structure is an expansion of a monadic Kleene algebra. However, the class of such monadic Kleene algebras does not generate the variety of all monadic Kleene algebras