Математика
Научно-популярное
Комментарии 32
+1
Так ответ на «Главный вопрос жизни, вселенной и всего такого» — 21, а не 42?
+2

А ведь говорят же, что правильно сформулированный вопрос содержит в себе половину ответа… Мы на верном пути, товарищи!

+1
Говорят, что половина ответа содержится в самом вопросе. Но вот только в данном случае как раз вопроса никто и не знает.
0
Пф. Я знаю вопрос: «Главный вопрос жизни, вселенной и всего такого»
+3
Истинные утверждения, которые невозможно доказать, могут существовать. Если утверждение не доказано, нельзя сказать может ли оно быть доказано или нет. Спасибо товарищу Гёделю…
0
Нет, товарищ Гедель как раз доказал, что все истинные утверждения доказуемы (completeness theorem). Теорема о неполноте немного про другое.
0
Формула является выводимой, если она истинна. Но не всякая формула выводима, разве нет?
0
Да, например, не тождественно истинные формулы невыводимы (soundness). Но только они тогда, как ни странно, не истинные, вопреки первой фразе из исходного комментария.
+5
Все истинные утверждения доказуемы в исчислении предикатов (completeness theorem). В арифметике и более сильных теориях уже нет. Тут даже не сила теории важна, а выразительность языка. Если в теории можно говорить о натуральных числах (или о словах в конечном алфавите), то она неполна.
0
Арифметика Пеано вполне себе выражается в исчислении предикатов, если расширить его схемой аксиом для индукции (чтобы не залезать в квантификацию по предикатам).
+3
Поверьте на слово специалисту по матлогике. Гёдель сначала доказал полноту исчисления предикатов (там можно доказать все содержательно истинные формулы), потом попытался доказать полноту арифметики и обнаружил, что она неполна. Содержательно, если в теории можно говорить о словах в конечном алфавите, то в ней можно говорить и о её собственных формулах (которые тоже слова в конечном алфавите). Дальше хитрым трюком строится формула, говорящая что-то о себе самой, она оказывается не доказуема и не опровержима. Что-то вроде парадокса лжеца, но хитрее.
0
Так зачем так сложно, если мы о неполноте говорим? Достаточно рассмотреть более простую (без индукции) теорию натуральных чисел, которая окажется неполной в FOL.

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

А так-то я в матлогике дно, прост книжки всякие читаю на досуге. Так что интересно, где и что я не понимаю правильно.
0
Если начать с исчисления высказываний: там есть таблицы истинности и формула может быть «общезначимой на таблицах истинности» и есть правила вывода, позволяющие некоторые формулы доказывать. Довольно легко проверить, что все доказуемые формулы общезначимы (надо проверить, что все правила вывода из общезначимых формул получают опять общезначимые), это soundness (всё, что можно доказать, истинно в содержательном смысле). В обратную сторону, что все общезначимые формулы доказуемы (completeness), проверить труднее. Можно, например, использовать дизъюнктивные (или конъюнктивные, всё равно) нормальные формы. Для общезначимой формулы в д.н.ф. сравнительно легко понять, как её доказывать. Это первым сделал, кажется, Пост в 20-е годы. Гёдель доказал аналогичную теорему о полноте для исчисления предикатов, там формула «общезначима», если она верна при любой интерпретации входящих в неё предикатных символов. Все общезначимые формулы доказуемы в исчислении предикатов, мы не упустили никаких важных логических законов, когда выписывали исчисление предикатов.
0
Это как раз понятно.

Равно как и понятно, что если у вас есть теория, из которой не выводится некоторая формула и не выводится её отрицание, то она неполна, только и всего (можно, например, взять теорию упорядоченных множеств и формулу, показывающую всюду плотность — в некоторых интерпретациях она истина, в некоторых — ложна, но каких-то громких слов из этого не следует).

