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

67

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 .CfSCS

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.)Sb1b2x=b1b2xSxS SS

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).

Ryan Williams
źródło
CW? albo nie ? niepewny.
Suresh Venkat
Nie jestem też pewien ... to jedno pytanie, w którym jestem bardzo niepewny co do „złożoności” odpowiedzi ...
Ryan Williams
5
Inni matematycy nie zwracają uwagi na użycie tych aksjomatów jako dowodu lub nie zwracają na nie żadnej uwagi. Czy matematycy naprawdę używają obu aksjomatów niedbale? Jeśli przypadkowo przyjmiesz oba aksjomaty, możesz coś udowodnić!
Warren Schudy,
1
Przypuszczenie Harveya Friedmana . Nie wiem, czy dotyczy to również informatyki teoretycznej.
Kaveh
1
Nie znam żadnego wyniku w informatyce teoretycznej, którego nie można udowodnić w ZF, ale można to udowodnić w ciekawym rozszerzeniu ZF. To powiedziawszy, zgaduję, że nawet takie wyniki prawdopodobnie nie będą wymagały pełnego aksjomatu wyboru (AC) i że będą wymagały jedynie słabszej wersji AC, takiej jak aksjomat wyboru zależnego (DC) lub jeszcze słabszego aksjomatu policzalnego wybór (AC_ω). Nawiasem mówiąc , DC (a zatem AC_ω) jest zgodny z aksjomatem determinacji .
Tsuyoshi Ito

Odpowiedzi:

47

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”.PNP

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.

Timothy Chow
źródło
8
Udowodnienie normalizacji typowanego rachunku lambda z polimorfizmem wymaga co najmniej arytmetyki drugiego rzędu, a wykazanie tego samego w przypadku bardziej hojnych teorii typów może wymagać dużych kardynalnych aksjomatów, aczkolwiek dość skromnych. IIRC, dowód normalizacji Coq potrzebuje niezliczonej ilości niedostępnych, ponieważ można go użyć do kodowania argumentów uniwersalnych w stylu Grothendiecka.
Neel Krishnaswami,
3
@Neel: Dobra uwaga, chociaż te przykłady IMO „oszukują”, ponieważ jest to oczywiste, że możesz potrzebować silnych logicznych aksjomatów, aby udowodnić spójność systemu logicznego.
Timothy Chow,
4
Podoba mi się ta odpowiedź, ponieważ wyjaśnia, dlaczego stosowanie aksjomatu wyboru w TCS wydaje się niezwykle rzadkie.
Tsuyoshi Ito,
11
@Tsuyoshi: w rzeczywistości jest to jeszcze trudniejsze, aby znaleźć przykład, który należy przekroczyć nie tylko hierarchię arytmetyczną, ale także ponad , ponieważ wszystkie konsekwencje są już możliwe do udowodnienia w . Π 1 3 Z F C Z FΠ31Π31ZFCZF
Kaveh
1
Ta odpowiedź znajduje się na blogu społeczności.
Aaron Sterling
39

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.

Janne H. Korhonen
źródło
To dobry początek, ponieważ nie wiadomo, jak udowodnić twierdzenie inaczej.
Ryan Williams
7
Jak wspomniano na stronie Wikipedii, praca Friedmana, Robertsona i Seymoura na temat metamatematyki twierdzenia o grafie mniejszym pokazuje, że twierdzenie o grafie mniejszym implikuje (formę) twierdzenia o drzewku Kruskala nad podstawową teorią RCA_0, więc ustala to, że Twierdzenie o drzewie jest wymagane w przypadku silnego twierdzenia grafowego. Jednak to, czy oznacza to, że do twierdzenia o grafie mniejszym wymagany jest aksjomat wyboru, jest nieco trudnym pytaniem. Zależy to w subtelny sposób od tego, jak zdecydować się na twierdzenie o grafie mniejszym. Zobacz moją odpowiedź, aby uzyskać więcej informacji.
Timothy Chow
7
Emil Jeřábek pokazał na MathOverflow, jak udowodnić twierdzenie Robertsona-Seymour'a bez aksjomatu wyboru. Było to dla mnie zaskakujące, ponieważ miałem wrażenie, że Robertson-Seymour dla nieznakowanych grafów wymagał prądu zmiennego, ale było to oczywiście błędne wrażenie.
Timothy Chow,
Czy zaakceptowana odpowiedź jest w rzeczywistości fałszywa?
Andrej Bauer,
@AndrejBauer: Jeśli odwołujesz się do mojej odpowiedzi, masz rację, że to, co powiedziałem o Robertson-Seymour, jest błędne. Próbowałem teraz edytować swoją odpowiedź, ale nie mogłem. Może nie mam wystarczającej reputacji, aby edytować tak stary post.
Timothy Chow,
21

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.

Iddo Tzameret
źródło
16

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.R2

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.
Derrick Stolee
źródło
Czy to nie jest bardziej zorientowane na matematykę niż na TCS?
MS Dousti,
Dlatego powiedziałem „stycznie” związany. Problemy z kolorowaniem są zorientowane na TCS, ale nie na ten konkretny.
Derrick Stolee,
4
ahem. Chodzi o kolorowanie obiektów geometrycznych. Geometry na całym świecie przygotowują teraz cienkie taśmy do wysłania w twoją stronę :)α
Suresh Venkat
Doskonały. Uprawomocnienie.
Derrick Stolee,
5

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 0Tn:=ZFC+``There exist (at least) n inaccessible cardinals''n0
Sylvain
źródło
3

[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.

MS Dousti
źródło
5
Innym interesującym faktem (również z Wikipedii) jest to, że główna (jedyna?) Ogólna technika dowodzenia niezależności w ZFC, wymuszanie, nie może udowodnić, że P =? NP jest niezależna od ZFC. Jest to konsekwencja twierdzenia Shoenfielda o absolutności.
Travis Service
Zauważ, że Bill bierze udział w kolejnej ankiecie, która jest otwarta przez kolejny miesiąc: blog.computationalcomplexity.org/2011/06/…
Charles
@Charles: Dzięki za aktualizację. Bardzo chcę poznać najnowszy konsensus społeczności.
MS Dousti,
2

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 GGχ(H)HGG

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

Stella Biderman
źródło
Niezły przykład. Myślę, że Timothy Chow podał ten przykład w paragrafie na temat liczby chromatycznej samolotu.
Sasho Nikolov
@SashoNikolov Kolorystyka grafów jest moim zdaniem wyraźnie problemem TCS, nawet jeśli wykresy są nieskończone. Problem Hadwigera-Nelsona jest znacznie mniej oczywisty w dziedzinie TCS, jak zauważyli komentatorzy i OP tej odpowiedzi zgodził się. W przeciwieństwie do tego, nie sądzę, żeby był ktoś, kto spojrzałby na to twierdzenie i powiedziałby „to nie jest tak naprawdę problem CS”
Stella Biderman
W ogóle nie widzę takiego rozróżnienia: Hadwiger-Nelson również chodzi o kolorowanie nieskończonego wykresu geometrycznego. W każdym razie naprawdę podoba mi się oba przykłady i jestem za nimi i uważam, że nie ma sensu zbyt dobrze rozróżniać TCS od innych dziedzin matematyki.
Sasho Nikolov