Kolejność Kleene-Brouwera

W opisowej teorii mnogości , porządek Kleene-Brouwera lub porządek Lusina-Sierpińskiego jest liniowym porządkiem na skończonych sekwencjach nad jakimś liniowo uporządkowanym zbiorem ${\ Displaystyle (X, <)}$ , który różni się od częściej używanego leksykograficznego porządku w sposobie, w jaki obsługuje przypadek, gdy jedna sekwencja jest przedrostkiem drugiej. W porządku Kleene – Brouwer przedrostek jest późniejszy niż zawierająca go dłuższa sekwencja, a nie wcześniejszy.

Porządek Kleene-Brouwera uogólnia pojęcie przejścia postorderowego od drzew skończonych do drzew, które niekoniecznie są skończone. W przypadku drzew nad dobrze uporządkowanym zbiorem porządek Kleene-Brouwera sam w sobie jest dobrze uporządkowany wtedy i tylko wtedy, gdy drzewo nie ma nieskończonej gałęzi. Nosi imię Stephena Cole'a Kleene'a , Luitzena Egbertusa Jana Brouwera , Nikołaja Luzina i Wacława Sierpińskiego .

Definicja

Jeśli $\$$s}$ skończonymi sekwencjami elementów z $mówimy$ , że istnieje ${\ displaystyle t}$ { ${\ displaystyle n}$ takie, że albo:

• ${\ Displaystyle t \ upharpoonright n = s \ upharpoonright n}$ i ${\ Displaystyle t (n)}$ jest zdefiniowany, ale ${\ Displaystyle s (n)}$ jest niezdefiniowany (tj $displaystyle$ poprawnie rozciąga się $s}$ ) lub
• s ${\ Displaystyle s (n)}$ i ${\ Displaystyle t (n)}$${\ Displaystyle t (n) <s (n) }$ zdefiniowane, i ${\ Displaystyle t \ upharpoonright n = s \ upharpoonright n}$ .

Tutaj zapis odnosi się do przedrostka ${\ displaystyle t \ upharpoonright n}$ do $,$ ale nie włącznie $\ displaystyle t (n)}$ { Mówiąc prościej, ${\ Displaystyle t <_ {KB} s}$$ilekroć$ jest przedrostkiem ${\ displaystyle t}$ (tj. ${\ displaystyle s$$pierwszego$$różnią$ przed i są one równe do tego punktu) lub znajduje się na „lewo” $.$ miejsca, w którym się

Interpretacja drzewa

Drzewo , w opisowej teorii mnogości, jest definiowane jako zbiór skończonych sekwencji, który jest zamknięty przez operacje przedrostkowe . Rodzic w drzewie dowolnej sekwencji jest krótszą sekwencją utworzoną przez usunięcie jej ostatniego elementu. Zatem dowolny zestaw skończonych sekwencji można rozszerzyć, tworząc drzewo, a porządek Kleene-Brouwera jest naturalnym porządkiem, który można nadać temu drzewu. Jest to uogólnienie na potencjalnie nieskończone drzewa przechodzenia postorder skończonego drzewa: w każdym węźle drzewa poddrzewa potomne są uporządkowane od lewej do prawej, a sam węzeł następuje po wszystkich swoich dzieciach. Fakt, że porządek Kleene-Brouwera jest porządkiem liniowym (to znaczy, że jest zarówno przechodni, jak i całkowity) wynika bezpośrednio z tego, ponieważ dowolne trzy sekwencje, na których przechodniość ma być testowana, tworzą (wraz z ich przedrostkami) skończony drzewo, na którym porządek Kleene-Brouwer pokrywa się z postorderem.

Znaczenie uporządkowania Kleene-Brouwera wynika z faktu, że jeśli jest dobrze uporządkowane , to drzewo nad jest uzasadnione (nie ma nieskończenie długich gałęzi) wtedy i tylko wtedy, gdy ${$$displaystyle X}$ uporządkowanie Kleene-Brouwera jest dobrym uporządkowaniem elementów drzewa.

Teoria rekurencji

W teorii rekurencji porządek Kleene-Brouwera można zastosować do drzew obliczeniowych implementacji całkowitych funkcjonałów rekurencyjnych . Drzewo obliczeń jest uzasadnione wtedy i tylko wtedy, gdy wykonywane przez nie obliczenia są całkowicie rekurencyjne. Każdemu stanowi $liczbę$ drzewie obliczeniowym można przypisać porządkową ${\ Displaystyle ||x||}$ supremum liczb porządkowych ${\ Displaystyle 1+||y||}$$drzewie$$się$ na dzieci w . W ten sposób same funkcjonały rekurencyjne można sklasyfikować w hierarchię, zgodnie z minimalną wartością liczby porządkowej w korzeniu drzewa obliczeniowego, zminimalizowaną we wszystkich drzewach obliczeniowych, które implementują funkcjonał. Porządek Kleene-Brouwera dobrze ugruntowanego drzewa obliczeniowego jest sam w sobie dobrze uporządkowanym rekurencyjnie i co najmniej tak dużym, jak porządkowy przypisany do drzewa, z którego wynika, że ​​​​poziomy tej hierarchii są indeksowane przez rekurencyjne liczby porządkowe .

Historia

Kolejność tę zastosowali Lusin i Sierpinski (1923) , a następnie ponownie Brouwer (1924) . Brouwer nie cytuje żadnych odniesień, ale Moschovakis twierdzi, że mógł albo widzieć Lusina i Sierpińskiego (1923) , albo być pod wpływem wcześniejszych prac tych samych autorów, które doprowadziły do ​​tej pracy. Znacznie później Kleene (1955) przestudiował to samo uporządkowanie i przypisał je Brouwerowi.