теорема Гёделя о полноте -- 3
Это третья, завершающая часть поста. Комментарии отменены; обсуждение всех трёх частей проводится здесь.
Часть первая
Часть вторая
12. Вспомним, как у нас строятся формулы. Мы не давали формального определения, а давали лишь описание. Сейчас мы из этого описания извлечём то, что нам нужно, причём говорить будем лишь о замкнутых формулах теории T*. Всякая такая формула, как было нами ранее сказано, строится при помощи логических связок и кванторов из более простых формул, а в основе всего лежат так называемые "атомарные" формулы, которые в нашем случае имеют вид P(d1,..., dk), где в предикатный символ подставлены некие константы. Для таких формул мы уже знаем, что они истинны тогда и только тогда, когда принадлжет теории T*. Удобно ввести "рабочий" термин на время доказательства: называть замкнутую формулу корректной, если она либо истинна и при этом принадлежит T*, либо ложна и при этом не принадлежит T*. Истинность и ложность здесь понимаются, конечно же, в интерпретации M, так как никакой другой у нас нет.
Все замкнутые формулы можно естественным образи разбить на "классы сложности", обращая внимание на то, сколько они содержат логических символов -- связок и кванторов вместе взятых. Атомарные формулы будут относиться к классу 0, и про них мы уже знаем, что они корректны. Мы будем постепенно переходить от более простых формул к более сложным, сначала убеждаясь в корректности формул класса 1, затем -- класса 2, и так далее для всех формул. Поэтому следует проанализировать случай формулы, содержащей связки или кванторы, и убедится в её корректности -- в предположении, что мы это уже сделали для формул более простых, содержащих меньше связок и кванторов, то есть принадлежащих каким-то предыдущим, уже рассмотренным классам.
В соответствии с правилами построения формул, может возникнуть три случая. Замкнутая формула, которую мы анализируем на предмет корректности, может быть либо а) отрицанием формулы, либо б) импликацией формул, либо в) получаться из некоторой формулы при помощи "навешивания" квантора всеобщности. Все эти случаи мы сейчас и рассмотрим.
а) Ф есть отрицание некоторой формулы, то есть имеет вид not(Ψ). Заметим, что корректность Ψ нам уже известна, так как она принадлежит предыдущему, уже рассмотренному классу. Если Ψ истинна и принадлежит T*, то Ф ложна, и не принадлежит T* ввиду непротиворечивости теории. Если Ψ ложна и не принадлежит T*, то Ф, соответственно, истинна, и принадлежит T* -- теперь уже ввиду полноты теории. То есть Ф корректна.
б) Пусть теперь Ф имеет вид импликации: (Ψ1 -> Ψ2). Каждая из формул Ψ1, Ψ2 не содержит символа -> посередине, а потому она входит в один из предыдущих классов, то есть обе эти формулы корректны. В зависимости от того, истинны они или ложны, возникают три подслучая.
(i) Ψ1 ложна и не принадлежит T*. Тогда Ф как импликация с ложной посылкой оказывается истинной, и нам надо убедиться в том, что она входит в T*. Прежде всего, формула not(Ψ1) имеется в T* ввиду полноты, и остаётся сослаться на тот факт, что из not(Ψ1) логически следует Ψ1 -> Ψ2 по правилам логического рассуждения. Это очень простой факт на уровне исчисления высказываний, но мы коротко напомним обоснование. Нужно принять посылку импликации и вывести её заключение, что далее нас приводит к цели ввиду правила (2). Но принятие посылки импликации создаёт ситуацию противоречия, где выводимым является что угодно при помощи универсального "трюка": надо инициировать рассуждение от противного, предположив, что доказывамое не имеет места, после чего заявить об имеющемся противоречии. Действуем мы при этом строго в соответствии с правилами. Таким образом, мы выводим Ф и тем самым получаем, что Ф принадлежит T*.
(ii) Ψ2 истинна и принадлежит T*. Здесь Ф также истинна по определению импликации, и достаточно вывести Ф из Ψ2. Делается это опять-таки при помощи тавтологий исчисления высказываний, и я напомню, как именно. Доказывая импликацию, мы принимаем её посылку, а потом обнаруживаем, что заключение её у нас уже есть. Тем самым импликация доказана ввиду (2). Здесь фактически реализован тот принцип, что если нечто "верно", то оно тем более будет верным и "условно", то есть с учётом дополнительного условия, которое здесь просто упоминается для соблюдения необходимых формальностей.
(iii) Ψ1 истинна, Ψ2 ложна. Это случай, когда импликация Ф ложна. Ввиду корректности формул Ψ1 и Ψ2, а также полноты теории T*, мы можем опереться на то, что в эту теорию входят Ψ1 и not(Ψ2). Убедится же нам надо в том, что Ф отсутствует в T*, для чего достаточно убедиться в совсем простой вещи: что Ф вступает в противоречие с предыдущими двумя формулами. Что очевидно, так как из Ψ1 и Ψ1 -> Ψ2 по правилу (1) выводится Ψ2, и возникает противоречие с not(Ψ2).
Во всех трёх подслучаях импликация Ф оказалась корректной.
в) Ф имеет вид (Ax)Ψ(x) для некоторой формулы Ψ, которую мы для удобства записали в виде Ψ(x). Возможно два варианта: либо Ф входит в T*, либо не входит. В первом случае надо установить её истинность, а во втором -- ложность.
Пусть Ф входит в T*. Предположим, что она не будет истинной. Это означает, что Ψ(x) выполняется не для всех d из D, а потому при некотором d формула Ψ(d) ложна. Поскольку эта формула замкнута, и она "утратила" квантор, то она входит в уже рассмотренный ранее класс формул, про которые установлена их корректность. Поэтому Ψ(d) в теорию T* не входит, и тогда ввиду полноты, туда входит её отрицание not(Ψ(d)). Однако к формуле Ф можно применить правило (5) перехода к частному случаю, выводя из (Ax)Ψ(x) её частный случай Ψ(d), который тем самым входит в T*. В итоге мы обнаруживаем в T* две прямо противоречащие друг другу формулы, а этого быть не может. Следовательно, наше предположение ошибочно, и Ф обязана быть истинной.
Пусть теперь Ф не входит в T*. Так как T* полна, в неё входит not(Ф), то есть not((Ax)Ψ(x)). Но это есть не что иное как E-формула, и мы её просматривали на каком-то из этапов, строя экзистенциальное пополнение теории C(Tn). В этот момент мы добавляли специальную константу d, а к теории присоединяли формулу not(Ψ(d)). Формула Ψ(d) замкнута, а также корректна, так как принадлежит предыдущему классу. Она не может входить в T* ввиду непротиворечивости последней, то есть она ложна. Откуда сразу ясно, что Ф также ложна, поскольку ложным оказывается частный случай формулы Ψ(x), возникающий при подстановке d вместо x.
Итак, все проверки завершены, и нами построена модель M непротиворечивой теории T. Легко заметить, что она всегда является счётной. Иногда её возможно бывает "сжать" даже до конечной, отождествляя те элементы, роль которой во всех рассматриваемых свойствах неотличима. Полезно также отследить использование нами всех пяти правил логического рассуждения в ходе проверок.
Есть ещё момент, который я считаю очень важным: мы построили модель, и хочется спросить, а единственна ли она? Ответ в подавляющем большинстве случаев отрицательный, то есть обычно таких моделей бывает очень много, и они друг от друга отличаются при помощи каких-то свойств, выразимых на языке теории. Причину этого явления можно понять вот как. Когда мы нумеруем формулы, то эта нумерация может быть осуществлена как угодно. И когда мы "определяемся" по каждому вопросу, то может так оказаться, что в принципе мы могли бы принять как Ф, так и не-Ф, потому что ни одно из этих положений из всего предыдущего логически не следует. Поскольку описанный нами способ заключается в том, что мы соглашаемся со всем, что не ведёт к противоречию, то при одной нумерации формул, когда Ф нам встретится раньше, мы в конце концов построим модель, на которой выполнено условие Ф. А если нумерация устроена иначе, и нам раньше встретится формула not(Ф), то примем мы уже её (а Ф потом, конечно, отвергнем), и построенная модель условию Ф удовлетворять не будет. Учитывая то, по скольким вопросам, где априори допустимы оба ответа, мы можем по-разному "определиться", можно себе представить, какое огромное количество моделей при этом процессе в принципе может возникнуть. Это говорит не о чём ином как о невероятном изобилии "возможных миров".
Мы также обещали сказать, что будет, если мы работаем с несчётными множествами символов. Здесь разница только в том, что вместо нумерации формул натуральными числами и проведения "обычной" индукции при построениях, нужно опираться на "нумерацию" элементов множеств "порядковыми числами" или "ординалами", которые суть обобщение натуральных чисел. Такое всегда возможно, если применить теорему Цермело -- следствие "аксиомы выбоа" в теории множеств. Индукция же при этом становится "трансфинитной". В остальном же никаких отличий от счётного случая не имеется. (Понимание этого абзаца теми, кто не имеет специальной подготовки, не предполагается.)
В заключение хотелось бы подчеркнуть, что если рассмотреть какую-либо "абстрактную" математическую задачу в очень общей постановке -- когда речь идёт о доказательстве чего-то, о выводе какого-то положения из аксиом, то возможны две принципиально разные ситуации. Такое доказательство либо возможно, либо невозможно. В первом случае его можно предъявить -- хотя бы в принципе, поскольку оно являет собой некий построенный по чётким правилам текст конечной длины. Во втором же случае, когда доказательтва не имеется, ввиду теоремы Гёделя о полноте должен существовать "контрпример" вот в каком смысле: должна существовать такая модель, на которой выполнены все "аксиомы", а то положение, которое мы хотели доказать -- не выполнено. Надо заметить, что хотя это и всегда возможно, но реальное построение такой модели зачастую оказывается очень трудным, поскольку "материала" для построения возможных моделей так много, что он не подлежит какому бы то ни было "перебору" -- в отличие от текстов. Последнее замечание наводит на мысль о "творческой неисчерпаемости" той части математической деятельности, которая относится к созданию новых конструкций (моделей).
К ОБСУЖДЕНИЮ
Часть первая
Часть вторая
12. Вспомним, как у нас строятся формулы. Мы не давали формального определения, а давали лишь описание. Сейчас мы из этого описания извлечём то, что нам нужно, причём говорить будем лишь о замкнутых формулах теории T*. Всякая такая формула, как было нами ранее сказано, строится при помощи логических связок и кванторов из более простых формул, а в основе всего лежат так называемые "атомарные" формулы, которые в нашем случае имеют вид P(d1,..., dk), где в предикатный символ подставлены некие константы. Для таких формул мы уже знаем, что они истинны тогда и только тогда, когда принадлжет теории T*. Удобно ввести "рабочий" термин на время доказательства: называть замкнутую формулу корректной, если она либо истинна и при этом принадлежит T*, либо ложна и при этом не принадлежит T*. Истинность и ложность здесь понимаются, конечно же, в интерпретации M, так как никакой другой у нас нет.
Все замкнутые формулы можно естественным образи разбить на "классы сложности", обращая внимание на то, сколько они содержат логических символов -- связок и кванторов вместе взятых. Атомарные формулы будут относиться к классу 0, и про них мы уже знаем, что они корректны. Мы будем постепенно переходить от более простых формул к более сложным, сначала убеждаясь в корректности формул класса 1, затем -- класса 2, и так далее для всех формул. Поэтому следует проанализировать случай формулы, содержащей связки или кванторы, и убедится в её корректности -- в предположении, что мы это уже сделали для формул более простых, содержащих меньше связок и кванторов, то есть принадлежащих каким-то предыдущим, уже рассмотренным классам.
В соответствии с правилами построения формул, может возникнуть три случая. Замкнутая формула, которую мы анализируем на предмет корректности, может быть либо а) отрицанием формулы, либо б) импликацией формул, либо в) получаться из некоторой формулы при помощи "навешивания" квантора всеобщности. Все эти случаи мы сейчас и рассмотрим.
а) Ф есть отрицание некоторой формулы, то есть имеет вид not(Ψ). Заметим, что корректность Ψ нам уже известна, так как она принадлежит предыдущему, уже рассмотренному классу. Если Ψ истинна и принадлежит T*, то Ф ложна, и не принадлежит T* ввиду непротиворечивости теории. Если Ψ ложна и не принадлежит T*, то Ф, соответственно, истинна, и принадлежит T* -- теперь уже ввиду полноты теории. То есть Ф корректна.
б) Пусть теперь Ф имеет вид импликации: (Ψ1 -> Ψ2). Каждая из формул Ψ1, Ψ2 не содержит символа -> посередине, а потому она входит в один из предыдущих классов, то есть обе эти формулы корректны. В зависимости от того, истинны они или ложны, возникают три подслучая.
(i) Ψ1 ложна и не принадлежит T*. Тогда Ф как импликация с ложной посылкой оказывается истинной, и нам надо убедиться в том, что она входит в T*. Прежде всего, формула not(Ψ1) имеется в T* ввиду полноты, и остаётся сослаться на тот факт, что из not(Ψ1) логически следует Ψ1 -> Ψ2 по правилам логического рассуждения. Это очень простой факт на уровне исчисления высказываний, но мы коротко напомним обоснование. Нужно принять посылку импликации и вывести её заключение, что далее нас приводит к цели ввиду правила (2). Но принятие посылки импликации создаёт ситуацию противоречия, где выводимым является что угодно при помощи универсального "трюка": надо инициировать рассуждение от противного, предположив, что доказывамое не имеет места, после чего заявить об имеющемся противоречии. Действуем мы при этом строго в соответствии с правилами. Таким образом, мы выводим Ф и тем самым получаем, что Ф принадлежит T*.
(ii) Ψ2 истинна и принадлежит T*. Здесь Ф также истинна по определению импликации, и достаточно вывести Ф из Ψ2. Делается это опять-таки при помощи тавтологий исчисления высказываний, и я напомню, как именно. Доказывая импликацию, мы принимаем её посылку, а потом обнаруживаем, что заключение её у нас уже есть. Тем самым импликация доказана ввиду (2). Здесь фактически реализован тот принцип, что если нечто "верно", то оно тем более будет верным и "условно", то есть с учётом дополнительного условия, которое здесь просто упоминается для соблюдения необходимых формальностей.
(iii) Ψ1 истинна, Ψ2 ложна. Это случай, когда импликация Ф ложна. Ввиду корректности формул Ψ1 и Ψ2, а также полноты теории T*, мы можем опереться на то, что в эту теорию входят Ψ1 и not(Ψ2). Убедится же нам надо в том, что Ф отсутствует в T*, для чего достаточно убедиться в совсем простой вещи: что Ф вступает в противоречие с предыдущими двумя формулами. Что очевидно, так как из Ψ1 и Ψ1 -> Ψ2 по правилу (1) выводится Ψ2, и возникает противоречие с not(Ψ2).
Во всех трёх подслучаях импликация Ф оказалась корректной.
в) Ф имеет вид (Ax)Ψ(x) для некоторой формулы Ψ, которую мы для удобства записали в виде Ψ(x). Возможно два варианта: либо Ф входит в T*, либо не входит. В первом случае надо установить её истинность, а во втором -- ложность.
Пусть Ф входит в T*. Предположим, что она не будет истинной. Это означает, что Ψ(x) выполняется не для всех d из D, а потому при некотором d формула Ψ(d) ложна. Поскольку эта формула замкнута, и она "утратила" квантор, то она входит в уже рассмотренный ранее класс формул, про которые установлена их корректность. Поэтому Ψ(d) в теорию T* не входит, и тогда ввиду полноты, туда входит её отрицание not(Ψ(d)). Однако к формуле Ф можно применить правило (5) перехода к частному случаю, выводя из (Ax)Ψ(x) её частный случай Ψ(d), который тем самым входит в T*. В итоге мы обнаруживаем в T* две прямо противоречащие друг другу формулы, а этого быть не может. Следовательно, наше предположение ошибочно, и Ф обязана быть истинной.
Пусть теперь Ф не входит в T*. Так как T* полна, в неё входит not(Ф), то есть not((Ax)Ψ(x)). Но это есть не что иное как E-формула, и мы её просматривали на каком-то из этапов, строя экзистенциальное пополнение теории C(Tn). В этот момент мы добавляли специальную константу d, а к теории присоединяли формулу not(Ψ(d)). Формула Ψ(d) замкнута, а также корректна, так как принадлежит предыдущему классу. Она не может входить в T* ввиду непротиворечивости последней, то есть она ложна. Откуда сразу ясно, что Ф также ложна, поскольку ложным оказывается частный случай формулы Ψ(x), возникающий при подстановке d вместо x.
Итак, все проверки завершены, и нами построена модель M непротиворечивой теории T. Легко заметить, что она всегда является счётной. Иногда её возможно бывает "сжать" даже до конечной, отождествляя те элементы, роль которой во всех рассматриваемых свойствах неотличима. Полезно также отследить использование нами всех пяти правил логического рассуждения в ходе проверок.
Есть ещё момент, который я считаю очень важным: мы построили модель, и хочется спросить, а единственна ли она? Ответ в подавляющем большинстве случаев отрицательный, то есть обычно таких моделей бывает очень много, и они друг от друга отличаются при помощи каких-то свойств, выразимых на языке теории. Причину этого явления можно понять вот как. Когда мы нумеруем формулы, то эта нумерация может быть осуществлена как угодно. И когда мы "определяемся" по каждому вопросу, то может так оказаться, что в принципе мы могли бы принять как Ф, так и не-Ф, потому что ни одно из этих положений из всего предыдущего логически не следует. Поскольку описанный нами способ заключается в том, что мы соглашаемся со всем, что не ведёт к противоречию, то при одной нумерации формул, когда Ф нам встретится раньше, мы в конце концов построим модель, на которой выполнено условие Ф. А если нумерация устроена иначе, и нам раньше встретится формула not(Ф), то примем мы уже её (а Ф потом, конечно, отвергнем), и построенная модель условию Ф удовлетворять не будет. Учитывая то, по скольким вопросам, где априори допустимы оба ответа, мы можем по-разному "определиться", можно себе представить, какое огромное количество моделей при этом процессе в принципе может возникнуть. Это говорит не о чём ином как о невероятном изобилии "возможных миров".
Мы также обещали сказать, что будет, если мы работаем с несчётными множествами символов. Здесь разница только в том, что вместо нумерации формул натуральными числами и проведения "обычной" индукции при построениях, нужно опираться на "нумерацию" элементов множеств "порядковыми числами" или "ординалами", которые суть обобщение натуральных чисел. Такое всегда возможно, если применить теорему Цермело -- следствие "аксиомы выбоа" в теории множеств. Индукция же при этом становится "трансфинитной". В остальном же никаких отличий от счётного случая не имеется. (Понимание этого абзаца теми, кто не имеет специальной подготовки, не предполагается.)
В заключение хотелось бы подчеркнуть, что если рассмотреть какую-либо "абстрактную" математическую задачу в очень общей постановке -- когда речь идёт о доказательстве чего-то, о выводе какого-то положения из аксиом, то возможны две принципиально разные ситуации. Такое доказательство либо возможно, либо невозможно. В первом случае его можно предъявить -- хотя бы в принципе, поскольку оно являет собой некий построенный по чётким правилам текст конечной длины. Во втором же случае, когда доказательтва не имеется, ввиду теоремы Гёделя о полноте должен существовать "контрпример" вот в каком смысле: должна существовать такая модель, на которой выполнены все "аксиомы", а то положение, которое мы хотели доказать -- не выполнено. Надо заметить, что хотя это и всегда возможно, но реальное построение такой модели зачастую оказывается очень трудным, поскольку "материала" для построения возможных моделей так много, что он не подлежит какому бы то ни было "перебору" -- в отличие от текстов. Последнее замечание наводит на мысль о "творческой неисчерпаемости" той части математической деятельности, которая относится к созданию новых конструкций (моделей).
К ОБСУЖДЕНИЮ