Результаты в теоретической CS независимо от ZFC

37

Я собираюсь задать довольно расплывчатый вопрос, поскольку грань между теоретической информатикой и математикой не всегда легко различить.

ВОПРОС: Известно ли вам о каком-либо интересном результате в CS, который либо не зависит от ZFC (т. Е. Стандартная теория множеств), либо который был первоначально доказан в ZFC (+ некоторая другая аксиома) и только позже доказан в ZFC alorne?

Я спрашиваю, потому что я близок к завершению своей кандидатской диссертации, и мой основной результат (определенность класса игр, которые используются для придания "семантики игры" вероятностному модальному вычислению) в настоящий момент доказан в ZFC распространяется на другие аксиомы (а именно отрицание гипотезы Континуума ¬ C H и аксиомы Мартина ).μ¬СЧАСMA

Таким образом, настройка явно является информатикой (модальный калькуляция - это временная логика, и я расширяю ее для работы с вероятностными системами).μ

Я хотел бы привести в своей диссертации другие примеры (если вы их знаете) такого рода.

Заранее спасибо,

до свидания

Matteo

IamMeeoh
источник
9
Эти предыдущие вопросы могут быть полезны: cstheory.stackexchange.com/questions/4816/… cstheory.stackexchange.com/questions/1923/…
Марк Рейтблатт
9
Я собирался ответить, что Маттео Мио и Алекс Симпсон использовали аксиому Мартина, чтобы доказать очень интересные результаты ...
Андрей Бауэр
7
Это может быть лучший пример, который я видел в вопросе, лучший ответ которого содержится в самом вопросе! Я не знал о вашем очень интересном результате.
Тимоти Чоу

Ответы:

19

Хотя я не знаю ни о каких таких результатах, кроме ваших собственных, я думаю, что вы могли бы немного расширить сферу и спросить: какие результаты в TCS были доказаны с использованием (любого рода) нестандартных аксиом. Под нестандартным здесь я подразумеваю нечто иное, чем классическая логика с ZF (или ZFC).

Прекрасным примером работы, которую я имею в виду, являются результаты Алекса Симпсона о свойствах языков программирования, использующих синтетическую теорию предметной области. Он использует интуиционистскую теорию множеств с аксиомами, которые противоречат классической логике.

Кроме того, Алекс и я использовали интуиционистские аксиомы с антиклассическими принципами непрерывности, чтобы показать результаты о вычислимости Банаха-Мазура.

Однако ни один из упомянутых примеров не имеет «открытого» статуса, как ваши доказательства, потому что мы знаем, что нестандартные аксиомы, которые мы использовали, могут быть поняты просто как работа внутри модели интуиционистской математики, где модель может быть показана как существующая в ZFC. Таким образом, нестандартная настройка - это действительно способ сделать вещи более элегантно, и в принципе они могут быть выполнены в прямом ZFC (хотя я боюсь думать о том, как именно это будет происходить).

Андрей Бауэр
источник
Спасибо! Я спрошу Алекса более подробно об этом, когда буду писать введение.
IamMeeoh
13

Это зависит от вашего определения "компьютерных наук". Возьмите пример ниже - это считается?

Кодирования целых чисел однозначно декодируемый бинарный код . Если длина кодовых слов не уменьшается, мы называем код монотонным . КодN являетсялучшечем кода C 2 , если | C 1 ( n ) | - | C 2 ( n ) | - . Другими словами, для каждого L из некоторой точки на кодовых словах C 1 по меньшей мере LС1С2|С1(N)|-|С2(N)|-LС1L бит короче.

Набор кодов называется конфинально , если для каждого кода C есть код D S , который лучше , чем C . Это хорошо упорядочено, если оно упорядочено по отношению к «лучше». шкалаSСDSС является вполне упорядоченным конфинально набор кодов.

Вот два свойства, которые не зависят от ZFC:

  1. Существует шкала кодов.
  2. Существует шкала монотонных кодов (т.е. хорошо упорядоченный набор монотонных кодов, который является окончательным в наборе всех монотонных кодов).
