истинные формулы
Этот пост написан по мотивам дискуссий с alex_semenov и kaktus77 в одной из веток. Его можно рассматривать также в качестве некоторого дополнения к моим недавным постам на тему математической логики. Но здесь я обсуждаю в целом довольно специальные вопросы, поэтому для "широкой публики" написанное, скорее всего, не будет представлять интереса.
В дискуссиях шла речь о возможной "реальной" интерпретации смысла тех или иных арифметических формул. Мне показалось уместным написать на эту тему отдельно. Прежде всего я хочу напомнить об одной интерпретации общего характера. Пусть имеется замкнутая (то есть не зависящая от переменных) формула Ф, которая что-то утверждает. Можно считать, что эта формула имеет вид (Q_{1}x_1)...(Q_{n}x_{n})P(x_1,...,x_n), где Q_{1}, ..., Q_{n} -- логические кванторы A или E, расставленные в любом порядке, а P(x_1,...,x_n) -- бескванторная формула. Мы берём сначала наиболее общую ситуацию. Пусть переменные принимают значения на некоторой предметной области M, а P задаёт какое-то n-местное отношение P^M на множестве M. Будем считать, что для любых конкретных предметов m_1, ..., m_n из M у нас имеется "оракул", который нам возвещает о том, истинно или ложно высказывание P^M(m_1, ..., m_n) о данных объектах. Истинное и ложное значение будем обозначать как 1 и 0 соответственно.
Для арифметических формул у нас M есть множество натуральных (целых неотрицательных) чисел, а отношение P^M представляет собой конкретный алгоритм. На вход алгоритма подаётся последовательность n чисел m_1, ...,m_n; на выходе мы получаем 0 или 1 (за конечное число шагов работы алгоритма).
Сейчас нас интересует общий случай придания смысла формуле Ф. Этот смысл тем сложнее выявить, чем больше значение n, а ещё точнее -- чем больше имеется перемен кванторов среди Q_1, ..., Q_n. Я сейчас напоминаю о том, что такое игра Эренфойхта (об этом говорилось в недрах комментов в третьей части поста о книге Дойча).
Есть два игрока; пусть это будут Алла и Егор :) Алла играет "за" кванторы всеобщности, Егор -- за кванторы существования. Всего в игре ровно n ходов, причём ходы делаются не по очереди, а в соответствии со значениями кванторов. Если Q_k -- это квантор всеобщности A, то k-й ход делает Алла. Если же это квантор существования E, то k-й ход делает Егор. В качестве k-го хода тот игрок, который его делает, просто выбирает значение переменной x_k, указывая некоторый элемент m_k из M. После n ходов образуется последовательность m_1, ..., m_n, которую надлежит подставить в P^M, то есть задать вопрос "оракулу" об истинности или ложности итоговое высказывания P^M(m_1,...,m_n). Единственное содержательное правило игры, которое следует запомнить, состоит в следующем: если итоговое высказывание истинно, то победа присуждается Егору; если оно ложно, то Алле. То есть "хозяин" кванторов существования стремится сделать итоговое высказывание истинным, а его оппонент -- наоборот.
Истинность формулы Ф означает наличие выигрышной стратегии у Егора, а ложность формулы Ф -- наличие выигрышной стратегии у Аллы. Поскольку само по себе наличие стратегии у одного из игроков может наличествовать не всегда, хотелось бы понять, почему в рассматриваемом случае стратегия имеется, то есть формулу следует считать истинной или ложной (в выбранной интерпретации). Точнее, я хочу в явном виде проследить, на какие допущения мы при этом опираемся. Заодно это поможет себе более наглядно представить себе процесс придания истинностного значения формулам. Для наглядности и удобства я пока ограничусь случаем арифметических формул.
Как и в случае почти любых игр, в данном случае мы можем нарисовать дерево игры. Его в принципе очень легко себе представить. Вершинами дерева служат все числовые последовательности, имеющие не более n членов. Мы начинаем рисовать дерево сверху вниз. У этого дерева, как обычно, есть "корневая вершина" (вершина нулевого уровня), соответствующая "пустой" последовательности. Из этой вершины вниз выходит бесконечное число рёбер, занумерованных слева направо числами 0,1,2, ... . Каждое такое ребро ведёт к вершине первого уровня, соответствующей последовательности из одного члена. Далее, из каждой вершины первого уровня мы также проводим бесконечно много рёбер, идущих вниз к вершинам второго уровня и так далее, пока не достигнем вершин фиксированного n-го уровня. Каждой вершине k-го уровня соответствует числовая последовательность из k членов; если k меньше n, то из этой вершины идут вниз рёбра с метками 0,1,2, ... . После прохождения ребра с данной меткой мы приписываем к последовательности метку этого ребра. При этом получается примерно следующая картинка.
[]
[0] [1] [2] [3] .........................................................
[0,0] [0,1] [0,2] [0,3] ..... [1,0] [1,1] [1,2] [1,3] ..... [2,0] [2,1] [2,2] [2,3] ..... [3,0] [3,1] [3,2] [3,3] ..........
..............................................................................................................................................................................
Думаю, общая закономерность ясна. За неимением подходящих изобразительных средств, я не рисую здесь рёбра.
Итак, дерево построено. Каждая вершина расположена на одном из уровней от 0 до n. Рёбрам соответствуют уровни от 1 до n. Мы считаем, что ребро k-го уровня соединяет вершину (k-1)-го уровня с вершиной k-го уровня.
Сейчас опишем процедуру оценки вершин, проводимой снизу вверх, от n-го уровня к нулевому. Вершины n-го уровня имеют метку [m_1,...,m_n]. Имеющийся у нас алгоритм P^M приписывает каждой из этих вершин оценку 0 или 1, равную P^M(m_1,...,P_n). Оценка 1 соответствует победе Егора, оценка 0 -- победе Аллы. Теперь переходим к оценке вершин (n-1)-го уровня. Здесь ситуация будет зависеть от того, какой из кванторов у нас выступает в роли Q_n, поэтому возникает два случая.
1) Q_n -- это квантор всеобщности. Это означает, что n-й ход делает Алла. Она выигрывает в данной позиции, если сможет своим ходом перейти в вершину с оценкой 0. В её распоряжении бесконечно много ходов. Если среди них есть хотя бы один ход к вершине с оценкой 0, то мы присваиваем соответствующей вершине оценку 0. В противном случае оценка вершины (n-1)-го уровня будет равна единице. То есть ответ зависит от того, будет ли последовательность оценок вершин непосредственно снизу от данной состоять из одних единиц.
2) Q_n -- это квантор существования. Здесь n-й ход за Егором. Он выиграет, если сможет перейти своим ходом в вершину с оценкой 1. В этом случае оцениваемой вершине (n-1)-го уровня присваиваем 1. В противном случае -- присваиваем 0. Последний случай имеет место, если непосредственно внизу от оцениваемой вершины последовательность оценок будет состоять из одних нулей.
Итак, мы придаём описанным способом оценку всем вершинам (n-1)-го уровня. Продолжая действовать аналогично, мы переходим к вершинам (n-2)-го уровня и так далее, пока не дойдём до корневой вершины. Она получит некоторую оценку 0 или 1. В первом случае при правильной игре выигрывает Алла, и формула Ф ложна. Во втором случае выигрывает Егор, и формула Ф истинна.
Легко проследить, какие именно допущения лежат в основе осмысленности описываемого процесса. Каждый раз мы работаем с бесконечной последовательностью из нулей и единиц, которая как-то задана. Возможны три случая: последовательность является нулевой (из одних нулей), единичной (из одних единиц) и смешанной (содержит как нули, так и единицы). Если мы рассматриваем последовательность как актуально существующую, то есть как минимум допускаем возможность "божественного" её просмотра целиком, то про неё имеет смысл говорить, к какому из трёх типов она относится. На самом деле часто бывает достаточно просмотреть несколько первых членов, чтобы прийти к заключению, что последовательность имеет смешанный тип. Но если мы видим одни нули до какого-то места, то мы не знаем пока что, будут ли нули встречаться на всех местах, или же где-то нам встретится единица. (Аналогично с рядом последовательных единиц на первых местах.)
Какие последовательности можно считать "актуально существующими"? Радикальная точка зрения (отвергающая "актуальную бесконечность") может состоять в том, что вообще никакие. Противоположная точка зрения допускает какие угодно манипуляции с актуальной бесконечностью, включая случаи множеств "большой мощности". Хотелось бы выбрать что-то промежуточное. Причём не какую-то "правильную" точку зрения, а ту, которая позволяет "верить" в осмысленность понятия истинности арифметических формул при минимальных предположениях.
Мне кажется разумным перейти сейчас на несколько иной язык, но этот переход хотелось бы для начала мотивировать. Пусть имеется некоторая последовательность нулей и единиц, генерируемых при помощи алгоритма. Поскольку она однозначно задаётся конечным текстом, то вполне естественно считать, что она "существует", и потому либо обладает, либо не обладает какими-то свойствами. В частности, она либо нулевая, либо единичная, либо смешанная. Допустим, мы отслеживаем свойство последовательностей быть нулевыми. Тогда в принципе можно рассмотреть последовательность последовательностей и сопоставить ей числовую последовательность по такому принципу: заменить нулевые последовательности на 0, а остальные -- на 1. "Существование" новой последовательности зависит от того, насколько "единообразным" был процесс задания старых последовательностей. Опять же, мы можем считать, что последовательности были заданы "хорошо", если мы можем эффективно (то есть при помощи алгоритма) вычислить член заданной последовательности с заданным номером. То есть здесь на вход алгоритма подаются уже два числа.
В общем случае мы имеем итерации, то есть на следующем шаге возникают последовательности последовательностей последовательностей. Но все они в нашем примере с формулой генерируются единообразно, потому что за всё отвечает один и тот же алгоритм P^M с "входом" из n чисел. Поэтому удобно переформулировать всё происходящее в следующем виде. Будем говорить не о последовательностях, которые "актуально существуют", а о множествах чисел, множествах (упорядоченных) пар чисел, множествах троек, четвёрок и так далее. Если имеется некоторый алгоритм, на вход которого подаётся (упорядоченный) набор из n чисел, а на выходе получается значение 0 или 1, то будем считать, что множество всех наборов, на котором значение алгоритма равно 0 (равно 1) в каком-то смысле "актуально существует". Посмотрим, что происходит с множествами с процессе навешивания кванторов.
Если A -- некоторое уже объявленное "существующим" множество n-ок (то есть упорядоченных наборов из n чисел), то применение квантора существования приводит к операции проекции. А именно, если B -- множество всех таких наборов вида (m_1,...,m_{n-1}), для которых существует такое m_n, при котором набор (m_1,...,m_{n-1},m_n) принадлежит A, то B естественно назвать проекцией множества A на первые n-1 "координат". Осмысленность навешивания квантора существования, таким образом, сводится к следующему положению: если A "актуально существует", то этим же свойством обладает и его проекция.
Вместо кванторов всеобщности можно использовать отрицание, так как любой из кванторов выражается через другой при помощи отрицания. При этом мы ничего не теряем и не приобретаем, так как отрицания в любом случае разрешалось "навешивать" на формулы. А это позволяет извлечь следующий принцип: если A "актуально существует", то его дополнение (состоящее из всех n-ок, не принадлежащих A), также "актуально существует".
Таким образом, в основе "веры" в абсолютный истинностный статус арифметических формул лежит не что иное как принятие следующих постулатов:
1) разрешимые множества (то есть распознаваемые при помощи алгоритма) "актуально существуют";
2) класс "актуально существующих" множеств замкнут относительно операций проекции и дополнения.
Здесь везде речь идёт о множествах n-ок натуральных чисел, по всем n сразу.
Представляется, что допущения, о которых идёт речь, не являются слишком сильными, чтобы их отвергать.
В заключение хочется сказать ещё пару слов на ту же тему. Рассмотрим формулу (Ax)(Ey)(Az)(Et)P(x,y,z,t), где P(x,y,z,t) -- бескванторный предикат. Истинность этой формулы означает существование двух функций: y=f(x) и t=g(x,z) таких, что высказывание P(x,f(x),z,g(x,z)) истинно всегда, при любых x,z. Такой способ осмысления истинности формул также может быть полезен. Он, в частности, заставляет задуматься о том, насколько богат используемый нами язык в плане задания тех функций, которые могут возникнуть в данном контексте. В принципе, ниоткуда не следует, что такие функции должны иметь какой-то простой вид.
В дискуссиях шла речь о возможной "реальной" интерпретации смысла тех или иных арифметических формул. Мне показалось уместным написать на эту тему отдельно. Прежде всего я хочу напомнить об одной интерпретации общего характера. Пусть имеется замкнутая (то есть не зависящая от переменных) формула Ф, которая что-то утверждает. Можно считать, что эта формула имеет вид (Q_{1}x_1)...(Q_{n}x_{n})P(x_1,...,x_n), где Q_{1}, ..., Q_{n} -- логические кванторы A или E, расставленные в любом порядке, а P(x_1,...,x_n) -- бескванторная формула. Мы берём сначала наиболее общую ситуацию. Пусть переменные принимают значения на некоторой предметной области M, а P задаёт какое-то n-местное отношение P^M на множестве M. Будем считать, что для любых конкретных предметов m_1, ..., m_n из M у нас имеется "оракул", который нам возвещает о том, истинно или ложно высказывание P^M(m_1, ..., m_n) о данных объектах. Истинное и ложное значение будем обозначать как 1 и 0 соответственно.
Для арифметических формул у нас M есть множество натуральных (целых неотрицательных) чисел, а отношение P^M представляет собой конкретный алгоритм. На вход алгоритма подаётся последовательность n чисел m_1, ...,m_n; на выходе мы получаем 0 или 1 (за конечное число шагов работы алгоритма).
Сейчас нас интересует общий случай придания смысла формуле Ф. Этот смысл тем сложнее выявить, чем больше значение n, а ещё точнее -- чем больше имеется перемен кванторов среди Q_1, ..., Q_n. Я сейчас напоминаю о том, что такое игра Эренфойхта (об этом говорилось в недрах комментов в третьей части поста о книге Дойча).
Есть два игрока; пусть это будут Алла и Егор :) Алла играет "за" кванторы всеобщности, Егор -- за кванторы существования. Всего в игре ровно n ходов, причём ходы делаются не по очереди, а в соответствии со значениями кванторов. Если Q_k -- это квантор всеобщности A, то k-й ход делает Алла. Если же это квантор существования E, то k-й ход делает Егор. В качестве k-го хода тот игрок, который его делает, просто выбирает значение переменной x_k, указывая некоторый элемент m_k из M. После n ходов образуется последовательность m_1, ..., m_n, которую надлежит подставить в P^M, то есть задать вопрос "оракулу" об истинности или ложности итоговое высказывания P^M(m_1,...,m_n). Единственное содержательное правило игры, которое следует запомнить, состоит в следующем: если итоговое высказывание истинно, то победа присуждается Егору; если оно ложно, то Алле. То есть "хозяин" кванторов существования стремится сделать итоговое высказывание истинным, а его оппонент -- наоборот.
Истинность формулы Ф означает наличие выигрышной стратегии у Егора, а ложность формулы Ф -- наличие выигрышной стратегии у Аллы. Поскольку само по себе наличие стратегии у одного из игроков может наличествовать не всегда, хотелось бы понять, почему в рассматриваемом случае стратегия имеется, то есть формулу следует считать истинной или ложной (в выбранной интерпретации). Точнее, я хочу в явном виде проследить, на какие допущения мы при этом опираемся. Заодно это поможет себе более наглядно представить себе процесс придания истинностного значения формулам. Для наглядности и удобства я пока ограничусь случаем арифметических формул.
Как и в случае почти любых игр, в данном случае мы можем нарисовать дерево игры. Его в принципе очень легко себе представить. Вершинами дерева служат все числовые последовательности, имеющие не более n членов. Мы начинаем рисовать дерево сверху вниз. У этого дерева, как обычно, есть "корневая вершина" (вершина нулевого уровня), соответствующая "пустой" последовательности. Из этой вершины вниз выходит бесконечное число рёбер, занумерованных слева направо числами 0,1,2, ... . Каждое такое ребро ведёт к вершине первого уровня, соответствующей последовательности из одного члена. Далее, из каждой вершины первого уровня мы также проводим бесконечно много рёбер, идущих вниз к вершинам второго уровня и так далее, пока не достигнем вершин фиксированного n-го уровня. Каждой вершине k-го уровня соответствует числовая последовательность из k членов; если k меньше n, то из этой вершины идут вниз рёбра с метками 0,1,2, ... . После прохождения ребра с данной меткой мы приписываем к последовательности метку этого ребра. При этом получается примерно следующая картинка.
[]
[0] [1] [2] [3] .........................................................
[0,0] [0,1] [0,2] [0,3] ..... [1,0] [1,1] [1,2] [1,3] ..... [2,0] [2,1] [2,2] [2,3] ..... [3,0] [3,1] [3,2] [3,3] ..........
..............................................................................................................................................................................
Думаю, общая закономерность ясна. За неимением подходящих изобразительных средств, я не рисую здесь рёбра.
Итак, дерево построено. Каждая вершина расположена на одном из уровней от 0 до n. Рёбрам соответствуют уровни от 1 до n. Мы считаем, что ребро k-го уровня соединяет вершину (k-1)-го уровня с вершиной k-го уровня.
Сейчас опишем процедуру оценки вершин, проводимой снизу вверх, от n-го уровня к нулевому. Вершины n-го уровня имеют метку [m_1,...,m_n]. Имеющийся у нас алгоритм P^M приписывает каждой из этих вершин оценку 0 или 1, равную P^M(m_1,...,P_n). Оценка 1 соответствует победе Егора, оценка 0 -- победе Аллы. Теперь переходим к оценке вершин (n-1)-го уровня. Здесь ситуация будет зависеть от того, какой из кванторов у нас выступает в роли Q_n, поэтому возникает два случая.
1) Q_n -- это квантор всеобщности. Это означает, что n-й ход делает Алла. Она выигрывает в данной позиции, если сможет своим ходом перейти в вершину с оценкой 0. В её распоряжении бесконечно много ходов. Если среди них есть хотя бы один ход к вершине с оценкой 0, то мы присваиваем соответствующей вершине оценку 0. В противном случае оценка вершины (n-1)-го уровня будет равна единице. То есть ответ зависит от того, будет ли последовательность оценок вершин непосредственно снизу от данной состоять из одних единиц.
2) Q_n -- это квантор существования. Здесь n-й ход за Егором. Он выиграет, если сможет перейти своим ходом в вершину с оценкой 1. В этом случае оцениваемой вершине (n-1)-го уровня присваиваем 1. В противном случае -- присваиваем 0. Последний случай имеет место, если непосредственно внизу от оцениваемой вершины последовательность оценок будет состоять из одних нулей.
Итак, мы придаём описанным способом оценку всем вершинам (n-1)-го уровня. Продолжая действовать аналогично, мы переходим к вершинам (n-2)-го уровня и так далее, пока не дойдём до корневой вершины. Она получит некоторую оценку 0 или 1. В первом случае при правильной игре выигрывает Алла, и формула Ф ложна. Во втором случае выигрывает Егор, и формула Ф истинна.
Легко проследить, какие именно допущения лежат в основе осмысленности описываемого процесса. Каждый раз мы работаем с бесконечной последовательностью из нулей и единиц, которая как-то задана. Возможны три случая: последовательность является нулевой (из одних нулей), единичной (из одних единиц) и смешанной (содержит как нули, так и единицы). Если мы рассматриваем последовательность как актуально существующую, то есть как минимум допускаем возможность "божественного" её просмотра целиком, то про неё имеет смысл говорить, к какому из трёх типов она относится. На самом деле часто бывает достаточно просмотреть несколько первых членов, чтобы прийти к заключению, что последовательность имеет смешанный тип. Но если мы видим одни нули до какого-то места, то мы не знаем пока что, будут ли нули встречаться на всех местах, или же где-то нам встретится единица. (Аналогично с рядом последовательных единиц на первых местах.)
Какие последовательности можно считать "актуально существующими"? Радикальная точка зрения (отвергающая "актуальную бесконечность") может состоять в том, что вообще никакие. Противоположная точка зрения допускает какие угодно манипуляции с актуальной бесконечностью, включая случаи множеств "большой мощности". Хотелось бы выбрать что-то промежуточное. Причём не какую-то "правильную" точку зрения, а ту, которая позволяет "верить" в осмысленность понятия истинности арифметических формул при минимальных предположениях.
Мне кажется разумным перейти сейчас на несколько иной язык, но этот переход хотелось бы для начала мотивировать. Пусть имеется некоторая последовательность нулей и единиц, генерируемых при помощи алгоритма. Поскольку она однозначно задаётся конечным текстом, то вполне естественно считать, что она "существует", и потому либо обладает, либо не обладает какими-то свойствами. В частности, она либо нулевая, либо единичная, либо смешанная. Допустим, мы отслеживаем свойство последовательностей быть нулевыми. Тогда в принципе можно рассмотреть последовательность последовательностей и сопоставить ей числовую последовательность по такому принципу: заменить нулевые последовательности на 0, а остальные -- на 1. "Существование" новой последовательности зависит от того, насколько "единообразным" был процесс задания старых последовательностей. Опять же, мы можем считать, что последовательности были заданы "хорошо", если мы можем эффективно (то есть при помощи алгоритма) вычислить член заданной последовательности с заданным номером. То есть здесь на вход алгоритма подаются уже два числа.
В общем случае мы имеем итерации, то есть на следующем шаге возникают последовательности последовательностей последовательностей. Но все они в нашем примере с формулой генерируются единообразно, потому что за всё отвечает один и тот же алгоритм P^M с "входом" из n чисел. Поэтому удобно переформулировать всё происходящее в следующем виде. Будем говорить не о последовательностях, которые "актуально существуют", а о множествах чисел, множествах (упорядоченных) пар чисел, множествах троек, четвёрок и так далее. Если имеется некоторый алгоритм, на вход которого подаётся (упорядоченный) набор из n чисел, а на выходе получается значение 0 или 1, то будем считать, что множество всех наборов, на котором значение алгоритма равно 0 (равно 1) в каком-то смысле "актуально существует". Посмотрим, что происходит с множествами с процессе навешивания кванторов.
Если A -- некоторое уже объявленное "существующим" множество n-ок (то есть упорядоченных наборов из n чисел), то применение квантора существования приводит к операции проекции. А именно, если B -- множество всех таких наборов вида (m_1,...,m_{n-1}), для которых существует такое m_n, при котором набор (m_1,...,m_{n-1},m_n) принадлежит A, то B естественно назвать проекцией множества A на первые n-1 "координат". Осмысленность навешивания квантора существования, таким образом, сводится к следующему положению: если A "актуально существует", то этим же свойством обладает и его проекция.
Вместо кванторов всеобщности можно использовать отрицание, так как любой из кванторов выражается через другой при помощи отрицания. При этом мы ничего не теряем и не приобретаем, так как отрицания в любом случае разрешалось "навешивать" на формулы. А это позволяет извлечь следующий принцип: если A "актуально существует", то его дополнение (состоящее из всех n-ок, не принадлежащих A), также "актуально существует".
Таким образом, в основе "веры" в абсолютный истинностный статус арифметических формул лежит не что иное как принятие следующих постулатов:
1) разрешимые множества (то есть распознаваемые при помощи алгоритма) "актуально существуют";
2) класс "актуально существующих" множеств замкнут относительно операций проекции и дополнения.
Здесь везде речь идёт о множествах n-ок натуральных чисел, по всем n сразу.
Представляется, что допущения, о которых идёт речь, не являются слишком сильными, чтобы их отвергать.
В заключение хочется сказать ещё пару слов на ту же тему. Рассмотрим формулу (Ax)(Ey)(Az)(Et)P(x,y,z,t), где P(x,y,z,t) -- бескванторный предикат. Истинность этой формулы означает существование двух функций: y=f(x) и t=g(x,z) таких, что высказывание P(x,f(x),z,g(x,z)) истинно всегда, при любых x,z. Такой способ осмысления истинности формул также может быть полезен. Он, в частности, заставляет задуматься о том, насколько богат используемый нами язык в плане задания тех функций, которые могут возникнуть в данном контексте. В принципе, ниоткуда не следует, что такие функции должны иметь какой-то простой вид.