On Preservation Theorems for Two-Variable Logic
Let \(\text{FO}^k\) be the class of first-order formulas in which no more than \(k\) distinct variables appear. These fragments of FO play an important role particularly in finite model theory. The paper proves the following preservation-type results for \(\text{FO}^2\), and explains how they complement the current body of knowledge in the field: 1. There exists a sentence \(\phi\) in \(\text{FO}^2\) with \(\text{Mod}(\phi)\) closed under extensions but not equivalent to any existential \(\text{FO}^2\)-sentence. (This result was previously known for all \(\text{FO}^k\) with \(k\geq 3\).) 2. There is a recursive function \(f\) on \(\text{FO}^2\)-sentences with \(f(\phi)\) an existential \(\text{FO}^2\)-sentence equivalent to \(\phi\) if \(\text{Mod}(\phi)\) is closed under extensions, and \(*\) otherwise. 3. A sentence \(\phi\) in \(\text{FO}^2\) is equivalent to an existential one in FO iff the class of its finite models is closed under extensions. (This is known to be false if \(\text{FO}^2\) is replaced by \(\text{FO}^3\).) 4. A sentence \(\phi\) in \(\text{FO}^2\) is equivalent to a positive-existential \(\text{FO}^2\)-sentence iff the class of its models is closed under homomorphisms. (Whether this is true in the \(\text{FO}^k\)-context for \(k\geq 3\), or, alternatively, in the finite model context, is a well-known open problem).
- Preservation theorems in linear continuous logic
- On logics with two variables
- Two theorems on many-valued logics
- Some characterization and preservation theorems in modal logic
- Logics preserving degrees of truth from varieties of residuated lattices
- Syntactic preservation theorems for intuitionistic predicate logic
- Properties of Intuitionistic Provability and Preservativity Logics
- scientific article; zbMATH DE number 1078559
- Two-variable logic with two order relations (extended abstract)
- Bounded model checking of infinite state systems
- Preservation under substructures modulo bounded cores
- scientific article; zbMATH DE number 6866317 (Why is no real title available?)
- On the Restraining Power of Guards
- Omitting types for finite variable fragments and complete representations of algebras
- A generalization of the Łoś-Tarski preservation theorem
This page was built for publication: On Preservation Theorems for Two-Variable Logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4264532)
