A note on hereditarily Π10- and Σ10-complete sets of sentences

DOI10.1093/LOGCOM/EXU066zbMath1401.03072OpenAlexW2417369165MaRDI QIDQ2957964

Stanislav O. Speranski

Publication date: 31 January 2017

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/logcom/exu066

zbMATH Keywords

elementary definabilityhereditary undecidabilityeffective inseparabilitycomputable inseparabilityhereditary \(\Pi_1^0\)-completenesshereditary \(\Sigma_1^0\)-completeness

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Related Items (3)

Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ Computational complexity of theories of a binary predicate with a small number of variables ⋮ Elementary theories and hereditary undecidability for semilattices of numberings

This page was built for publication: A note on hereditarily Π10- and Σ10-complete sets of sentences