An existential fragment of second order logic

DOI10.1007/S001530050126MaRDI QIDQ1306791zbMATH OpenOpenAlexFDO

Authors Eric Rosen

Publication date 15 May 2000

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001530050126

zbMATH Keywords

decidabilityfinite satisfiabilityfinite structurefinite submodel propertyfinite-variable fragmentsnon-definabilityRamsey theorysecond-order logic

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13) Second- and higher-order model theory (03C85) Descriptive complexity and finite models (68Q19)

Review text

The author deals with the set SO(\(\exists\)) of those second-order sentences in a finite relational signature, whose quantifier prefix is an arbitrary string of second-order quantifiers followed by a string of existential first-order quantifiers. This fragment of second-order logic is shown to be decidable with respect to finite satisfiability; some other model-theoretic properties of it (compactness, finite submodel property) are also discussed. Using Ramsey theory in a somewhat unusual context, the author obtains a few non-definability results for SO(\(\exists\)). At last a hierarchy of finite-variable fragments of SO(\(\exists\)) is examined.

Recommendations

• Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable
• Existential second-order logic over strings
• 0-1 laws and decision problems for fragments of second-order logic
• Existential Fixed-Point Logic as a Fragment of Second-Order Logic
• On the expressiveness of frame satisfiability and fragments of second-order logic

Cited in

(6)

• Verification of relational transducers for electronic commerce
• Existential Fixed-Point Logic as a Fragment of Second-Order Logic
• Existential second-order logic over strings
• Expressivity within second-order transitive-closure logic
• Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable
• Synthesising programs with non-trivial constants

This page was built for publication: An existential fragment of second order logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306791)