?

Log in

No account? Create an account

Previous Entry | Next Entry

Гедель 2

1   2   3  4  5  6  7

V. Кубики со смыслом

Никакого смысла в строках системы ХИХИ нет. Математика — игра ума. Математики любят играть в кубики и смотреть, как ведет себя система из кубиков, правила которой придуманы произвольно, но жестко соблюдаются. Эта игра интересна сама по себе; никакой другой ценности от нее математику не требуется.

Интересно, однако, понять, какое место занимают ФС в ряду прочих математических инструментов. Чтобы ФС «заговорила» о математике, нам потребуется наделить строки ФС смыслом. Смысл этот мы присваиваем только результату работы ФС; на самом процессе ее работы он не сказывается. Смысл этот, таким образом, определяется снаружи ФС.

Как осмыслить результат работы системы ХИХИ, я не представляю. Это не значит, что смысла нет, или что он есть, но неизвестен. Смысл мы придаем строкам по желанию, любые утверждения о его существовании бессодержательны. Возможно, что кто-то сопоставит строки этой системы с другим математическим объектом, и это даст толчок какой-то новой его идее.

Мы же сейчас рассмотрим другую ФС. Ее алфавит состоит из трех символов: { •, §, # }. Единственную строку •§•#•• будем считать верной по определению. Введем следующие два правила получения новых верных строк:

1. К верной строке можно приписать слева и справа по •, например, из верной строки •§•#•• выйдет по этому правилу ••§•#•••
2. Слева и справа от символа # в верной строке можно вставить по •: из строки •§•#•• получится •§••#•••

Применяя эти правила по очереди в разных сочетаниях, можно получить, например, такие строки (все они будут верными):

••§•••#•••••
••••§•#•••••
•••§•••#••••••

Вы наверняка уже заметили, что если заменить число звездочек на натуральное число и понимать § как операцию сложения, а # как равенство, строки эти можно осмыслить как 2+3=5, 4+1=5, 3+3=6. Я нарочно не сделал + и = символами алфавита нашей системы, а выбрал для этого § и #, чтобы подчеркнуть, что мы осмысливаем § как +, а # как = вне системы.

Кроме того, возможно и иное осмысление. Введем операцию «отнять от» и обозначим ее ÷, например, 1 отнять от 5 даст 4: 1÷5=4. Теперь мы можем задать иной смысл формальному результату: заменим § на =, а # на ÷, и получим тогда верные арифметические выражения: 2=3÷5, 4=1÷5, 3=3÷6.

Формальную систему можно осмыслить множеством способов — насколько хватит фантазии играющего в кубики.

Нелишне будет нам еще раз вспомнить, что результат работы ФС, все ее строки, можно пронумеровать натуральными числами6. Эта нумерация, само собой, тоже происходит вне системы: система не нумерует строк, это мы с вами, находясь за границей системы, их нумеруем.

VI. Семантика

До сих пор, мы четко разграничивали формальную («внутреннюю») и интерпретационную («внешнюю») стороны ФС. Сейчас мы с вами построим из ФС и ее избранной интерпретации новый объект, формальную систему со смыслом, или семантикой (ФСС). Каждый раз, когда вы читаете фразу «ФС говорит, что…», «ФС утверждает…», вы имеете дело с ФСС, включающей некоторую интерпретацию ее строк. Такие выражения — совершенно общее место в литературе. Мы, тем не менее, не случайно заострили внимание на различении синтаксиса системы (механических правил преобразования символов) и ее семантики — слоя, положенного поверх синтаксиса и предназначенного для осмысления результата ее работы.

Синтаксис ФС заключен в себе. Это означает, что нам ничего не стоит написать компьютерную программу, которая выполнит все преобразования строк. Семантика ФСС, с другой стороны, не замыкается на себя, но неизбежно обращается к другим понятиям. Чтобы осознать это, рассмотрим осмысление нашей предыдущей ФС в виде ФСС, описывающей сложение натуральных чисел.

Итак, договоримся, что звездочки • означают запись числа в единичной системе: количество звездочек означает натуральное число, равное этому количеству. К каким понятиям мы обратились здесь? Понятия натурального числа и количества. Количество мы, возможно, формализуем, но, опять же, через понятие натурального ряда (нам потребуются числа и операция увеличения на 1, или перехода к следующему числу в ряду). Таким образом, первое же наше смысловое правило привнесло внешнее понятие, именно, понятие натурального ряда, которое мы знали ранее.

Теперь определим § как операцию сложения, а # как равенство, как мы уже делали ранее. Это привнесет новые, уже знакомые нам арифметические понятия сложения натуральных чисел и сравнения их между собой. Результатом сложения является натуральное же число, например, складывая 3 и 4, получим 7. Результатом сравнения чисел может быть одно из двух значений: истина или ложь. Например, утверждение 2=2 истинно, а 2=5 ложно.

Легко показать, что наша ФСС производит все верные выражения для сложения натуральных чисел, и не выдает ни одного неверного7.

Давайте взглянем внимательно, как проходит наша новая, семантическая граница, что находится теперь внутри и вовне ФСС. Утверждение 2+2=4 выводится внутри семантики ФСС, той предметной области, в которой определена наша смысловая интерпретация. Однако, утверждение «2+2=4 истинно» лежит вовне нашей новой системы. Когда мы говорим о семантической интерпретации, следует отличать истинность, которую мы определяем для себя, сравнивая результат осмысления строк системы с «внешним миром», и выводимость, возможность получения строки-утверждения в ФС. Выводимость утверждения (в семантической области мы называем строки утверждениями) определяется формализмом системы. Истинность же «на самом деле» система сама по себе не утверждает; любое «на самом деле», какой бы смысл ни вкладывался в эти слова, находится всегда вовне системы.

Это утверждение, если мы с вами рассуждаем о такой простой системе, конечно же, тривиально. В дальнейшем, однако, когда мы рассмотрим более сложную ФСС, вынесение «истинности» за границу системы создает серьезные диалектические вопросы в понимании математики.

VII. Элементарная арифметика

ФСС, которую мы рассмотрели, порождает результат чрезвычайно тривиальный: перечисление всех выражений вида a+b=c с конкретными числами. Однако, далеко не все формальные системы так просты. Назначая правила синтаксиса и базовую семантику символов, мы можем получить и систему, которая, как оказывается, выводит теоремы элементарной арифметики!

Тоже мне, скажете вы, особое достижение — элементарная арифметика! Это ведь то, что мы к третьему классу уже все знали, сложение-умножение? Нет, неверно. Младшеклассникам, изучающим арифметику в школе, показывают даже не краешек, а тень этой математической горы! К элементарной арифметике (ЭА) относятся, например, задачи решения диофантовых уравнений, изучение простых чисел, и очень многое другое. К примеру, Великая теорема Ферма, остававшаяся недоказанной несколько веков, тоже относится к области арифметики. Вся современная компьютерная криптография имеет в своей научной основе арифметику. А элементарной мы называем такую систему арифметики вовсе не потому, что она очень простая, а потому, что она не требует основания в других разделах математики, строится на основе своих собственных аксиом. Геометрия Эвклида тоже будет в этом смысле элементарной геометрией, потому что она не требует для основания ничего, кроме своих собственных понятий и аксиом.

Так же, как и в геометрии, где не определяются некоторые понятия, например,точки или прямой, в арифметике тоже есть неопределимые понятия. Одно из них — интуитивно знакомое всем натуральное число. Хоть нам все интуитивно известно, что такое число, никакого определения числа арифметика не дает. Аксиомами задаются лишь их свойства, такие, как «для каждого числа есть ровно одно последующее число», «1 не следует ни за каким числом» и прочие. Устройством своих основ ЭА напоминает геометрию; хотя последней уделяется в школе определенное внимание, аксиоматическое определение арифметики в школе не упоминается вовсе.

В число теорем арифметики включаются, разумеется, и утверждения, широко известные под именем собственно теорем («для любого натурального числа существует превышающее его простое число»), и более частные утверждения, возникающие при решении отдельных задач («не существует трех простых чисел, больших 3, подряд через одно», т. е. для любого простого числа p>3, по крайней мере одно из p+2 и p+4 не является простым), и совсем уж тривиальные, не интересные, на первый взгляд, утверждения (например, «для любого числа а, 0+а=а»).

В этом популярном изложении не найдется места детальному описанию ФСС, производящей теоремы ЭА. Если вас интересуют подробности ее работы и устройства, лучше обратиться к [1] за популярным изложением или к [2] за глубоким математическим изъяснением предмета. Мы ограничимся только общими принципами ее построения, и сама теорема Геделя будет объяснена лишь «на пальцах», без надлежащих стройных формулировок и строгих доказательств.

1   2   3  4  5  6  7
__________________________________
6. Подумайте, как можно пронумеровать строки, порождаемые нашей системой.

7. Попробуйте, в качестве упражнения, доказать это.

Tags:

Comments

( 53 comments — Leave a comment )
happy_husband
Dec. 14th, 2009 11:44 am (UTC)
Символы не видны. Одни квадратики...
fregimus
Dec. 14th, 2009 06:13 pm (UTC)
Исправил, теперь видны? Скажите еще, пожалуйста, нет ли в этой строчке квадратиков:

∀x:∃a:~∃b:∃c:(x+a)=(b+1)×(c+1)
искоренение - falcao - Dec. 14th, 2009 06:58 pm (UTC) - Expand
fat_crocodile
Dec. 14th, 2009 11:45 am (UTC)
> за каждым числом, кроме 1, следует число

Что-то тут не так.

А вообще -- отлично пишите, спасибо.
fregimus
Dec. 14th, 2009 06:21 pm (UTC)
А что тут не так? За 1 следует 2, за 2 — 3, и так далее. И только 1 ни за чем не следует. Вроде бы, это две из аксиом Пеано. Которые один перц на экзамене назвал аксиомами Пеанино — именно так, выделив, произнося, «е».

…А Мамба всех ненавидит…
(no subject) - fat_crocodile - Dec. 14th, 2009 07:02 pm (UTC) - Expand
(no subject) - fregimus - Dec. 14th, 2009 07:07 pm (UTC) - Expand
rruben
Dec. 14th, 2009 12:36 pm (UTC)
Фундаментально! Только что осилил и первую и вторую часть, спасибо :)
fregimus
Dec. 14th, 2009 06:17 pm (UTC)
А что было труднее всего понять?
(no subject) - rruben - Dec. 14th, 2009 09:22 pm (UTC) - Expand
(no subject) - fregimus - Dec. 14th, 2009 10:24 pm (UTC) - Expand
falcao
Dec. 14th, 2009 12:51 pm (UTC)
квадратеги
У меня тоже символы не видны!
fregimus
Dec. 14th, 2009 06:14 pm (UTC)
Re: квадратеги
Ой. Исправил, получилось? А в следующей строчке нет квадратиков?

