) будет все же не больше, чем множество всех положительных чисел. С каждым положительным целым числом
n оказывается связанным определенное множество чисел Аn, имеющее имя на нашем языке — это позволяет представить себе, что все именуемые множества расположены в виде последовательности
A>1,
A>2…,
А>n… (Если хотите, можете вообразить себе, например, книгу с бесконечным числом страниц, причем для каждого целого положительного
n на соответствующей
n-й странице приведено описание того или иного множества положительных целых чисел. Тогда система
A>n — это множество, описанное на
n-й странице этой книги.)
Введем теперь математический символ ∈, который означает «принадлежит» или «является членом». Для каждого числа х и произвольного числа у мы можем сформировать утверждение х ∈ А>у, которое означает, что х принадлежит множеству А>у. Это единственный вид утверждений, которые воспринимает моя машина. При этом задача машины состоит в том, чтобы определить, какие числа каким поддающимся описанию множествам принадлежат.
Далее, каждое утверждение x ∈ A>y имеет свой кодовый номер — число, которое, будучи записано в обычной десятичной системе счисления, состоит из цепочки единиц длиной x и следующей за ней цепочки нулей длиной у. Например, кодовый номер утверждения З ∈ A>2 выглядит как 11100; кодовый номер утверждения 1 ∈ A>5 имеет вид 100000. При этом кодовый номер утверждения x ∈ A>y, то есть число, состоящее из x единиц и следующих за ними у нулей, я буду обозначать символом x*y.
— Машина работает следующим образом, — продолжал Фергюссон. — Когда она обнаруживает, что число x принадлежит множеству A>y, то она отпечатывает число x*y, то есть кодовый номер утверждения x ∈ A>y. Если при этом машина печатает число x*y, то я говорю, что машина доказала утверждение x ∈ A>y. Кроме того, если машина способна напечатать число x*y, то я говорю, что утверждение x ∈ A>y доказуемо (с помощью моей машины).
Наконец, я знаю, что моя машина всегда точна — в том смысле, что каждое утверждение, которое можно доказать с ее помощью, является истинным.
— Минуточку, — вмешался Крейг. — Что значит «является истинным»? Какая разница между «является истинным» и «доказуемо»?
— Да это же совершенно разные вещи, — объяснил Фергюссон. — Я говорю, что утверждение x ∈ A>y истинно, если x действительно является элементом множества A>y. Если же оказывается, что машина способна напечатать число x*y, тогда я говорю, что утверждение x ∈ A>y доказуемо с помощью моей машины.
— Вот теперь ясно, — сказал Крейг. — Другими словами, утверждая, что ваша машина точна — или, иначе, что каждое утверждение, доказуемое с помощью машины, является истинным, — вы имеете в виду, что ваша машина никогда не напечатает число