Принцесса или тигр?

1. С помощью свойств 1–3 можно, оказывается, строго показать, что машина Фергюссона не способна доказать все истинные утверждения. Читателю предлагается найти такое утверждение, которое является истинным, но при этом не может быть доказано с помощью этой машины. Иначе говоря, мы должны найти такие числа n и m (они могут быть как одинаковыми, так и разными), для которых кодовый номер утверждения n ∈ A_m — то есть число n*m — не мог бы быть напечатан машиной, но чтобы при этом число n являлось бы элементом множества A_m.

2. В решении задачи 1, которое приведено ниже, числа n и m оба меньше 100. Имеется и другое решение этой задачи, для которого числа n, m также оказываются меньше 100 (при этом они опять могут быть как одинаковыми, так и разными). Сумеет ли читатель найти это решение?

3. Если не ограничивать сверху величину чисел n и m, то сколько всего решений может быть у такой задачи? Иначе, сколько существует истинных утверждений, которые недоказуемы с помощью машины Фергюссона?

Заключение

Фергюссон вовсе не хотел отказываться от идеи создания такой машины, которая могла бы доказывать арифметические истины, не будучи в состоянии доказывать ложные заключения, поэтому он напридумывал целую кучу таких логических машин.[7] Однако для каждой новой машины либо он сам, либо Крейг с Мак-Каллохом все-таки находили такое истинное утверждение, которое машина доказать не могла. Поэтому в конце концов Фергюссон отказался от мысли сконструировать чисто механическое устройство, которое было бы одновременно и точным (в указанном выше смысле. — Перев.), и могло бы доказать любое истинное арифметическое утверждение.

Итак, все героические попытки Фергюссона не увенчались успехом, однако причина этого заключалась отнюдь не в недостатке авторской изобретательности. Мы не должны забывать о том, что он жил за несколько десятилетий до знаменитых открытий таких известных логиков, как Гёдель, Тарский, Клини, Тьюринг, Пост, Черч и другие ученые, о работах которых у нас вот-вот пойдет речь. Если бы Фергюссон дожил до этих открытий, то он понял бы, что неудачи его обусловлены исключительно тем, что он пытался создать нечто по сути своей совершенно невозможное! Поэтому, отдав должное Фергюссону и его коллегам Крейгу и Мак-Каллоху, распрощаемся с ними и перенесемся на три-четыре десятилетия вперед, в переломный 1931 год.

Решения

1. Одно из решений состоит в следующем: утверждение 75 ∈ A₇₅ является истинным, но не может быть доказано машиной. И вот почему.

Допустим, что утверждение 75 ∈ A₇₅ ложно. Тогда число 75 не принадлежит множеству A₇₅. Следовательно, это число должно принадлежать множеству A₂₅ (согласно свойству 2, множество А₇₅ является дополнением множества A₂₅). Это означает (согласно свойству 3), что число 75*75 принадлежит множеству A₈, поскольку 25 = 3×8 + 1, и, следовательно, машина может напечатать число 75*75. Иначе говоря, это означает, что утверждение 75 ∈ A₇₅ может быть доказано машиной. Таким образом, если бы утверждение 75 ∈ A₇₅ было ложным, то оно вполне могло бы быть доказано машиной. Однако нам известно по условию, что машина точна и никогда не доказывает ложные утверждения. Поэтому утверждение 75 ∈ A₇₅ не может оказаться ложным, и, стало быть, оно должно быть истинным.

Далее, поскольку утверждение 75 ∈ A₇₅ истинно, то число 75 действительно принадлежит множеству A₇₅. Поэтому оно не может принадлежать множеству А₂₅ (согласно свойству 2), и, следовательно, число 75*75 в свою очередь не может принадлежать множеству A₈, поскольку если бы это было так, то тогда, согласно свойству 3, число 75 принадлежало бы множеству А₂₅. Поскольку ясно, что число 75*75 не принадлежит множеству A₈, то утверждение 75 ∈ A₇₅ не может быть доказано машиной. Итак, утверждение 75 ∈ A₇₅ является истинным, но оно недоказуемо с помощью машины.