947:
586:
776:
1025:
5534:
177:
way to tell whether some natural number represents an ordinal, or whether two numbers represent the same ordinal. However, one can effectively find notations which represent the ordinal sum, product, and power (see
781:
453:
3863:
1623:
4260:
is the universal system of ordinal notations in the sense that any specific set of ordinal notations can be mapped into it in a straightforward way. More precisely, there is a computable function
4546:
4434:
1782:
3268:
3206:
1678:
446:
5223:
2474:
2146:
663:
5314:
3392:
3129:
5587:
3674:
3642:
136:
104:
4738:
2209:
2019:
1981:
1850:
4859:
4659:
3769:
3736:
3449:
2677:
2570:
2321:
1707:
1057:
363:
1103:
3418:
3157:
2953:
2758:
2174:
4466:
3603:
5657:
5257:
5125:
5064:
4121:
2521:
5861:
5834:
5711:
5470:
5396:
5341:
5281:
5152:
5088:
5027:
5003:
4959:
4935:
4907:
4883:
4830:
4806:
4782:
4703:
4630:
4606:
4582:
4490:
4351:
4258:
4232:
4169:
4145:
4025:
3969:
3907:
3793:
3701:
3551:
3527:
3497:
3473:
3021:
2802:
2727:
2594:
2420:
2092:
1468:
1292:
1175:
391:
334:
260:
204:
160:
51:
5810:
5775:
5743:
4204:
4089:
4057:
4001:
3939:
2925:
1561:
5687:
5372:
5179:
3317:
3353:
2982:
2832:
1942:
1896:
1411:
1268:
5922:
Ash, Knight, *Computable
Structures and the Hyperarithmetical Hierarchy* p.83. Studies in Logic and the Foundations of Mathematics vol. 144 (2000), ISBN 0-444-50072-3.
4378:
2703:
2644:
2347:
953:
1123:
1077:
3067:
2614:
2541:
1508:
1488:
5614:
5446:
3047:
1339:
614:
4327:
2259:
1812:
1444:
1242:
1209:
310:
5554:
5419:
4979:
4758:
4679:
4298:
4278:
3883:
3816:
3574:
3556:
Since every computable function has countably many indices, each infinite ordinal receives countably many notations; the finite ordinals have unique notations,
2892:
2872:
2852:
2778:
2387:
2367:
2279:
2229:
2059:
2039:
1581:
1528:
1359:
1312:
1151:
658:
634:
280:
236:
5745:. Given a progression of computably enumerable theories based on iterating Uniform Reflection, each such path is incomplete with respect to the set of true
3707:. (The fact that every computable ordinal has a notation follows from the closure of this system of ordinal notations under successor and effective limits.)
5475:
942:{\displaystyle 3\cdot 5^{e}\in {\mathcal {O}}\land \forall n,\{e\}(n)<_{\mathcal {O}}3\cdot 5^{e}\land |3\cdot 5^{e}|=\lim _{k}|\{e\}(k)|}
581:{\displaystyle i\in {\mathcal {O}}\land |i|=\alpha \rightarrow 2^{i}\in {\mathcal {O}}\land |2^{i}|=\alpha +1\land i<_{\mathcal {O}}2^{i}}
1294:, a successor ordinal is defined in terms of a notation for the ordinal immediately preceding it. Specifically, a successor notation
3821:
1586:
6003:
1030:
This definition has the advantages that one can computably enumerate the predecessors of a given ordinal (though not in the
4495:
4383:
1712:
3215:
218:
The basic idea of Kleene's system of ordinal notations is to build up ordinals in an effective manner. For members
3165:
1628:
771:{\displaystyle {\textrm {range}}(\{e\})\subset {\mathcal {O}}\land \forall n(\{e\}(n)<_{\mathcal {O}}\{e\}(n+1))}
399:
5187:
2425:
2097:
1125:. There are alternate definitions, such as the set of indices of (partial) well-orderings of the natural numbers.
5286:
3358:
3072:
5559:
3647:
3615:
109:
77:
4708:
2179:
1989:
1951:
1820:
4835:
4635:
3745:
3712:
3425:
2652:
2546:
2292:
1683:
1033:
637:
339:
1082:
6012:
Feferman, Solomon; Spector, Clifford (1962), "Incompleteness along paths in progressions of theories",
3739:
3397:
3134:
2930:
2735:
2151:
207:
4442:
3579:
5863:
have been shown to exist, each with specific kinds of reducibility properties. (See references below)
5619:
5228:
5096:
5035:
4094:
3609:
2479:
166:
71:
5842:
5815:
5692:
5451:
5377:
5322:
5262:
5133:
5069:
5008:
4984:
4940:
4916:
4888:
4864:
4811:
4787:
4763:
4684:
4611:
4587:
4563:
4471:
4332:
4239:
4213:
4150:
4126:
4006:
3950:
3888:
3774:
3682:
3532:
3508:
3478:
3454:
2987:
2783:
2708:
2575:
2392:
2064:
1449:
1273:
1156:
372:
315:
241:
185:
141:
32:
6058:
138:
is the first ordinal not representable in a computable system of ordinal notations the elements of
5783:
5748:
5716:
4177:
4062:
4030:
3974:
3912:
2897:
1533:
5878:
5665:
5350:
5157:
3286:
1020:{\displaystyle p<_{\mathcal {O}}q\land q<_{\mathcal {O}}r\rightarrow p<_{\mathcal {O}}r}
3322:
2961:
2811:
1901:
1855:
5933:
1364:
1247:
4356:
2682:
2623:
2326:
165:
Kleene (1938) described a system of notation for all computable ordinals (those less than the
5903:
3500:
2617:
1108:
1062:
210:
of notations which contains one element for each smaller ordinal and is effectively ordered.
3052:
2599:
2526:
1493:
1473:
5592:
5424:
3942:
3026:
1317:
593:
21:
4303:
8:
2234:
1787:
1419:
1217:
1184:
285:
174:
26:
6037:
6029:
5983:
5975:
5539:
5404:
4964:
4743:
4664:
4283:
4263:
4207:
3868:
3801:
3559:
2877:
2857:
2837:
2763:
2372:
2352:
2264:
2214:
2044:
2024:
1566:
1513:
1344:
1297:
1136:
1059:
ordering) and that the notations are downward closed, i.e., if there is a notation for
643:
619:
265:
221:
179:
5999:
5873:
3704:
67:
59:
6041:
5987:
5950:
6021:
5967:
5945:
5883:
63:
4961:
is computably enumerable (c.e.). It follows by remarks above that every element
1490:
amounts to a computable sequence of notations for smaller ordinals limiting to
170:
55:
5529:{\displaystyle {\mathcal {P}}=\lbrace p\mid p<_{\mathcal {O}}e_{d}\rbrace }
6052:
366:
5836:
each initial segment of which is not merely c.e., but computable. (Jockusch)
173:
instead of finite strings of symbols. Unfortunately, there is in general no
3209:
2284:
3529:
only branches at limit ordinals; and at each notation of a limit ordinal,
3644:. Since there are only countably many computable functions, the ordinal
6033:
5979:
17:
2646:, then a computer program will eventually find a proof of this fact.
6025:
5971:
3742:, but there is a computably enumerable relation which agrees with
3608:
The first ordinal that doesn't receive a notation is called the
5996:
The Theory of
Recursive Functions and Effective Computability
1680:
of notations, which are strictly increasing under the order
3858:{\displaystyle \lbrace q\mid q<_{\mathcal {O}}p\rbrace }
1618:{\displaystyle \{e\}:\mathbb {N} \rightarrow \mathbb {N} }
5958:
Kleene, S. C. (1938), "On
Notation for Ordinal Numbers",
2285:
A Computably
Enumerable Order Extending the Kleene Order
393:) are the smallest sets such that the following holds.
5845:
5818:
5786:
5751:
5719:
5695:
5668:
5622:
5595:
5562:
5542:
5478:
5454:
5427:
5407:
5380:
5353:
5325:
5289:
5265:
5231:
5190:
5160:
5136:
5099:
5072:
5038:
5011:
4987:
4967:
4943:
4919:
4891:
4867:
4838:
4814:
4790:
4766:
4746:
4711:
4687:
4667:
4638:
4614:
4590:
4566:
4498:
4474:
4445:
4386:
4380:
is order-isomorphic to an initial segment of the set
4359:
4335:
4306:
4286:
4266:
4242:
4216:
4180:
4153:
4129:
4097:
4065:
4033:
4009:
3977:
3953:
3915:
3891:
3871:
3824:
3804:
3777:
3748:
3715:
3685:
3650:
3618:
3582:
3562:
3535:
3511:
3481:
3457:
3428:
3400:
3361:
3325:
3289:
3218:
3212:, so that there are no infinite descending sequences
3168:
3137:
3075:
3055:
3029:
2990:
2964:
2933:
2900:
2880:
2860:
2840:
2814:
2786:
2766:
2738:
2711:
2685:
2655:
2626:
2602:
2578:
2549:
2529:
2482:
2428:
2395:
2375:
2355:
2329:
2295:
2267:
2237:
2217:
2182:
2154:
2100:
2067:
2047:
2027:
1992:
1954:
1904:
1858:
1823:
1790:
1715:
1686:
1631:
1589:
1569:
1536:
1516:
1496:
1476:
1452:
1422:
1367:
1347:
1320:
1300:
1276:
1250:
1220:
1187:
1159:
1139:
1111:
1085:
1065:
1036:
956:
784:
666:
646:
622:
596:
456:
402:
375:
342:
318:
288:
268:
244:
224:
188:
144:
112:
80:
35:
4492:, mimics ordinal addition and has the property that
206:; and given any notation for an ordinal, there is a
162:
can be regarded as the canonical ordinal notations.
5855:
5828:
5804:
5769:
5737:
5705:
5681:
5651:
5608:
5581:
5548:
5528:
5464:
5440:
5413:
5390:
5366:
5335:
5308:
5275:
5251:
5217:
5173:
5146:
5119:
5082:
5058:
5021:
4997:
4973:
4953:
4929:
4901:
4877:
4853:
4824:
4800:
4776:
4752:
4732:
4697:
4673:
4653:
4624:
4600:
4576:
4541:{\displaystyle \max\{p,q\}\leq p+_{\mathcal {O}}q}
4540:
4484:
4460:
4429:{\displaystyle \{p\mid p<_{\mathcal {O}}f(e)\}}
4428:
4372:
4345:
4321:
4292:
4272:
4252:
4226:
4198:
4163:
4139:
4115:
4083:
4051:
4019:
3995:
3963:
3933:
3901:
3877:
3857:
3810:
3787:
3763:
3730:
3695:
3668:
3636:
3597:
3568:
3545:
3521:
3491:
3467:
3443:
3412:
3386:
3347:
3311:
3262:
3200:
3151:
3123:
3061:
3041:
3015:
2976:
2947:
2919:
2886:
2866:
2846:
2826:
2796:
2772:
2752:
2721:
2697:
2671:
2638:
2608:
2588:
2564:
2535:
2515:
2468:
2414:
2381:
2361:
2341:
2315:
2273:
2253:
2223:
2203:
2168:
2140:
2086:
2053:
2033:
2013:
1975:
1936:
1890:
1844:
1806:
1777:{\displaystyle \langle |q_{0}|,|q_{1}|...\rangle }
1776:
1701:
1672:
1617:
1575:
1555:
1522:
1502:
1482:
1462:
1438:
1405:
1353:
1333:
1306:
1286:
1262:
1236:
1203:
1169:
1145:
1117:
1097:
1071:
1051:
1019:
941:
770:
652:
628:
608:
580:
440:
385:
357:
328:
304:
274:
254:
230:
198:
154:
130:
98:
45:
4300:is an index for a computable well-ordering, then
1625:is a total function listing an infinite sequence
1181:and is meant to give a definition of the ordinal
6050:
4499:
3945:) and not arithmetical because of the following:
3263:{\displaystyle ...\prec q_{1}\prec q_{0}\prec p}
902:
6011:
5918:
5916:
4552:
5966:(4), Association for Symbolic Logic: 150–155,
5029:; and every non-maximal path is so determined.
3201:{\displaystyle \{q\in \mathbb {N} :q\prec p\}}
2231:is eventually referenced in the definition of
1673:{\displaystyle \langle q_{0},q_{1}...\rangle }
441:{\displaystyle 0\in {\mathcal {O}}\land |0|=0}
2804:only when all of the criteria below are met:
5913:
5523:
5489:
5218:{\displaystyle \lambda <\omega _{1}^{CK}}
4514:
4502:
4423:
4387:
3885:is computably enumerable. However, Kleene's
3852:
3825:
3274:
3195:
3169:
3103:
3097:
3082:
3076:
3036:
3030:
2507:
2501:
2469:{\displaystyle 3\cdot 5^{e}\mapsto \{e\}(i)}
2454:
2448:
2141:{\displaystyle 3\cdot 5^{e}\mapsto \{e\}(i)}
2126:
2120:
1771:
1716:
1667:
1632:
1596:
1590:
1214:The successor notations are those such that
922:
916:
829:
823:
747:
741:
717:
711:
683:
677:
603:
597:
5090:; since they are maximal, they are non-c.e.
4661:and is closed under predecessors, i.e. if
5949:
5309:{\displaystyle \omega ^{2}\cdot \lambda }
4091:set is Turing reducible to it) and every
3679:The ordinals with a notation in Kleene's
3380:
3179:
3145:
2941:
2746:
2309:
2162:
1611:
1603:
182:) of any two given notations in Kleene's
5904:The Hierarchy Based on the Jump Operator
3387:{\displaystyle i<_{\mathcal {O}}j\,,}
3124:{\displaystyle \{e\}(i)\prec \{e\}(i+1)}
1709:. The limit of the sequence of ordinals
1416:The limit notations are those such that
5582:{\displaystyle \alpha \geq \omega ^{2}}
5556:. In fact, for each computable ordinal
3669:{\displaystyle \omega _{1}^{\text{CK}}}
3637:{\displaystyle \omega _{1}^{\text{CK}}}
3049:is total and strictly increasing under
131:{\displaystyle \omega _{1}^{\text{CK}}}
99:{\displaystyle \omega _{1}^{\text{CK}}}
6051:
5993:
5957:
5934:"The constructive second number class"
5931:
2389:by repeatedly applying the operations
2061:by repeatedly applying the operations
5998:, First MIT press paperback edition,
4808:is maximal if there is no element of
4733:{\displaystyle q<_{\mathcal {O}}p}
2204:{\displaystyle q<_{\mathcal {O}}p}
2014:{\displaystyle q<_{\mathcal {O}}p}
1976:{\displaystyle q<_{\mathcal {O}}p}
1845:{\displaystyle q<_{\mathcal {O}}p}
3420:; but the converse may fail to hold.
5777:sentences. (Feferman & Spector)
4854:{\displaystyle <_{\mathcal {O}}}
4654:{\displaystyle <_{\mathcal {O}}}
3764:{\displaystyle <_{\mathcal {O}}}
3731:{\displaystyle <_{\mathcal {O}}}
3444:{\displaystyle <_{\mathcal {O}}}
2672:{\displaystyle p\in {\mathcal {O}}}
2565:{\displaystyle <_{\mathcal {O}}}
2316:{\displaystyle p,q\in \mathbb {N} }
1702:{\displaystyle <_{\mathcal {O}}}
1052:{\displaystyle <_{\mathcal {O}}}
358:{\displaystyle <_{\mathcal {O}}}
13:
5848:
5821:
5788:
5753:
5721:
5698:
5670:
5507:
5481:
5457:
5383:
5328:
5268:
5238:
5139:
5106:
5075:
5045:
5014:
4990:
4946:
4922:
4894:
4870:
4845:
4817:
4793:
4769:
4721:
4690:
4645:
4617:
4593:
4569:
4529:
4477:
4452:
4405:
4338:
4245:
4219:
4182:
4156:
4132:
4099:
4067:
4035:
4012:
3979:
3956:
3917:
3894:
3843:
3780:
3755:
3722:
3688:
3589:
3538:
3514:
3484:
3460:
3435:
3371:
2789:
2714:
2664:
2581:
2556:
2192:
2002:
1964:
1833:
1693:
1455:
1279:
1162:
1098:{\displaystyle \alpha <\gamma }
1043:
1008:
987:
966:
847:
814:
806:
735:
702:
694:
562:
510:
465:
411:
378:
349:
321:
247:
191:
147:
38:
14:
6070:
3413:{\displaystyle \alpha <\beta }
3152:{\displaystyle i\in \mathbb {N} }
2948:{\displaystyle e\in \mathbb {N} }
2753:{\displaystyle p\in \mathbb {N} }
2169:{\displaystyle i\in \mathbb {N} }
1470:, a notation for a limit ordinal
4832:which is above (in the sense of
4461:{\displaystyle +_{\mathcal {O}}}
3598:{\displaystyle n_{\mathcal {O}}}
1583:'th partial computable function
1446:is a limit ordinal. In Kleene's
5951:10.1090/S0002-9904-1938-06720-1
5652:{\displaystyle |e_{d}|=\alpha }
5252:{\displaystyle 2^{\aleph _{0}}}
5120:{\displaystyle 2^{\aleph _{0}}}
5059:{\displaystyle 2^{\aleph _{0}}}
4439:There is a computable function
4116:{\displaystyle \Sigma _{1}^{1}}
2516:{\displaystyle i\in dom(\{e\})}
5896:
5856:{\displaystyle {\mathcal {O}}}
5829:{\displaystyle {\mathcal {O}}}
5706:{\displaystyle {\mathcal {O}}}
5639:
5624:
5465:{\displaystyle {\mathcal {O}}}
5391:{\displaystyle {\mathcal {P}}}
5336:{\displaystyle {\mathcal {P}}}
5276:{\displaystyle {\mathcal {O}}}
5147:{\displaystyle {\mathcal {O}}}
5083:{\displaystyle {\mathcal {O}}}
5022:{\displaystyle {\mathcal {P}}}
5005:determines a non-maximal path
4998:{\displaystyle {\mathcal {O}}}
4954:{\displaystyle {\mathcal {P}}}
4937:is non-maximal if and only if
4930:{\displaystyle {\mathcal {P}}}
4902:{\displaystyle {\mathcal {P}}}
4878:{\displaystyle {\mathcal {P}}}
4825:{\displaystyle {\mathcal {O}}}
4801:{\displaystyle {\mathcal {P}}}
4777:{\displaystyle {\mathcal {P}}}
4698:{\displaystyle {\mathcal {P}}}
4625:{\displaystyle {\mathcal {O}}}
4601:{\displaystyle {\mathcal {P}}}
4577:{\displaystyle {\mathcal {O}}}
4485:{\displaystyle {\mathcal {O}}}
4420:
4414:
4346:{\displaystyle {\mathcal {O}}}
4316:
4310:
4253:{\displaystyle {\mathcal {O}}}
4227:{\displaystyle {\mathcal {O}}}
4164:{\displaystyle {\mathcal {O}}}
4140:{\displaystyle {\mathcal {O}}}
4020:{\displaystyle {\mathcal {O}}}
3964:{\displaystyle {\mathcal {O}}}
3902:{\displaystyle {\mathcal {O}}}
3788:{\displaystyle {\mathcal {O}}}
3696:{\displaystyle {\mathcal {O}}}
3546:{\displaystyle {\mathcal {O}}}
3522:{\displaystyle {\mathcal {O}}}
3492:{\displaystyle {\mathcal {O}}}
3468:{\displaystyle {\mathcal {O}}}
3335:
3327:
3299:
3291:
3118:
3106:
3091:
3085:
3016:{\displaystyle q=3\cdot 5^{e}}
2797:{\displaystyle {\mathcal {O}}}
2722:{\displaystyle {\mathcal {O}}}
2589:{\displaystyle {\mathcal {O}}}
2510:
2498:
2463:
2457:
2445:
2415:{\displaystyle 2^{n}\mapsto n}
2406:
2247:
2239:
2135:
2129:
2117:
2087:{\displaystyle 2^{n}\mapsto n}
2078:
1930:
1922:
1914:
1906:
1884:
1876:
1868:
1860:
1800:
1792:
1758:
1743:
1735:
1720:
1607:
1463:{\displaystyle {\mathcal {O}}}
1432:
1424:
1393:
1385:
1377:
1369:
1287:{\displaystyle {\mathcal {O}}}
1230:
1222:
1197:
1189:
1170:{\displaystyle {\mathcal {O}}}
1128:
996:
935:
931:
925:
912:
894:
873:
838:
832:
765:
762:
750:
726:
720:
708:
686:
674:
534:
519:
492:
482:
474:
428:
420:
386:{\displaystyle {\mathcal {O}}}
329:{\displaystyle {\mathcal {O}}}
298:
290:
255:{\displaystyle {\mathcal {O}}}
199:{\displaystyle {\mathcal {O}}}
155:{\displaystyle {\mathcal {O}}}
46:{\displaystyle {\mathcal {O}}}
1:
5960:The Journal of Symbolic Logic
5889:
1105:then there is a notation for
213:
54:is a canonical subset of the
5805:{\displaystyle \Pi _{1}^{1}}
5770:{\displaystyle \Pi _{1}^{0}}
5738:{\displaystyle \Pi _{1}^{1}}
4632:which is totally ordered by
4199:{\displaystyle \Pi _{1}^{1}}
4084:{\displaystyle \Pi _{1}^{1}}
4052:{\displaystyle \Pi _{1}^{1}}
3996:{\displaystyle \Pi _{1}^{1}}
3934:{\displaystyle \Pi _{1}^{1}}
3909:, when taken as a whole, is
3451:induces a tree structure on
2920:{\displaystyle 3\cdot 5^{e}}
2705:are themselves notations in
1556:{\displaystyle 3\cdot 5^{e}}
7:
5867:
5682:{\displaystyle \aleph _{0}}
5367:{\displaystyle \omega ^{2}}
5184:For every non-zero ordinal
5174:{\displaystyle \omega ^{2}}
4553:Properties of paths in <
3312:{\displaystyle |i|=\alpha }
638:partial computable function
169:). It uses a subset of the
10:
6075:
5343:is a path whose length is
4147:is effectively bounded in
3348:{\displaystyle |j|=\beta }
2977:{\displaystyle q\preceq p}
2827:{\displaystyle q\preceq p}
1937:{\displaystyle |q|<|p|}
1891:{\displaystyle |q|<|p|}
70:, that is, ordinals below
6014:Journal of Symbolic Logic
5994:Rogers, Hartley (1987) ,
1406:{\displaystyle |p|=|q|+1}
1263:{\displaystyle \alpha +1}
208:computably enumerable set
4468:, which, for members of
4373:{\displaystyle <_{e}}
3771:precisely on members of
3553:is infinitely branching.
3275:Basic properties of <
2698:{\displaystyle q\prec p}
2639:{\displaystyle q\prec p}
2342:{\displaystyle q\prec p}
1341:for some other notation
262:, the ordinal for which
5932:Church, Alonzo (1938),
5879:Large countable ordinal
5839:Various other paths in
5398:is not maximal. (Aczel)
3676:is evidently countable.
2041:must be reachable from
1244:is a successor ordinal
1118:{\displaystyle \alpha }
1072:{\displaystyle \gamma }
5938:Bull. Amer. Math. Soc.
5857:
5830:
5806:
5771:
5739:
5707:
5683:
5653:
5610:
5583:
5550:
5530:
5466:
5442:
5415:
5392:
5368:
5337:
5310:
5277:
5253:
5219:
5175:
5148:
5121:
5084:
5066:maximal paths through
5060:
5023:
4999:
4975:
4955:
4931:
4903:
4879:
4855:
4826:
4802:
4778:
4754:
4734:
4699:
4681:is a member of a path
4675:
4655:
4626:
4602:
4578:
4542:
4486:
4462:
4430:
4374:
4347:
4323:
4294:
4274:
4254:
4228:
4200:
4171:(a result of Spector).
4165:
4141:
4117:
4085:
4053:
4021:
3997:
3965:
3935:
3903:
3879:
3859:
3812:
3789:
3765:
3732:
3697:
3670:
3638:
3599:
3570:
3547:
3523:
3493:
3469:
3445:
3414:
3388:
3349:
3313:
3264:
3202:
3153:
3125:
3063:
3062:{\displaystyle \prec }
3043:
3017:
2978:
2949:
2921:
2888:
2868:
2848:
2828:
2798:
2774:
2754:
2723:
2699:
2673:
2640:
2610:
2609:{\displaystyle \prec }
2590:
2566:
2537:
2536:{\displaystyle \prec }
2517:
2470:
2416:
2383:
2363:
2343:
2317:
2275:
2255:
2225:
2205:
2170:
2142:
2088:
2055:
2035:
2015:
1977:
1938:
1892:
1846:
1808:
1778:
1703:
1674:
1619:
1577:
1557:
1524:
1504:
1503:{\displaystyle \beta }
1484:
1483:{\displaystyle \beta }
1464:
1440:
1407:
1355:
1335:
1308:
1288:
1264:
1238:
1205:
1171:
1147:
1119:
1099:
1073:
1053:
1021:
943:
772:
654:
630:
610:
582:
442:
387:
359:
330:
306:
276:
256:
232:
200:
156:
132:
100:
47:
5910:(North-Holland, 1980)
5858:
5831:
5807:
5772:
5740:
5708:
5684:
5654:
5611:
5609:{\displaystyle e_{d}}
5584:
5551:
5531:
5467:
5443:
5441:{\displaystyle e_{d}}
5416:
5401:For each c.e. degree
5393:
5369:
5338:
5311:
5278:
5259:maximal paths within
5254:
5220:
5181:. (Crossley, SchĂĽtte)
5176:
5149:
5122:
5085:
5061:
5024:
5000:
4976:
4956:
4932:
4904:
4880:
4856:
4827:
4803:
4779:
4755:
4735:
4700:
4676:
4656:
4627:
4603:
4579:
4543:
4487:
4463:
4431:
4375:
4348:
4324:
4295:
4275:
4255:
4229:
4201:
4166:
4142:
4118:
4086:
4054:
4022:
3998:
3966:
3936:
3904:
3880:
3860:
3813:
3790:
3766:
3740:computably enumerable
3733:
3698:
3671:
3639:
3610:Church–Kleene ordinal
3600:
3571:
3548:
3524:
3494:
3470:
3446:
3415:
3389:
3350:
3314:
3265:
3203:
3154:
3126:
3064:
3044:
3042:{\displaystyle \{e\}}
3018:
2979:
2950:
2922:
2889:
2869:
2849:
2829:
2799:
2775:
2755:
2724:
2700:
2674:
2641:
2618:computably enumerable
2611:
2591:
2567:
2538:
2518:
2471:
2417:
2384:
2364:
2344:
2318:
2276:
2256:
2226:
2206:
2171:
2143:
2089:
2056:
2036:
2016:
1978:
1939:
1893:
1847:
1809:
1779:
1704:
1675:
1620:
1578:
1558:
1525:
1510:. Any limit notation
1505:
1485:
1465:
1441:
1408:
1356:
1336:
1334:{\displaystyle 2^{q}}
1309:
1289:
1265:
1239:
1206:
1172:
1148:
1120:
1100:
1074:
1054:
1022:
944:
773:
655:
631:
611:
609:{\displaystyle \{e\}}
583:
443:
388:
360:
331:
307:
277:
257:
233:
201:
167:Church–Kleene ordinal
157:
133:
101:
72:Church–Kleene ordinal
48:
5908:The Kleene Symposium
5843:
5816:
5784:
5749:
5717:
5693:
5666:
5620:
5593:
5560:
5540:
5536:has many-one degree
5476:
5452:
5425:
5421:, there is a member
5405:
5378:
5351:
5323:
5287:
5263:
5229:
5188:
5158:
5134:
5097:
5070:
5036:
5009:
4985:
4965:
4941:
4917:
4889:
4865:
4836:
4812:
4788:
4764:
4760:is also a member of
4744:
4709:
4685:
4665:
4636:
4612:
4588:
4564:
4496:
4472:
4443:
4384:
4357:
4333:
4322:{\displaystyle f(e)}
4304:
4284:
4264:
4240:
4214:
4178:
4151:
4127:
4095:
4063:
4031:
4007:
3975:
3951:
3943:analytical hierarchy
3913:
3889:
3869:
3822:
3802:
3775:
3746:
3713:
3683:
3648:
3616:
3580:
3560:
3533:
3509:
3479:
3455:
3426:
3398:
3359:
3323:
3287:
3216:
3166:
3135:
3073:
3053:
3027:
2988:
2962:
2931:
2898:
2878:
2858:
2838:
2812:
2784:
2764:
2736:
2709:
2683:
2653:
2624:
2600:
2576:
2547:
2527:
2480:
2426:
2393:
2373:
2353:
2327:
2293:
2265:
2235:
2215:
2180:
2152:
2098:
2065:
2045:
2025:
1990:
1952:
1902:
1856:
1821:
1788:
1713:
1684:
1629:
1587:
1567:
1534:
1514:
1494:
1474:
1450:
1420:
1365:
1345:
1318:
1298:
1274:
1248:
1218:
1185:
1157:
1137:
1109:
1083:
1063:
1034:
954:
782:
664:
644:
620:
594:
454:
400:
373:
340:
316:
286:
266:
242:
222:
186:
142:
110:
78:
33:
22:computability theory
5801:
5766:
5734:
5472:such that the path
5214:
5093:In fact, there are
4195:
4112:
4080:
4048:
3992:
3930:
3865:of notations below
3705:computable ordinals
3665:
3633:
2254:{\displaystyle |p|}
1807:{\displaystyle |p|}
1439:{\displaystyle |p|}
1237:{\displaystyle |p|}
1204:{\displaystyle |p|}
305:{\displaystyle |p|}
127:
95:
5874:Computable ordinal
5853:
5826:
5802:
5787:
5767:
5752:
5735:
5720:
5703:
5679:
5649:
5606:
5579:
5546:
5526:
5462:
5438:
5411:
5388:
5364:
5333:
5306:
5273:
5249:
5215:
5197:
5171:
5144:
5117:
5080:
5056:
5019:
4995:
4971:
4951:
4927:
4909:is non-maximal.
4899:
4875:
4861:) every member of
4851:
4822:
4798:
4774:
4750:
4730:
4695:
4671:
4651:
4622:
4598:
4574:
4538:
4482:
4458:
4426:
4370:
4343:
4319:
4290:
4270:
4250:
4224:
4208:many-one reducible
4196:
4181:
4161:
4137:
4113:
4098:
4081:
4066:
4049:
4034:
4017:
3993:
3978:
3961:
3931:
3916:
3899:
3875:
3855:
3808:
3785:
3761:
3728:
3693:
3666:
3651:
3634:
3619:
3612:and is denoted by
3595:
3566:
3543:
3519:
3489:
3465:
3441:
3410:
3384:
3345:
3309:
3260:
3198:
3149:
3121:
3059:
3039:
3013:
2974:
2945:
2917:
2884:
2864:
2844:
2824:
2794:
2770:
2750:
2719:
2695:
2669:
2636:
2606:
2586:
2562:
2533:
2513:
2466:
2412:
2379:
2369:is reachable from
2359:
2339:
2313:
2271:
2251:
2221:
2201:
2176:. In other words,
2166:
2138:
2084:
2051:
2031:
2011:
1973:
1934:
1888:
1842:
1804:
1774:
1699:
1670:
1615:
1573:
1553:
1520:
1500:
1480:
1460:
1436:
1403:
1351:
1331:
1304:
1284:
1260:
1234:
1201:
1167:
1143:
1115:
1095:
1069:
1049:
1017:
939:
910:
768:
650:
626:
606:
578:
438:
383:
355:
326:
302:
272:
252:
228:
196:
180:ordinal arithmetic
152:
128:
113:
96:
81:
68:computable ordinal
43:
6005:978-0-262-68052-3
5549:{\displaystyle d}
5414:{\displaystyle d}
4974:{\displaystyle p}
4753:{\displaystyle q}
4674:{\displaystyle p}
4293:{\displaystyle e}
4273:{\displaystyle f}
3878:{\displaystyle p}
3811:{\displaystyle p}
3798:For any notation
3663:
3631:
3569:{\displaystyle n}
2887:{\displaystyle 2}
2867:{\displaystyle 0}
2847:{\displaystyle q}
2780:is a notation of
2773:{\displaystyle p}
2649:For any notation
2382:{\displaystyle p}
2362:{\displaystyle q}
2274:{\displaystyle p}
2224:{\displaystyle q}
2054:{\displaystyle p}
2034:{\displaystyle q}
1576:{\displaystyle e}
1523:{\displaystyle p}
1354:{\displaystyle q}
1307:{\displaystyle p}
1146:{\displaystyle p}
901:
671:
653:{\displaystyle e}
629:{\displaystyle e}
282:is a notation is
275:{\displaystyle p}
231:{\displaystyle p}
125:
93:
64:ordinal notations
60:ordinal notations
58:when regarded as
6066:
6044:
6008:
5990:
5954:
5953:
5923:
5920:
5911:
5900:
5884:Ordinal notation
5862:
5860:
5859:
5854:
5852:
5851:
5835:
5833:
5832:
5827:
5825:
5824:
5811:
5809:
5808:
5803:
5800:
5795:
5776:
5774:
5773:
5768:
5765:
5760:
5744:
5742:
5741:
5736:
5733:
5728:
5712:
5710:
5709:
5704:
5702:
5701:
5688:
5686:
5685:
5680:
5678:
5677:
5658:
5656:
5655:
5650:
5642:
5637:
5636:
5627:
5615:
5613:
5612:
5607:
5605:
5604:
5588:
5586:
5585:
5580:
5578:
5577:
5555:
5553:
5552:
5547:
5535:
5533:
5532:
5527:
5522:
5521:
5512:
5511:
5510:
5485:
5484:
5471:
5469:
5468:
5463:
5461:
5460:
5447:
5445:
5444:
5439:
5437:
5436:
5420:
5418:
5417:
5412:
5397:
5395:
5394:
5389:
5387:
5386:
5373:
5371:
5370:
5365:
5363:
5362:
5342:
5340:
5339:
5334:
5332:
5331:
5315:
5313:
5312:
5307:
5299:
5298:
5282:
5280:
5279:
5274:
5272:
5271:
5258:
5256:
5255:
5250:
5248:
5247:
5246:
5245:
5224:
5222:
5221:
5216:
5213:
5205:
5180:
5178:
5177:
5172:
5170:
5169:
5153:
5151:
5150:
5145:
5143:
5142:
5126:
5124:
5123:
5118:
5116:
5115:
5114:
5113:
5089:
5087:
5086:
5081:
5079:
5078:
5065:
5063:
5062:
5057:
5055:
5054:
5053:
5052:
5028:
5026:
5025:
5020:
5018:
5017:
5004:
5002:
5001:
4996:
4994:
4993:
4980:
4978:
4977:
4972:
4960:
4958:
4957:
4952:
4950:
4949:
4936:
4934:
4933:
4928:
4926:
4925:
4908:
4906:
4905:
4900:
4898:
4897:
4884:
4882:
4881:
4876:
4874:
4873:
4860:
4858:
4857:
4852:
4850:
4849:
4848:
4831:
4829:
4828:
4823:
4821:
4820:
4807:
4805:
4804:
4799:
4797:
4796:
4783:
4781:
4780:
4775:
4773:
4772:
4759:
4757:
4756:
4751:
4739:
4737:
4736:
4731:
4726:
4725:
4724:
4704:
4702:
4701:
4696:
4694:
4693:
4680:
4678:
4677:
4672:
4660:
4658:
4657:
4652:
4650:
4649:
4648:
4631:
4629:
4628:
4623:
4621:
4620:
4607:
4605:
4604:
4599:
4597:
4596:
4583:
4581:
4580:
4575:
4573:
4572:
4547:
4545:
4544:
4539:
4534:
4533:
4532:
4491:
4489:
4488:
4483:
4481:
4480:
4467:
4465:
4464:
4459:
4457:
4456:
4455:
4435:
4433:
4432:
4427:
4410:
4409:
4408:
4379:
4377:
4376:
4371:
4369:
4368:
4352:
4350:
4349:
4344:
4342:
4341:
4328:
4326:
4325:
4320:
4299:
4297:
4296:
4291:
4279:
4277:
4276:
4271:
4259:
4257:
4256:
4251:
4249:
4248:
4233:
4231:
4230:
4225:
4223:
4222:
4205:
4203:
4202:
4197:
4194:
4189:
4170:
4168:
4167:
4162:
4160:
4159:
4146:
4144:
4143:
4138:
4136:
4135:
4122:
4120:
4119:
4114:
4111:
4106:
4090:
4088:
4087:
4082:
4079:
4074:
4058:
4056:
4055:
4050:
4047:
4042:
4026:
4024:
4023:
4018:
4016:
4015:
4003:-complete (i.e.
4002:
4000:
3999:
3994:
3991:
3986:
3970:
3968:
3967:
3962:
3960:
3959:
3940:
3938:
3937:
3932:
3929:
3924:
3908:
3906:
3905:
3900:
3898:
3897:
3884:
3882:
3881:
3876:
3864:
3862:
3861:
3856:
3848:
3847:
3846:
3817:
3815:
3814:
3809:
3794:
3792:
3791:
3786:
3784:
3783:
3770:
3768:
3767:
3762:
3760:
3759:
3758:
3737:
3735:
3734:
3729:
3727:
3726:
3725:
3703:are exactly the
3702:
3700:
3699:
3694:
3692:
3691:
3675:
3673:
3672:
3667:
3664:
3661:
3659:
3643:
3641:
3640:
3635:
3632:
3629:
3627:
3604:
3602:
3601:
3596:
3594:
3593:
3592:
3576:usually denoted
3575:
3573:
3572:
3567:
3552:
3550:
3549:
3544:
3542:
3541:
3528:
3526:
3525:
3520:
3518:
3517:
3498:
3496:
3495:
3490:
3488:
3487:
3474:
3472:
3471:
3466:
3464:
3463:
3450:
3448:
3447:
3442:
3440:
3439:
3438:
3419:
3417:
3416:
3411:
3393:
3391:
3390:
3385:
3376:
3375:
3374:
3354:
3352:
3351:
3346:
3338:
3330:
3318:
3316:
3315:
3310:
3302:
3294:
3269:
3267:
3266:
3261:
3253:
3252:
3240:
3239:
3207:
3205:
3204:
3199:
3182:
3158:
3156:
3155:
3150:
3148:
3130:
3128:
3127:
3122:
3068:
3066:
3065:
3060:
3048:
3046:
3045:
3040:
3022:
3020:
3019:
3014:
3012:
3011:
2983:
2981:
2980:
2975:
2954:
2952:
2951:
2946:
2944:
2926:
2924:
2923:
2918:
2916:
2915:
2893:
2891:
2890:
2885:
2873:
2871:
2870:
2865:
2853:
2851:
2850:
2845:
2833:
2831:
2830:
2825:
2803:
2801:
2800:
2795:
2793:
2792:
2779:
2777:
2776:
2771:
2759:
2757:
2756:
2751:
2749:
2728:
2726:
2725:
2720:
2718:
2717:
2704:
2702:
2701:
2696:
2678:
2676:
2675:
2670:
2668:
2667:
2645:
2643:
2642:
2637:
2615:
2613:
2612:
2607:
2595:
2593:
2592:
2587:
2585:
2584:
2571:
2569:
2568:
2563:
2561:
2560:
2559:
2542:
2540:
2539:
2534:
2522:
2520:
2519:
2514:
2475:
2473:
2472:
2467:
2444:
2443:
2421:
2419:
2418:
2413:
2405:
2404:
2388:
2386:
2385:
2380:
2368:
2366:
2365:
2360:
2348:
2346:
2345:
2340:
2322:
2320:
2319:
2314:
2312:
2280:
2278:
2277:
2272:
2260:
2258:
2257:
2252:
2250:
2242:
2230:
2228:
2227:
2222:
2210:
2208:
2207:
2202:
2197:
2196:
2195:
2175:
2173:
2172:
2167:
2165:
2147:
2145:
2144:
2139:
2116:
2115:
2093:
2091:
2090:
2085:
2077:
2076:
2060:
2058:
2057:
2052:
2040:
2038:
2037:
2032:
2020:
2018:
2017:
2012:
2007:
2006:
2005:
1982:
1980:
1979:
1974:
1969:
1968:
1967:
1943:
1941:
1940:
1935:
1933:
1925:
1917:
1909:
1897:
1895:
1894:
1889:
1887:
1879:
1871:
1863:
1851:
1849:
1848:
1843:
1838:
1837:
1836:
1813:
1811:
1810:
1805:
1803:
1795:
1783:
1781:
1780:
1775:
1761:
1756:
1755:
1746:
1738:
1733:
1732:
1723:
1708:
1706:
1705:
1700:
1698:
1697:
1696:
1679:
1677:
1676:
1671:
1657:
1656:
1644:
1643:
1624:
1622:
1621:
1616:
1614:
1606:
1582:
1580:
1579:
1574:
1562:
1560:
1559:
1554:
1552:
1551:
1529:
1527:
1526:
1521:
1509:
1507:
1506:
1501:
1489:
1487:
1486:
1481:
1469:
1467:
1466:
1461:
1459:
1458:
1445:
1443:
1442:
1437:
1435:
1427:
1412:
1410:
1409:
1404:
1396:
1388:
1380:
1372:
1360:
1358:
1357:
1352:
1340:
1338:
1337:
1332:
1330:
1329:
1313:
1311:
1310:
1305:
1293:
1291:
1290:
1285:
1283:
1282:
1269:
1267:
1266:
1261:
1243:
1241:
1240:
1235:
1233:
1225:
1210:
1208:
1207:
1202:
1200:
1192:
1176:
1174:
1173:
1168:
1166:
1165:
1152:
1150:
1149:
1144:
1124:
1122:
1121:
1116:
1104:
1102:
1101:
1096:
1078:
1076:
1075:
1070:
1058:
1056:
1055:
1050:
1048:
1047:
1046:
1026:
1024:
1023:
1018:
1013:
1012:
1011:
992:
991:
990:
971:
970:
969:
948:
946:
945:
940:
938:
915:
909:
897:
892:
891:
876:
868:
867:
852:
851:
850:
810:
809:
800:
799:
777:
775:
774:
769:
740:
739:
738:
698:
697:
673:
672:
669:
659:
657:
656:
651:
635:
633:
632:
627:
615:
613:
612:
607:
587:
585:
584:
579:
577:
576:
567:
566:
565:
537:
532:
531:
522:
514:
513:
504:
503:
485:
477:
469:
468:
447:
445:
444:
439:
431:
423:
415:
414:
392:
390:
389:
384:
382:
381:
367:partial ordering
364:
362:
361:
356:
354:
353:
352:
335:
333:
332:
327:
325:
324:
311:
309:
308:
303:
301:
293:
281:
279:
278:
273:
261:
259:
258:
253:
251:
250:
237:
235:
234:
229:
205:
203:
202:
197:
195:
194:
161:
159:
158:
153:
151:
150:
137:
135:
134:
129:
126:
123:
121:
105:
103:
102:
97:
94:
91:
89:
52:
50:
49:
44:
42:
41:
6074:
6073:
6069:
6068:
6067:
6065:
6064:
6063:
6059:Ordinal numbers
6049:
6048:
6047:
6026:10.2307/2964544
6006:
5972:10.2307/2267778
5927:
5926:
5921:
5914:
5902:S. G. Simpson,
5901:
5897:
5892:
5870:
5847:
5846:
5844:
5841:
5840:
5820:
5819:
5817:
5814:
5813:
5796:
5791:
5785:
5782:
5781:
5761:
5756:
5750:
5747:
5746:
5729:
5724:
5718:
5715:
5714:
5697:
5696:
5694:
5691:
5690:
5673:
5669:
5667:
5664:
5663:
5638:
5632:
5628:
5623:
5621:
5618:
5617:
5600:
5596:
5594:
5591:
5590:
5573:
5569:
5561:
5558:
5557:
5541:
5538:
5537:
5517:
5513:
5506:
5505:
5501:
5480:
5479:
5477:
5474:
5473:
5456:
5455:
5453:
5450:
5449:
5432:
5428:
5426:
5423:
5422:
5406:
5403:
5402:
5382:
5381:
5379:
5376:
5375:
5358:
5354:
5352:
5349:
5348:
5327:
5326:
5324:
5321:
5320:
5294:
5290:
5288:
5285:
5284:
5267:
5266:
5264:
5261:
5260:
5241:
5237:
5236:
5232:
5230:
5227:
5226:
5206:
5201:
5189:
5186:
5185:
5165:
5161:
5159:
5156:
5155:
5138:
5137:
5135:
5132:
5131:
5109:
5105:
5104:
5100:
5098:
5095:
5094:
5074:
5073:
5071:
5068:
5067:
5048:
5044:
5043:
5039:
5037:
5034:
5033:
5013:
5012:
5010:
5007:
5006:
4989:
4988:
4986:
4983:
4982:
4966:
4963:
4962:
4945:
4944:
4942:
4939:
4938:
4921:
4920:
4918:
4915:
4914:
4893:
4892:
4890:
4887:
4886:
4869:
4868:
4866:
4863:
4862:
4844:
4843:
4839:
4837:
4834:
4833:
4816:
4815:
4813:
4810:
4809:
4792:
4791:
4789:
4786:
4785:
4768:
4767:
4765:
4762:
4761:
4745:
4742:
4741:
4720:
4719:
4715:
4710:
4707:
4706:
4689:
4688:
4686:
4683:
4682:
4666:
4663:
4662:
4644:
4643:
4639:
4637:
4634:
4633:
4616:
4615:
4613:
4610:
4609:
4592:
4591:
4589:
4586:
4585:
4568:
4567:
4565:
4562:
4561:
4558:
4556:
4528:
4527:
4523:
4497:
4494:
4493:
4476:
4475:
4473:
4470:
4469:
4451:
4450:
4446:
4444:
4441:
4440:
4404:
4403:
4399:
4385:
4382:
4381:
4364:
4360:
4358:
4355:
4354:
4337:
4336:
4334:
4331:
4330:
4329:is a member of
4305:
4302:
4301:
4285:
4282:
4281:
4265:
4262:
4261:
4244:
4243:
4241:
4238:
4237:
4218:
4217:
4215:
4212:
4211:
4190:
4185:
4179:
4176:
4175:
4155:
4154:
4152:
4149:
4148:
4131:
4130:
4128:
4125:
4124:
4107:
4102:
4096:
4093:
4092:
4075:
4070:
4064:
4061:
4060:
4043:
4038:
4032:
4029:
4028:
4011:
4010:
4008:
4005:
4004:
3987:
3982:
3976:
3973:
3972:
3955:
3954:
3952:
3949:
3948:
3925:
3920:
3914:
3911:
3910:
3893:
3892:
3890:
3887:
3886:
3870:
3867:
3866:
3842:
3841:
3837:
3823:
3820:
3819:
3803:
3800:
3799:
3779:
3778:
3776:
3773:
3772:
3754:
3753:
3749:
3747:
3744:
3743:
3721:
3720:
3716:
3714:
3711:
3710:
3687:
3686:
3684:
3681:
3680:
3660:
3655:
3649:
3646:
3645:
3628:
3623:
3617:
3614:
3613:
3588:
3587:
3583:
3581:
3578:
3577:
3561:
3558:
3557:
3537:
3536:
3534:
3531:
3530:
3513:
3512:
3510:
3507:
3506:
3483:
3482:
3480:
3477:
3476:
3459:
3458:
3456:
3453:
3452:
3434:
3433:
3429:
3427:
3424:
3423:
3399:
3396:
3395:
3370:
3369:
3365:
3360:
3357:
3356:
3334:
3326:
3324:
3321:
3320:
3298:
3290:
3288:
3285:
3284:
3280:
3278:
3248:
3244:
3235:
3231:
3217:
3214:
3213:
3178:
3167:
3164:
3163:
3144:
3136:
3133:
3132:
3074:
3071:
3070:
3054:
3051:
3050:
3028:
3025:
3024:
3007:
3003:
2989:
2986:
2985:
2963:
2960:
2959:
2940:
2932:
2929:
2928:
2911:
2907:
2899:
2896:
2895:
2879:
2876:
2875:
2859:
2856:
2855:
2839:
2836:
2835:
2813:
2810:
2809:
2788:
2787:
2785:
2782:
2781:
2765:
2762:
2761:
2745:
2737:
2734:
2733:
2713:
2712:
2710:
2707:
2706:
2684:
2681:
2680:
2663:
2662:
2654:
2651:
2650:
2625:
2622:
2621:
2601:
2598:
2597:
2580:
2579:
2577:
2574:
2573:
2555:
2554:
2550:
2548:
2545:
2544:
2528:
2525:
2524:
2523:. The relation
2481:
2478:
2477:
2439:
2435:
2427:
2424:
2423:
2400:
2396:
2394:
2391:
2390:
2374:
2371:
2370:
2354:
2351:
2350:
2328:
2325:
2324:
2308:
2294:
2291:
2290:
2287:
2266:
2263:
2262:
2246:
2238:
2236:
2233:
2232:
2216:
2213:
2212:
2191:
2190:
2186:
2181:
2178:
2177:
2161:
2153:
2150:
2149:
2111:
2107:
2099:
2096:
2095:
2072:
2068:
2066:
2063:
2062:
2046:
2043:
2042:
2026:
2023:
2022:
2001:
2000:
1996:
1991:
1988:
1987:
1963:
1962:
1958:
1953:
1950:
1949:
1929:
1921:
1913:
1905:
1903:
1900:
1899:
1883:
1875:
1867:
1859:
1857:
1854:
1853:
1832:
1831:
1827:
1822:
1819:
1818:
1799:
1791:
1789:
1786:
1785:
1757:
1751:
1747:
1742:
1734:
1728:
1724:
1719:
1714:
1711:
1710:
1692:
1691:
1687:
1685:
1682:
1681:
1652:
1648:
1639:
1635:
1630:
1627:
1626:
1610:
1602:
1588:
1585:
1584:
1568:
1565:
1564:
1547:
1543:
1535:
1532:
1531:
1530:is of the form
1515:
1512:
1511:
1495:
1492:
1491:
1475:
1472:
1471:
1454:
1453:
1451:
1448:
1447:
1431:
1423:
1421:
1418:
1417:
1392:
1384:
1376:
1368:
1366:
1363:
1362:
1346:
1343:
1342:
1325:
1321:
1319:
1316:
1315:
1314:is of the form
1299:
1296:
1295:
1278:
1277:
1275:
1272:
1271:
1249:
1246:
1245:
1229:
1221:
1219:
1216:
1215:
1196:
1188:
1186:
1183:
1182:
1161:
1160:
1158:
1155:
1154:
1138:
1135:
1134:
1131:
1110:
1107:
1106:
1084:
1081:
1080:
1064:
1061:
1060:
1042:
1041:
1037:
1035:
1032:
1031:
1007:
1006:
1002:
986:
985:
981:
965:
964:
960:
955:
952:
951:
934:
911:
905:
893:
887:
883:
872:
863:
859:
846:
845:
841:
805:
804:
795:
791:
783:
780:
779:
734:
733:
729:
693:
692:
668:
667:
665:
662:
661:
645:
642:
641:
621:
618:
617:
595:
592:
591:
572:
568:
561:
560:
556:
533:
527:
523:
518:
509:
508:
499:
495:
481:
473:
464:
463:
455:
452:
451:
427:
419:
410:
409:
401:
398:
397:
377:
376:
374:
371:
370:
348:
347:
343:
341:
338:
337:
320:
319:
317:
314:
313:
297:
289:
287:
284:
283:
267:
264:
263:
246:
245:
243:
240:
239:
223:
220:
219:
216:
190:
189:
187:
184:
183:
171:natural numbers
146:
145:
143:
140:
139:
122:
117:
111:
108:
107:
90:
85:
79:
76:
75:
56:natural numbers
37:
36:
34:
31:
30:
12:
11:
5:
6072:
6062:
6061:
6046:
6045:
6020:(4): 383–390,
6009:
6004:
5991:
5955:
5944:(4): 224–232,
5928:
5925:
5924:
5912:
5894:
5893:
5891:
5888:
5887:
5886:
5881:
5876:
5869:
5866:
5865:
5864:
5850:
5837:
5823:
5812:paths through
5799:
5794:
5790:
5778:
5764:
5759:
5755:
5732:
5727:
5723:
5700:
5689:paths through
5676:
5672:
5660:
5648:
5645:
5641:
5635:
5631:
5626:
5603:
5599:
5576:
5572:
5568:
5565:
5545:
5525:
5520:
5516:
5509:
5504:
5500:
5497:
5494:
5491:
5488:
5483:
5459:
5435:
5431:
5410:
5399:
5385:
5361:
5357:
5347:a multiple of
5330:
5317:
5305:
5302:
5297:
5293:
5270:
5244:
5240:
5235:
5212:
5209:
5204:
5200:
5196:
5193:
5182:
5168:
5164:
5141:
5127:maximal paths
5112:
5108:
5103:
5091:
5077:
5051:
5047:
5042:
5030:
5016:
4992:
4970:
4948:
4924:
4896:
4872:
4847:
4842:
4819:
4795:
4771:
4749:
4729:
4723:
4718:
4714:
4692:
4670:
4647:
4642:
4619:
4595:
4571:
4557:
4554:
4551:
4550:
4549:
4537:
4531:
4526:
4522:
4519:
4516:
4513:
4510:
4507:
4504:
4501:
4479:
4454:
4449:
4437:
4425:
4422:
4419:
4416:
4413:
4407:
4402:
4398:
4395:
4392:
4389:
4367:
4363:
4340:
4318:
4315:
4312:
4309:
4289:
4269:
4247:
4235:
4221:
4193:
4188:
4184:
4172:
4158:
4134:
4110:
4105:
4101:
4078:
4073:
4069:
4046:
4041:
4037:
4014:
3990:
3985:
3981:
3958:
3946:
3928:
3923:
3919:
3896:
3874:
3854:
3851:
3845:
3840:
3836:
3833:
3830:
3827:
3807:
3796:
3782:
3757:
3752:
3724:
3719:
3708:
3690:
3677:
3658:
3654:
3626:
3622:
3606:
3591:
3586:
3565:
3554:
3540:
3516:
3504:
3486:
3462:
3437:
3432:
3421:
3409:
3406:
3403:
3383:
3379:
3373:
3368:
3364:
3344:
3341:
3337:
3333:
3329:
3308:
3305:
3301:
3297:
3293:
3279:
3276:
3273:
3272:
3271:
3259:
3256:
3251:
3247:
3243:
3238:
3234:
3230:
3227:
3224:
3221:
3197:
3194:
3191:
3188:
3185:
3181:
3177:
3174:
3171:
3160:
3147:
3143:
3140:
3120:
3117:
3114:
3111:
3108:
3105:
3102:
3099:
3096:
3093:
3090:
3087:
3084:
3081:
3078:
3058:
3038:
3035:
3032:
3010:
3006:
3002:
2999:
2996:
2993:
2973:
2970:
2967:
2956:
2943:
2939:
2936:
2914:
2910:
2906:
2903:
2883:
2863:
2843:
2823:
2820:
2817:
2791:
2769:
2748:
2744:
2741:
2716:
2694:
2691:
2688:
2666:
2661:
2658:
2635:
2632:
2629:
2605:
2583:
2558:
2553:
2532:
2512:
2509:
2506:
2503:
2500:
2497:
2494:
2491:
2488:
2485:
2465:
2462:
2459:
2456:
2453:
2450:
2447:
2442:
2438:
2434:
2431:
2411:
2408:
2403:
2399:
2378:
2358:
2338:
2335:
2332:
2311:
2307:
2304:
2301:
2298:
2289:For arbitrary
2286:
2283:
2270:
2249:
2245:
2241:
2220:
2200:
2194:
2189:
2185:
2164:
2160:
2157:
2137:
2134:
2131:
2128:
2125:
2122:
2119:
2114:
2110:
2106:
2103:
2083:
2080:
2075:
2071:
2050:
2030:
2010:
2004:
1999:
1995:
1972:
1966:
1961:
1957:
1932:
1928:
1924:
1920:
1916:
1912:
1908:
1886:
1882:
1878:
1874:
1870:
1866:
1862:
1841:
1835:
1830:
1826:
1802:
1798:
1794:
1773:
1770:
1767:
1764:
1760:
1754:
1750:
1745:
1741:
1737:
1731:
1727:
1722:
1718:
1695:
1690:
1669:
1666:
1663:
1660:
1655:
1651:
1647:
1642:
1638:
1634:
1613:
1609:
1605:
1601:
1598:
1595:
1592:
1572:
1550:
1546:
1542:
1539:
1519:
1499:
1479:
1457:
1434:
1430:
1426:
1402:
1399:
1395:
1391:
1387:
1383:
1379:
1375:
1371:
1350:
1328:
1324:
1303:
1281:
1270:. In Kleene's
1259:
1256:
1253:
1232:
1228:
1224:
1199:
1195:
1191:
1164:
1142:
1130:
1127:
1114:
1094:
1091:
1088:
1068:
1045:
1040:
1028:
1027:
1016:
1010:
1005:
1001:
998:
995:
989:
984:
980:
977:
974:
968:
963:
959:
949:
937:
933:
930:
927:
924:
921:
918:
914:
908:
904:
900:
896:
890:
886:
882:
879:
875:
871:
866:
862:
858:
855:
849:
844:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
808:
803:
798:
794:
790:
787:
767:
764:
761:
758:
755:
752:
749:
746:
743:
737:
732:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
696:
691:
688:
685:
682:
679:
676:
649:
625:
605:
602:
599:
588:
575:
571:
564:
559:
555:
552:
549:
546:
543:
540:
536:
530:
526:
521:
517:
512:
507:
502:
498:
494:
491:
488:
484:
480:
476:
472:
467:
462:
459:
449:
437:
434:
430:
426:
422:
418:
413:
408:
405:
380:
351:
346:
323:
300:
296:
292:
271:
249:
227:
215:
212:
193:
149:
120:
116:
88:
84:
62:. It contains
40:
9:
6:
4:
3:
2:
6071:
6060:
6057:
6056:
6054:
6043:
6039:
6035:
6031:
6027:
6023:
6019:
6015:
6010:
6007:
6001:
5997:
5992:
5989:
5985:
5981:
5977:
5973:
5969:
5965:
5961:
5956:
5952:
5947:
5943:
5939:
5935:
5930:
5929:
5919:
5917:
5909:
5905:
5899:
5895:
5885:
5882:
5880:
5877:
5875:
5872:
5871:
5838:
5797:
5792:
5779:
5762:
5757:
5730:
5725:
5674:
5661:
5646:
5643:
5633:
5629:
5601:
5597:
5589:, a notation
5574:
5570:
5566:
5563:
5543:
5518:
5514:
5502:
5498:
5495:
5492:
5486:
5433:
5429:
5408:
5400:
5359:
5355:
5346:
5318:
5303:
5300:
5295:
5291:
5242:
5233:
5210:
5207:
5202:
5198:
5194:
5191:
5183:
5166:
5162:
5130:
5110:
5101:
5092:
5049:
5040:
5031:
4968:
4912:
4911:
4910:
4840:
4747:
4727:
4716:
4712:
4668:
4640:
4535:
4524:
4520:
4517:
4511:
4508:
4505:
4447:
4438:
4417:
4411:
4400:
4396:
4393:
4390:
4365:
4361:
4313:
4307:
4287:
4280:such that if
4267:
4236:
4209:
4191:
4186:
4174:In fact, any
4173:
4108:
4103:
4076:
4071:
4044:
4039:
3988:
3983:
3947:
3944:
3926:
3921:
3872:
3849:
3838:
3834:
3831:
3828:
3805:
3797:
3750:
3741:
3717:
3709:
3706:
3678:
3656:
3652:
3624:
3620:
3611:
3607:
3584:
3563:
3555:
3505:
3502:
3430:
3422:
3407:
3404:
3401:
3381:
3377:
3366:
3362:
3342:
3339:
3331:
3306:
3303:
3295:
3282:
3281:
3257:
3254:
3249:
3245:
3241:
3236:
3232:
3228:
3225:
3222:
3219:
3211:
3192:
3189:
3186:
3183:
3175:
3172:
3161:
3141:
3138:
3115:
3112:
3109:
3100:
3094:
3088:
3079:
3056:
3033:
3008:
3004:
3000:
2997:
2994:
2991:
2971:
2968:
2965:
2957:
2937:
2934:
2912:
2908:
2904:
2901:
2881:
2874:, a power of
2861:
2841:
2821:
2818:
2815:
2807:
2806:
2805:
2767:
2742:
2739:
2730:
2692:
2689:
2686:
2659:
2656:
2647:
2633:
2630:
2627:
2619:
2603:
2551:
2530:
2504:
2495:
2492:
2489:
2486:
2483:
2460:
2451:
2440:
2436:
2432:
2429:
2409:
2401:
2397:
2376:
2356:
2336:
2333:
2330:
2305:
2302:
2299:
2296:
2282:
2268:
2243:
2218:
2198:
2187:
2183:
2158:
2155:
2132:
2123:
2112:
2108:
2104:
2101:
2081:
2073:
2069:
2048:
2028:
2008:
1997:
1993:
1986:In order for
1984:
1970:
1959:
1955:
1947:
1926:
1918:
1910:
1880:
1872:
1864:
1839:
1828:
1824:
1815:
1796:
1768:
1765:
1762:
1752:
1748:
1739:
1729:
1725:
1688:
1664:
1661:
1658:
1653:
1649:
1645:
1640:
1636:
1599:
1593:
1570:
1548:
1544:
1540:
1537:
1517:
1497:
1477:
1428:
1414:
1400:
1397:
1389:
1381:
1373:
1348:
1326:
1322:
1301:
1257:
1254:
1251:
1226:
1212:
1193:
1180:
1140:
1126:
1112:
1092:
1089:
1086:
1066:
1038:
1014:
1003:
999:
993:
982:
978:
975:
972:
961:
957:
950:
928:
919:
906:
898:
888:
884:
880:
877:
869:
864:
860:
856:
853:
842:
835:
826:
820:
817:
811:
801:
796:
792:
788:
785:
759:
756:
753:
744:
730:
723:
714:
705:
699:
689:
680:
660:is total and
647:
639:
623:
600:
589:
573:
569:
557:
553:
550:
547:
544:
541:
538:
528:
524:
515:
505:
500:
496:
489:
486:
478:
470:
460:
457:
450:
435:
432:
424:
416:
406:
403:
396:
395:
394:
368:
344:
294:
269:
225:
211:
209:
181:
176:
172:
168:
163:
118:
114:
86:
82:
73:
69:
65:
61:
57:
53:
28:
23:
19:
6017:
6013:
5995:
5963:
5959:
5941:
5937:
5907:
5898:
5780:There exist
5662:There exist
5659:. (Jockusch)
5616:exists with
5344:
5319:Further, if
5225:, there are
5128:
4885:, otherwise
4584:is a subset
4559:
4548:. (Jockusch)
3501:well-founded
3210:well-founded
2731:
2648:
2543:agrees with
2288:
1985:
1945:
1816:
1415:
1213:
1178:
1177:is called a
1153:of Kleene's
1132:
1029:
369:of Kleene's
217:
164:
25:
15:
2323:, say that
1129:Explanation
5890:References
5713:which are
5283:of length
5154:of length
5032:There are
4560:A path in
4123:subset of
4059:and every
3818:, the set
2854:is either
1563:where the
1361:, so that
214:Definition
66:for every
18:set theory
5906:, p.269.
5789:Π
5754:Π
5722:Π
5671:ℵ
5647:α
5571:ω
5567:≥
5564:α
5496:∣
5356:ω
5316:. (Aczel)
5304:λ
5301:⋅
5292:ω
5239:ℵ
5199:ω
5192:λ
5163:ω
5107:ℵ
5046:ℵ
4784:. A path
4518:≤
4394:∣
4183:Π
4100:Σ
4068:Π
4036:Π
3980:Π
3918:Π
3832:∣
3653:ω
3621:ω
3408:β
3402:α
3343:β
3307:α
3255:≺
3242:≺
3229:≺
3190:≺
3176:∈
3142:∈
3095:≺
3057:≺
3001:⋅
2969:⪯
2938:∈
2927:for some
2905:⋅
2819:⪯
2743:∈
2690:≺
2660:∈
2631:≺
2604:≺
2531:≺
2487:∈
2446:↦
2433:⋅
2407:↦
2334:≺
2306:∈
2261:given by
2159:∈
2118:↦
2105:⋅
2079:↦
1817:Although
1772:⟩
1717:⟨
1668:⟩
1633:⟨
1608:→
1541:⋅
1498:β
1478:β
1252:α
1133:A member
1113:α
1093:γ
1087:α
1067:γ
997:→
976:∧
881:⋅
870:∧
857:⋅
815:∀
812:∧
802:∈
789:⋅
703:∀
700:∧
690:⊂
551:∧
542:α
516:∧
506:∈
493:→
490:α
471:∧
461:∈
417:∧
407:∈
175:effective
115:ω
83:ω
6053:Category
6042:33892829
5988:34314018
5868:See also
3162:The set
3131:for any
2958:For any
2808:For all
1852:implies
1179:notation
590:Suppose
106:. Since
6034:2964544
5980:2267778
4913:A path
4206:set is
3738:is not
3069:; i.e.
778:, then
616:is the
6040:
6032:
6002:
5986:
5978:
5129:within
2679:, all
2596:, but
1948:imply
27:Kleene
6038:S2CID
6030:JSTOR
5984:S2CID
5976:JSTOR
5374:then
4740:then
3941:(see
3475:, so
3394:then
3023:then
2984:, if
2894:, or
2620:: if
2349:when
2211:when
1944:does
670:range
640:. If
6000:ISBN
5503:<
5195:<
4841:<
4717:<
4705:and
4641:<
4401:<
4362:<
4353:and
3839:<
3751:<
3718:<
3431:<
3405:<
3367:<
3355:and
3319:and
2732:For
2552:<
2476:for
2422:and
2188:<
2148:for
2094:and
1998:<
1960:<
1919:<
1873:<
1829:<
1689:<
1090:<
1079:and
1039:<
1004:<
983:<
962:<
843:<
731:<
636:-th
558:<
345:<
336:and
20:and
6022:doi
5968:doi
5946:doi
5448:of
5345:not
4981:of
4608:of
4500:max
4210:to
4027:is
3971:is
3499:is
3283:If
3208:is
2616:is
2572:on
1946:not
1784:is
903:lim
365:(a
238:of
29:'s
16:In
6055::
6036:,
6028:,
6018:27
6016:,
5982:,
5974:,
5962:,
5942:44
5940:,
5936:,
5915:^
3662:CK
3630:CK
2834:,
2760:,
2729:.
2281:.
2021:,
1983:.
1898:,
1814:.
1413:.
1211:.
312:.
124:CK
92:CK
74:,
24:,
6024::
5970::
5964:3
5948::
5849:O
5822:O
5798:1
5793:1
5763:0
5758:1
5731:1
5726:1
5699:O
5675:0
5644:=
5640:|
5634:d
5630:e
5625:|
5602:d
5598:e
5575:2
5544:d
5524:}
5519:d
5515:e
5508:O
5499:p
5493:p
5490:{
5487:=
5482:P
5458:O
5434:d
5430:e
5409:d
5384:P
5360:2
5329:P
5296:2
5269:O
5243:0
5234:2
5211:K
5208:C
5203:1
5167:2
5140:O
5111:0
5102:2
5076:O
5050:0
5041:2
5015:P
4991:O
4969:p
4947:P
4923:P
4895:P
4871:P
4846:O
4818:O
4794:P
4770:P
4748:q
4728:p
4722:O
4713:q
4691:P
4669:p
4646:O
4618:O
4594:P
4570:O
4555:O
4536:q
4530:O
4525:+
4521:p
4515:}
4512:q
4509:,
4506:p
4503:{
4478:O
4453:O
4448:+
4436:.
4424:}
4421:)
4418:e
4415:(
4412:f
4406:O
4397:p
4391:p
4388:{
4366:e
4339:O
4317:)
4314:e
4311:(
4308:f
4288:e
4268:f
4246:O
4234:.
4220:O
4192:1
4187:1
4157:O
4133:O
4109:1
4104:1
4077:1
4072:1
4045:1
4040:1
4013:O
3989:1
3984:1
3957:O
3927:1
3922:1
3895:O
3873:p
3853:}
3850:p
3844:O
3835:q
3829:q
3826:{
3806:p
3795:.
3781:O
3756:O
3723:O
3689:O
3657:1
3625:1
3605:.
3590:O
3585:n
3564:n
3539:O
3515:O
3503:.
3485:O
3461:O
3436:O
3382:,
3378:j
3372:O
3363:i
3340:=
3336:|
3332:j
3328:|
3304:=
3300:|
3296:i
3292:|
3277:O
3270:.
3258:p
3250:0
3246:q
3237:1
3233:q
3226:.
3223:.
3220:.
3196:}
3193:p
3187:q
3184::
3180:N
3173:q
3170:{
3159:.
3146:N
3139:i
3119:)
3116:1
3113:+
3110:i
3107:(
3104:}
3101:e
3098:{
3092:)
3089:i
3086:(
3083:}
3080:e
3077:{
3037:}
3034:e
3031:{
3009:e
3005:5
2998:3
2995:=
2992:q
2972:p
2966:q
2955:.
2942:N
2935:e
2913:e
2909:5
2902:3
2882:2
2862:0
2842:q
2822:p
2816:q
2790:O
2768:p
2747:N
2740:p
2715:O
2693:p
2687:q
2665:O
2657:p
2634:p
2628:q
2582:O
2557:O
2511:)
2508:}
2505:e
2502:{
2499:(
2496:m
2493:o
2490:d
2484:i
2464:)
2461:i
2458:(
2455:}
2452:e
2449:{
2441:e
2437:5
2430:3
2410:n
2402:n
2398:2
2377:p
2357:q
2337:p
2331:q
2310:N
2303:q
2300:,
2297:p
2269:p
2248:|
2244:p
2240:|
2219:q
2199:p
2193:O
2184:q
2163:N
2156:i
2136:)
2133:i
2130:(
2127:}
2124:e
2121:{
2113:e
2109:5
2102:3
2082:n
2074:n
2070:2
2049:p
2029:q
2009:p
2003:O
1994:q
1971:p
1965:O
1956:q
1931:|
1927:p
1923:|
1915:|
1911:q
1907:|
1885:|
1881:p
1877:|
1869:|
1865:q
1861:|
1840:p
1834:O
1825:q
1801:|
1797:p
1793:|
1769:.
1766:.
1763:.
1759:|
1753:1
1749:q
1744:|
1740:,
1736:|
1730:0
1726:q
1721:|
1694:O
1665:.
1662:.
1659:.
1654:1
1650:q
1646:,
1641:0
1637:q
1612:N
1604:N
1600::
1597:}
1594:e
1591:{
1571:e
1549:e
1545:5
1538:3
1518:p
1456:O
1433:|
1429:p
1425:|
1401:1
1398:+
1394:|
1390:q
1386:|
1382:=
1378:|
1374:p
1370:|
1349:q
1327:q
1323:2
1302:p
1280:O
1258:1
1255:+
1231:|
1227:p
1223:|
1198:|
1194:p
1190:|
1163:O
1141:p
1044:O
1015:r
1009:O
1000:p
994:r
988:O
979:q
973:q
967:O
958:p
936:|
932:)
929:k
926:(
923:}
920:e
917:{
913:|
907:k
899:=
895:|
889:e
885:5
878:3
874:|
865:e
861:5
854:3
848:O
839:)
836:n
833:(
830:}
827:e
824:{
821:,
818:n
807:O
797:e
793:5
786:3
766:)
763:)
760:1
757:+
754:n
751:(
748:}
745:e
742:{
736:O
727:)
724:n
721:(
718:}
715:e
712:{
709:(
706:n
695:O
687:)
684:}
681:e
678:{
675:(
648:e
624:e
604:}
601:e
598:{
574:i
570:2
563:O
554:i
548:1
545:+
539:=
535:|
529:i
525:2
520:|
511:O
501:i
497:2
487:=
483:|
479:i
475:|
466:O
458:i
448:.
436:0
433:=
429:|
425:0
421:|
412:O
404:0
379:O
350:O
322:O
299:|
295:p
291:|
270:p
248:O
226:p
192:O
148:O
119:1
87:1
39:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.