Тогда остаётся непонятным, о чём спор :)
0
Вы снова вернули мне веру в себя, а то я уже думал что что-то не так понял! Есть хорошие книги на эту тему для полных профанов?
+2
Вот в этих двух архивах
www.mediafire.com/download/cn7hskh3t3w1uto/djvu.rar
www.mediafire.com/download/4g54uiij5yvezu8/pdf.rar
почти все книги по матлогике, изданные в СССР (и некоторое количество философской фигни, вроде Зиновьева). Собирал один энтузиаст уже давно, сейчас многое есть в лучшем качестве на libgen. Попробуйте почитать Клини «Введение в метаматематику» и Колмогоров, Драгалин «Введение в математическую логику». Если не понравится, попробуйте всё остальное (но книга Гильберта и Бернайса столетней давности как учебник уже не годится). Клини однажды приезжал в Советский Союз и его водили в сберкассу МГУ получать гонорар за книгу. Клини спросил «Какой тираж?», ему сказали «десять тысяч». Клини офигел и сказал «У вас десять тысяч математических логиков???»
0
большинство математиков стало считать, что ранг ничем не ограничен, что означает, что можно обнаружить кривые с бесконечно большими рангами.
С каких пор оно это стало означать? Значения функции y=x² тоже не ограничены сверху, однако это не означает, что существует x, для которого y имеет бесконечное значение. Или под «бесконечно большими рангами» подразумеваются «сколь угодно большие»?

Однако модель поведала иную историю. Она говорит о том, что существует лишь конечное число эллиптических кривых с рангом более 21. А если их конечное количество, то у одной из них ранг будет наивысшим – что будет означать, что у ранга всё же есть верхняя граница.
Не увидел логической связи. «Конечное количество» вполне может означать: две кривых с рангом 22, три кривых с рангом 42 и десять кривых с рангом ∞.
0
Мне кажется, здесь удачнее перевести как «представляется возможным»…
But by the 1970s the prevailing view had shifted — most mathematicians had come to believe that rank was unbounded, meaning it should be possible to find curves with infinitely high ranks.

… и «могло бы означать»:
If there are only finitely many of them, one of them has to have the highest rank in the bunch — which would mean that rank is bounded after all.
0
Мне кажется, здесь удачнее перевести как «представляется возможным»…
Так результат же не меняется. Что так, что эдак, а возможность бесконечного ранга из приведённого текста никак не следует.

… и «могло бы означать»
А тут, на мой взгляд, просто согласование глагольных форм. «Если А, то Б, в каковом случае было бы В.» «Would» — не для обозначения возможности, а как условная форма.
0

Если считать, что имеются в виду "сколь угодно большие" ранги, то по второму вашму пункту проблем нет: две кривых с рангом 22, три кривых с рангом 42 и десять кривых с рангом 7654467899422 (большое, но конечное число, являющееся верхней границей).

0
Дело в том, что может быть так, а может быть эдак. Предложение сформулировано в причинно-следственной форме, тогда как по факту этой связи там нет. Ранг может быть как конечным (пусть и сколь угодно большим), так и бесконечным; и для обоих случаев возможна ситуация, когда кривых с рангом, превышающим 21, конечное число (для конечного ранга ваш пример, для бесконечного ранга — мой).

Возможно, отсутствующие связи имеются в исходной работе, но в таком случае статья должна хотя бы упомянуть об этом, а не подсовывать неадекватные логические цепочки.
+1
Я не могу понять, о чём вы тут спорите, если определение ранга эллиптической кривой свободно доступно в википедии, и из него очевидно, что ранг всегда конечен
0
OK, спасибо за наводку (я до этого пытался нагуглить, но подходящих статей сходу найти не удалось). В таком случае к статье остаётся претензия по отсутствию явного упоминания этого факта и по использованию термина «кривые с бесконечно большими рангами», что совсем не равносильно «кривым со сколь угодно большими рангами».
+1
Ранг эллиптической кривой — это по определению целое число, бесконечным он быть не может
0
В определении, сказано размер множества независимых «примитивных» рациональных чисел, из которых строится множество остальных рациональных решений. Это множество вполне может быть и бесконечным.
0
Не может. В этом и состоит содержательное утверждение теоремы Морделла
Только полноправные пользователи могут оставлять комментарии. , пожалуйста.