753:, in descriptive set theory, is defined as a set of finite sequences that is closed under prefix operations. The parent in the tree of any sequence is the shorter sequence formed by removing its final element. Thus, any set of finite sequences can be augmented to form a tree, and the Kleene–Brouwer order is a natural ordering that may be given to this tree. It is a generalization to potentially-infinite trees of the
757:
of a finite tree: at every node of the tree, the child subtrees are given their left to right ordering, and the node itself comes after all its children. The fact that the Kleene–Brouwer order is a linear ordering (that is, that it is transitive as well as being total) follows immediately from this,
981:
in the tree. In this way, the total recursive functionals themselves can be classified into a hierarchy, according to the minimum value of the ordinal at the root of a computation tree, minimized over all computation trees that implement the functional. The Kleene–Brouwer order of a well-founded
79:
from finite trees to trees that are not necessarily finite. For trees over a well-ordered set, the Kleene–Brouwer order is itself a well-ordering if and only if the tree has no infinite branch. It is named after
500:
259:
982:
computation tree is itself a recursive well-ordering, and at least as large as the ordinal assigned to the tree, from which it follows that the levels of this hierarchy are indexed by
530:
462:
619:
198:
62:
939:
758:
as any three sequences on which transitivity is to be tested form (with their prefixes) a finite tree on which the Kleene–Brouwer order coincides with the postorder.
893:
583:
418:
389:
317:
288:
979:
959:
850:
803:
779:
739:
719:
699:
679:
659:
639:
554:
357:
337:
218:
162:
142:
122:
809:(having no infinitely long branches) if and only if the Kleene–Brouwer ordering is a well-ordering of the elements of the tree.
1072:
1045:
72:
of the other. In the Kleene–Brouwer order, the prefix is later than the longer sequence containing it, rather than earlier.
467:
226:
832:. A computation tree is well-founded if and only if the computation performed by it is total recursive. Each state
1210:
750:
1131:
85:
509:
1220:
1194:. See in particular section 26, "A digression concerning recursive linear orderings", pp. 419–422.
1104:
423:
588:
167:
1010:, or have been influenced by earlier work of the same authors leading to this work. Much later,
1100:
1003:
93:
17:
35:
1215:
1060:
898:
829:
806:
1190:
1082:
858:
559:
394:
365:
293:
264:
8:
1158:
826:
754:
81:
76:
65:
1040:(2nd ed.), Rhode Island: American Mathematical Society, pp. 148–149, 203–204,
1178:
964:
944:
835:
788:
764:
724:
704:
684:
664:
644:
624:
539:
342:
322:
203:
147:
127:
107:
1063:; Wainer, Stanley S. (2012), "2.8 Recursive type-2 functionals and well-foundedness",
1161:(1955), "On the forms of the predicates in the theory of constructive ordinals. II",
1068:
1041:
983:
1170:
822:
818:
1186:
1078:
1067:, Perspectives in Logic, Cambridge: Cambridge University Press, pp. 98–101,
853:
1204:
1136:
Koninklijke
Nederlandse Akademie van Wetenschappen, Proc. Section of Sciences
1096:
89:
761:
The significance of the Kleene–Brouwer ordering comes from the fact that if
782:
29:
1182:
533:
69:
1174:
1134:(1924), "Beweis, dass jede volle Funktion gleichmässig stetig ist",
1116:
1014:
studied the same ordering, and credited it to
Brouwer.
967:
947:
901:
861:
838:
791:
767:
727:
707:
687:
667:
647:
627:
591:
562:
542:
512:
495:{\displaystyle t\upharpoonright n=s\upharpoonright n}
470:
426:
397:
368:
345:
325:
296:
267:
254:{\displaystyle t\upharpoonright n=s\upharpoonright n}
229:
206:
170:
150:
130:
110:
75:
The Kleene–Brouwer order generalizes the notion of a
38:
1059:
32:on finite sequences over some linearly ordered set
973:
953:
933:
887:
844:
797:
773:
733:
713:
693:
673:
653:
633:
613:
577:
548:
524:
494:
456:
412:
383:
351:
331:
311:
282:
253:
212:
192:
156:
136:
116:
68:in how it handles the case when one sequence is a
56:
821:, the Kleene–Brouwer order may be applied to the
1202:
1095:
1007:
995:
1031:
1029:
1027:
1109:Journal de Mathématiques Pures et Appliquées
1002:. Brouwer does not cite any references, but
1035:
64:, that differs from the more commonly used
1024:
701:, and they are equal up to that point) or
852:in a computation tree may be assigned an
1130:
999:
1203:
1157:
1145:
1011:
895:, the supremum of the ordinal numbers
744:
144:are finite sequences of elements from
1006:argues that he may either have seen
812:
13:
1105:"Sur un ensemble non measurable B"
525:{\displaystyle t\upharpoonright n}
14:
1232:
741:on the first place they differ.
1163:American Journal of Mathematics
1151:
1124:
1089:
1053:
927:
922:
914:
909:
881:
876:
868:
863:
572:
566:
516:
486:
474:
451:
445:
436:
430:
407:
401:
378:
372:
306:
300:
277:
271:
245:
233:
51:
39:
1:
1036:Moschovakis, Yiannis (2009),
1017:
1008:Lusin & Sierpinski (1923)
996:Lusin & Sierpinski (1923)
99:
961:ranges over the children of
457:{\displaystyle t(n)<s(n)}
86:Luitzen Egbertus Jan Brouwer
7:
614:{\displaystyle t<_{KB}s}
193:{\displaystyle t<_{KB}s}
10:
1237:
1115:(2): 53–72, archived from
994:This ordering was used by
989:
556:up to but not including
57:{\displaystyle (X,<)}
1065:Proofs and computations
934:{\displaystyle 1+||y||}
1211:Descriptive set theory
1061:Schwichtenberg, Helmut
1038:Descriptive Set Theory
975:
955:
935:
889:
846:
825:of implementations of
799:
775:
735:
715:
695:
675:
655:
635:
615:
579:
550:
526:
496:
458:
414:
385:
353:
333:
313:
284:
255:
214:
194:
158:
138:
118:
58:
26:Lusin–Sierpiński order
18:descriptive set theory
976:
956:
936:
890:
888:{\displaystyle ||x||}
847:
800:
776:
736:
716:
696:
676:
656:
636:
616:
580:
551:
527:
497:
459:
415:
386:
354:
334:
314:
285:
256:
215:
195:
159:
139:
119:
59:
998:, and then again by
965:
945:
899:
859:
836:
789:
785:, then a tree over
765:
725:
721:is to the "left" of
705:
685:
665:
645:
625:
589:
578:{\displaystyle t(n)}
560:
540:
510:
468:
424:
413:{\displaystyle t(n)}
395:
384:{\displaystyle s(n)}
366:
343:
323:
312:{\displaystyle s(n)}
294:
283:{\displaystyle t(n)}
265:
227:
204:
168:
148:
128:
108:
36:
22:Kleene–Brouwer order
755:postorder traversal
745:Tree interpretation
585:. In simple terms,
506:Here, the notation
319:is undefined (i.e.
82:Stephen Cole Kleene
77:postorder traversal
66:lexicographic order
1101:Sierpinski, Waclaw
984:recursive ordinals
971:
951:
931:
885:
842:
795:
771:
731:
711:
691:
681:terminates before
671:
651:
631:
611:
575:
546:
522:
492:
454:
410:
381:
349:
329:
309:
280:
251:
220:such that either:
210:
190:
154:
134:
114:
54:
1132:Brouwer, L. E. J.
1074:978-0-521-51769-0
1047:978-0-8218-4813-5
974:{\displaystyle x}
954:{\displaystyle y}
845:{\displaystyle x}
823:computation trees
798:{\displaystyle X}
774:{\displaystyle X}
734:{\displaystyle s}
714:{\displaystyle t}
694:{\displaystyle t}
674:{\displaystyle s}
654:{\displaystyle t}
634:{\displaystyle s}
549:{\displaystyle t}
352:{\displaystyle s}
339:properly extends
332:{\displaystyle t}
213:{\displaystyle n}
200:when there is an
157:{\displaystyle X}
137:{\displaystyle s}
117:{\displaystyle t}
94:Wacław Sierpiński
1228:
1195:
1193:
1155:
1149:
1143:
1128:
1122:
1120:
1093:
1087:
1085:
1057:
1051:
1050:
1033:
980:
978:
977:
972:
960:
958:
957:
952:
940:
938:
937:
932:
930:
925:
917:
912:
894:
892:
891:
886:
884:
879:
871:
866:
851:
849:
848:
843:
819:recursion theory
813:Recursion theory
804:
802:
801:
796:
780:
778:
777:
772:
740:
738:
737:
732:
720:
718:
717:
712:
700:
698:
697:
692:
680:
678:
677:
672:
660:
658:
657:
652:
640:
638:
637:
632:
620:
618:
617:
612:
607:
606:
584:
582:
581:
576:
555:
553:
552:
547:
531:
529:
528:
523:
501:
499:
498:
493:
463:
461:
460:
455:
419:
417:
416:
411:
390:
388:
387:
382:
358:
356:
355:
350:
338:
336:
335:
330:
318:
316:
315:
310:
289:
287:
286:
281:
260:
258:
257:
252:
219:
217:
216:
211:
199:
197:
196:
191:
186:
185:
163:
161:
160:
155:
143:
141:
140:
135:
123:
121:
120:
115:
63:
61:
60:
55:
1236:
1235:
1231:
1230:
1229:
1227:
1226:
1225:
1221:Wellfoundedness
1201:
1200:
1199:
1198:
1175:10.2307/2372632
1156:
1152:
1129:
1125:
1094:
1090:
1075:
1058:
1054:
1048:
1034:
1025:
1020:
992:
966:
963:
962:
946:
943:
942:
926:
921:
913:
908:
900:
897:
896:
880:
875:
867:
862:
860:
857:
856:
837:
834:
833:
827:total recursive
815:
790:
787:
786:
766:
763:
762:
747:
726:
723:
722:
706:
703:
702:
686:
683:
682:
666:
663:
662:
646:
643:
642:
641:is a prefix of
626:
623:
622:
599:
595:
590:
587:
586:
561:
558:
557:
541:
538:
537:
511:
508:
507:
469:
466:
465:
425:
422:
421:
396:
393:
392:
367:
364:
363:
344:
341:
340:
324:
321:
320:
295:
292:
291:
290:is defined but
266:
263:
262:
228:
225:
224:
205:
202:
201:
178:
174:
169:
166:
165:
149:
146:
145:
129:
126:
125:
109:
106:
105:
102:
37:
34:
33:
12:
11:
5:
1234:
1224:
1223:
1218:
1213:
1197:
1196:
1150:
1144:. As cited by
1123:
1097:Lusin, Nicolas
1088:
1073:
1052:
1046:
1022:
1021:
1019:
1016:
1000:Brouwer (1924)
991:
988:
970:
950:
929:
924:
920:
916:
911:
907:
904:
883:
878:
874:
870:
865:
854:ordinal number
841:
814:
811:
794:
770:
746:
743:
730:
710:
690:
670:
650:
630:
610:
605:
602:
598:
594:
574:
571:
568:
565:
545:
532:refers to the
521:
518:
515:
504:
503:
491:
488:
485:
482:
479:
476:
473:
453:
450:
447:
444:
441:
438:
435:
432:
429:
409:
406:
403:
400:
380:
377:
374:
371:
360:
348:
328:
308:
305:
302:
299:
279:
276:
273:
270:
250:
247:
244:
241:
238:
235:
232:
209:
189:
184:
181:
177:
173:
164:, we say that
153:
133:
113:
101:
98:
53:
50:
47:
44:
41:
9:
6:
4:
3:
2:
1233:
1222:
1219:
1217:
1214:
1212:
1209:
1208:
1206:
1192:
1188:
1184:
1180:
1176:
1172:
1168:
1164:
1160:
1159:Kleene, S. C.
1154:
1147:
1146:Kleene (1955)
1141:
1137:
1133:
1127:
1119:on 2013-04-14
1118:
1114:
1110:
1106:
1102:
1098:
1092:
1084:
1080:
1076:
1070:
1066:
1062:
1056:
1049:
1043:
1039:
1032:
1030:
1028:
1023:
1015:
1013:
1012:Kleene (1955)
1009:
1005:
1001:
997:
987:
985:
968:
948:
918:
905:
902:
872:
855:
839:
831:
828:
824:
820:
810:
808:
792:
784:
768:
759:
756:
752:
742:
728:
708:
688:
668:
648:
628:
608:
603:
600:
596:
592:
569:
563:
543:
535:
519:
513:
489:
483:
480:
477:
471:
448:
442:
439:
433:
427:
420:are defined,
404:
398:
375:
369:
361:
346:
326:
303:
297:
274:
268:
248:
242:
239:
236:
230:
223:
222:
221:
207:
187:
182:
179:
175:
171:
151:
131:
111:
97:
95:
91:
90:Nikolai Luzin
87:
83:
78:
73:
71:
67:
48:
45:
42:
31:
27:
23:
19:
1216:Order theory
1166:
1162:
1153:
1139:
1135:
1126:
1117:the original
1112:
1108:
1091:
1064:
1055:
1037:
993:
816:
807:well-founded
783:well-ordered
760:
748:
505:
103:
74:
30:linear order
25:
21:
15:
1169:: 405–428,
1004:Moschovakis
830:functionals
1205:Categories
1018:References
100:Definition
1142:: 189–193
621:whenever
517:↾
487:↾
475:↾
246:↾
234:↾
1103:(1923),
1191:0070595
1183:2372632
1083:2893891
990:History
1189:
1181:
1081:
1071:
1044:
941:where
661:(i.e.
534:prefix
464:, and
92:, and
70:prefix
20:, the
1179:JSTOR
362:both
359:), or
28:is a
1069:ISBN
1042:ISBN
751:tree
597:<
440:<
391:and
261:and
176:<
124:and
49:<
1171:doi
817:In
805:is
781:is
536:of
104:If
24:or
16:In
1207::
1187:MR
1185:,
1177:,
1167:77
1165:,
1140:27
1138:,
1111:,
1107:,
1099:;
1079:MR
1077:,
1026:^
986:.
749:A
96:.
88:,
84:,
1173::
1148:.
1121:.
1113:9
1086:.
969:x
949:y
928:|
923:|
919:y
915:|
910:|
906:+
903:1
882:|
877:|
873:x
869:|
864:|
840:x
793:X
769:X
729:s
709:t
689:t
669:s
649:t
629:s
609:s
604:B
601:K
593:t
573:)
570:n
567:(
564:t
544:t
520:n
514:t
502:.
490:n
484:s
481:=
478:n
472:t
452:)
449:n
446:(
443:s
437:)
434:n
431:(
428:t
408:)
405:n
402:(
399:t
379:)
376:n
373:(
370:s
347:s
327:t
307:)
304:n
301:(
298:s
278:)
275:n
272:(
269:t
249:n
243:s
240:=
237:n
231:t
208:n
188:s
183:B
180:K
172:t
152:X
132:s
112:t
52:)
46:,
43:X
40:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.