Policzalność podrzędna - Subcountability

W konstruktywnych matematyki , zbiór jest subcountable jeśli istnieje częściowe surjection od liczb naturalnych na nim. Może to być wyrażone jako ${\ Displaystyle X}$

${\ Displaystyle \ istnieje (I \ subseteq \ omega ). \ \ istnieje f. \ (f \ dwukropek I \ twoheadrightarrow X).}$

gdzie są liczby liczące ( z pominięciem arytmetyki) i gdzie oznacza, że jest to funkcja surjektywna od na . Innymi słowy, wszystkie elementy zbioru policzalnego są funkcjonalnie w obrazie zbioru indeksującego liczb zliczających, a zatem zbiór może być rozumiany jako zdominowany przez zbiór policzalny . ${\ Displaystyle \ omega}$${\ Displaystyle {\ mathbb {N} }}$${\displaystyle f\colon I\twoheadrightarrow X}$${\displaystyle f}$${\ Displaystyle I}$${\ Displaystyle X}$${\ Displaystyle X}$${\ Displaystyle I \ subseteq \ omega }$${\ Displaystyle X}$${\ Displaystyle \ omega}$

Dyskusja

Przykład

Ważnym przypadkiem jest sytuacja, w której oznacza pewną podklasę większej klasy funkcji badanej w teorii obliczalności . ${\ Displaystyle X}$

Rozważmy podklasę funkcji całkowitych i zauważ, że bycie całkowitym nie jest właściwością rozstrzygalną, tzn. nie może istnieć konstruktywna bijekcja między funkcjami całkowitymi a liczbami naturalnymi. Jednak poprzez wyliczenie kodów wszystkich możliwych funkcji częściowych (co obejmuje również funkcje niekończące), ich podzbiory, takie jak funkcje całkowite, są postrzegane jako zbiory podliczalne. Zauważ, że według twierdzenia Rice'a o zestawach indeksów większość domen nie jest rekurencyjna. Rzeczywiście, nie zapewnia się tutaj żadnego efektywnego odwzorowania między wszystkimi liczbami zliczającymi a nieskończonym (nieskończonym) zbiorem indeksowania , a jedynie relację podzbioru . Będąc zdominowanym przez konstruktywnie niepoliczalny zbiór liczb , nazwa podpoliczalny oznacza zatem, że zbiór niepoliczalny nie jest większy niż . ${\ Displaystyle I}$${\ Displaystyle \ omega}$${\ Displaystyle I}$${\ Displaystyle I \ subseteq \ omega }$${\ Displaystyle I}$${\ Displaystyle X}$${\ Displaystyle \ omega}$

Wykazanie, że jest policzalne, implikuje również, że jest ono policzalne klasycznie (niekonstruktywnie) formalnie, ale nie odzwierciedla to żadnej efektywnej policzalności. Innymi słowy, fakt, że algorytm wyliczający wszystkie funkcje w sekwencji nie może być zakodowany, nie jest uchwycony przez klasyczne aksjomaty dotyczące istnienia zbioru i funkcji. Widzimy, że w zależności od aksjomatów teorii, podrzędność może być bardziej dowodliwa niż policzalna. ${\ Displaystyle X}$

Stosunek do wykluczonego środka

W logikach konstruktywnych i teoriach mnogości , które wiążą istnienie funkcji między zbiorami nieskończonymi (nieskończonymi) z pytaniami o skuteczność i rozstrzygalność , własność przeliczalności oddziela się od przeliczalności, a zatem nie jest pojęciem nadmiarowym. Zbiór indeksujący liczb naturalnych może istnieć, np. jako podzbiór poprzez zbiór teoretycznych aksjomatów, takich jak Aksjomat separacji , tak że ${\ Displaystyle I}$

${\ Displaystyle \ forall (i \ w I). (i \ w \ omega )}$.

Ale ten zestaw może nadal nie być odpinany, w tym sensie, że

