Harvey Friedman wykazał, że istnieje dokładny wynik punktu stałego, którego nie można udowodnić w ZFC (zwykła teoria mnogości Zermelo-Frankela z Axiom of Choice). Wiele współczesnych układów logicznych opiera się na operatorach stałoprzecinkowych, więc zastanawiałem się: czy są znane konsekwencje twierdzenia o przesunięciu górnego przesunięcia dla teoretycznej informatyki?
Nie do udowodnienia Twierdzenie o stałym punkcie przesunięcia górnego
Dla wszystkich część zawiera .
Twierdzenie USFP wydaje się być twierdzeniem , więc może być „wystarczająco blisko” do obliczalności (np. Sprawdzanie nieizomorfizmu struktur automatycznych), aby wpłynąć na teoretyczną informatykę.
Aby uzyskać kompletność, oto definicje z przemówienia Friedmana na MIT z listopada 2009 r. (Patrz także szkic książki „Teoria relacji logicznych” ).
jest zbiorem liczb wymiernych. sąrównoważne porządkom,jeśli ilekroć to . Gdy wówczasgórny przesuwnyz , oznaczonej , otrzymuje się przez dodanie 1 do każdego nieujemne współrzędnej . Relacja jestkolejność niezmienna, jeśli dla każdego rzęduniezmiennego równoważnej jest warunek . Relacja jest niezmiennikiem porządku, jeśli jest niezmiennikiem porządku jako podzbiorem , iściśle dominuje,jeśli dla wszystkich za każdym razem, gdyA Q k R [ A ] { y | ∃ x ∈ A R ( x , y ) } A us ( A ) = { us ( x ) | x ∈ A } sześcian ( A , 0 ) B k 0 ∈ B A B kR ⊆ Q k × Q k
Edycja: Jak zauważył Dömötör Pálvölgyi w komentarzach, przyjmowanie i jako zwykłej kolejności racjonalnej wydaje się dawać kontrprzykład. Po pierwsze, zestaw nie może być pusty, ponieważ jest wówczas również pusty, a musiałby wówczas zawierać 0 według warunku kostki, co jest sprzecznością. Jeśli niepuste zbiory mają minimum, to nie mogą zawierać żadnych racjonalności większych niż to, więc musi to być singleton, co jest sprzeczne z warunkiem górnej zmiany. Jeżeli natomiast nie ma minimum, to więc musi być puste, co jest sprzecznością. R A R [ A ] A A A R [ A ] = Q AJakieś komentarze na temat tego, czy są jakieś ukryte nieoczywiste problemy definicyjne, takie jak być może ukryty niestandardowy model racjonalności?
Dalsza edycja: powyższy argument jest w przybliżeniu poprawny, ale jest błędny w zastosowaniu górnego przesunięcia. Ten operator dotyczy tylko współrzędnych nieujemnych , więc ustawienie na dowolny ujemny zbiór singletonów daje stały punkt, zgodnie z potrzebami. Innymi słowy, jeśli to jest rozwiązaniem i nie ma innych rozwiązań.m < 0 A = { m }