A counterexample to the 0-1 law for the class of existential second-order minimal Gödel sentences with equality
type: Item
instance of: scholarly article
title: A counterexample to the 0-1 law for the class of existential second-order minimal Gödel sentences with equality
zbMATH Open document ID: 0803.03016
author: Leszek Pacholski
author: Wiesław Szwast
published in: Information and Computation
publication date: 1994-03-24T00:00:00Z
review text: It is shown that the 0-1 law fails for the class of existential second- order sentences whose first-order part is of the form \(\forall x\forall y\exists z\varphi(x,y,z)\) with quantifier-free \(\varphi\). This result completes the characterization of the classes of existential second-order sentences according to its first-order quantifier prefix, for which the 0-1 law holds. It coincides with the characterization of the solvable cases of the decision problem.
reviewed by: Jörg Flum
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03B15
zbMATH DE Number: 529887
zbMATH Keywords: 0-1 law
zbMATH Keywords: existential second-order sentences
MaRDI profile type: Publication
full work available at URL: inco.1993.1062
OpenAlex ID: W2082513803
Wikidata QID: Q124830017
DOI: 10.1006/INCO.1993.1062
description: scientific article; zbMATH DE number 529887