${\ Displaystyle \ forall (n \ w \ omega). {\ duży (} (n \ w ja) \ lub \ neg (n \ w ja) {\ duży)}}$

nie można udowodnić bez przyjęcia tego jako aksjomatu. Z tego powodu można nie udać się skutecznie zliczyć, jeśli nie uda się zmapować liczb zliczania do zestawu indeksowania . ${\ Displaystyle X}$${\ Displaystyle \ omega}$${\ Displaystyle I}$

W matematyce klasycznej

Stwierdzając wszystkie prawa logiki klasycznej, rozdzielna własność omawianej powyżej istotnie obowiązuje dla wszystkich zbiorów. Następnie, dla nonempty, własności numerowalne ( wstrzykuje do ), policzalne ( ma jako swój zakres ), podzbiór (podzbiór surjects do ) i również nieproduktywne (właściwość policzalna zasadniczo zdefiniowana w kategoriach podzbiorów , sformalizowana poniżej) są wszystkie równoważne i wyrażają, że zbiór jest skończony lub przeliczalnie nieskończony . ${\ Displaystyle I}$${\ Displaystyle X}$${\ Displaystyle X}$${\ Displaystyle \ omega}$${\ Displaystyle \ omega}$${\ Displaystyle X}$${\ Displaystyle \ omega}$${\ Displaystyle X}$${\ Displaystyle \ omega}$${\ Displaystyle X}$

Nieklasyczne twierdzenia

Nie domagać się prawa wykluczonego środka

${\ Displaystyle (\ phi \ lub \ neg \ phi )}$dla wszystkich propozycji ,${\displaystyle \phi}$

