Принцесса или тигр? (Смаллиан) - страница 112

; и G_>3 (условие G_>1 пока несущественно). Ранее мы определили P как множество гёделевых номеров всех утверждений, доказуемых в данной системе; пусть теперь Т будет множеством гёделевых номеров всех истинных утверждений в этой системе. В 1933 г. логик Альфред Тарский поставил вопрос: «Именуемо ли множество Т в данной системе или нет?» — и ответил на него. Ответ может быть получен на основе лишь условий G_>2 и G_>3. Однако, прежде чем говорить об этом, обратимся сначала к вопросу не меньшей важности — о системах, которые удовлетворяют по крайней мере условию G_>3.

Для любого заданного утверждения X и любого множества положительных целых чисел А мы будем называть X гёделевым утверждением для A, если либо X истинно и его гёделев номер принадлежит A, либо X ложно и его гёделев номер не принадлежит A. (Подобное утверждение можно представлять себе как высказывание о том, что его собственный гёделев номер принадлежит A: если это утверждение истинно, то его гёделев номер действительно принадлежит A; если же оно ложно, то его гёделев номер не принадлежит A.) Далее, мы будем называть систему гёделевой в том случае, если для каждого множества A, допускающего наименование в этой системе, существует хотя бы одно гёделево утверждение для A.

При этом самым существенным для нас пунктом является следующая теорема.

Теорема С.Если система удовлетворяет условию G_>3, то эта система является гёделевой.

1. Докажите теорему С.

2. В качестве частного случая рассмотрите систему Фергюссона. Найдите гёделево утверждение для множества A_>100.

3. Предположим, что некоторая система является гёделевой (даже если она и не удовлетворяет условию G_>3). Если эта система правильна и удовлетворяет условиям G_>1, и G_>2, то обязательно ли она содержит утверждение, которое является истинным, но недоказуемым в данной системе?

4. Пусть Т — множество гёделевых номеров всех истинных утверждений. Существует ли гёделево утверждение для Т? Существует ли гёделево утверждение для множества T̅, то есть дополнения Т?

Вот теперь мы наконец можем ответить и на вопрос, поставленный Тарским. В самой общей форме теорема Тарского формулируется следующим образом:

Теорема Т.Для любой заданной системы, удовлетворяющей условиям G_>2и G_>3, множество Т гёделевых номеров истинных утверждений не именуемо в данной системе.

Примечание. Иногда слово «именуемо» заменяется словом «определимо», в результате чего теорему Т формулируют так: для достаточно богатой системы истинность в ее рамках не определима в пой системе.

5. Докажите теорему Т.

6. Следует отметить, что, доказав теорему Т, мы сразу и в качестве непосредственного следствия получаем теорему G. Может ли читатель сообразить, как это сделать?