теорема Гёделя о полноте -- 1
Этот пост я планировал написать чуть ли не с лета, но всё как-то откладывал и откладывал. Но вот в недавней френд-ленте мне встретилось упоминание о том же самом, и я в комментах пообещал, что напишу планируемый пост в самое ближайшее время. Как и предыдущие мои посты, затрагивающие логическую тематику (некоторые из записей перечислены здесь), он идёт как открытый. Комментарии отменены, а для обсуждения я завожу, как обычно, отдельный пост (тоже открытый).
Как обычно, мой текст адресован всем, кто сколько-нибудь интересуется логической проблематикой. Писать я стараюсь всегда в "популярном" стиле, то есть стремлюсь к тому, чтобы не требовалось специальных знаний, и текст мог быть понят, например, теми, кого называют "гуманитариями". Кроме того, я даже в постах на тему математической логики, стремлюсь не перегружать читателя обилием формул, в которые надо вникать. В идеале, такого рода текст должен читаться примерно как художественная литература, то есть всё должно усваиваться "в первом чтении". (Правда, скорость восприятия должна быть замедленной по сравнению с обычной.) В то же время, я стараюсь излагать всё без смысловых искажений и упрощений, которыми нередко "грешат" авторы популярных текстов. Но я стараюсь передавать смысл, что называется, "без потерь".
Текст я разделяю на две части, а изложение разбито на отдельные пункты. В первой части, то есть в данном посте, информация даётся в основном "вводная", а собственно доказательство теоремы я изложу в одном из следующих постов. При "сокращённом" варианте чтения, можно пункты 2 и 4 лишь "пробежать глазами", так как они в большей степени посвящены обоснованию значимости обсуждаемого результата. А вот на пункты 1, 3 и особенно 5 следует обратить особое внимание, так как это важно для понимания доказательства.
1. Начать я хочу с того, что не следует путать теорему Гёделя о полноте, которой посвящён этот пост, со знаменитыми теоремами Гёделя о неполноте (о которых я когда-то уже писал, и которым не так давно посвятил серию постов fregimus). Тут речь идёт о "полноте" и "неполноте" совершенно разных вещей. "Неполнота" относится к свойствам формальных теорий, в которых оказывается принципиально невозможно доказать всё, что нам бы хотелось; в таком смысле этот результат можно назвать "пессимистическим". То же, о чём я хочу написать здесь, есть результат в каком-то смысле противоположного характера, и его можно причислить к "оптимистическим". Здесь слово "полнота" относится к системе правил логических рассуждений. Оказывается, что эти правила (которые я описывал в своих старых постах и которые ниже коротко напомню), оказываются достаточно "полными" для того, чтобы с их помощью можно было провести любое математическое рассуждение.
Сейчас я прежде всего сформулирую теорему о полноте в "сжатой" форме, чтобы было понятно, о чём будет идти речь. Кратко это будет звучать так: всякая непротиворечивая формальная теория имеет модель. Смысл этого утверждения вот какой. Допустим, у нас имеется некоторый набор формальных положений, записанных на логическом языке. Такой набор положений мы будем называть "формальной теорией". Предположим, что из этих положений невозможно вывести логическое противоречие (то есть наша теория "непротиворечива"). Теорема утверждает, что все наши формальные положения можно так проинтерпретировать в содержательном виде, что они станут в этой интерпретации истинными. Это и подразумевается под построением "модели" данной теории.
То есть, если совсем коротко: всякий непротиворечивый набор формальных положений что-нибудь да описывает.
2. Есть довольно много примеров из истории науки, когда оказывалось, что придуманные математиками чисто "умственные" конструкции вдруг находили применение, которого изначально никто не ожидал. Я вообще-то не люблю приводить исторические примеры, но бегло всё-таки упомяну хотя бы часть таких конструкций. Например, всем известен пример неевклидовой геометрии (геометрии Лобачевского). Поначалу многие думали, что это есть чистая "игра ума", но в итоге оказалось, что она прекрасно описывает "искривлённые" пространства, и в физических теориях она заняла своё достойное место. Часто вспоминают также о "некоммутативном умножении", то есть такой конструкции, где возможно, что произведение AB не равно произведению BA. Здесь, конечно, речь идёт не об обычных числах, для которых переместительный закон умножения, известный всем из школьной программы, выполнен всегда. Но какие-то другие объекты (например, матрицы, или преобразования, или даже что-то ещё более близкое к числам) могут уже обладать свойством некоммутативности умножения. И такого рода вещи широко используются в моделях квантовой физики.
Можно привести ещё такой пример, который относится к уже более новому времени. Когда я учился в школе, то я хорошо помню, что деятельность по нахождению "очень больших" простых чисел считалась чисто "спортивной", и общепринятым было мнение, что это не может иметь никакого применения на практике. Прошло совсем немного лет, и выяснилось, что для нужд криптографии такие числа оказываются совершенно необходимыми для создания "секретных" способов передачи данных. Всё это давно реализовано в программах, которые мы используем, совершая электронные платежи и прочее.
Последний пример вообще-то немного выходит за рамки разговора, потому что упомянутые числа вряд ли можно считать примером некой "теории". Однако я счёл нужным вспомнить и об этом для иллюстрации такой довольно привычной для меня мысли: какие бы "странные" и на первый взгляд "ненужные" объекты ни изучали математики, рано или поздно всё это оказывается "востребованным" практикой. Изучается обычно что-то, имеющее внутреннюю ценность, обладающее богатым внутренним содержанием. Причём, как правило, без "нацеленности" на какие-то практические нужды. И теорема Гёделя о полноте, как мне кажется, помогает осознать, почему так происходит. Конечно, её значение этим далеко не исчерпывается, но сам тот факт, что любая логически состятельная система положений описывает что-то вполне осмысленное (и часто имеющее в реальности даже не одну, а очень много разных интерпретаций), имеет немалое значение для осмысления причин "непостижимой эффективности" математических теорий и конструкций.
Кстати сказать, даже компьютер можно считать в каком-то смысле "внебрачным потомком" математической логики: ведь поначалу математики просто изучали то, как устроены логические рассуждения, доказательства. А также разного рода "детерминированные" процессы. Эта деятельность привела к осознанию того, как устроены алгоритмы, и как можно создать "универсальное" устройство по "проигрыванию" каких угодно алгоритмов по заранее составленной программе. А это как раз в точности компьютер и есть -- как минимум, на уровне теории.
3. Хотелось бы ещё сказать пару слов о "теориях" как таковых, то есть о том, как они возникают. Прежде всего, теория может изучать что-то вполне конкретное -- например, систему натуральных чисел, или какую-то механическую систему, или какой-то вид животных. Короче говоря, что угодно. Это наиболее распространённый случай возникновения теорий, и обычно наука такого типа как-то накапливает знания об интересующем нас "объекте" или "системе", то есть об изучаемом предмете. В этом случае, если мы рассмотрим все имеющиеся в наличии теоретические положения, то при условии, что мы нигде не ошиблись, у нас получится набор теоретических положений, который уже имеет модель. Он же, конечно, будет внутренне непротиворечив, так как описывает нечто вполне "реальное". Этот пример говорит о том, что теории такого типа не имеет смысла рассматривать в том контексте, который здесь имеется в виду. Правда, проблема может возникнуть, если изучается мир каких-то "воображаемых" объектов типа "множеств" в математике, но мы сейчас об этом говорить не будем, а сосредоточимся на "теориях" совершенно другого типа.
Бывает так, что мы не изучаем что-то, а пытаемся создать или построить. В таких случаях мы часто перечисляем некий набор требований, которые нам хотелось бы иметь выполненными. Деятельность этого рода также достаточно широко распространена, но надо об этом сказать явно, чтобы сосредоточить внимание именно на этом. Например, мы могли бы выписать некие условия, которым подчинялась бы та или иная "система", и главный вопрос, который при этом возник -- это вопрос о том, а осуществимы ли эти требования, взятые вместе? А вдруг мы немного "переборщили", и пожелали создать что-то такое, что в принципе осуществлено быть не может, так как ведёт к логическому противоречию?
Я не буду здесь в качестве примера приводить что-то вроде "вечного двигателя", так как тут возникает противоречие с физическими законами, открытыми на опыте, то есть имеющими "эмпирический" характер. Понятно, что в той мере, в какой мы верим в "надёжность" этих законов, мы должны верить и в невозможность создания "перпетуум мобиле". Но это противоречие всё-таки имеет природу, отличную от логической. Мы хотя бы в "сказочном" варианте в состоянии представить себе некое вечно вращающееся колесо -- независимо от возможности его создать. А я сейчас приведу довольно смешной пример, когда ситуацию, в которой выполнены наложенные требования, невозможно представить себе в принципе.
Это, по сути дела, сюжет из анекдота. В школьном классе появился "активист", который пожелал, чтобы успеваемость каждого ученика была выше средней по классу :)
Я не раз сталкивался с ситуацией, когда после произнесения этой фразы кто-то ожидал продолжения типа "а что дальше?" Но на самом деле сказанного вполне достаточно, чтобы любой человек смог понять, что такое требование противоречиво, и потому не может быть осуществлено. На всякий случай поясню: если представить себе, что такая ситуация возможна, и сложить все показатели успеваемости, то получится число, которое больше (строго больше!) чем средний показатель, умноженный на число учеников. И если теперь вспомнить, как вычисляется само "среднее" -- сумма "баллов" делится на число участников, и разделить обе величины на это количество, то окажется, что средний балл оказался больше ... самого себя! :) То есть это, по сути, призыв "прыгнуть выше головы".
Чуть позже я приведу ещё кое-какие примеры противоречивых требований, про которые сразу не ясно, что они в принципе не осуществимы. А сейчас я хотел бы ещё раз остановиться на нашей ситуации, когда мы пытаемся создать нечто, удовлетворяющее заранее наложенным требованиям. Понятно, что логической противоречивости мы должны в любом случае избегать, но достаточно ли этого? Может, есть ещё какие-то препятствия к осуществимости замысла? Теорема Гёделя о полноте (если, конечно, её применение в таком контексте корректно) говорит нам, что по сути дела это единственное препятствие. Если логического противоречия нет, значит, какой-то "мир", описываемый сочинёнными нами положениями, возможен. То есть он в принципе бывает -- хотя бы на уровне теоретической конструкции.
Конечно, все прекрасно понимают, что практических препятствий к осуществлению чего бы то ни было может быть сколько угодно. Типа недостатка "ресурсов" или чего-то ещё. Но и здесь мы вообще-то можем ограничения включить в число накладываемых требований. Так или иначе, сам факт о существовании модели нашей теории позволяет как минимум изучать такой "объект", даже если он ещё не построен! Этот приём, кстати, часто применяется при осуществлении школьных геометрических построений. Мы представляем себе ситуацию, когда построение "якобы" уже осуществлено, и начинаем анализировать, какими свойствами оно обладает. Этот анализ особенностей будущего построения (или "модели") помогает в будущем и осуществить сам "проект"! То есть такая работа совершенно не бесполезна, и чисто "теоретическое" или "умозрительное" существование некого объекта, гарантируемое теоремой Гёделя, на самом деле способно сильно помочь в его построении.
Здесь нельзя не затронуть ещё вот какой момент. Пусть у нас есть система каких-то положений, которые мы сами придумали, или нам их кто-то выписал (скажем, наш "заказчик"). Как мы можем определить, противоречива ли эта система требований? Первое, что приходит в голову -- это как-то начать извлекать логические следствия из этих положений. И, если мы не придём к противоречию, то появится надежда, что такового просто и нет. Но это всего лишь надежда, а возможна ли какая-то "гарантия"?
4. Прежде всего, здесь я сформулирую один тезис "пессимистического характера", который на самом деле по своей природе близок к тому, о чём говорится в теоремах Гёделя о неполноте. А именно, никакого общего способа проверки системы утверждений на внутреннюю логическую противоречивость (который бы гарантированно давал нам ответ в форме "да" или "нет"), не существует. Математики в таких случаях говорят, что соответствующая проблема алгоритмически неразрешима. Об алгоритмических проблемах как таковых, я писал в серии своих предыдущих постов. Отсутствие общего способа, конечно, не означает, что при анализе вполне конкретной системы нас обязательно ждёт "неуспех". Но тогда встаёт вот какой вопрос: а если "успех" нас на этом пути всё-таки ожидает, то каким способом мы можем убедиться в непротиворечивости некоторой отдельно взятой теории?
Вообще-то наиболее распространённым способом установления непротиворечивости теории является как раз построение какой-то её модели. Но тогда может возникнуть вопрос, а какую же роль играет обсуждаемая теорема? Ведь применить её мы можем только к тем теориям, непротиворечивость которых уже установлена!
По этому поводу я считаю нужным сказать две вещи. Первое -- это то, что не будь этой теоремы Гёделя, мы бы не могли быть уверены, что выбранный нами способ установления непротиворечивости теории (при помощи построения модели), является состоятельным. А вдруг теория непротиворечива, но модели, тем не менее, она по каким-то причинам не имеет? И строить модель бессмысленно, а в непротиворечивости следует убеждаться каким-то другим путём. Если бы не теорема Гёделя о полноте, такая ситуация могла быть вполне возможной. А когда мы знаем, что эта теорема справедлива, то это может придать нам уверенности в поиске требуемой модели.
Но это ещё не всё; имеется вторая важная вещь. Очень часто рассматриваемые нами теории состоят из бесконечного числа положений. Чтобы представить себе, как такое вообще может быть, достаточно вообразить некий "шаблон", в соответствии с которым могут получаться те или иные положения теории. Например, обычный переместительный закон сложения имеет бесконечное число следствий, применительно к конкретным парам чисел. Скажем, каждое из равенств наподобие 3+4=4+3, 6+1=1+6, 11+111=111+11 есть следствие нашего общего закона, и таковых можно выписать бесконечно много. Конечно, все они могут быть "упакованы" в одну "буквенную" формулу типа x+y=y+x, как обычно и делается. Но даже в формальной арифметике (о ней у меня тоже имеется один из постов в списке) мы имеем дело с некоторой схемой "однотипных" аксиом, которых имеется бесконечное количество. И во многих других формальных теориях дело обстоит похожим образом. Поэтому такой случай, когда число основных положений теории бесконечно, является не каким-то "экзотическим", а вполне "ходовым".
И вот теперь представим себе, что мы хотим убедиться в непротиворечивости теории, состоящей из бесконечного числа занумерованных положений Y_1, Y_2, ..., Y_n, ... . Из общего устройства логических доказательств, легко осознать такую совсем простую вещь: если противоречие выводится из бесконечного числа положений, то оно обязательно выводится и из некоторого конечного числа этих положений. Просто по той причине, что доказательство представляет собой текст конечной длины, и оно опирается по этой причине лишь на конечное число положений "теории".
Отсюда ясно, что установление непротиворечивости нашей теории сводится к установлению непротиворечивости теорий, у которых число положений конечно. А эта задача зачастую оказывается намного проще. Делается это при помощи нахождения такой модели, на которой истинными оказываются утверждения из некоторого начального отрезка нашего списка. Мы фактически строим бесконечное число моделей, а именно M_1, M_2, M_3, ... таким образом, что на модели, скажем, M_7 выполнены утверждения Y_1, Y_2, ..., Y_7, а про всё остальное мы ничего не знаем. Соответственно, в общем случае на модели M_n у нас выполнены условия Y_1, Y_2, ..., Y_n -- всего n начальных условий списка. И так для каждого n. Но условие Y_{n+1} на модели M_n выполняться при этом уже не обязано.
Так вот, если мы посмотрим теперь на все построенные модели "сверху", то мы поймём, что непротиворечивость нашей теории в итоге нами установлена, но вот общей модели M -- для всего бесконечного множества условий -- у нас при этом пока нет. То есть из "обрезков" моделей M_1, M_2, ..., M_n, ... мы не имеем возможности как-то просто, путём "слияния" или чего-то ещё, соорудить одну "большую" модель.
Можно представить себе, что каждое из условий Y_1, Y_2, .... Y_n, ... есть некое уравнение; тогда, зная для каждого отдельного n некое решение системы, состоящей из первых n уравнений, мы не имеем ни одного примера решения всей нашей системы целиком. Но если воспользоваться теоремой Гёделя о полноте, то мы можем заключить, что такое общее для всех условий решение всё-таки существует -- конечно, при условии корректного применения самого результата.
5. Сейчас я хочу кое-что сказать о том, в какой форме будут представляться положения теории. Их принято записывать на языке логики предикатов, который является в известной мере "универсальным", то есть описывать в этих терминах можно практически какие угодно явления, если иметь в виду описания на чисто формальном уровне. Использовать разрешается, во-первых, логические связки, то есть слова "и", "или", "не", записанные при помощи логических символов (у меня здесь это будут "and", "or" и "not"). Во-вторых, особенностью логики предикатов является использование логических кванторов, которых имеется всего два. Это квантор всеобщности, который я здесь буду обозначать через A (от слова "All", и со значением "для всех"), а также квантор существования, который я буду обозначать через E (от слова "Exist", со значением "существует"). Чаще всего в литературе в качестве обозначений используются "перевёрнутые" буквы, но я для удобства буду просто использовать жирный шрифт. Так тоже нередко поступают.
Но самую главную роль в формулах играют, конечно же, предикаты, то есть свойства. Точнее было бы здесь говорить о предикатных символах, которые вводятся для обозначения тех или иных свойств. Если брать самый простой случай, то в нём рассматриваются свойства, которым может обладать или не обладать тот или иной "объект". Если мы хотим ввести символ, например, для обозначения свойства объекта "быть красным", то можно выбрать какую-то букву -- скажем, R, и писать R(x), имея в виду, что объект x обладает свойством R, то есть он является красным. Таких свойств, самых разнообразных, можно ввести в рассмотрение сколько угодно. Эти свойства могут быть взаимосвязаны; например, может так оказаться, что "все P суть Q", то есть все объекты, обладающие свойством P, также обладают и свойством Q. Этот факт может быть записан при помощи логической символики в виде формулы (Ax)(P(x) -> Q(x)).
Те символы, которые используются для выделения определённых свойств объектов, называются одноместными предикатными символами. Если использовать только их, то на таком языке можно выражать так называемые "силлогизмы". Им у меня был посвящён отдельный пост, где я проводил ту мысль, что теория силлогизмов представлет собой не какое-то "вершинное" достижение логики, а всего лишь попытку проанализировать самые простые логические законы на "символьном" языке. По-настоящему серьёзные вопросы для своего освещения требуют многоместных предикатных символов, которые указывают на наличие каких-то связей между двумя и более объектами.
Например, пусть мы хотим отразить отношение знакомства. С этой целью мы вводим какой-то двуместный предикатный символ (скажем, K) и пишем K(x,y) в случае, если "объект" x знаком с "объектом" y. В данном случае мы не имеем в виду симметричное отношение, то есть здесь подразумевается, что x знает y -- примерно в том смысле, что я "знаю" Аллу Пугачёву (хотя она меня -- навряд ли :)) Для отношения взаимного знакомства можно ввести другой символ -- например, M, и писать M(x,y) в случае, если мы хотим выразить мысль, что x и y знакомы между собой (каждый из них знает каждого). Соответственно, можно ввести символ F для обозначения "френдования" в ЖЖ, и так далее. То есть допустимо рассматривать какое угодно число двуместных предикатных символов, примерами которых у нас служат рассмотренные выше K, M, F и так далее. Особо мы отметим такое отношение как "отношение равенства", для которого обычно используется символ "=", но он вообще-то является "внелогическим", и если его не разрешается использовать "по умолчанию", то мысль о том, что x и y равны (то есть x=y) можно записывать в виде E(x,y), где E -- ещё один пример двуместного предикатного символа.
Во многих случаях полезнобывает рассматривать трёхместные предикатные символы. Скажем, говоря об арифметике, мы можем писать S(x,y,z), имея в виду, что x+y=z, или П(x,y,z) для обозначения того факта, что x*y=z. Здесь S и П суть трёхместные предикатные символы. Привлекая их, можно избежать использования отдельных знаков для тех или иных операций -- например, для сложения или умножения.
Полезно осмыслить тот факт, что кратко описанный здесь "язык" является в значительной степени "универсальным", то есть на нём можно выражать сколь угодно сложные "мысли". Я проиллюстрирую это на нескольких примерах. Допустим, я хочу на языке логики предикатов записать фразу о том, что "всякий кулик своё болото хвалит". Смысл здесь понимается несколько упрощённо, а именно: про всякого кулика известно, что он хвалит какое-нибудь болото -- без дополнительных уточнений. Которые при желании также можно было бы ввести.
Итак, мы помним, что у нас имеются в рассмотрении просто "объекты", среди которых встречается всё: и кулики, и болота, и точки, и прямые, и числа -- абсолютно всё на свете. Поскольку здесь мы говорим о куликах и болотах, то можно ввести два предикатных символа К и Б. Оба они будут одноместными, и запись К(x) будет означать, что x есть кулик, а запись Б(y) -- что y есть болото. (Та идея, что всё можно рассматривать "скопом", просто выделяя при помощи выбранных обозначений объекты совершенно разной природы, кому-то может показаться неожиданной, но для математической логики это как бы "норма".) У нас здесь в примере ещё имеется глагол "хвалить", и для его выражения мы должны ввести двуместный предикатный символ Х, и если мы пишем X(a,b), то это означает, что a хвалит b. Заметим, что буквы a, b здесь могут быть заменены на любые другие, и даже на одинаковые; запись Х(s,s) будет при этом означать, что s хвалит сам себя :)
Итак, вот как строится теперь нужная нам фраза:
для всякого "объекта" x, если x является куликом, то существует "объект" y, являющийся болотом, и обладающий тем свойством, что x хвалит y.
В символьной форме имеем вот что: (Ax)(К(x) -> (Ey)(Б(y) and Х(x,y))).
Аналогичным способом можно описывать любые другие ситуации, привлекая при этом нужные для рассмотрения символы, призванные обозначать свойства, отношения и прочее. При этом следует отдавать себе отчёт в том, что формулы, которые мы получаем -- это не более чем последовательности символов, и никакого "смысла" они сами по себе не имеют. Например, если кто-то посмотрит на формулу, написанную нами выше, то он не будет знать, что мы сказали, не зная, что именно означают наши буквы К, Б и Х. Более того, если им придать другой смысл -- не тот, который имели в виду мы, то вместо какого-то верного высказывания запросто может получиться неверное.
6. Теперь хотелось бы привести ещё пример "теории", которая оказывается противоречивой, хотя логический вывод противоречия из самих формул тут довольно сложен. Представим себе, что мы задались целью найти такую компанию из девяти пользователей Живого Журнала, чтобы у каждого члена этой компании в ней имелись в точности три взаимных френда. (При этом мы не учитываем того, что кто-то может иметь во френдах самого себя.)
Прежде всего, предлагается понять, почему компании с такими свойствами существовать не может. Представим себе, что каждый их девяти человек представил список всех своих взаимных френдов, назвав при этом три имени. Если мы соединим все эти списки, то получим 27 имён, которые при этом могут упоминаться несколько раз. Но такого не может быть, потому что общее число записей должно оказаться чётным: ввиду того, что "френдование" нами рассматривается взаимное, все записи можно разбить на пары. В одну пару войдут два упоминания: A упомянул B, и при этом B упомянул A. То есть мы пришли к логическому противоречию.
Если мы теперь попытаемся описать "теорию" (на языке логики предикатов), то она в силу сказанного выше окажется противоречивой, однако этого нам не будет явно видно из самих формул. Выписывать все требования мы не будем, а всего лишь укажем, как можно это сделать. Это полезно осознать хотя бы в общих чертах, чтобы знать, с какого рода системами утверждений мы хотим далее иметь дело.
Итак, нам тут нужно 2 двуместных предикатных символа: символ E для равенства, и символ F для обозначения "френдования" (взаимного). Мы накладываем требование симметричности (взаимности), которое у нас будет иметь такой вид:
(Ax)(Ay)(F(x,y) -> F(y,x))
Далее, мы требуем, чтобы в число френдов никто не включал сам себя, то есть (Ax)(not(F(x,x)).
Как выразить то, что в компании имеется ровно 9 участников? Это делается при помощи довольно длинной формулы, которые желающие могут выписать явно. Мы утверждаем существование таких x1, ..., x9, которые попарно не равны друг другу, и таких, которыми всё исчерпывается, то есть для любого x оказывается, что он совпадает с одним из девяти рассмотренных участников. Всё полностью я выписывать не буду, а дам лишь фрагмент, отмечая пропуски многоточиями, а также опуская излишние скобки:
(Ex1)(Ex2)...(Ex9)(not E(x1,x2) and not E(x1,x3) and ... and not E(x8,x9) and (Ax)(E(x,x1) or E(x,x2) or ... or E(x,x9) ))
Примерно таким же путём можно написать предложение, утверждающее, что каждый участник нашей компании имеет в точности трёх френдов.
Поскольку предикатный символ E означает у нас не что иное как равенство, то нужно добавить к списку требований основные свойства, которыми обладает отношение равенства. Прежде всего, этот три свойства, показывающие, что равенство есть "отношение эквивалентности". Это рефлексивность (всякий объект равен сам себе), симметричность (если x равен y, то y равен x) и транзитивность (если x равен y, и y равен z, то x равен z). В виде формул это выглядит так:
(Ax)E(x,x)
(Ax)(Ay)(E(x,y) -> E(y,x))
(Ax)(Ay)(Az)(E(x,y) and E(y,z) -> E(x,z))
Кроме этих свойств, есть ещё свойство "подстановочности" равенства. Оно означает, что если в условии F(x,y) мы заменим x или y на равный ему элемент, то после замены получится условие, которое окажется выполненным. Такую замену можно осуществить для x и y сразу, и тогда получится вот что:
(Ax)(Ay)(Ax')(Ay')(F(x,y) and E(x,x') and E(y,y') -> F(x',y'))
Соединяя все требования вместе, мы получим пример противоречивой теории, которая моделью обладать не может. Нашей целью теперь является доказательство того факта, что если из каких-то выписанных нами положений логическое противоречие никаким способом вывести нельзя, то эти положения могут быть проинтерпретированы хотя бы одним способом так, что все они окажутся истинными. То есть "теория" будет иметь модель.
ПРОДОЛЖЕНИЕ (часть 2)
К ОБСУЖДЕНИЮ
Как обычно, мой текст адресован всем, кто сколько-нибудь интересуется логической проблематикой. Писать я стараюсь всегда в "популярном" стиле, то есть стремлюсь к тому, чтобы не требовалось специальных знаний, и текст мог быть понят, например, теми, кого называют "гуманитариями". Кроме того, я даже в постах на тему математической логики, стремлюсь не перегружать читателя обилием формул, в которые надо вникать. В идеале, такого рода текст должен читаться примерно как художественная литература, то есть всё должно усваиваться "в первом чтении". (Правда, скорость восприятия должна быть замедленной по сравнению с обычной.) В то же время, я стараюсь излагать всё без смысловых искажений и упрощений, которыми нередко "грешат" авторы популярных текстов. Но я стараюсь передавать смысл, что называется, "без потерь".
Текст я разделяю на две части, а изложение разбито на отдельные пункты. В первой части, то есть в данном посте, информация даётся в основном "вводная", а собственно доказательство теоремы я изложу в одном из следующих постов. При "сокращённом" варианте чтения, можно пункты 2 и 4 лишь "пробежать глазами", так как они в большей степени посвящены обоснованию значимости обсуждаемого результата. А вот на пункты 1, 3 и особенно 5 следует обратить особое внимание, так как это важно для понимания доказательства.
1. Начать я хочу с того, что не следует путать теорему Гёделя о полноте, которой посвящён этот пост, со знаменитыми теоремами Гёделя о неполноте (о которых я когда-то уже писал, и которым не так давно посвятил серию постов fregimus). Тут речь идёт о "полноте" и "неполноте" совершенно разных вещей. "Неполнота" относится к свойствам формальных теорий, в которых оказывается принципиально невозможно доказать всё, что нам бы хотелось; в таком смысле этот результат можно назвать "пессимистическим". То же, о чём я хочу написать здесь, есть результат в каком-то смысле противоположного характера, и его можно причислить к "оптимистическим". Здесь слово "полнота" относится к системе правил логических рассуждений. Оказывается, что эти правила (которые я описывал в своих старых постах и которые ниже коротко напомню), оказываются достаточно "полными" для того, чтобы с их помощью можно было провести любое математическое рассуждение.
Сейчас я прежде всего сформулирую теорему о полноте в "сжатой" форме, чтобы было понятно, о чём будет идти речь. Кратко это будет звучать так: всякая непротиворечивая формальная теория имеет модель. Смысл этого утверждения вот какой. Допустим, у нас имеется некоторый набор формальных положений, записанных на логическом языке. Такой набор положений мы будем называть "формальной теорией". Предположим, что из этих положений невозможно вывести логическое противоречие (то есть наша теория "непротиворечива"). Теорема утверждает, что все наши формальные положения можно так проинтерпретировать в содержательном виде, что они станут в этой интерпретации истинными. Это и подразумевается под построением "модели" данной теории.
То есть, если совсем коротко: всякий непротиворечивый набор формальных положений что-нибудь да описывает.
2. Есть довольно много примеров из истории науки, когда оказывалось, что придуманные математиками чисто "умственные" конструкции вдруг находили применение, которого изначально никто не ожидал. Я вообще-то не люблю приводить исторические примеры, но бегло всё-таки упомяну хотя бы часть таких конструкций. Например, всем известен пример неевклидовой геометрии (геометрии Лобачевского). Поначалу многие думали, что это есть чистая "игра ума", но в итоге оказалось, что она прекрасно описывает "искривлённые" пространства, и в физических теориях она заняла своё достойное место. Часто вспоминают также о "некоммутативном умножении", то есть такой конструкции, где возможно, что произведение AB не равно произведению BA. Здесь, конечно, речь идёт не об обычных числах, для которых переместительный закон умножения, известный всем из школьной программы, выполнен всегда. Но какие-то другие объекты (например, матрицы, или преобразования, или даже что-то ещё более близкое к числам) могут уже обладать свойством некоммутативности умножения. И такого рода вещи широко используются в моделях квантовой физики.
Можно привести ещё такой пример, который относится к уже более новому времени. Когда я учился в школе, то я хорошо помню, что деятельность по нахождению "очень больших" простых чисел считалась чисто "спортивной", и общепринятым было мнение, что это не может иметь никакого применения на практике. Прошло совсем немного лет, и выяснилось, что для нужд криптографии такие числа оказываются совершенно необходимыми для создания "секретных" способов передачи данных. Всё это давно реализовано в программах, которые мы используем, совершая электронные платежи и прочее.
Последний пример вообще-то немного выходит за рамки разговора, потому что упомянутые числа вряд ли можно считать примером некой "теории". Однако я счёл нужным вспомнить и об этом для иллюстрации такой довольно привычной для меня мысли: какие бы "странные" и на первый взгляд "ненужные" объекты ни изучали математики, рано или поздно всё это оказывается "востребованным" практикой. Изучается обычно что-то, имеющее внутреннюю ценность, обладающее богатым внутренним содержанием. Причём, как правило, без "нацеленности" на какие-то практические нужды. И теорема Гёделя о полноте, как мне кажется, помогает осознать, почему так происходит. Конечно, её значение этим далеко не исчерпывается, но сам тот факт, что любая логически состятельная система положений описывает что-то вполне осмысленное (и часто имеющее в реальности даже не одну, а очень много разных интерпретаций), имеет немалое значение для осмысления причин "непостижимой эффективности" математических теорий и конструкций.
Кстати сказать, даже компьютер можно считать в каком-то смысле "внебрачным потомком" математической логики: ведь поначалу математики просто изучали то, как устроены логические рассуждения, доказательства. А также разного рода "детерминированные" процессы. Эта деятельность привела к осознанию того, как устроены алгоритмы, и как можно создать "универсальное" устройство по "проигрыванию" каких угодно алгоритмов по заранее составленной программе. А это как раз в точности компьютер и есть -- как минимум, на уровне теории.
3. Хотелось бы ещё сказать пару слов о "теориях" как таковых, то есть о том, как они возникают. Прежде всего, теория может изучать что-то вполне конкретное -- например, систему натуральных чисел, или какую-то механическую систему, или какой-то вид животных. Короче говоря, что угодно. Это наиболее распространённый случай возникновения теорий, и обычно наука такого типа как-то накапливает знания об интересующем нас "объекте" или "системе", то есть об изучаемом предмете. В этом случае, если мы рассмотрим все имеющиеся в наличии теоретические положения, то при условии, что мы нигде не ошиблись, у нас получится набор теоретических положений, который уже имеет модель. Он же, конечно, будет внутренне непротиворечив, так как описывает нечто вполне "реальное". Этот пример говорит о том, что теории такого типа не имеет смысла рассматривать в том контексте, который здесь имеется в виду. Правда, проблема может возникнуть, если изучается мир каких-то "воображаемых" объектов типа "множеств" в математике, но мы сейчас об этом говорить не будем, а сосредоточимся на "теориях" совершенно другого типа.
Бывает так, что мы не изучаем что-то, а пытаемся создать или построить. В таких случаях мы часто перечисляем некий набор требований, которые нам хотелось бы иметь выполненными. Деятельность этого рода также достаточно широко распространена, но надо об этом сказать явно, чтобы сосредоточить внимание именно на этом. Например, мы могли бы выписать некие условия, которым подчинялась бы та или иная "система", и главный вопрос, который при этом возник -- это вопрос о том, а осуществимы ли эти требования, взятые вместе? А вдруг мы немного "переборщили", и пожелали создать что-то такое, что в принципе осуществлено быть не может, так как ведёт к логическому противоречию?
Я не буду здесь в качестве примера приводить что-то вроде "вечного двигателя", так как тут возникает противоречие с физическими законами, открытыми на опыте, то есть имеющими "эмпирический" характер. Понятно, что в той мере, в какой мы верим в "надёжность" этих законов, мы должны верить и в невозможность создания "перпетуум мобиле". Но это противоречие всё-таки имеет природу, отличную от логической. Мы хотя бы в "сказочном" варианте в состоянии представить себе некое вечно вращающееся колесо -- независимо от возможности его создать. А я сейчас приведу довольно смешной пример, когда ситуацию, в которой выполнены наложенные требования, невозможно представить себе в принципе.
Это, по сути дела, сюжет из анекдота. В школьном классе появился "активист", который пожелал, чтобы успеваемость каждого ученика была выше средней по классу :)
Я не раз сталкивался с ситуацией, когда после произнесения этой фразы кто-то ожидал продолжения типа "а что дальше?" Но на самом деле сказанного вполне достаточно, чтобы любой человек смог понять, что такое требование противоречиво, и потому не может быть осуществлено. На всякий случай поясню: если представить себе, что такая ситуация возможна, и сложить все показатели успеваемости, то получится число, которое больше (строго больше!) чем средний показатель, умноженный на число учеников. И если теперь вспомнить, как вычисляется само "среднее" -- сумма "баллов" делится на число участников, и разделить обе величины на это количество, то окажется, что средний балл оказался больше ... самого себя! :) То есть это, по сути, призыв "прыгнуть выше головы".
Чуть позже я приведу ещё кое-какие примеры противоречивых требований, про которые сразу не ясно, что они в принципе не осуществимы. А сейчас я хотел бы ещё раз остановиться на нашей ситуации, когда мы пытаемся создать нечто, удовлетворяющее заранее наложенным требованиям. Понятно, что логической противоречивости мы должны в любом случае избегать, но достаточно ли этого? Может, есть ещё какие-то препятствия к осуществимости замысла? Теорема Гёделя о полноте (если, конечно, её применение в таком контексте корректно) говорит нам, что по сути дела это единственное препятствие. Если логического противоречия нет, значит, какой-то "мир", описываемый сочинёнными нами положениями, возможен. То есть он в принципе бывает -- хотя бы на уровне теоретической конструкции.
Конечно, все прекрасно понимают, что практических препятствий к осуществлению чего бы то ни было может быть сколько угодно. Типа недостатка "ресурсов" или чего-то ещё. Но и здесь мы вообще-то можем ограничения включить в число накладываемых требований. Так или иначе, сам факт о существовании модели нашей теории позволяет как минимум изучать такой "объект", даже если он ещё не построен! Этот приём, кстати, часто применяется при осуществлении школьных геометрических построений. Мы представляем себе ситуацию, когда построение "якобы" уже осуществлено, и начинаем анализировать, какими свойствами оно обладает. Этот анализ особенностей будущего построения (или "модели") помогает в будущем и осуществить сам "проект"! То есть такая работа совершенно не бесполезна, и чисто "теоретическое" или "умозрительное" существование некого объекта, гарантируемое теоремой Гёделя, на самом деле способно сильно помочь в его построении.
Здесь нельзя не затронуть ещё вот какой момент. Пусть у нас есть система каких-то положений, которые мы сами придумали, или нам их кто-то выписал (скажем, наш "заказчик"). Как мы можем определить, противоречива ли эта система требований? Первое, что приходит в голову -- это как-то начать извлекать логические следствия из этих положений. И, если мы не придём к противоречию, то появится надежда, что такового просто и нет. Но это всего лишь надежда, а возможна ли какая-то "гарантия"?
4. Прежде всего, здесь я сформулирую один тезис "пессимистического характера", который на самом деле по своей природе близок к тому, о чём говорится в теоремах Гёделя о неполноте. А именно, никакого общего способа проверки системы утверждений на внутреннюю логическую противоречивость (который бы гарантированно давал нам ответ в форме "да" или "нет"), не существует. Математики в таких случаях говорят, что соответствующая проблема алгоритмически неразрешима. Об алгоритмических проблемах как таковых, я писал в серии своих предыдущих постов. Отсутствие общего способа, конечно, не означает, что при анализе вполне конкретной системы нас обязательно ждёт "неуспех". Но тогда встаёт вот какой вопрос: а если "успех" нас на этом пути всё-таки ожидает, то каким способом мы можем убедиться в непротиворечивости некоторой отдельно взятой теории?
Вообще-то наиболее распространённым способом установления непротиворечивости теории является как раз построение какой-то её модели. Но тогда может возникнуть вопрос, а какую же роль играет обсуждаемая теорема? Ведь применить её мы можем только к тем теориям, непротиворечивость которых уже установлена!
По этому поводу я считаю нужным сказать две вещи. Первое -- это то, что не будь этой теоремы Гёделя, мы бы не могли быть уверены, что выбранный нами способ установления непротиворечивости теории (при помощи построения модели), является состоятельным. А вдруг теория непротиворечива, но модели, тем не менее, она по каким-то причинам не имеет? И строить модель бессмысленно, а в непротиворечивости следует убеждаться каким-то другим путём. Если бы не теорема Гёделя о полноте, такая ситуация могла быть вполне возможной. А когда мы знаем, что эта теорема справедлива, то это может придать нам уверенности в поиске требуемой модели.
Но это ещё не всё; имеется вторая важная вещь. Очень часто рассматриваемые нами теории состоят из бесконечного числа положений. Чтобы представить себе, как такое вообще может быть, достаточно вообразить некий "шаблон", в соответствии с которым могут получаться те или иные положения теории. Например, обычный переместительный закон сложения имеет бесконечное число следствий, применительно к конкретным парам чисел. Скажем, каждое из равенств наподобие 3+4=4+3, 6+1=1+6, 11+111=111+11 есть следствие нашего общего закона, и таковых можно выписать бесконечно много. Конечно, все они могут быть "упакованы" в одну "буквенную" формулу типа x+y=y+x, как обычно и делается. Но даже в формальной арифметике (о ней у меня тоже имеется один из постов в списке) мы имеем дело с некоторой схемой "однотипных" аксиом, которых имеется бесконечное количество. И во многих других формальных теориях дело обстоит похожим образом. Поэтому такой случай, когда число основных положений теории бесконечно, является не каким-то "экзотическим", а вполне "ходовым".
И вот теперь представим себе, что мы хотим убедиться в непротиворечивости теории, состоящей из бесконечного числа занумерованных положений Y_1, Y_2, ..., Y_n, ... . Из общего устройства логических доказательств, легко осознать такую совсем простую вещь: если противоречие выводится из бесконечного числа положений, то оно обязательно выводится и из некоторого конечного числа этих положений. Просто по той причине, что доказательство представляет собой текст конечной длины, и оно опирается по этой причине лишь на конечное число положений "теории".
Отсюда ясно, что установление непротиворечивости нашей теории сводится к установлению непротиворечивости теорий, у которых число положений конечно. А эта задача зачастую оказывается намного проще. Делается это при помощи нахождения такой модели, на которой истинными оказываются утверждения из некоторого начального отрезка нашего списка. Мы фактически строим бесконечное число моделей, а именно M_1, M_2, M_3, ... таким образом, что на модели, скажем, M_7 выполнены утверждения Y_1, Y_2, ..., Y_7, а про всё остальное мы ничего не знаем. Соответственно, в общем случае на модели M_n у нас выполнены условия Y_1, Y_2, ..., Y_n -- всего n начальных условий списка. И так для каждого n. Но условие Y_{n+1} на модели M_n выполняться при этом уже не обязано.
Так вот, если мы посмотрим теперь на все построенные модели "сверху", то мы поймём, что непротиворечивость нашей теории в итоге нами установлена, но вот общей модели M -- для всего бесконечного множества условий -- у нас при этом пока нет. То есть из "обрезков" моделей M_1, M_2, ..., M_n, ... мы не имеем возможности как-то просто, путём "слияния" или чего-то ещё, соорудить одну "большую" модель.
Можно представить себе, что каждое из условий Y_1, Y_2, .... Y_n, ... есть некое уравнение; тогда, зная для каждого отдельного n некое решение системы, состоящей из первых n уравнений, мы не имеем ни одного примера решения всей нашей системы целиком. Но если воспользоваться теоремой Гёделя о полноте, то мы можем заключить, что такое общее для всех условий решение всё-таки существует -- конечно, при условии корректного применения самого результата.
5. Сейчас я хочу кое-что сказать о том, в какой форме будут представляться положения теории. Их принято записывать на языке логики предикатов, который является в известной мере "универсальным", то есть описывать в этих терминах можно практически какие угодно явления, если иметь в виду описания на чисто формальном уровне. Использовать разрешается, во-первых, логические связки, то есть слова "и", "или", "не", записанные при помощи логических символов (у меня здесь это будут "and", "or" и "not"). Во-вторых, особенностью логики предикатов является использование логических кванторов, которых имеется всего два. Это квантор всеобщности, который я здесь буду обозначать через A (от слова "All", и со значением "для всех"), а также квантор существования, который я буду обозначать через E (от слова "Exist", со значением "существует"). Чаще всего в литературе в качестве обозначений используются "перевёрнутые" буквы, но я для удобства буду просто использовать жирный шрифт. Так тоже нередко поступают.
Но самую главную роль в формулах играют, конечно же, предикаты, то есть свойства. Точнее было бы здесь говорить о предикатных символах, которые вводятся для обозначения тех или иных свойств. Если брать самый простой случай, то в нём рассматриваются свойства, которым может обладать или не обладать тот или иной "объект". Если мы хотим ввести символ, например, для обозначения свойства объекта "быть красным", то можно выбрать какую-то букву -- скажем, R, и писать R(x), имея в виду, что объект x обладает свойством R, то есть он является красным. Таких свойств, самых разнообразных, можно ввести в рассмотрение сколько угодно. Эти свойства могут быть взаимосвязаны; например, может так оказаться, что "все P суть Q", то есть все объекты, обладающие свойством P, также обладают и свойством Q. Этот факт может быть записан при помощи логической символики в виде формулы (Ax)(P(x) -> Q(x)).
Те символы, которые используются для выделения определённых свойств объектов, называются одноместными предикатными символами. Если использовать только их, то на таком языке можно выражать так называемые "силлогизмы". Им у меня был посвящён отдельный пост, где я проводил ту мысль, что теория силлогизмов представлет собой не какое-то "вершинное" достижение логики, а всего лишь попытку проанализировать самые простые логические законы на "символьном" языке. По-настоящему серьёзные вопросы для своего освещения требуют многоместных предикатных символов, которые указывают на наличие каких-то связей между двумя и более объектами.
Например, пусть мы хотим отразить отношение знакомства. С этой целью мы вводим какой-то двуместный предикатный символ (скажем, K) и пишем K(x,y) в случае, если "объект" x знаком с "объектом" y. В данном случае мы не имеем в виду симметричное отношение, то есть здесь подразумевается, что x знает y -- примерно в том смысле, что я "знаю" Аллу Пугачёву (хотя она меня -- навряд ли :)) Для отношения взаимного знакомства можно ввести другой символ -- например, M, и писать M(x,y) в случае, если мы хотим выразить мысль, что x и y знакомы между собой (каждый из них знает каждого). Соответственно, можно ввести символ F для обозначения "френдования" в ЖЖ, и так далее. То есть допустимо рассматривать какое угодно число двуместных предикатных символов, примерами которых у нас служат рассмотренные выше K, M, F и так далее. Особо мы отметим такое отношение как "отношение равенства", для которого обычно используется символ "=", но он вообще-то является "внелогическим", и если его не разрешается использовать "по умолчанию", то мысль о том, что x и y равны (то есть x=y) можно записывать в виде E(x,y), где E -- ещё один пример двуместного предикатного символа.
Во многих случаях полезнобывает рассматривать трёхместные предикатные символы. Скажем, говоря об арифметике, мы можем писать S(x,y,z), имея в виду, что x+y=z, или П(x,y,z) для обозначения того факта, что x*y=z. Здесь S и П суть трёхместные предикатные символы. Привлекая их, можно избежать использования отдельных знаков для тех или иных операций -- например, для сложения или умножения.
Полезно осмыслить тот факт, что кратко описанный здесь "язык" является в значительной степени "универсальным", то есть на нём можно выражать сколь угодно сложные "мысли". Я проиллюстрирую это на нескольких примерах. Допустим, я хочу на языке логики предикатов записать фразу о том, что "всякий кулик своё болото хвалит". Смысл здесь понимается несколько упрощённо, а именно: про всякого кулика известно, что он хвалит какое-нибудь болото -- без дополнительных уточнений. Которые при желании также можно было бы ввести.
Итак, мы помним, что у нас имеются в рассмотрении просто "объекты", среди которых встречается всё: и кулики, и болота, и точки, и прямые, и числа -- абсолютно всё на свете. Поскольку здесь мы говорим о куликах и болотах, то можно ввести два предикатных символа К и Б. Оба они будут одноместными, и запись К(x) будет означать, что x есть кулик, а запись Б(y) -- что y есть болото. (Та идея, что всё можно рассматривать "скопом", просто выделяя при помощи выбранных обозначений объекты совершенно разной природы, кому-то может показаться неожиданной, но для математической логики это как бы "норма".) У нас здесь в примере ещё имеется глагол "хвалить", и для его выражения мы должны ввести двуместный предикатный символ Х, и если мы пишем X(a,b), то это означает, что a хвалит b. Заметим, что буквы a, b здесь могут быть заменены на любые другие, и даже на одинаковые; запись Х(s,s) будет при этом означать, что s хвалит сам себя :)
Итак, вот как строится теперь нужная нам фраза:
для всякого "объекта" x, если x является куликом, то существует "объект" y, являющийся болотом, и обладающий тем свойством, что x хвалит y.
В символьной форме имеем вот что: (Ax)(К(x) -> (Ey)(Б(y) and Х(x,y))).
Аналогичным способом можно описывать любые другие ситуации, привлекая при этом нужные для рассмотрения символы, призванные обозначать свойства, отношения и прочее. При этом следует отдавать себе отчёт в том, что формулы, которые мы получаем -- это не более чем последовательности символов, и никакого "смысла" они сами по себе не имеют. Например, если кто-то посмотрит на формулу, написанную нами выше, то он не будет знать, что мы сказали, не зная, что именно означают наши буквы К, Б и Х. Более того, если им придать другой смысл -- не тот, который имели в виду мы, то вместо какого-то верного высказывания запросто может получиться неверное.
6. Теперь хотелось бы привести ещё пример "теории", которая оказывается противоречивой, хотя логический вывод противоречия из самих формул тут довольно сложен. Представим себе, что мы задались целью найти такую компанию из девяти пользователей Живого Журнала, чтобы у каждого члена этой компании в ней имелись в точности три взаимных френда. (При этом мы не учитываем того, что кто-то может иметь во френдах самого себя.)
Прежде всего, предлагается понять, почему компании с такими свойствами существовать не может. Представим себе, что каждый их девяти человек представил список всех своих взаимных френдов, назвав при этом три имени. Если мы соединим все эти списки, то получим 27 имён, которые при этом могут упоминаться несколько раз. Но такого не может быть, потому что общее число записей должно оказаться чётным: ввиду того, что "френдование" нами рассматривается взаимное, все записи можно разбить на пары. В одну пару войдут два упоминания: A упомянул B, и при этом B упомянул A. То есть мы пришли к логическому противоречию.
Если мы теперь попытаемся описать "теорию" (на языке логики предикатов), то она в силу сказанного выше окажется противоречивой, однако этого нам не будет явно видно из самих формул. Выписывать все требования мы не будем, а всего лишь укажем, как можно это сделать. Это полезно осознать хотя бы в общих чертах, чтобы знать, с какого рода системами утверждений мы хотим далее иметь дело.
Итак, нам тут нужно 2 двуместных предикатных символа: символ E для равенства, и символ F для обозначения "френдования" (взаимного). Мы накладываем требование симметричности (взаимности), которое у нас будет иметь такой вид:
(Ax)(Ay)(F(x,y) -> F(y,x))
Далее, мы требуем, чтобы в число френдов никто не включал сам себя, то есть (Ax)(not(F(x,x)).
Как выразить то, что в компании имеется ровно 9 участников? Это делается при помощи довольно длинной формулы, которые желающие могут выписать явно. Мы утверждаем существование таких x1, ..., x9, которые попарно не равны друг другу, и таких, которыми всё исчерпывается, то есть для любого x оказывается, что он совпадает с одним из девяти рассмотренных участников. Всё полностью я выписывать не буду, а дам лишь фрагмент, отмечая пропуски многоточиями, а также опуская излишние скобки:
(Ex1)(Ex2)...(Ex9)(not E(x1,x2) and not E(x1,x3) and ... and not E(x8,x9) and (Ax)(E(x,x1) or E(x,x2) or ... or E(x,x9) ))
Примерно таким же путём можно написать предложение, утверждающее, что каждый участник нашей компании имеет в точности трёх френдов.
Поскольку предикатный символ E означает у нас не что иное как равенство, то нужно добавить к списку требований основные свойства, которыми обладает отношение равенства. Прежде всего, этот три свойства, показывающие, что равенство есть "отношение эквивалентности". Это рефлексивность (всякий объект равен сам себе), симметричность (если x равен y, то y равен x) и транзитивность (если x равен y, и y равен z, то x равен z). В виде формул это выглядит так:
(Ax)E(x,x)
(Ax)(Ay)(E(x,y) -> E(y,x))
(Ax)(Ay)(Az)(E(x,y) and E(y,z) -> E(x,z))
Кроме этих свойств, есть ещё свойство "подстановочности" равенства. Оно означает, что если в условии F(x,y) мы заменим x или y на равный ему элемент, то после замены получится условие, которое окажется выполненным. Такую замену можно осуществить для x и y сразу, и тогда получится вот что:
(Ax)(Ay)(Ax')(Ay')(F(x,y) and E(x,x') and E(y,y') -> F(x',y'))
Соединяя все требования вместе, мы получим пример противоречивой теории, которая моделью обладать не может. Нашей целью теперь является доказательство того факта, что если из каких-то выписанных нами положений логическое противоречие никаким способом вывести нельзя, то эти положения могут быть проинтерпретированы хотя бы одним способом так, что все они окажутся истинными. То есть "теория" будет иметь модель.
ПРОДОЛЖЕНИЕ (часть 2)
К ОБСУЖДЕНИЮ