Kleene hierarchy

E601581

classification of predicates classification of sets concept in arithmetic hierarchy theory concept in mathematical logic concept in recursion theory hierarchy of definability

The Kleene hierarchy is a classification of sets and predicates in arithmetic and recursion theory based on their definability and complexity, introduced by logician Stephen Kleene.

Try in SPARQL Jump to: Statements Referenced by

Statements (39)

Predicate	Object
instanceOf	classification of predicates ⓘ classification of sets ⓘ concept in arithmetic hierarchy theory ⓘ concept in mathematical logic ⓘ concept in recursion theory ⓘ hierarchy of definability ⓘ
appliesTo	arithmetical predicates ⓘ subsets of natural numbers ⓘ
areaOfApplication	foundations of mathematics ⓘ proof theory ⓘ theory of computation ⓘ
basedOn	arithmetical definability ⓘ complexity of formulas ⓘ quantifier complexity ⓘ
characterizes	complexity of definable predicates over arithmetic ⓘ complexity of definable sets of integers ⓘ
concerns	effective definability ⓘ logical complexity of definitions ⓘ
describes	classification of predicates by definability ⓘ classification of sets by definability ⓘ
field	arithmetical hierarchy NERFINISHED ⓘ mathematical logic ⓘ recursion theory ⓘ
hasLevel	finite levels indexed by natural numbers ⓘ
influenced	classification schemes in descriptive set theory ⓘ later work on hierarchies in recursion theory ⓘ
introducedBy	Stephen Cole Kleene NERFINISHED ⓘ
namedAfter	Stephen Cole Kleene NERFINISHED ⓘ
organizes	predicates by increasing definitional complexity ⓘ sets by increasing definitional complexity ⓘ
relatedTo	Kleene normal form theorem NERFINISHED ⓘ Turing degrees NERFINISHED ⓘ analytical hierarchy ⓘ arithmetical hierarchy NERFINISHED ⓘ effective descriptive set theory ⓘ
usesConcept	arithmetical formula ⓘ partial recursive function ⓘ quantifier alternation ⓘ recursive function ⓘ

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

Stephen Kleene → knownFor → Kleene hierarchy ⓘ

Stephen Kleene → notableConcept → Kleene hierarchy ⓘ