Jakie interesujące twierdzenia w TCS opierają się na Axiom of Choice? (Lub alternatywnie, aksjomat determinacji?)

Matematycy czasem martwią się o aksjomat wyboru (AC) i aksjomat determinacji (AD).

Aksjomat wyboru : Biorąc pod uwagę dowolny zbiór z niepustych zestawach jest funkcja , które, biorąc pod uwagę zestaw w , zwraca element z .${\cal C}$$f$$S$${\cal C}$$S$

Aksjomat Determinacji : Niech będzie zbiorem nieskończenie długich ciągów bitów. Alice i Bob grają w grę, w której Alice wybiera pierwszy bit , Bob wybiera drugi bit itd., Dopóki nie zostanie skonstruowany nieskończony ciąg . Alice wygrywa jeśli , Bob wygrywa, jeśli . Zakłada się, że dla każdego istnieje strategia wygrywająca dla jednego z graczy. (Na przykład, jeśli składa się tylko z ciągu samych jedynek, Bob może wygrać w skończonej liczbie ruchów.)$S$$b_1$$b_2$$x = b_1 b_2 \cdots$$x \in S$$x \not \in S$ $S$$S$

Wiadomo, że te dwa aksjomaty są ze sobą niespójne. (Pomyśl o tym lub przejdź tutaj .)

Inni matematycy nie zwracają uwagi na użycie tych aksjomatów jako dowodu lub nie zwracają na nie uwagi. Wydaje się, że są one prawie nieistotne dla teoretycznej informatyki, ponieważ uważamy, że pracujemy głównie z obiektami skończonymi. Ponieważ jednak TCS definiuje obliczeniowe problemy decyzyjne jako nieskończone ciągi bitów, a my mierzymy (na przykład) złożoność czasową algorytmu jako funkcję asymptotyczną nad naturali, zawsze istnieje możliwość, że użycie jednego z tych aksjomatów może się pełzać w kilka dowodów.

Jaki jest najbardziej uderzający przykład w TCS, że wiesz, gdzie wymagany jest jeden z tych aksjomatów ? (Czy znasz jakieś przykłady?)

Żeby tylko trochę zapowiedzieć, zauważ, że argument przekątnej (powiedzmy, że jest zestawem wszystkich maszyn Turinga), nie jest zastosowaniem Aksjomatu Wyboru. Chociaż język, który definiuje maszyna Turinga, jest nieskończonym ciągiem bitów, każda maszyna Turinga ma skończony opis, więc tak naprawdę nie wymagamy funkcji wyboru dla nieskończenie wielu zestawów nieskończonych.

(Umieszczam wiele tagów, ponieważ nie mam pojęcia, skąd będą pochodzić przykłady).

Każde wyrażenie arytmetyczne możliwe do udowodnienia w ZFC jest możliwe do udowodnienia w ZF, a zatem nie „potrzebuje” wybranego aksjomatu. Przez wyrażenie „arytmetyczne” rozumiem wyrażenie w języku arytmetycznym pierwszego rzędu, co oznacza, że ​​można je określić przy użyciu tylko kwantyfikatorów w stosunku do liczb naturalnych („dla wszystkich liczb naturalnych x” lub „istnieje liczba naturalna x”), bez kwantyfikacji zbiorów liczb naturalnych. Na pierwszy rzut oka może wydawać się bardzo restrykcyjne, aby zakazać kwantyfikacji w odniesieniu do zbiorów liczb całkowitych; jednak skończone zestawy liczb całkowitych można „zakodować” przy użyciu jednej liczby całkowitej, więc można obliczyć liczbę skończonych liczb całkowitych.

Praktycznie każde oświadczenie o zainteresowaniu w TCS może być, z odrobiną finaglingu, sformułowane jako wyrażenie arytmetyczne, a zatem nie wymaga aksjomatu wyboru. Na przykład na pierwszy rzut oka wygląda jak twierdzenie o nieskończonych zestawach liczb całkowitych, ale można je przeformułować w następujący sposób: „dla każdej maszyny Turinga w czasie wielomianowym istnieje instancja SAT, która się myli”, co jest arytmetyką komunikat. Tak więc moja odpowiedź na pytanie Ryana brzmi: „Nie znam nic takiego”.$P\ne NP$