∀x:∃a:~∃b:∃c:(x+a)=(b+1)×(c+1)
не туда - falcao - Dec. 14th, 2009 06:59 pm (UTC) - Expand
(no subject) - fregimus - Dec. 14th, 2009 07:10 pm (UTC) - Expand
смена шрифта - falcao - Dec. 14th, 2009 07:37 pm (UTC) - Expand
Re: смена шрифта - fregimus - Dec. 14th, 2009 07:51 pm (UTC) - Expand
plakhov
Dec. 14th, 2009 02:36 pm (UTC)
accuracy nazi
«не существует трех простых чисел подряд через одно»
Наглая ложь!!
fregimus
Dec. 14th, 2009 05:41 pm (UTC)
Re: accuracy nazi
Ай. 3, 5, 7. Ну больше-то не существует?
(Deleted comment)
fregimus
Dec. 14th, 2009 06:15 pm (UTC)
Спасибо, учту обязательно.
связь - falcao - Dec. 14th, 2009 07:09 pm (UTC) - Expand
(Anonymous)
Dec. 15th, 2009 12:01 am (UTC)
а что это за ссылки [1] и [2]?
fregimus
Dec. 15th, 2009 09:15 am (UTC)
Библиография в первой части. Поскольку я кусочками выкладываю, лучше в начале ее было дать.
bvn_mai
Dec. 15th, 2009 01:26 pm (UTC)
Уважаемый Fregimus, наконец удалось прочесть первую и "по-диагонали" вторую части - получил огромнейшее удовольствие :). Очень расстроили некоторые комментарии, но боюсь, что этой публике объяснять что либо просто бессмысленно. Надеюсь, что они не помешают Вам написать продолжение, которого я жду с огромным интересом.
fregimus
Dec. 15th, 2009 06:56 pm (UTC)
Меня вовсе ничего не огорчило и не расстроило. Люди спорят о тонкостях — это хорошо.
yurvor
Dec. 15th, 2009 03:05 pm (UTC)
По мелочи
"Хоть нам все интуитивно известно, что такое число, никакого определения числа арифметика не дает. "

