Sformalizowanie teorii zbiorów skończonych w teorii typów

Większość asystentów dowodowych ma sformalizowaną koncepcję „zbioru skończonego”. Te formalizacje różnią się jednak bardzo dziko (choć można mieć nadzieję, że wszystkie są w zasadzie równoważne!). Nie rozumiem w tym momencie zajmowanej przestrzeni projektowej oraz jakie są zalety i wady każdej formalizacji.

W szczególności chciałbym zrozumieć, co następuje:

• Czy mogę aksjatyzować zbiory skończone (tj. Typy zamieszkałe przez skończoną liczbę mieszkańców) w prostej teorii typów? System F? Jakie są wady robienia tego w ten sposób?
• Wiem, że można to zrobić „elegancko” w systemie zależnym od typu. Jednak z klasycznego punktu widzenia powstałe definicje wydają się bardzo obce. [Nie twierdzę, że się mylą, wręcz przeciwnie!]. Ale nie rozumiem też, dlaczego mają rację. Rozumiem, że wybrali prawidłową koncepcję, ale głębszego powodu „mówienia w ten sposób” jest to, czego nie do końca rozumiem.

Zasadniczo chciałbym uzasadnione wprowadzenie do przestrzeni projektowej sformalizowania pojęcia „zbioru skończonego” w teorii typów.

Wiem, że można to zrobić „elegancko” w systemie zależnym od typu. Jednak z klasycznego punktu widzenia powstałe definicje wydają się bardzo obce.

Czy potrafisz wyjaśnić, co rozumiesz przez „kosmitę”? Wydaje mi się, że formalizujesz pojęcie zbioru skończonego dokładnie w ten sam sposób w teorii typów i teorii mnogości.

W teorii zbiorów kontynuujesz definiując zbiór jako Następnie definiujesz predykat skończoności jako: Gdzie oznacza izomorfizm zbiorów.$Fin(n)$

$$\mathrm{Fin}(n) \triangleq \{ k \in \mathbb{N} \;|\; k < n \}$$ $$\mathrm{Finite}(X) \triangleq \exists n\in\mathbb{N}.\; X \simeq \mathrm{Fin}(n)$$ $A \simeq B$

W teorii typów możesz zrobić dokładnie to samo! Zauważ, że jest typem zawierającym elementów (ponieważ drugi składnik pary nie ma znaczenia dla dowodów). Następnie możesz zdefiniować konstruktor typu skończoności jako: Gdzie oznacza izomorfizm typów.

$$\mathrm{Fin}(n) \triangleq \Sigma k:\mathbb{N}.\; \mathsf{if}\; k < n\,\mathsf{then}\; \mathsf{Unit} \;\mathsf{else}\; \mathsf{Void}$$ $\mathrm{Fin}(n)$$n$ $$\mathrm{Finite}(X) \triangleq \Sigma n:\mathbb{N}.\; X \simeq \mathrm{Fin}(n)$$ $A \simeq B$

Zobaczę, czy mogę dodać coś użytecznego do odpowiedzi Neela. „Przestrzeń projektowa” dla zbiorów skończonych jest znacznie większa konstrukcyjnie niż klasycznie, ponieważ różne definicje „skończonych” nie muszą konstruktywnie się zgadzać. Różne definicje w teorii typów dają nieco inne pojęcia. Oto kilka możliwości.

Zestawy skończone Kuratowskiego ( skończone) można scharakteryzować jako wolne -semilattice: biorąc pod uwagę zbiór, typ lub obiekt , elementy wolnego -semilattice mogą być thougth jako skończone podzbiory . Rzeczywiście, każdy taki element jest generowany przez:$K$$\lor$$X$$\lor$$K(X)$$X$

• element neutralny , który odpowiada pustemu zestawowi, lub$0$
• generator , który odpowiada singletonowi , lub$x \in X$$\lbrace x \rbrace$
• połączyć lub dwa elementy, co odpowiada unii.$S \lor T$

Równoważna kompozycja z wynosi: znaczy -finite wtedy i tylko wtedy, gdy istnieje i surjection .$K(X)$$S \subseteq X$$K$$n \in \mathbb{N}$ $e : \lbrace 1, \ldots, n \rbrace \to S$

Jeśli porównamy to z definicji Neel widzimy, że wymaga on do bijection . Sprowadza się to do wzięcia tych skończonych podzbiorów które mają rozstrzygającą równość: . Użyjmy do zbierania rozstrzygalne -finite podzbiorów .$e : \lbrace 1, \ldots, n \rbrace \to S$$K$$S \subseteq X$$\forall x, y \in S . x = y \lor x \neq y$$D(X)$$K$$X$

Oczywiście jest zamknięty w skończonych związkach, ale nie musi być zamknięty w skończonych skrzyżowaniach. I nie jest zamknięty w ramach żadnych operacji. Ponieważ ludzie oczekują, że zbiory skończone zachowują się trochę jak „agoola boolowska bez góry”, można również spróbować zdefiniować je jako dowolną uogólnioną algebrę boolowską ( , , i krewny / uzupełnienie ), ale tak naprawdę nigdy słyszałem o takim wysiłku.$K(X)$$D(X)$$0$$\lor$$\land$$\setminus$

Decydując, jaka jest „poprawna” definicja, musisz zwrócić uwagę na to, co chcesz zrobić ze zbiorami skończonymi. I nie ma jednej poprawnej definicji. Na przykład, w jakim sensie „skończony” jest zbiorem złożonych pierwiastków wielomianowego skończonego ?

Zobacz konstruktywnie skończony? Thierry'ego Coquanda i Arnauda Spiwacka za szczegółowe omówienie skończoności. Lekcja jest taka, że ​​skończoność wcale nie jest oczywista konstruktywnie.