February 27, 20260 citationsOpen Access

Random Models and Guarded Logic

Q: What does this research mean for the field?

The Guarded Fragment of First-Order Logic has a finite model property with an optimal doubly-exponential upper bound on the size of minimal models. Novelty: ClaimNovelty.NOVEL_FINDING. Consensus alignment: ConsensusAlignment.NEUTRAL.

OFOskar Fiuk

Key Points

This work aims to establish a probabilistic proof of the finite model property for the Guarded Fragment of First-Order Logic.
Developed a probabilistic proof for the finite model property.
Analyzed the size of minimal models, achieving a doubly-exponential upper bound.
Extended the approach to the Triguarded Fragment.
Derandomized the proof using deterministic hash functions.
Achieved optimal bounds on the sizes of minimal models.
Constructed sentences enforcing models of specific sizes.
Established that the probabilistic method leads to a deterministic model construction.

Abstract

Building on ideas of Gurevich and Shelah for the Gödel Class, we present a new probabilistic proof of the finite model property for the Guarded Fragment of First-Order Logic. Our proof is conceptually simple and yields the optimal doubly-exponential upper bound on the size of minimal models. We precisely analyse the obtained bound, up to constant factors in the exponents, and construct sentences that enforce models of tightly matching size. The probabilistic approach adapts naturally to the Triguarded Fragment, an extension of the Guarded Fragment that also subsumes the Two-Variable Fragment. Finally, we derandomise the probabilistic proof by providing an explicit model construction which replaces randomness with deterministic hash functions.

Ask AI

Helpful

Bookmark

View Full Paper