В каком смысле - "не даёт"? В матклассе нам, помнится, определяли множество натуральных чисел.

Есть множество и есть его элементы (эти две вещи действительно неопределяемые).

1). Есть такой элемент, называется 1.
2). Для каждого элемента существует элемент, следующий за ним.
3). Натуральное множество является подмножеством любого множества, удовлетворяющего 1) и 2)

Вот элементы этого множества и называются числами. Чем не определение?

"Аксиомами задаются лишь их свойства"

Вот тут, видимо, самый непонятный пассаж. Задание их свойств - ведь это же и есть их определение! Или нет? Или что тогда такое - определение?

Edited at 2009-12-15 03:11 pm (UTC)
fregimus
Dec. 15th, 2009 06:02 pm (UTC)
Через множества — неопределимое понятие теории множеств — запросто. А вот если не привлекать теорию множеств и ее понятия, чтобы арифметика оставалась элементарной, то никакого определения не получится.

Про определение и свойства. Возьми точку и прямую. В геометрии их не определяют, хотя аксиомы задают их свойства. «Через две точки проходит ровно одна прямая» — свойство. «Прямой называется…» — определение.
(no subject) - yurvor - Dec. 15th, 2009 06:34 pm (UTC) - Expand
(no subject) - fregimus - Dec. 15th, 2009 06:54 pm (UTC) - Expand
yurvor
Dec. 15th, 2009 05:13 pm (UTC)
"Когда мы говорим о семантической интерпретации, следует отличать истинность, которую мы определяем для себя, сравнивая результат осмысления строк системы с «внешним миром», и выводимость, возможность получения строки-утверждения в ФС. "

