Wyniki w teoretycznej CS niezależnej od ZFC

37

Zadam dość niejasne pytanie, ponieważ granica między informatyką teoretyczną a matematyką nie zawsze jest łatwa do rozróżnienia.

PYTANIE: Czy znasz jakieś interesujące wyniki w CS, które są albo niezależne od ZFC (tj. Standardowa teoria zbiorów), albo które zostały pierwotnie udowodnione w ZFC (+ niektóre inne aksjomaty), a dopiero później udowodnione w ZFC alorne?

Pytam, ponieważ jestem bliski ukończenia pracy doktorskiej, a mój główny wynik (determinacja klasy gier, które są używane do nadania „semantyki gry” probabilistycznemu modalnemu obliczeniom) jest w tej chwili udowodniony w ZFC rozszerzony o inne aksjomaty (mianowicie zaprzeczenie hipotezy Continuum ¬ C H i Martin's Axiom M A ).μ¬CHMA

Tak więc ustawieniem jest wyraźnie Informatyka (modalny calculus jest logiką czasową i rozszerzam go na pracę z systemami probabilistycznymi).μ

Chciałbym zacytować w mojej pracy inne przykłady tego rodzaju (jeśli są Państwo tego świadomi).

Z góry dziękuję,

PA

Matteo

IamMeeoh
źródło
9
Te poprzednie pytania mogą być pomocne: cstheory.stackexchange.com/questions/4816/… cstheory.stackexchange.com/questions/1923/...
Mark Reitblatt
9
Chciałem odpowiedzieć, że Matteo Mio i Alex Simpson użyli Aksjomatu Martina, aby udowodnić bardzo interesujące wyniki ...
Andrej Bauer,
7
To może być najlepszy przykład pytania, którego najlepsza odpowiedź zawiera samo pytanie! Nie wiedziałem o twoim bardzo interesującym wyniku.
Timothy Chow

Odpowiedzi:

19

Chociaż nie jestem świadomy żadnych takich wyników innych niż twoje, myślę, że możesz nieco rozszerzyć zakres i zapytać: jakie wyniki w TCS zostały udowodnione przy użyciu (dowolnego rodzaju) niestandardowych aksjomatów. Przez niestandardowy rozumiem tutaj coś innego niż klasyczna logika z ZF (lub ZFC).

Pięknym przykładem tego rodzaju pracy, którą mam na myśli, są wyniki Alexa Simpsona dotyczące właściwości języków programowania z wykorzystaniem syntetycznej teorii domen. Używa intuicyjnej teorii mnogości z aksjomatami sprzecznymi z logiką klasyczną.

Również Alex i ja zastosowaliśmy intuicyjne aksjomaty z antyklasycznymi zasadami ciągłości, aby pokazać wyniki dotyczące obliczalności Banacha-Mazura.

Jednak żaden z wymienionych przykładów nie ma statusu „otwartego”, podobnie jak twoje dowody, ponieważ wiemy, że stosowane przez nas niestandardowe aksjomaty można rozumieć po prostu jako działające w modelu matematyki intuicyjnej, w którym można wykazać, że model istnieje w ZFC. Tak więc niestandardowa konfiguracja jest naprawdę sposobem na bardziej eleganckie wykonanie i w zasadzie można to zrobić w prostej ZFC (chociaż boję się myśleć o tym, jak to dokładnie pójdzie).

Andrej Bauer
źródło
Dziękuję Ci! Zapytam Alex więcej szczegółów na ten temat, kiedy będę pisać wstęp.
IamMeeoh
13

To zależy od twojej definicji „informatyki”. Weź przykład poniżej - czy to się liczy?

NC1C2|C1(n)||C2(n)|LC1L

SCDSC

Oto dwie właściwości, które są niezależne od ZFC:

  1. Istnieje skala kodów.
  2. Istnieje skala kodów monotonicznych (tj. Dobrze uporządkowany zestaw kodów monotonicznych, który jest spójny w zestawie wszystkich kodów monotonicznych).
Yuval Filmus
źródło
Cześć Yuval, dzięki za odpowiedź. Nie jestem pewien, czy twój przykład pasuje do mojej definicji „informatyka”. Z pewnością mówienie o „kodach” nie wystarczy do sklasyfikowania go jako CS. Co sprawia, że ​​imho to „papier CS”: Czy pojawił się w jakiejś konferencji / czasopiśmie CS, czy też został użyty do udowodnienia jakiegoś wyniku w konferencji / czasopiśmie CS? na podstawie artykułu CS jestem dość elastyczny, ale tematami mogą być „teoria informacji, złożoność, logika programu / systemu, teoria rekurencji” itp. W każdym razie możesz przytoczyć źródło przykładu i / lub referatów, które wykorzystują „istnieje skala kodów ”? Dzięki! Pa
IamMeeoh,
1
Artykuły o kodach liczb całkowitych pojawiają się w czasopismach elektrotechnicznych, takich jak transakcje IEEE dotyczące teorii informacji. To trafia w jedno z twoich słów kluczowych.
Yuval Filmus
1
Nie wydaje mi się, żeby jakikolwiek papier wykorzystywał te wyniki. Ponadto głęboko wierzę, że wynik niezależny od ZFC nie ma sensu w złożoności, więc w pewnym sensie twoje pytanie dotyczy rozciągnięcia granic tego, co uważa się za informatykę.
Yuval Filmus,
1
Cześć Yuval, przede wszystkim jeszcze raz dziękuję za odpowiedzi. Nie zgadzam się jednak z twoją silną pozycją. Na przykład twierdzenie Robertsona-Seymour'a (które wydaje się wymagać wyboru) ma ważne konsekwencje w złożoności. Jest więc jasne, że Wybór jest użyteczny (może nieco zaskakujący) w teorii złożoności. Teraz praca ze spójnymi rozszerzeniami ZFC oczywiście upraszcza zadanie sprawdzania, powiedzmy, złożoności, wyników, nawet jeśli te wyniki są możliwe do udowodnienia w ZFC, ale nikt jeszcze nie wie jak.
IamMeeoh
1
Ponadto nie rozumiem, dlaczego nie powinny istnieć konkretne wyniki w złożoności niezależne od ZFC, podobnie jak twierdzenie Robertsona-Seymour'a jest (być może) niezależne od ZF.
IamMeeoh
9

DbDcbTccD

Stwierdzenie determinacji stopnia Turinga :

Każdy zestaw stopni Turinga zawiera stożek lub jest odłączony od jakiegoś stożka

jest konsekwencją aksjomatu determinacji (AD), który jest niezależny od ZF i niezgodny z ZFC. Słabsze stwierdzenie

Każdy zestaw reali Borela, który jest zamknięty w ramach równoważności Turinga, albo zawiera stożek, albo jest odłączony od stożka

jest konsekwencją twierdzenia Martina o determinacji Borela, którą można udowodnić w ZFC. Oba te stwierdzenia zostały zbadane, zanim udowodniono wynik Martina na determinacji Borela, w którym to czasie wiadomo było tylko, że oba można udowodnić w ZF + AD.

SbcSbTcSS

Carl Mummert
źródło
0

Wiele konstruktywnej matematyki. Zobacz pracę Per Martina-Löfa nad konstruktywną teorią zbiorów, stosowaną jako podstawa dla języków programowania o typie zależnym.

Obrabować
źródło
6
IIRC, teoria typu Martin-Lof ma taką samą wytrzymałość konsystencji jak teoria mnogości Kripkego-Platka, która jest znacznie słabsza niż ZFC. Ponadto MLTT nie ma żadnych wyraźnie antyklasycznych zasad, takich jak aksjomaty ciągłości, o których wspomniał Andrej.
Neel Krishnaswami,
@Neel Nigdy nie mówiłem nic o spójności lub sile MLTT. Uważam jednak, że niektóre wyniki w konstruktywnej matematyce są odpowiednie do pytania, prosząc o „interesujący wynik w CS, który jest… niezależny od ZFC”.
Rob
5
Zakładam, że „niezależny” ma tutaj znaczenie formalne.
Mark Reitblatt,