Revision #715 → #1020 · back to history
addedArithmetical hierarchy1d0eb24b5af3
addedArithmetical set6cff4c3b6071
addedBounded-quantifier formula classificationef05b3edbeb0
addedInductive classifications Σn and Πn for formulas8c6b049c18cc
addedΣn/Πn quantifier alternation formaf3c73d95136
addedEvery formula receives a classification445c942b9952
addedSet defined by a formulafe8d4be8fe33
addedDefinable in first-order arithmeticbac527490521
addedClassifications Σn, Πn, Δn of sets14c4e07599b4
addedOdd natural numbers37fceb330976
addedArithmetical hierarchy on k-tuples171116037233
addedMeaning of subscript n2c224383e815
addedMeaning of superscript (type)71ae8079048e
addedΣ1 sets are recursively enumerable17b1323216b6
addedIndices of total Turing machines are Π2194a6237ff37
addedEffectively open and effectively closed sets456f703e074d
addedArithmetical sets are Borel2bad2ec8b8be
addedBounded-quantifier formulas decidable in E60cd211706a0
addedAlternative definition with primitive recursive functionsb49e6247ac88
addedRelativized arithmetical hierarchy63626f5e1d83
addedNumbers divisible by an element of Y6ec6abd53a23
addedArithmetical reducibility9b8678d85c43
addedArithmetical set / arithmetical in Y2270848a8fe2
addedArithmetic degreesf025a0b5b198
addedCantor space and Baire space1579bf098242
addedClassification of subsets of Cantor space17f02b2ab77e
addedNon-empty sets of natural numbers as Σ1 subset of Cantor space1f544bd70a4f
addedTwo hierarchies on Cantor space differ16a1c16f639b
addedArithmetical hierarchy on Baire space via Cantor correspondence2161ad298004
addedFunctional second-order definition on Baire space87b89c3a3f03
addedHierarchy on Cartesian powers and effective Polish spacesf9cfc0fb7ad8
addedBoldface arithmetic hierarchy = Borel hierarchy2aae073040ca
addedHierarchy with primitive recursive function symbolsa7d3f00fbbb0
addedSemantic hierarchy on finitary relations16e20c9c49e5
addedClosure under finite unions and intersections31f9c0834a7a
addedComplement and Δn characterizationda322f3e45fe
addedStrict inclusions; hierarchy does not collapse8b21426ed28e
addedInclusions Σn, Πn ⊆ Δn+1d051c10aa7f7
addedHalts-on-n-not-on-m pair seta33ae35b6dcb
addedComputable sets are recursively enumerable with r.e. complement6afb59fb00e2
addedComputable sets are Δ16eafd04153fd
addedΔ1 sets are computable36b185244d6c
addedTuring computable = Δ1; r.e. = Σ16094921d76fd
addedHalting problem for oracle10aa31d2a6b0
addedPost's theoremc6538cc248e9
addedPolynomial hierarchy as resource-bounded analogeb9a0fd7377e