Computable Numberings of Families of Infinite Sets

Research output: Contribution to journalArticlepeer-review

Abstract

We state the following results: the family of all infinite computably enumerable sets has no computable numbering; the family of all infinite Π11 sets has no Π11 -computable numbering; the family of all infinite Σ21 sets has no Σ21 -computable numbering. For k > 2, the existence of a Σk1 -computable numbering for the family of all infinite Σk1 sets leads to the inconsistency of ZF.

Original languageEnglish
Pages (from-to)224-231
Number of pages8
JournalAlgebra and Logic
Volume58
Issue number3
DOIs
Publication statusPublished - 1 Jul 2019

Keywords

  • analytical hierarchy
  • computability
  • computable numberings
  • Friedberg numbering
  • Gödel’s axiom of constructibility
  • Godel's axiom of constructibility
  • AXIOM

Fingerprint Dive into the research topics of 'Computable Numberings of Families of Infinite Sets'. Together they form a unique fingerprint.

Cite this