Тут всё-таки не ясно. Когда мы заменяли звёздочки на числа, а знаки на операции, мы делали не более, чем подстановки - вместо одних кубиков другие. Ну, будет у нас не три варианта кубиков, а бесконечное число (вопрос замены произвольного количества звёздочек и появления бесконечности мы сейчас отложим).

Фактически мы ничего не приобрели: числа - это просто кубики такие. Как узнать, истинно ли, что 347+149=496? Только попробовать его вывести, как иначе? Поэтому разделение (чего?) на истинность и выводимость тут неясно. Чем же всё-таки они отличаются друг от друга?

* * *
Или другими словами попробую сформулировать. Вот ты пишешь: "К каким понятиям мы обратились здесь? Понятия натурального числа и количества." Ну да, другие кубики. Вводим дополнительные кубики и правила замены - кубик "число", кубик "количество", правила замены звёздочек на кубик "n".

И какую бы "семантику" мы не придумывали, фактически мы просто будем дополнять ФС кубиками и правилами. Откуда берётся "самая семантическая семантика"? По-моему, любую семантику можно рассмотреть, как формальную систему. Или, вернее, если ты хочешь сказать, что семантический слой - это не ФС, то это стоит как-то доказать.

Edited at 2009-12-15 05:19 pm (UTC)
fregimus
Dec. 15th, 2009 06:35 pm (UTC)
Это очень хорошее наблюдение. Все это верно.

В математике объект, с которым мы играем, сначала строится. Вот мы так провели границу, разделяющуюю «внутри» и «вовне»: определили систему, выдающую строки — это внутри — и начали над ней думать — вовне. Оказалось, что система такая удачная, что ее строки интерпретируются как утверждения некоей теории Х.

Дальше, ты совершенно верно заметил, мы можем формализовать осмысление Х и поместить его вовнутрь новой машины, вместе с первой. Мы получим машину, выдающую нечто о теории Х. Когда мы — вовне этой штуки — осмыслим, что она выдает, мы получаем утверждения о теории Х.

Дальше, ты совершенно верно заметил, мы можем формализовать осмысление утверждений о теории Х и поместить его вовнутрь новой машины, вместе со второй и первой. Мы получим машину, выдающую нечто об утверждениях о теории Х. Когда мы — вовне этой штуки — осмыслим, что она выдает, мы получаем утверждения об утверждениях о теории Х.

Дальше, ты совершенно верно заметил, мы можем формализовать осмысление утверждений об утверждениях о теории Х и поместить его вовнутрь новой машины, вместе с третьей, второй и первой. Мы получим машину, выдающую нечто об утверждениях об утверждениях о теории Х. Когда мы — вовне этой штуки — осмыслим, что она выдает, мы получаем утверждения об утверждениях об утверждениях о теории Х.

Конца у этой цепочки нет. Каждый раз мы привносим новые правила семантики (семантиу теориии, затем метатеории, метаметатеории…), и процесс этот не остановится.

Выводимость — техническое понятие, выдает ли ФС данную строку. Истинность — понятие вне системы. Истинно ли 347+149=496? В той семантике, что мы приписали — видимо, да. Она опирается на теорию чисел, арифметику, и мы можем воспользоваться более сильной теорией, чтобы проверить выводы этой более слабой. Истинность других утверждений, сгенерированных более сложными системами, проверить уже не так легко. Ведь у нас нет более сильной теории, чтобы их проверить!