Юваль Фильмус
источник
Привет Юваль, спасибо за ответ. Я не уверен, что ваш пример соответствует моему определению "Компьютерные науки". Конечно, говорить о «кодах» недостаточно для того, чтобы классифицировать его как CS. Что делает бумагу «бумагой CS» в следующем: это появилась в какой-либо конференции / журнале CS, или она использовалась для доказательства какого-либо результата в конференции / журнале CS? КС бумага, я довольно гибок, но темы могут быть "теория информации, сложность, логика программы / системы, теория рекурсии" и т. д. В любом случае вы можете привести источник примера и / или статей, которые используют "существует масштаб кодов "? Благодарность! Пока
IamMeeoh
1
Статьи о кодах целых чисел появляются в электротехнических журналах, таких как транзакции IEEE по теории информации. Это поражает одно из ваших ключевых слов.
Юваль Фильмус
1
Я не думаю, что есть какие-либо документы, использующие эти результаты. Более того, я твердо верю, что результат, независимый от ZFC, не имеет смысла в сложности, поэтому в некотором смысле ваш вопрос касается расширения границ того, что считается информатикой.
Юваль Фильмус
1
Здравствуйте, Юваль, прежде всего, позвольте мне еще раз поблагодарить вас за ответы. Однако я не согласен с вашей сильной позицией. Например, теорема Робертсона-Сеймура (которая, кажется, требует выбора) имеет важные последствия в сложности. Таким образом, ясно, что Выбор полезен (возможно, немного удивительно) в теории сложности. Теперь работа с согласованными расширениями ZFC, очевидно, упрощает задачу проверки, скажем, сложности результатов, даже если эти результаты могут быть доказаны в ZFC, но пока никто не знает как.
IamMeeoh
1
Кроме того, я не понимаю, почему не должно быть конкретных результатов в сложности, независимых от ZFC, точно так же, как теорема Робертсона-Сеймура (возможно) не зависит от ZF.
IamMeeoh
9

DbDcbTссD

Утверждение определенности степени Тьюринга :

Каждый набор степеней Тьюринга либо содержит конус, либо не пересекается с некоторым конусом

является следствием аксиомы определенности (AD), которая не зависит от ZF и несовместима с ZFC. Более слабое утверждение

Каждое борелевское множество вещественных чисел, замкнутое по эквивалентности Тьюринга, содержит либо конус, либо не пересекается с конусом

является следствием теоремы Мартина о борелевской определимости, доказуемой в ZFC. Оба эти утверждения были изучены до того, как был доказан результат Мартина об определенности Бореля, когда было известно только, что они оба доказуемы в ZF + AD.

Второй приведенный результат имеет следующий интересный вывод: предположим, что - борелевское множество вещественных чисел, замкнутое по эквивалентности Тьюринга, такое, что для любого действительного bSбсSбTсSS

Карл Муммерт
источник
5

Недавно я участвовал в беседе с одним из таких результатов, посвященным определению игр Büchi с одним счетчиком: Оливье Финкель, «Определенность бесконтекстных игр» , STACS 2012, http://drops.dagstuhl.de/opus/volltexte/2012/ 3389 / pdf / 5.pdf .

Сильвен
источник
0

Много конструктивной математики. См. Работу Пера Мартина-Лёфа о конструктивной теории множеств, используемой в качестве основы для языков программирования с зависимой типизацией.

обкрадывать
источник
6
IIRC, теория типа Мартина-Лофа имеет такую ​​же прочность согласованности, как теория множеств Крипке-Платека, которая значительно слабее, чем ZFC. Кроме того, MLTT не имеет явных антиклассических принципов, таких как аксиомы непрерывности, упомянутые Андреем.
Нил Кришнасвами
@Neel Я никогда не говорил ничего о последовательности или силе MLTT. Тем не менее, я считаю, что некоторые результаты в конструктивной математике имеют отношение к вопросу, требуя «интересного результата в CS, который ... независим от ZFC».
Роб
5
Я предполагаю, что «независимый» здесь подразумевается в формальном смысле.
Марк Рейтблатт