2090:
1683:
1876:
1550:
2187:
1729:
2135:
1045:
2822:
1755:
1815:
92:
1973:
1363:
2527:
2414:
1297:
1223:
990:
858:
425:
272:
2994:
2854:
2251:
631:
522:
2283:
1157:
2962:
2935:
2908:
2881:
2337:
2310:
2217:
1968:
1425:
1258:
1184:
951:
819:
572:
373:
346:
319:
170:
119:
2738:
2710:
2690:
2670:
2647:
2607:
2567:
2547:
2501:
2477:
2457:
2437:
2377:
2357:
1928:
1908:
1325:
1129:
1108:
1088:
1065:
1013:
922:
901:
881:
790:
767:
746:
726:
698:
678:
652:
593:
489:
469:
449:
397:
292:
242:
222:
194:
143:
49:
1229:
Additional connections between recursion theory and Ī± recursion theory can be drawn, although explicit definitions may not have yet been written to formalize them:
2782:
2762:
2627:
2587:
542:
2652:
A problem in Ī±-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible
1558:
3136:
3055:
1827:
1433:
2144:
2824:, the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a
3206:
173:
1699:
2787:
In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on
2387:
2105:
1018:
2790:
1738:
2085:{\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}
1768:
54:
2741:
122:
1330:
3122:
S. G. Simpson, "Degree Theory on
Admissible Ordinals", pp.170--171. Appearing in J. Fenstad, P. Hinman,
2506:
2393:
1263:
1189:
956:
824:
404:
251:
3110:
3068:
2967:
2827:
2222:
1300:
603:
494:
428:
3097:
2256:
1136:
2940:
2913:
2886:
2859:
2315:
2288:
2195:
1933:
1390:
1236:
1162:
929:
797:
550:
351:
324:
297:
148:
29:
2937:
is a level of the Levy hierarchy. More generally, definability of a subset of Ļ over HF with a
97:
2723:
2695:
2675:
2655:
2632:
2592:
2552:
2532:
2486:
2462:
2442:
2422:
2362:
2342:
1913:
1893:
1310:
1114:
1093:
1073:
1050:
998:
907:
886:
866:
775:
752:
731:
711:
683:
663:
637:
578:
474:
454:
434:
382:
277:
227:
207:
179:
128:
34:
705:
25:
17:
3084:
2767:
2747:
2612:
2572:
2480:
2380:
527:
3200:
3020:
3010:
2784:
for the language of second-order arithmetic, that consists of sets of integers.
3026:
3162:
1758:
597:
and play a similar role to the finite numbers in classical recursion theory.
1765:
is recursive. However A being recursive in B is not equivalent to A being
3150:
Embedding
Theorem for the automorphism group of the Ī±-enumeration degrees
1678:{\displaystyle K\subseteq \alpha /A\leftrightarrow \exists H:\exists J:.}
3098:
Inductive
Definitions and Reflecting Properties of Admissible Ordinals
3111:
Proof theory for theories of ordinals - I: recursively Mahlo ordinals
1871:{\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }}
3124:
Generalized
Recursion Theory: Proceedings of the 1972 Oslo Symposium
3028:
An introduction to the fine structure of the constructible hierarchy
3071:, Annals of Mathematical Logic 17 (1979). Accessed 1 January 2023.
3178:(p.152). "Perspectives in Logic", Association for Symbolic Logic.
3139:". Annals of Pure and Applied Logic vol. 160 (2009), pp.310--318.
1545:{\displaystyle K\subseteq A\leftrightarrow \exists H:\exists J:,}
660:
There are also some similar definitions for functions mapping
2964:
formula coincides with its arithmetical definability using a
2182:{\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C}
1327:
recursively enumerable and every member of R is of the form
3056:
Ordinal machines and admissible recursion theory (preprint)
2483:
of cell contents, state, and head position. For admissible
2692:-enumeration degrees embed into the automorphisms of the
2137:
then there exists a regular Ī±-recursively enumerable set
2740:-recursion can be translated into similar results about
3163:
The
Ramified Analytical Hierarchy using Extended Logics
2764:
has with the ramified analytic hierarchy, an analog of
2148:
2109:
1742:
1703:
992:. Like in the case of classical recursion theory, any
2970:
2943:
2916:
2889:
2862:
2830:
2793:
2770:
2750:
2726:
2698:
2678:
2658:
2635:
2615:
2595:
2575:
2555:
2535:
2509:
2489:
2465:
2445:
2425:
2396:
2365:
2345:
2318:
2291:
2259:
2225:
2198:
2147:
2108:
1976:
1936:
1916:
1896:
1830:
1771:
1741:
1702:
1561:
1436:
1393:
1333:
1313:
1266:
1239:
1192:
1165:
1139:
1117:
1096:
1076:
1053:
1021:
1001:
959:
932:
910:
889:
869:
827:
800:
778:
755:
734:
714:
686:
666:
640:
606:
581:
553:
530:
497:
477:
457:
437:
407:
385:
354:
327:
300:
280:
254:
230:
210:
182:
151:
131:
100:
57:
37:
2459:-Turing machines" with a two-symbol tape of length
2102:be Ī±-regular recursively enumerable sets such that
2988:
2956:
2929:
2902:
2875:
2848:
2816:
2776:
2756:
2732:
2704:
2684:
2664:
2641:
2621:
2601:
2581:
2561:
2541:
2521:
2495:
2471:
2451:
2431:
2408:
2371:
2351:
2331:
2304:
2277:
2245:
2211:
2181:
2129:
2084:
1962:
1922:
1902:
1870:
1809:
1749:
1723:
1677:
1544:
1419:
1357:
1319:
1291:
1252:
1217:
1178:
1151:
1123:
1102:
1082:
1059:
1039:
1007:
984:
945:
916:
895:
875:
852:
813:
784:
761:
740:
720:
692:
672:
646:
625:
587:
566:
536:
516:
483:
463:
443:
419:
391:
367:
340:
313:
286:
266:
236:
216:
188:
164:
137:
113:
86:
43:
1910:recursively enumerable and regular. There exist
3137:Ordinal machines and admissible recursion theory
3021:https://projecteuclid.org/euclid.bams/1183541465
244:. These sets are said to have some properties:
3011:https://projecteuclid.org/euclid.pl/1235422631
1878:or in other words if every initial portion of
1724:{\displaystyle \scriptstyle A\leq _{\alpha }B}
2130:{\displaystyle \scriptstyle A<_{\alpha }C}
8:
2629:is the range of a function computable by an
1621:
1603:
1488:
1470:
1352:
1334:
1040:{\displaystyle f:\alpha \rightarrow \alpha }
3079:
3077:
2479:, that at limit computation steps take the
1307:We say R is a reduction procedure if it is
471:-recursively-enumerable. It's of note that
3085:Relatively constructible transitive models
2817:{\displaystyle L_{\omega }={\textrm {HF}}}
2339:denotes the next admissible ordinal above
3100:" (1974), p.30. Accessed 7 February 2023.
2980:
2975:
2969:
2948:
2942:
2921:
2915:
2894:
2888:
2867:
2861:
2840:
2835:
2829:
2808:
2807:
2798:
2792:
2769:
2749:
2725:
2697:
2677:
2657:
2634:
2614:
2594:
2574:
2554:
2534:
2508:
2488:
2464:
2444:
2424:
2395:
2364:
2344:
2323:
2317:
2296:
2290:
2269:
2264:
2258:
2235:
2230:
2224:
2203:
2197:
2169:
2156:
2146:
2117:
2107:
2058:
2048:
2026:
2013:
2000:
1987:
1975:
1954:
1941:
1935:
1915:
1895:
1862:
1829:
1789:
1776:
1770:
1750:{\displaystyle \scriptstyle \varnothing }
1740:
1711:
1701:
1661:
1631:
1571:
1560:
1528:
1498:
1435:
1411:
1398:
1392:
1332:
1312:
1274:
1265:
1244:
1238:
1200:
1191:
1170:
1164:
1138:
1116:
1095:
1075:
1052:
1020:
1000:
967:
958:
937:
931:
909:
888:
868:
835:
826:
805:
799:
777:
754:
733:
713:
685:
665:
639:
611:
605:
580:
558:
552:
529:
502:
496:
476:
456:
436:
406:
384:
359:
353:
332:
326:
305:
299:
279:
253:
229:
209:
181:
156:
150:
130:
105:
99:
75:
62:
56:
36:
3087:(1975, p.165). Accessed 21 October 2021.
3058:(2009, p.315). Accessed October 12, 2021
1810:{\displaystyle \Sigma _{1}(L_{\alpha })}
87:{\displaystyle \Sigma _{1}(L_{\alpha })}
3047:
3017:Recursively Enumerable Sets and Degrees
2035:
1743:
411:
3031:(p.38), North-Holland Publishing, 1974
2744:. This is because of the relationship
2549:-recursive iff it is computable by an
1070:Additionally, a partial function from
1890:Shore's splitting theorem: Let A be
1358:{\displaystyle \langle H,J,K\rangle }
51:. An admissible set is closed under
7:
3165:(2018, p.4). Accessed 8 August 2021.
1299:play a role similar to those of the
2972:
2945:
2918:
2864:
2832:
2522:{\displaystyle A\subseteq \alpha }
2419:A computational interpretation of
2409:{\displaystyle \alpha \to \alpha }
2366:
2261:
2200:
1831:
1773:
1591:
1582:
1458:
1449:
1292:{\displaystyle (L_{\alpha },\in )}
1241:
1218:{\displaystyle (L_{\alpha },\in )}
1167:
1159:such that the function's graph is
985:{\displaystyle (L_{\alpha },\in )}
934:
853:{\displaystyle (L_{\alpha },\in )}
802:
420:{\displaystyle \alpha \setminus A}
302:
267:{\displaystyle A\subseteq \alpha }
59:
14:
2192:Barwise has proved that the sets
1015:-recursively-enumerable function
294:-recursively-enumerable if it is
1427:reduction procedures such that:
348:, possibly with parameters from
2989:{\displaystyle \Sigma _{n}^{0}}
2849:{\displaystyle \Sigma _{1}^{0}}
2246:{\displaystyle L_{\alpha ^{+}}}
491:-recursive sets are members of
3036:Admissible Sets and Structures
2400:
2094:Shore's density theorem: Let
2076:
2064:
1804:
1801:
1795:
1782:
1669:
1600:
1579:
1536:
1467:
1446:
1286:
1267:
1212:
1193:
1031:
979:
960:
847:
828:
81:
68:
1:
2386:There is a generalization of
1383:is said to be Ī±-recursive in
1301:primitive recursive functions
626:{\displaystyle L_{\alpha +1}}
517:{\displaystyle L_{\alpha +1}}
2609:-recursively-enumerable iff
2278:{\displaystyle \Pi _{1}^{1}}
1152:{\displaystyle n\in \omega }
145:is an admissible ordinal if
3069:The Next Admissible Ordinal
2957:{\displaystyle \Sigma _{n}}
2930:{\displaystyle \Sigma _{1}}
2903:{\displaystyle L_{\omega }}
2876:{\displaystyle \Sigma _{1}}
2672:, the automorphisms of the
2332:{\displaystyle \alpha ^{+}}
2305:{\displaystyle L_{\alpha }}
2212:{\displaystyle \Sigma _{1}}
1963:{\displaystyle B_{0},B_{1}}
1420:{\displaystyle R_{0},R_{1}}
1253:{\displaystyle \Delta _{0}}
1179:{\displaystyle \Sigma _{n}}
946:{\displaystyle \Delta _{1}}
814:{\displaystyle \Sigma _{1}}
567:{\displaystyle L_{\alpha }}
368:{\displaystyle L_{\alpha }}
341:{\displaystyle L_{\alpha }}
314:{\displaystyle \Sigma _{1}}
196:is considered to be fixed.
165:{\displaystyle L_{\alpha }}
3223:
3189:Classical Recursion Theory
3152:(p.155), PhD thesis, 2019.
3135:P. Koepke, B. Seyfferth, "
3126:(1974), ISBN 0 7204 22760.
3054:P. Koepke, B. Seyfferth,
2439:-recursion exists, using "
121:denotes a rank of Godel's
224:recursion are subsets of
3191:(1989), theorem IV.3.22.
3019:, Springer Verlag, 1987
3009:, Springer Verlag, 1990
2716:Relationship to analysis
863:A partial function from
204:The objects of study in
174:KripkeāPlatek set theory
114:{\displaystyle L_{\xi }}
3176:Higher Recursion Theory
3096:W. Richter, P. Aczel, "
3007:Higher recursion theory
2742:second-order arithmetic
2733:{\displaystyle \alpha }
2705:{\displaystyle \alpha }
2685:{\displaystyle \alpha }
2665:{\displaystyle \alpha }
2642:{\displaystyle \alpha }
2602:{\displaystyle \alpha }
2562:{\displaystyle \alpha }
2542:{\displaystyle \alpha }
2496:{\displaystyle \alpha }
2472:{\displaystyle \alpha }
2452:{\displaystyle \alpha }
2432:{\displaystyle \alpha }
2372:{\displaystyle \Sigma }
2352:{\displaystyle \alpha }
1930:recursively enumerable
1923:{\displaystyle \alpha }
1903:{\displaystyle \alpha }
1320:{\displaystyle \alpha }
1124:{\displaystyle \alpha }
1103:{\displaystyle \alpha }
1083:{\displaystyle \alpha }
1060:{\displaystyle \alpha }
1008:{\displaystyle \alpha }
917:{\displaystyle \alpha }
896:{\displaystyle \alpha }
876:{\displaystyle \alpha }
785:{\displaystyle \alpha }
769:-recursively-enumerable
762:{\displaystyle \alpha }
741:{\displaystyle \alpha }
721:{\displaystyle \alpha }
693:{\displaystyle \alpha }
673:{\displaystyle \alpha }
647:{\displaystyle \alpha }
588:{\displaystyle \alpha }
484:{\displaystyle \alpha }
464:{\displaystyle \alpha }
444:{\displaystyle \alpha }
392:{\displaystyle \alpha }
287:{\displaystyle \alpha }
237:{\displaystyle \alpha }
217:{\displaystyle \alpha }
189:{\displaystyle \alpha }
138:{\displaystyle \alpha }
123:constructible hierarchy
44:{\displaystyle \alpha }
24:is a generalisation of
2990:
2958:
2931:
2904:
2877:
2850:
2818:
2778:
2758:
2734:
2712:-enumeration degrees.
2706:
2686:
2666:
2643:
2623:
2603:
2583:
2563:
2543:
2523:
2497:
2473:
2453:
2433:
2410:
2373:
2353:
2333:
2306:
2279:
2247:
2213:
2183:
2131:
2086:
1964:
1924:
1904:
1872:
1811:
1751:
1731:. By this definition
1725:
1679:
1546:
1421:
1359:
1321:
1293:
1254:
1219:
1180:
1153:
1133:iff there exists some
1125:
1104:
1084:
1061:
1041:
1009:
986:
947:
918:
897:
877:
854:
815:
786:
763:
742:
722:
694:
674:
648:
627:
589:
568:
538:
518:
485:
465:
445:
421:
393:
369:
342:
315:
288:
268:
238:
218:
190:
166:
139:
115:
88:
45:
2991:
2959:
2932:
2905:
2878:
2851:
2819:
2779:
2759:
2735:
2707:
2687:
2667:
2644:
2624:
2604:
2584:
2569:-Turing machine, and
2564:
2544:
2524:
2498:
2474:
2454:
2434:
2411:
2374:
2354:
2334:
2307:
2280:
2253:are exactly the sets
2248:
2214:
2184:
2132:
2087:
1965:
1925:
1905:
1873:
1812:
1752:
1726:
1680:
1547:
1422:
1360:
1322:
1294:
1255:
1220:
1181:
1154:
1126:
1105:
1085:
1062:
1042:
1010:
987:
948:
919:
898:
878:
855:
816:
787:
764:
743:
723:
695:
675:
649:
628:
590:
569:
539:
519:
486:
466:
446:
422:
394:
370:
343:
316:
289:
269:
239:
219:
191:
167:
140:
116:
89:
46:
3207:Computability theory
2968:
2941:
2914:
2887:
2860:
2828:
2791:
2768:
2748:
2724:
2696:
2676:
2656:
2633:
2613:
2593:
2573:
2553:
2533:
2507:
2487:
2463:
2443:
2423:
2394:
2363:
2343:
2316:
2289:
2257:
2223:
2196:
2145:
2106:
1974:
1934:
1914:
1894:
1828:
1769:
1739:
1700:
1559:
1434:
1391:
1331:
1311:
1264:
1237:
1190:
1163:
1137:
1115:
1094:
1074:
1051:
1019:
999:
957:
930:
908:
887:
867:
825:
798:
776:
753:
732:
712:
684:
664:
638:
604:
579:
551:
528:
495:
475:
455:
435:
405:
383:
352:
325:
298:
278:
252:
228:
208:
180:
149:
129:
98:
55:
35:
2985:
2845:
2388:limit computability
2274:
1886:Work in Ī± recursion
794:, iff its graph is
429:relative complement
176:. In what follows
30:admissible ordinals
2986:
2971:
2954:
2927:
2900:
2873:
2846:
2831:
2814:
2774:
2754:
2730:
2702:
2682:
2662:
2649:-Turing machine.
2639:
2619:
2599:
2579:
2559:
2539:
2519:
2493:
2469:
2449:
2429:
2406:
2369:
2349:
2329:
2302:
2275:
2260:
2243:
2209:
2179:
2178:
2127:
2126:
2082:
1960:
1920:
1900:
1868:
1807:
1747:
1746:
1721:
1720:
1675:
1542:
1417:
1377:are all Ī±-finite.
1355:
1317:
1289:
1250:
1215:
1176:
1149:
1121:
1100:
1080:
1057:
1037:
1005:
982:
943:
914:
893:
873:
850:
811:
792:-partial recursive
782:
759:
738:
718:
690:
670:
644:
623:
585:
564:
534:
514:
481:
461:
441:
417:
389:
375:in the definition.
365:
338:
311:
284:
264:
234:
214:
186:
162:
135:
111:
84:
41:
22:Ī± recursion theory
3083:Srebrny, Marian,
3043:Inline references
3025:Keith J. Devlin,
2856:formula iff it's
2811:
2777:{\displaystyle L}
2757:{\displaystyle L}
2622:{\displaystyle A}
2582:{\displaystyle A}
1761:) if and only if
926:iff its graph is
537:{\displaystyle L}
524:by definition of
94:functions, where
3214:
3192:
3185:
3179:
3172:
3166:
3159:
3153:
3146:
3140:
3133:
3127:
3120:
3114:
3107:
3101:
3094:
3088:
3081:
3072:
3065:
3059:
3052:
2995:
2993:
2992:
2987:
2984:
2979:
2963:
2961:
2960:
2955:
2953:
2952:
2936:
2934:
2933:
2928:
2926:
2925:
2909:
2907:
2906:
2901:
2899:
2898:
2882:
2880:
2879:
2874:
2872:
2871:
2855:
2853:
2852:
2847:
2844:
2839:
2823:
2821:
2820:
2815:
2813:
2812:
2809:
2803:
2802:
2783:
2781:
2780:
2775:
2763:
2761:
2760:
2755:
2739:
2737:
2736:
2731:
2720:Some results in
2711:
2709:
2708:
2703:
2691:
2689:
2688:
2683:
2671:
2669:
2668:
2663:
2648:
2646:
2645:
2640:
2628:
2626:
2625:
2620:
2608:
2606:
2605:
2600:
2588:
2586:
2585:
2580:
2568:
2566:
2565:
2560:
2548:
2546:
2545:
2540:
2528:
2526:
2525:
2520:
2502:
2500:
2499:
2494:
2478:
2476:
2475:
2470:
2458:
2456:
2455:
2450:
2438:
2436:
2435:
2430:
2415:
2413:
2412:
2407:
2378:
2376:
2375:
2370:
2358:
2356:
2355:
2350:
2338:
2336:
2335:
2330:
2328:
2327:
2311:
2309:
2308:
2303:
2301:
2300:
2284:
2282:
2281:
2276:
2273:
2268:
2252:
2250:
2249:
2244:
2242:
2241:
2240:
2239:
2218:
2216:
2215:
2210:
2208:
2207:
2188:
2186:
2185:
2180:
2174:
2173:
2161:
2160:
2136:
2134:
2133:
2128:
2122:
2121:
2091:
2089:
2088:
2083:
2063:
2062:
2053:
2052:
2031:
2030:
2018:
2017:
2005:
2004:
1992:
1991:
1969:
1967:
1966:
1961:
1959:
1958:
1946:
1945:
1929:
1927:
1926:
1921:
1909:
1907:
1906:
1901:
1877:
1875:
1874:
1869:
1867:
1866:
1816:
1814:
1813:
1808:
1794:
1793:
1781:
1780:
1756:
1754:
1753:
1748:
1735:is recursive in
1730:
1728:
1727:
1722:
1716:
1715:
1696:this is written
1692:is recursive in
1684:
1682:
1681:
1676:
1665:
1636:
1635:
1575:
1551:
1549:
1548:
1543:
1532:
1503:
1502:
1426:
1424:
1423:
1418:
1416:
1415:
1403:
1402:
1364:
1362:
1361:
1356:
1326:
1324:
1323:
1318:
1298:
1296:
1295:
1290:
1279:
1278:
1259:
1257:
1256:
1251:
1249:
1248:
1224:
1222:
1221:
1216:
1205:
1204:
1185:
1183:
1182:
1177:
1175:
1174:
1158:
1156:
1155:
1150:
1130:
1128:
1127:
1122:
1109:
1107:
1106:
1101:
1089:
1087:
1086:
1081:
1066:
1064:
1063:
1058:
1046:
1044:
1043:
1038:
1014:
1012:
1011:
1006:
991:
989:
988:
983:
972:
971:
952:
950:
949:
944:
942:
941:
923:
921:
920:
915:
902:
900:
899:
894:
882:
880:
879:
874:
859:
857:
856:
851:
840:
839:
820:
818:
817:
812:
810:
809:
791:
789:
788:
783:
768:
766:
765:
760:
747:
745:
744:
739:
727:
725:
724:
719:
706:partial function
699:
697:
696:
691:
679:
677:
676:
671:
653:
651:
650:
645:
632:
630:
629:
624:
622:
621:
594:
592:
591:
586:
573:
571:
570:
565:
563:
562:
543:
541:
540:
535:
523:
521:
520:
515:
513:
512:
490:
488:
487:
482:
470:
468:
467:
462:
450:
448:
447:
442:
426:
424:
423:
418:
398:
396:
395:
390:
374:
372:
371:
366:
364:
363:
347:
345:
344:
339:
337:
336:
320:
318:
317:
312:
310:
309:
293:
291:
290:
285:
273:
271:
270:
265:
243:
241:
240:
235:
223:
221:
220:
215:
195:
193:
192:
187:
171:
169:
168:
163:
161:
160:
144:
142:
141:
136:
120:
118:
117:
112:
110:
109:
93:
91:
90:
85:
80:
79:
67:
66:
50:
48:
47:
42:
26:recursion theory
18:recursion theory
3222:
3221:
3217:
3216:
3215:
3213:
3212:
3211:
3197:
3196:
3195:
3186:
3182:
3173:
3169:
3160:
3156:
3147:
3143:
3134:
3130:
3121:
3117:
3108:
3104:
3095:
3091:
3082:
3075:
3066:
3062:
3053:
3049:
3045:
3002:
2966:
2965:
2944:
2939:
2938:
2917:
2912:
2911:
2890:
2885:
2884:
2863:
2858:
2857:
2826:
2825:
2794:
2789:
2788:
2766:
2765:
2746:
2745:
2722:
2721:
2718:
2694:
2693:
2674:
2673:
2654:
2653:
2631:
2630:
2611:
2610:
2591:
2590:
2571:
2570:
2551:
2550:
2531:
2530:
2505:
2504:
2485:
2484:
2461:
2460:
2441:
2440:
2421:
2420:
2392:
2391:
2361:
2360:
2341:
2340:
2319:
2314:
2313:
2292:
2287:
2286:
2255:
2254:
2231:
2226:
2221:
2220:
2199:
2194:
2193:
2165:
2152:
2143:
2142:
2113:
2104:
2103:
2054:
2044:
2022:
2009:
1996:
1983:
1972:
1971:
1950:
1937:
1932:
1931:
1912:
1911:
1892:
1891:
1888:
1858:
1826:
1825:
1785:
1772:
1767:
1766:
1737:
1736:
1707:
1698:
1697:
1627:
1557:
1556:
1494:
1432:
1431:
1407:
1394:
1389:
1388:
1387:if there exist
1329:
1328:
1309:
1308:
1270:
1262:
1261:
1240:
1235:
1234:
1196:
1188:
1187:
1166:
1161:
1160:
1135:
1134:
1113:
1112:
1092:
1091:
1072:
1071:
1049:
1048:
1017:
1016:
997:
996:
963:
955:
954:
933:
928:
927:
906:
905:
885:
884:
865:
864:
831:
823:
822:
801:
796:
795:
774:
773:
751:
750:
730:
729:
710:
709:
682:
681:
662:
661:
636:
635:
607:
602:
601:
577:
576:
554:
549:
548:
526:
525:
498:
493:
492:
473:
472:
453:
452:
433:
432:
403:
402:
381:
380:
355:
350:
349:
328:
323:
322:
321:definable over
301:
296:
295:
276:
275:
250:
249:
226:
225:
206:
205:
202:
178:
177:
172:is a model of
152:
147:
146:
127:
126:
101:
96:
95:
71:
58:
53:
52:
33:
32:
12:
11:
5:
3220:
3218:
3210:
3209:
3199:
3198:
3194:
3193:
3187:P. Odifreddi,
3180:
3167:
3154:
3141:
3128:
3115:
3102:
3089:
3073:
3067:R. Gostanian,
3060:
3046:
3044:
3041:
3040:
3039:
3032:
3023:
3015:Robert Soare,
3013:
3005:Gerald Sacks,
3001:
2998:
2983:
2978:
2974:
2951:
2947:
2924:
2920:
2897:
2893:
2883:-definable on
2870:
2866:
2843:
2838:
2834:
2806:
2801:
2797:
2773:
2753:
2729:
2717:
2714:
2701:
2681:
2661:
2638:
2618:
2598:
2578:
2558:
2538:
2518:
2515:
2512:
2492:
2481:limit inferior
2468:
2448:
2428:
2405:
2402:
2399:
2381:Levy hierarchy
2368:
2348:
2326:
2322:
2299:
2295:
2285:-definable on
2272:
2267:
2263:
2238:
2234:
2229:
2219:-definable on
2206:
2202:
2177:
2172:
2168:
2164:
2159:
2155:
2151:
2125:
2120:
2116:
2112:
2081:
2078:
2075:
2072:
2069:
2066:
2061:
2057:
2051:
2047:
2043:
2040:
2037:
2034:
2029:
2025:
2021:
2016:
2012:
2008:
2003:
1999:
1995:
1990:
1986:
1982:
1979:
1957:
1953:
1949:
1944:
1940:
1919:
1899:
1887:
1884:
1865:
1861:
1857:
1854:
1851:
1848:
1845:
1842:
1839:
1836:
1833:
1824:is regular if
1806:
1803:
1800:
1797:
1792:
1788:
1784:
1779:
1775:
1745:
1719:
1714:
1710:
1706:
1686:
1685:
1674:
1671:
1668:
1664:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1639:
1634:
1630:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1587:
1584:
1581:
1578:
1574:
1570:
1567:
1564:
1553:
1552:
1541:
1538:
1535:
1531:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1501:
1497:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1414:
1410:
1406:
1401:
1397:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1316:
1305:
1304:
1288:
1285:
1282:
1277:
1273:
1269:
1260:-definable in
1247:
1243:
1233:The functions
1227:
1226:
1214:
1211:
1208:
1203:
1199:
1195:
1186:-definable on
1173:
1169:
1148:
1145:
1142:
1120:
1099:
1079:
1068:
1056:
1036:
1033:
1030:
1027:
1024:
1004:
981:
978:
975:
970:
966:
962:
953:-definable on
940:
936:
913:
892:
872:
861:
849:
846:
843:
838:
834:
830:
821:-definable on
808:
804:
781:
758:
737:
717:
689:
669:
658:
657:
643:
620:
617:
614:
610:
598:
584:
561:
557:
545:
533:
511:
508:
505:
501:
480:
460:
440:
416:
413:
410:
401:if both A and
388:
376:
362:
358:
335:
331:
308:
304:
283:
274:is said to be
263:
260:
257:
233:
213:
201:
198:
185:
159:
155:
134:
108:
104:
83:
78:
74:
70:
65:
61:
40:
28:to subsets of
13:
10:
9:
6:
4:
3:
2:
3219:
3208:
3205:
3204:
3202:
3190:
3184:
3181:
3177:
3174:G. E. Sacks,
3171:
3168:
3164:
3161:P. D. Welch,
3158:
3155:
3151:
3148:D. Natingga,
3145:
3142:
3138:
3132:
3129:
3125:
3119:
3116:
3112:
3106:
3103:
3099:
3093:
3090:
3086:
3080:
3078:
3074:
3070:
3064:
3061:
3057:
3051:
3048:
3042:
3037:
3033:
3030:
3029:
3024:
3022:
3018:
3014:
3012:
3008:
3004:
3003:
2999:
2997:
2981:
2976:
2949:
2922:
2895:
2891:
2868:
2841:
2836:
2804:
2799:
2795:
2785:
2771:
2751:
2743:
2727:
2715:
2713:
2699:
2679:
2659:
2650:
2636:
2616:
2596:
2576:
2556:
2536:
2516:
2513:
2510:
2490:
2482:
2466:
2446:
2426:
2417:
2403:
2397:
2389:
2384:
2382:
2346:
2324:
2320:
2297:
2293:
2270:
2265:
2236:
2232:
2227:
2204:
2190:
2175:
2170:
2166:
2162:
2157:
2153:
2149:
2140:
2123:
2118:
2114:
2110:
2101:
2097:
2092:
2079:
2073:
2070:
2067:
2059:
2055:
2049:
2045:
2041:
2038:
2032:
2027:
2023:
2019:
2014:
2010:
2006:
2001:
1997:
1993:
1988:
1984:
1980:
1977:
1955:
1951:
1947:
1942:
1938:
1917:
1897:
1885:
1883:
1882:is Ī±-finite.
1881:
1863:
1859:
1855:
1852:
1849:
1846:
1843:
1840:
1837:
1834:
1823:
1818:
1798:
1790:
1786:
1777:
1764:
1760:
1734:
1717:
1712:
1708:
1704:
1695:
1691:
1672:
1666:
1662:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1632:
1628:
1624:
1618:
1615:
1612:
1609:
1606:
1597:
1594:
1588:
1585:
1576:
1572:
1568:
1565:
1562:
1555:
1554:
1539:
1533:
1529:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1499:
1495:
1491:
1485:
1482:
1479:
1476:
1473:
1464:
1461:
1455:
1452:
1443:
1440:
1437:
1430:
1429:
1428:
1412:
1408:
1404:
1399:
1395:
1386:
1382:
1378:
1376:
1372:
1368:
1349:
1346:
1343:
1340:
1337:
1314:
1302:
1283:
1280:
1275:
1271:
1245:
1232:
1231:
1230:
1209:
1206:
1201:
1197:
1171:
1146:
1143:
1140:
1132:
1131:-arithmetical
1118:
1097:
1077:
1069:
1054:
1034:
1028:
1025:
1022:
1002:
995:
976:
973:
968:
964:
938:
925:
911:
890:
870:
862:
844:
841:
836:
832:
806:
793:
779:
770:
756:
735:
715:
707:
703:
702:
701:
687:
667:
655:
641:
618:
615:
612:
608:
599:
596:
582:
559:
555:
546:
531:
509:
506:
503:
499:
478:
458:
438:
430:
414:
408:
400:
386:
377:
360:
356:
333:
329:
306:
281:
261:
258:
255:
247:
246:
245:
231:
211:
199:
197:
183:
175:
157:
153:
132:
124:
106:
102:
76:
72:
63:
38:
31:
27:
23:
19:
3188:
3183:
3175:
3170:
3157:
3149:
3144:
3131:
3123:
3118:
3105:
3092:
3063:
3050:
3035:
3034:J. Barwise,
3027:
3016:
3006:
2786:
2719:
2651:
2418:
2385:
2379:is from the
2191:
2138:
2099:
2095:
2093:
1889:
1879:
1821:
1819:
1762:
1732:
1693:
1689:
1687:
1384:
1380:
1379:
1374:
1370:
1366:
1306:
1228:
1111:
993:
904:
772:
749:
659:
634:
575:
379:
203:
21:
15:
3113:(1998). p.2
2416:functions.
2390:to partial
1067:-recursive.
654:-arithmetic
633:are called
600:Members of
574:are called
547:Members of
200:Definitions
3000:References
2141:such that
1970:such that
924:-recursive
399:-recursive
3109:T. Arai,
2996:formula.
2973:Σ
2946:Σ
2919:Σ
2896:ω
2865:Σ
2833:Σ
2800:ω
2728:α
2700:α
2680:α
2660:α
2637:α
2597:α
2557:α
2537:α
2517:α
2514:⊆
2491:α
2467:α
2447:α
2427:α
2404:α
2401:→
2398:α
2367:Σ
2347:α
2321:α
2298:α
2262:Π
2233:α
2201:Σ
2171:α
2158:α
2119:α
2050:α
2039:∧
2036:∅
2020:∩
2007:∧
1994:∪
1918:α
1898:α
1864:α
1856:∈
1853:β
1850:∩
1841:α
1838:∈
1835:β
1832:∀
1791:α
1774:Σ
1759:empty set
1744:∅
1713:α
1709:≤
1659:α
1656:⊆
1650:∧
1644:⊆
1638:∧
1625:∈
1622:⟩
1604:⟨
1592:∃
1583:∃
1580:↔
1569:α
1566:⊆
1526:α
1523:⊆
1517:∧
1511:⊆
1505:∧
1492:∈
1489:⟩
1471:⟨
1459:∃
1450:∃
1447:↔
1441:⊆
1353:⟩
1335:⟨
1315:α
1284:∈
1276:α
1242:Δ
1210:∈
1202:α
1168:Σ
1147:ω
1144:∈
1119:α
1098:α
1078:α
1055:α
1035:α
1032:→
1029:α
1003:α
977:∈
969:α
935:Δ
912:α
891:α
871:α
845:∈
837:α
803:Σ
780:α
757:α
736:α
716:α
688:α
668:α
642:α
613:α
583:α
560:α
504:α
479:α
459:α
439:α
412:∖
409:α
387:α
361:α
334:α
303:Σ
282:α
262:α
259:⊆
232:α
212:α
184:α
158:α
133:α
107:ξ
77:α
60:Σ
39:α
3201:Category
2910:, where
2503:, a set
2312:, where
2046:≰
1820:We say
595:-finite
3038:. 1975
2359:, and
1365:where
451:) are
248:A set
1757:(the
994:total
771:, or
708:from
427:(its
378:A is
2167:<
2154:<
2115:<
2071:<
2589:is
2529:is
1688:If
1110:is
1090:to
1047:is
903:is
883:to
748:is
728:to
680:to
431:in
16:In
3203::
3076:^
2810:HF
2383:.
2189:.
2098:,
1817:.
1373:,
1369:,
704:A
700::
656:.
125:.
20:,
2982:0
2977:n
2950:n
2923:1
2892:L
2869:1
2842:0
2837:1
2805:=
2796:L
2772:L
2752:L
2617:A
2577:A
2511:A
2325:+
2294:L
2271:1
2266:1
2237:+
2228:L
2205:1
2176:C
2163:B
2150:A
2139:B
2124:C
2111:A
2100:C
2096:A
2080:.
2077:)
2074:2
2068:i
2065:(
2060:i
2056:B
2042:A
2033:=
2028:1
2024:B
2015:0
2011:B
2002:1
1998:B
1989:0
1985:B
1981:=
1978:A
1956:1
1952:B
1948:,
1943:0
1939:B
1880:A
1860:L
1847:A
1844::
1822:A
1805:)
1802:]
1799:B
1796:[
1787:L
1783:(
1778:1
1763:A
1733:A
1718:B
1705:A
1694:B
1690:A
1673:.
1670:]
1667:B
1663:/
1653:J
1647:B
1641:H
1633:1
1629:R
1619:K
1616:,
1613:J
1610:,
1607:H
1601:[
1598::
1595:J
1589::
1586:H
1577:A
1573:/
1563:K
1540:,
1537:]
1534:B
1530:/
1520:J
1514:B
1508:H
1500:0
1496:R
1486:K
1483:,
1480:J
1477:,
1474:H
1468:[
1465::
1462:J
1456::
1453:H
1444:A
1438:K
1413:1
1409:R
1405:,
1400:0
1396:R
1385:B
1381:A
1375:K
1371:J
1367:H
1350:K
1347:,
1344:J
1341:,
1338:H
1303:.
1287:)
1281:,
1272:L
1268:(
1246:0
1225:.
1213:)
1207:,
1198:L
1194:(
1172:n
1141:n
1026::
1023:f
980:)
974:,
965:L
961:(
939:1
860:.
848:)
842:,
833:L
829:(
807:1
619:1
616:+
609:L
556:L
544:.
532:L
510:1
507:+
500:L
415:A
357:L
330:L
307:1
256:A
154:L
103:L
82:)
73:L
69:(
64:1
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.