Ale poczekaj, możesz powiedzieć, a co z arytmetycznymi stwierdzeniami, których dowód wymaga czegoś takiego jak lemat Koeniga lub twierdzenie o drzewie Kruskala? Czy nie wymagają one słabej formy aksjomatu wyboru? Odpowiedź jest taka, że ​​zależy to dokładnie od tego, jak podasz dany wynik. Na przykład, jeśli podasz twierdzenie o grafie mniejszym w postaci „biorąc pod uwagę dowolny nieskończony zestaw nieoznaczonych grafów, muszą istnieć dwa z nich, tak aby jeden był mniejszy od drugiego”, to trzeba przejść pewną ilość wyboru, aby przejść przez twój nieskończony zestaw danych, wybieranie wierzchołków, subgrafów itp. [EDYCJA: Popełniłem tutaj błąd. Jak wyjaśnia Emil Jeřábek, twierdzenie o mniejszym wykresie - a przynajmniej najbardziej naturalne jego stwierdzenie przy braku AC - można udowodnić w ZF. Ale modulo ten błąd, to, co mówię poniżej, jest nadal zasadniczo poprawne. ] Jeśli jednak zamiast tego zapisujesz konkretne kodowanie liczbami naturalnymi mniejszej relacji na oznaczonych grafach skończonych i formułujesz twierdzenie o grafie mniejszym jako stwierdzenie o tym szczególnym porządku częściowym, wówczas instrukcja staje się arytmetyczna i nie wymaga AC w dowód.

Większość ludzi uważa, że ​​„esencja kombinatoryczna” twierdzenia o mniejszym wykresie jest już uchwycona przez wersję, która naprawia określone kodowanie, i że trzeba wywoływać AC, aby oznaczyć wszystko wszystkim, w przypadku przedstawienia ogólnego zestawu- teoretyczna wersja problemu jest rodzajem nieistotnego artefaktu decyzji o zastosowaniu teorii mnogości zamiast arytmetyki jako logicznej podstawy. Jeśli czujesz to samo, to twierdzenie o mniejszym wykresie nie wymaga AC. (Zobacz także ten post Ali Enayat na liście mailingowej Podstawy matematyki, napisany w odpowiedzi na podobne pytanie, które kiedyś miałem).

Przykład liczby chromatycznej płaszczyzny jest podobnie kwestią interpretacji. Istnieją różne pytania, które możesz zadać, jeśli okażą się, że są równoważne, ale są to odrębne pytania, jeśli nie przyjmiesz AC. Z punktu widzenia TCS kombinatorycznym sednem pytania jest kolorystyka skończonych subgrrafów płaszczyzny oraz fakt, że możesz (jeśli chcesz) użyć argumentu zwartości (w tym miejscu pojawia się AC), aby dojść do wniosku o liczbie chromatycznej całej płaszczyzny jest zabawne, ale nieco styczne. Więc nie sądzę, że to naprawdę dobry przykład.

Myślę, że ostatecznie możesz mieć więcej szczęścia pytając, czy są jakieś pytania TCS, które wymagają dużych kardynalnych aksjomatów do ich rozstrzygnięcia (a nie AC). Praca Harveya Friedmana wykazała, że ​​niektóre stwierdzenia skończone w teorii grafów mogą wymagać dużych aksjomatów kardynalnych (lub przynajmniej 1-spójności takich aksjomatów). Dotychczasowe przykłady Friedmana są nieco sztuczne, ale nie zdziwiłbym się, gdy podobne przykłady pojawiały się „naturalnie” w TCS w ciągu naszego życia.

