An existential fragment of second order logic (Q1306791)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1348043
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An existential fragment of second order logic |
scientific article; zbMATH DE number 1348043 |
Statements
An existential fragment of second order logic (English)
0 references
15 May 2000
0 references
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.
0 references
decidability
0 references
finite structure
0 references
finite submodel property
0 references
non-definability
0 references
second-order logic
0 references
Ramsey theory
0 references
finite-variable fragments
0 references
finite satisfiability
0 references
0.7798231840133667
0 references
0.7637852430343628
0 references
0.7548540234565735
0 references
0.7384312152862549
0 references
0.7339683771133423
0 references