Вопрос о «самой семантической семантике» тоже очень хороший. Мы ее придумываем, как и все остальное в математике, «просто так». Как бы сначала придумываем. потом смотрим, что вышло, только это неправда, вернее, не всегда правда. Когда я эту систему придумывал — вернее, адаптировал пример Хофштадтера — я уже загадал, что она будет сочинять верные сложения двух чисел. Выходит, семантику я придумал сначала. Потом, пользуясь этой семантикой, я написал несколько верных строк и заметил пару правил, как их надо формально переписывать, чтобы система выдавала строки, чтобы эти строки потом интерпретировались в той семантике, что я задал первой. «По настоящему» все происходит наоборот. Но это не отменяет ничего. Если ты читаешь доказательство — лемма 1, лемма 2 — скорее всего, леммы тоже были продуманы в обратном порядке, но это доказательства не аннулируиет.

Или же твой вопрос о том, какая семнтика правильная, достаточно сильная? Можно построить много разных систем. Некоторые из них будут слишком слабы для нашей цели — построить теорию чисел. Их мы отбросим. Множество других для этого пригодны. Однако, получается, что, начиная с некоторой системы, мощность их перестает расти. Например, ФС с операцией сложения (т. е. с символом, скажем, +, который будет интерпретирован как сложение) недостаточно сильна для выражения арифметики. Если добавтиь умножение — достаточно. А если добавить к ней еще и возведение в степень, то силы в ней не прибавится. Это в точности параллельно различным автоматам: система со сложением равна стековой машине, с умножением — машине Тьюринга, а с возведением в степень… тоже МТ, потому что ничего более мощного в дискретной математике не бывает. Это доказывается, но у этой шляпы поля слишком малы — ты сам сможешь найти.

…сначала выдумывают, потом садятся…
(no subject) - yurvor - Dec. 15th, 2009 07:01 pm (UTC) - Expand
Дописываю ответ - yurvor - Dec. 16th, 2009 05:18 am (UTC) - Expand
Re: Дописываю ответ - fregimus - Dec. 16th, 2009 05:49 am (UTC) - Expand
Re: Дописываю ответ - fregimus - Dec. 16th, 2009 09:40 am (UTC) - Expand
yurvor
Dec. 15th, 2009 05:54 pm (UTC)
Или вот - явное построение. Рассмотрим три ФС.

ФС1 - это твоя начальная ФС с тремя символами, двумя правилами и одной начальной строкой.

ФС2 - это ФС1 с добавлением кубиков "всевозможные числа", добавлением правила замены звёздочек на "числа" и правилом замены знаков.

ФС3 - это ФС2 с добавлением кубика T, начальной строки "Т" и правилом замены "к любому утверждению-строке, выводимой в ФС2, можно приписать Т справа". Ну, и опционально можно добавить правило "любое утверждение-строку, выводимую в ФС3, можно заменить на Т целиком".

Вот в ФС3 понятие истинности встроено внутрь самой системы.
fregimus
Dec. 16th, 2009 04:42 am (UTC)
Что такое «все возможные числа»? Алфавит должен быть конечным.

Насчет «Т» — Ну и что? Это не истинность, это строка Т т. е. та же самая выводимость. Ну, добавил ты к множеству строк те же самые строки, с любым количеством Т справа. Ну и что? Я не понимаю, в чем здесь принципиальное отличие.

Дождись следующей части. В системе найдется внутреннее противоречие, получится интересно.
(no subject) - yurvor - Dec. 16th, 2009 05:07 am (UTC) - Expand
(no subject) - fregimus - Dec. 16th, 2009 05:36 am (UTC) - Expand
(no subject) - yurvor - Dec. 16th, 2009 06:53 am (UTC) - Expand
(no subject) - yurvor - Dec. 16th, 2009 06:53 am (UTC) - Expand
(no subject) - kondybas - Dec. 19th, 2009 04:44 pm (UTC) - Expand
(no subject) - yurvor - Dec. 19th, 2009 05:03 pm (UTC) - Expand
(no subject) - kondybas - Dec. 19th, 2009 05:16 pm (UTC) - Expand
(no subject) - yurvor - Dec. 19th, 2009 07:28 pm (UTC) - Expand
(no subject) - kondybas - Dec. 19th, 2009 08:22 pm (UTC) - Expand
(no subject) - fregimus - Dec. 19th, 2009 08:37 pm (UTC) - Expand
(no subject) - kondybas - Dec. 19th, 2009 08:54 pm (UTC) - Expand
(no subject) - fregimus - Dec. 19th, 2009 09:08 pm (UTC) - Expand
(no subject) - kondybas - Dec. 19th, 2009 09:23 pm (UTC) - Expand
(no subject) - fregimus - Dec. 19th, 2009 09:40 pm (UTC) - Expand
(no subject) - fregimus - Dec. 19th, 2009 06:43 pm (UTC) - Expand
( 53 comments — Leave a comment )