Partial collapses of the Σ1 complexity hierarchy in models for fragments of bounded arithmetic

Autor:	Leszek Aleksander Kołodziejczyk, Zofia Adamowicz
Rok vydání:	2007
Předmět:	Combinatorics Discrete mathematics Bounded arithmetic Hierarchy (mathematics) Logic Analytical hierarchy Construct (python library) Arithmetical hierarchy Mathematics
Zdroj:	Annals of Pure and Applied Logic. 145:91-95
ISSN:	0168-0072
DOI:	10.1016/j.apal.2006.06.002
Popis:	For any n , we construct a model of T 2 n + ¬ exp in which each ∃ s Π n + 1 b formula is equivalent to an ∃ Π n b formula.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::cd56fe221ba1ca1de078f392acda0241 https://doi.org/10.1016/j.apal.2006.06.002 Zobrazit plný text záznamu Full Text from ScienceDirect