Rozumiem, że znany dowód na twierdzenie Robertsona-Seymoura wykorzystuje aksjomat wyboru (poprzez twierdzenie o drzewku Kruskala). Jest to szczególnie interesujące z punktu widzenia TCS, ponieważ twierdzenie Robertson-Seymour sugeruje, że testy przynależności w dowolnej podrzędnie zamkniętej rodzinie grafów można wykonać w czasie wielomianowym. Innymi słowy, Aksjomat wyboru można wykorzystać pośrednio, aby udowodnić, że istnieją algorytmy wielomianowe dla pewnych problemów, bez faktycznej ich budowy.

Może to jednak nie być dokładnie to, czego szukasz, ponieważ nie jest jasne, czy AC jest tutaj rzeczywiście wymagane.

Odnosi się to do odpowiedzi udzielonej przez Janne Korhonena.

W latach 80. i 90. istniał strumień wyników, które próbowały scharakteryzować systemy aksjomatów (innymi słowy teoria arytmetyczna) potrzebne do udowodnienia rozszerzenia twierdzenia o drzewie Kruskala (KTT; oryginalny KTT pochodzi z 1960 r.). W szczególności Harvey Friedman udowodnił kilka wyników zgodnie z tą linią (patrz SG Simpson. Brak udowodnienia niektórych właściwości kombinatorycznych skończonych drzew . W LA Harrington i in., Redaktor, Harvey Friedman's Research on Foundations of Mathematics. Elsevier, North-Holland, 1985) . Wyniki te wykazały, że (niektóre rozszerzenia) KTT muszą używać „silnych” aksjomatów rozumienia (tj. Aksjomaty mówiące, że istnieją pewne zestawy o wysokiej złożoności logicznej). Nie wiem dokładnie o możliwości udowodnienia rozszerzeń KTT w ZF (bez aksjomatu wyboru).

Równolegle do tego strumienia wyników podjęto próbę połączenia go z („Teorią B”) TCS za pomocą systemów przepisywania . Chodzi o to, aby zbudować systemy przepisywania (pomyśl o tym jako o rodzaju programowania funkcjonalnego lub programach rachunku lambda), dla których ich zakończenie zależy od pewnych (rozszerzeń) KTT (oryginalne połączenie KTT z zakończeniem systemu przepisywania zostało udowodnione przez N Dershowitz (1982)). Oznacza to, że aby pokazać, że niektóre programy kończą się, potrzebne są silne aksjomaty (ponieważ rozszerzenia KTT wymagają takich aksjomatów). Dla tego typu wyników patrz np. A. Weiermann, Granice złożoności dla niektórych skończonych form twierdzenia Kruskala , Journal of Symbolic Computation 18 (1994), 463-488.

Problem Hadwigera-Nelsona jest stycznie powiązany i wymaga minimalnej liczby kolorów wymaganych do pokolorowania płaszczyzny gdzie punkty w odległości dokładnie 1 mają różne kolory. Istnieją skończone podgrafy, które wymagają czterech kolorów, i istnieje siedem kolorów do zbudowania, układając płaszczyznę za pomocą sześciokątów.${\mathbb R}^2$

W Szelach i Soifer „Aksjomat wyboru i liczba chromatyczna płaszczyzny” wykazano, że jeśli wszystkie skończone podgrupy płaszczyzny są czterochromatyczne, to

• Jeśli przyjmiesz wybrany aksjomat, to płaszczyzna jest czterochromatyczna.
• Jeśli przyjmiesz zasadę zależnych wyborów i że wszystkie zbiory są mierzalne metodą Lebesgue'a, to płaszczyzna ma pięć, sześć lub siedem chromatów.

Niektóre prace Oliviera Finkela wydają się być związane z pytaniem --- choć niekoniecznie wprost o samym aksjomacie wyboru --- i zgodnie z odpowiedzią Timothy Chow. Na przykład cytując streszczenie twierdzeń o niekompletności, dużych kardynałów i automatów nad słowami skończonymi , TAMC 2017 ,

można konstruować różnego rodzaju automaty na podstawie skończonych słów, dla których niektóre elementarne właściwości są w rzeczywistości niezależne od teorii silnych zbiorów, takich jak , dla liczb całkowitych . n ≥ $T_n := ZFC + \text{``There exist (at least) $n$ inaccessible cardinals''}$$n \geq 0$

[To nie jest bezpośrednia odpowiedź na twoje pytanie, ale może być sugestywna i / lub informacyjna dla niektórych osób.]

Ankieta P vs. NP Sonda Williama Gasarcha podaje pewne statystyki dotyczące tego, jak zostanie rozwiązane P vs. NP:

1. 61 myślał P ≠ NP.
2. 9 myśli P = NP.
3. 4 myślałem, że jest niezależny . Chociaż nie wspomniano o żadnym konkretnym systemie aksjomatów, zakładam, że uważają, że jest on niezależny od ZFC .
4. 3 właśnie stwierdził, że NIE jest on niezależny od pierwotnej arytmetyki rekurencyjnej.
5. Powiedziałem, że będzie to zależeć od modelu.
6. 22 nie wyraził opinii.

Wikipedia ma ciekawe podejście do niezależności:

... Bariery te skłoniły również niektórych informatyków do zasugerowania, że ​​problem P kontra NP może być niezależny od standardowych systemów aksjomatów, takich jak ZFC (nie można w nich udowodnić ani obalić). Interpretacja wyniku niezależności może polegać na tym, że albo nie istnieje algorytm wielomianowy dla żadnego problemu NP-zupełnego, a takiego dowodu nie można zbudować w (np.) ZFC, lub że mogą istnieć algorytmy wielomianowe czasowe dla problemów NP-zupełnych, ale nie można udowodnić w ZFC, że takie algorytmy są poprawne [ 1]. Jeśli jednak można wykazać, stosując techniki, o których wiadomo, że mają zastosowanie, że problemu nie można rozstrzygnąć nawet przy znacznie słabszych założeniach rozszerzających aksjomaty Peano (PA) dla arytmetyki liczb całkowitych, wówczas koniecznie istniałaby prawie- algorytmy czasu wielomianowego dla każdego problemu w NP [ 2 ]. Dlatego jeśli ktoś uważa (jak robią to większość teoretycy złożoności), że nie wszystkie problemy w NP mają wydajne algorytmy, wynikałoby z tego, że dowody niezależności przy użyciu tych technik nie są możliwe. Dodatkowo wynik ten sugeruje, że udowodnienie niezależności od PA lub ZFC przy użyciu obecnie znanych technik nie jest łatwiejsze niż udowodnienie istnienia wydajnych algorytmów dla wszystkich problemów w NP.

Mam wrażenie, że czytając to pytanie, nie podano żadnego odpowiedniego przykładu problemu, który wymaga czegoś więcej niż tylko PA (nie mówiąc już o ZF), a doskonała odpowiedź Timothy Chow wyjaśnia, dlaczego tak trudno jest znaleźć przykłady. Istnieją jednak przykłady TCS wykraczające poza sferę arytmetyki, więc pomyślałem, że podam twierdzenie, które wymaga ściśle więcej niż . Chociaż nie wymaga pełnego wybranego aksjomatu, wymaga słabszej wersji.$ZF$

De Bruijin-Erdosa Twierdzenie teoria wykresu wskazuje, że liczba chromatyczna wykresu, , jest sup o a przebiega cały skończonych subgraphs o . Zauważ, że wniosek jest sceptycznie spełniony dla skończonego , więc jest to interesujące stwierdzenie o grafach nieskończonych. To twierdzenie ma wiele różnych dowodów, ale moim ulubionym jest przywołanie twierdzenia Tychonowa.χ ( H ) H G $G$$\chi(H)$$H$$G$$G$

Jak wspomniano w artykule w Wikipedii, z którym się powiązałem, twierdzenie to naprawdę i naprawdę wymaga więcej niż , jednak nie idzie tak daleko, że wymaga „pełnego aksjomatu wyboru”. Na stronie Wikipedii istnieje strasznie nieczytelny dowód, ale w gruncie rzeczy twierdzenie to mieści się w Modelu Solovaya z powodu sprytnych konstrukcji obejmujących teorię miar.$ZF$