wówczas konsekwentne może być również twierdzenie o przeliczalności zbiorów, które klasycznie (tj. niekonstruktywnie) przekraczają liczność liczb naturalnych. Zauważ, że w konstruktywnym otoczeniu twierdzenie o policzalności dotyczące przestrzeni funkcji poza pełnym zbiorem , jak w , może zostać obalone. Można jednak dopuścić przeliczalność zbioru niepoliczalnego przez zbiór, od którego nie można skutecznie oddzielić . ${\ Displaystyle {\ mathbb {N} } ^ {\ mathbb {N}}}$${\ Displaystyle \ omega}$${\ Displaystyle \ omega \ twoheadrightarrow {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ Displaystyle I \ twoheadrightarrow {\ mathbb {N} } ^ {\ mathbb {N}}}$${\ Displaystyle {\ mathbb {N} } ^ {\ mathbb {N}}}$${\ Displaystyle I \ subseteq \ omega }$${\ Displaystyle \ omega}$

Ponieważ jest to niepoliczalne, a klasycznie nie do udowodnienia z kolei, klasyczne ramy z dużą przestrzenią funkcyjną są nie do pogodzenia z konstruktywną tezą Kościoła , aksjomatem rosyjskiego konstruktywizmu. ${\ Displaystyle {\ mathbb {N} } ^ {\ mathbb {N}}}$

Teorie zestawów

Argumenty kantora dotyczące podzbiorów liczb naturalnych

Jako teorię odniesienia patrzymy na konstruktywną teorię mnogości , która ma Zastąpienie , Ograniczoną separację , silną Nieskończoność , jest agnostyczna wobec istnienia zbiorów potęgowych , ale zawiera aksjomat, który zapewnia, że ​​każda przestrzeń funkcyjna jest zbiorem, dane są również zbiorami. W tej teorii spójne jest ponadto twierdzenie, że każdy zbiór jest przeliczalny. ${\displaystyle {\mathsf {CZF}}}$${\ Displaystyle Y ^ {X}}$${\displaystyle X,Y}$

Zgodność różnych aksjomatów omówiona jest w tej sekcji za pomocą możliwych sujekcji na nieskończonym zbiorze liczb liczących . ${\ Displaystyle I \ podzbiór {\ mathbb {N} }}$

Sytuacje omówione poniżej - w przestrzeniach funkcyjnych i w klasach potęgowych - różnią się o tyle, o ile dla funkcji , z definicji istnieje unikalna wartość zwracana dla każdej wartości w domenie, . W przeciwieństwie do ogólnych predykatów i ich wartości logicznych (niekoniecznie tylko prawda i fałsz) funkcja (która w terminologii programistycznej kończy) udostępnia informacje o danych dla wszystkich swoich poddomen (podzbiorów ). Postrzegane jako funkcje charakterystyczne, decydują o przynależności. Jako takie, w , (całkowite) funkcje nie są automatycznie bijekcyjne ze wszystkimi podzbiorami . Konstrukcyjnie podzbiory są bardziej złożonym pojęciem niż funkcje charakterystyczne. ${\ Displaystyle f \ dwukropek X \ do Y}$${\ Displaystyle x \ w X}$${\ Displaystyle \ istnieje! (y \ w Y). f (x) = y}$${\ Displaystyle X}$${\displaystyle {\mathsf {CZF}}}$${\ Displaystyle X \ do \ {0,1 \}}$${\ Displaystyle X}$

W rzeczywistości, w kontekście niektórych nieklasycznych aksjomatów, nawet klasa potęgowa singletona, np. klasa wszystkich podzbiorów , okazuje się być klasą właściwą. ${\displaystyle {\mathcal {P}}\{0\}}$${\ Displaystyle \ {0 \}}$

W przestrzenie funkcyjne

Ustalenie dozwolonej przeliczalności wszystkich zbiorów zamienia się w szczególności w zbiór przeliczalny. ${\ Displaystyle {\ mathbb {N} } ^ {\ mathbb {N}}}$

Rozważamy więc tutaj funkcję surjektywną i zbiór rozumiany/oddzielony jako ${\ Displaystyle f \ dwukropek I \ twoheadrightarrow {\ mathbb {N} } ^ {\ mathbb {N} }}$

${\ Displaystyle {\ Duży \ {} \ langle n, r \ rangle \ w {\ mathbb {N}} \ razy {\ mathbb {N}} \ średni {\ duży (} n \ w I \ ziemi D (n ,y){\big )}\lor {\big (}\neg (n\in I)\land y=1{\big )}{\duży \}}}$

z predykatem diagonalizującym zdefiniowanym jako

${\ Displaystyle D (n, r) = {\ duży (} \ neg (f (n) (n) \ geq 1) \ ziemi y = 1 {\ duży )} \ lub {\ duży (} \ neg (f (n)(n)=0)\land y=0{\big )}}$

które możemy również wyrazić bez negacji jako

${\ Displaystyle D (n, r) = {\ duży (} f (n) (n) = 0 \ ziemi r = 1 {\ duży )} \ lub {\ duży (} f (n) (n) \ geq 1\land y=0{\duży )}}$.

Ten zbiór jest klasycznie funkcją i może być użyty do udowodnienia, że ​​istnienie jest faktycznie sprzeczne. Jednak konstruktywnie, o ile zdania w jego definicji nie są rozstrzygalne, tak że zbiór faktycznie definiuje przypisanie funkcyjne, po prostu nie możemy wyciągnąć tego wniosku. ${\ Displaystyle {\ mathbb {N} } ^ {\ mathbb {N}}}$${\displaystyle f}$${\displaystyle n\w ja}$

W ten sposób dozwolona jest podliczalność . Niemniej jednak, również w przypadku , istnienie pełnego wyrzeczenia , z domeną , jest rzeczywiście sprzeczne, ponieważ przynależność do jest rozstrzygalna. ${\ Displaystyle {\ mathbb {N} } ^ {\ mathbb {N}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathbb {N}}\twoheadrightarrow {\mathbb {N}}^{\mathbb {N}}}$${\ Displaystyle {\ mathbb {N} }}$${\ Displaystyle I = {\ mathbb {N} }}$

Poza tymi uwagami, również pamiętać, że dla dowolnej niezerowej liczby , funkcje w udziałem surjection nie może zostać rozszerzona na wszystkie podobnym argumentem sprzeczność. Innymi słowy, istnieją wtedy funkcje częściowe, których nie można rozszerzyć do funkcji pełnych . Należy zauważyć, że gdy podano a , nie można koniecznie zdecydować czy , a więc nie można nawet zdecydować, czy wartość potencjalnego rozszerzenia funkcji on jest już określona dla sujekcji . ${\displaystyle d}$${\ Displaystyle i \ mapsto f (i) (i) + d}$${\ Displaystyle I \ do {\ mathbb {N} }}$${\displaystyle f}$${\ Displaystyle {\ mathbb {N} }}$${\displaystyle {\mathbb {N}}\do {\mathbb {N}}}$${\ Displaystyle n \ w {\ mathbb {N} }}$${\displaystyle n\w ja}$${\ Displaystyle n}$${\displaystyle f}$

Aksjomat podliczalny, zmieniający wszystkie zbiory w podliczalne, jest niekompatybilny z jakimkolwiek nowym aksjomatem czyniącym policzalnym, w tym . ${\ Displaystyle I}$${\displaystyle {\mathrm {LEM}}}$

W klasach mocy

Następnie badamy możliwe postulaty istnienia sujekcji . To, przez Zastąpienie, oznacza, że jest to zestaw. Naruszony podzbiór is ${\ Displaystyle f \ dwukropek I \ twoheadrightarrow {\ mathcal {P}} {\ mathbb {N}}}$${\displaystyle {\mathsf {CZF}}}$${\ Displaystyle {\ mathcal {P}} {\ mathbb {N}}}$${\ Displaystyle I}$

${\ Displaystyle \ {n \ w {\ mathbb {N}} \ mid n \ w I \ ziemi D (n) \}}$

co, zgodnie z definicją , w tym przypadku upraszcza tylko ${\ Displaystyle I \ podzbiór {\ mathbb {N} }}$

${\ Displaystyle \ {n \ w I \ mid D (n) \}}$

gdzie

${\ Displaystyle D (n) = \ neg (n \ w f (n)),}$

zaadaptowane z twierdzenia Cantorsa o zbiorach potęgowych. Ten podzbiór istnieje poprzez separację. Istnienie sujekcji od razu implikuje istnienie liczby z ${\displaystyle c\w ja}$

${\ Displaystyle c \ w f (c) \ if \ neg (c \ w f (c))}$,

czyniąc członkostwo nierozstrzygalnym i niezgodnym z jakąkolwiek realizacją. Propozycje tej formy, , muszą zostać odrzucone ze względu na konsekwencje prawa wprowadzenia negacji . Więc takie odrzucenie nie istnieje i nie może być przeliczalne. ${\ Displaystyle P \ iff \ neg P}$${\ Displaystyle {\ mathcal {P}} {\ mathbb {N}}}$

Dochodzimy do wniosku, że aksjomat podprzeliczalności, zmieniający wszystkie zbiory pod przeliczalne, jest niezgodny z byciem zbiorem, na co wskazuje np. aksjomat potęgowy zbioru. ${\ Displaystyle {\ mathcal {P}} {\ mathbb {N}}}$

Pojęcie rozmiaru

Jak widać na przykładzie przestrzeni funkcyjnej rozważanej w teorii obliczalności , nie każdy nieskończony podzbiór koniecznie jest w konstruktywnej bijekcji z , tworząc w ten sposób miejsce na bardziej wyrafinowane rozróżnienie między niepoliczalnymi zbiorami w konstruktywnych kontekstach. Przestrzeń funkcji (a także ) w umiarkowanie bogatej teorii mnogości zawsze okazuje się ani skończona, ani w bijekcji z , zgodnie z argumentem diagonalnym Cantora . To znaczy być niepoliczalnym. Ale argument, że liczność tego zbioru przewyższałaby w pewnym sensie liczność liczb naturalnych, opiera się na ograniczeniu tylko do klasycznej koncepcji wielkości i jej indukowanego uporządkowania zbiorów według liczności. Motywowany powyższymi sekcjami zbiór nieskończony może być uważany za „mniejszy” niż klasa . Policzalności jako osądu małej wielkości nie należy mylić ze standardową matematyczną definicją relacji liczności zdefiniowaną przez Cantora, przy czym liczność mniejszą definiuje się w kategoriach wstrzyknięć , a równość liczeń definiuje się w kategoriach bijekcji. Co więcej, zauważ, że konstruktywnie, kolejność " " taka jak kardynalności może być nierozstrzygnięta. ${\ Displaystyle \ omega}$${\ Displaystyle \ omega}$${\ Displaystyle {\ mathbb {N} } ^ {\ mathbb {N}}}$${\ Displaystyle \ {0,1 \} ^ {\ mathbb {N}}}$${\ Displaystyle {\ mathbb {N} }}$${\ Displaystyle {\ mathbb {N} } ^ {\ mathbb {N}}}$${\ Displaystyle {\ mathcal {P}} {\ mathbb {N}}}$ ${\ Displaystyle X}$${\styl wyświetlania <}$

Modele

Powyższa analiza wpływa na formalne właściwości kodowań . Skonstruowano modele dla tego nieklasycznego rozszerzenia teorii. Takie niekonstruktywne aksjomaty mogą być postrzegane jako zasady wyboru, które jednak nie zwiększają zbytnio dowodowo-teoretycznej siły teorii. ${\ Displaystyle \ mathbb {R}}$${\displaystyle {\mathsf {CZF}}}$

Więcej przykładów:

• Istnieją modele, w których wszystkie zbiory z relacjami odosobnienia są przeliczalne.${\displaystyle {\mathsf {IZF}}}$
• W konstruktywnej teorii mnogości , jak omówiono, rzeczywiście spójne jest twierdzenie aksjomatu podliczalności, że wszystkie zbiory są (wewnętrznie) przeliczalne. Powstała teoria jest sprzeczna z Aksjomatem zbioru potęgi iz prawem wyłączonego środka .${\displaystyle {\mathsf {CZF}}}$
• Jeszcze mocniej, niektóre modele teorii mnogości Kripkego-Platka potwierdzają, że wszystkie zbiory są nawet policzalne.

Subcountable oznacza nie -productive${\ Displaystyle \ omega}$

Dowolny zbiór przeliczalny jest subcountable i każdy subcountable zestaw nie jest -productive: Zestaw mówi się - produktywny , jeśli kiedykolwiek którykolwiek z jego podzbiorów jest zakres od jakiegoś częściowego funkcji , zawsze pozostaje co najmniej jeden element, który znajduje się poza tym zakresem. Może to być wyrażone jako ${\ Displaystyle \ omega}$${\ Displaystyle X}$${\ Displaystyle \ omega}$${\displaystyle g}$

${\ Displaystyle \ forall g. \, {\ duży (} (g \ dwukropek \ omega \ do X) \ implikuje \ istnieje (x \ w X). \, x \ notin {\ operatorname {rng}} (g) {\duża )}.}$

Zbiór będący -produktywnym mówi o tym, jak trudno jest wygenerować jego elementy: nie można ich wygenerować za pomocą pojedynczej funkcji. Jako takie zbiory -produktywne wymykają się podliczeniom. Argumenty ukośne często zawierają to pojęcie, czy to wprost, czy niejawnie. ${\ Displaystyle \ omega}$${\ Displaystyle \ omega}$

Zobacz też

• Argument przekątny Cantora
• Funkcja obliczalna
• Konstruktywna teoria mnogości
• Twierdzenie Schrödera-Bernsteina
• Podiloraz
• Całkowite zamówienie

Bibliografia