 Концептуальное математическое искусство. | Oct. 14th, 2005 @ 11:14 pm  |
|---|
Спасибо Вам за развёрнутый ответ!
Но я по-прежнему не понимаю разницу между понятиями:
- истинный
- истинный всегда
- истинный в интерпретации
да и понятие "интерпретация" само по себе.
В моём, возможно, неправильном, представлении, мы имеем изначально систему аксиом некоторой теории, скажем, теории множеств Цермело-Френкеля. И правила логического вывода. Далее, мы можем попытаться раскрасить все утверждения нашей теории в два цвета: "истина" и "ложь" в зависимости от того, выводимо ли данное утверждение из аксиом с помощью данных правил вывода. Если выводимо, то пишем "истина", если выводимо его отрицание, то пишем "ложь". Некоторые утверждения мы не сможем раскрасить, как бы мы не старались (теорема Гёделя о неполноте).
При таком подходе совершенно непонятно, зачем нужна теорема Гёделя о полноте. Ведь она попросту повторяет определение истинности. Что такое "глобально выводима"? Мы можем задаться вопросом о том, что же выводимо из любого подмножества аксиом, пусть не из пяти, а из четырёх аксиом. Это тоже будет математикой.
Последний абзац я не понял вообще. Что значит, "в этой интерпретации", "не верим в существование"? Натуральный ряд существует ввиду существования пустого множества и вполне конструктивной процедуры его порождения. Это строгие рассуждения, не зависящие ни от каких "интерпретаций" (кстати, что это такое?).
Трудность состоит в том, что мы всё время перескакиваем с одного уровня понимания вещей на другой, причём это специально не оговаривается. Скажем, если мы занимаем чисто формальную позицию, то "истина" не имеет смысла вообще. При этом выводимые утверждения будут приравниваться к истинным, а те, у которых выводимо отрицание - к ложным. Такой подход возможен, но он не вынужден, т.е., признавая его актуальность, можно пытаться выходить и за пределы. Причину необходимости выхода за пределы объяснить легко. Выводимость подразумевается из данного множества аксиом типа теории множеств. Когда-то теории множеств не было. Завтра я или Вы можем предложить новую удовлетворяющую всех аксиоматику. При этом "пределы видимости" будут всё время меняться. Это говорит об условности данного подхода, так как он привязан к текущей (пусть даже общепринятой) конъюнктуре.
О понятиях. Формула - это правильно составленный набор знаков, т.е. объект чисто семантический. Интерпретация - это непустое множество + конкретное сопоставление а) предметным константам формулы некоторых элементов множества, б) функциональным символам формулы - операций на этом множестве, в) предикатным символам формулы - отношений на множестве. Если я возьму формулу \forall a \forall b \exists x \exists y (f(x,y)=a & g(x,y)=b), то этот набор значков станет истинным на множестве комплексных чисел при условии, что f мы сопоставили сложение, g - умножение. Для вещественных чисел это будет уже неверно; более того, можно интерпретировать и f, и g столь извратно, что утверждение будет не истинным совсем. Определение истинности формулы в данной интерпретации использует теоретико-множественный язык и даётся индуктивно по сложности построения самой формулы (число использованных связок и кванторов).
Истинное всегда = истинное в ЛЮБОЙ интерпретации (т.е. таких формул в каком-то смысле довольно мало). Я думаю, что дал ответы на вопросы из первого абзаца.
По поводу второго абзаца и недостаточности призязки к конкретной аксиоматике я уже сказал в начале.
Теорема Гёделя предполагает наличие лишь чисто логических аксиом. В этом смысле она (или, точнее, ИП) служит как бы ядром математики. Дополнительные аксиомы можно выбирать в самом деле любые. Это могут быть аксиомы Евклида или аксиомы Кантора (грубо говоря). Но, рассуждая, мы всегда принимаем эти аксиомы "как бы за истину", т.е. просто разрешаем ими свободно пользоваться, безотносительно их смысла. Поэтому наше рассуждение всегда можно считать чисто логическим - это основа аксиоматического подхода. Набор логических средств, достаточных для вывода всех тавтологий, может быть разным. Но указание на то, что конкретный набор средств полон - это содержательная и важная теорема логики. (Равно как и информация, что тот или иной набор элементов порождает группу, а другой - не порождает.) Скажем, у Гёделя можно избежать такой вещи как "разбор случаев". Этот приём применяется очень часто, но можно обойтись и без него.
Кстати, система аксиом и правил вывода там довольно проста. Я бы мог привести все 5 аксиом и 2 правила вывода, чтобы Вы смогли наглядно всё увидеть. (Замечу, что до того, как эти вещи выписаны, само утверждение теоремы ещё не имеет смысла.)
По поводу последнего Вашего абзаца я должен очень сильно возразить. Если мы находимся внутри математики, то в существовании натурального ряда никто не сомневается. Если же мы обсуждаем вопрос на уровне foundations of mathematics, то возможны совсем разные подходы к вопросам такого (будто бы реального) феномена как натуральный ряд. В этом случае уместно сомневаться в существовании "очень больших чисел". В разное время этот вопрос затрагивали совсем разные математики: Пуанкаре, А.С.Есенин-Вольпин, П.К.Рашевский, Вопенка и другие. В частности, есть книга Вопенки "Математика в альтернативной теории множеств" (в русском переводе с чешского), где вся математика строится, исходя из понятия конечного. Принцип индукции при этом отрицается, так как, исходя из здравого смысла, "не до любого числа можно досчитать". Эффект бесконечности просто имитируется через "очень большие числа" (которые никогда никто не видел, равно как и бесконечные множества). При этом получается красивая и строгая альтернативная теория, чем-то напоминающая по содержанию нестандартный анализ.
Спасибо! Сейчас уже гораздо понятнее. Но про тавтологии ещё не до конца понятно. Сейчас Вы пишете, что: Истинное всегда = истинное в ЛЮБОЙ интерпретации (т.е. таких формул в каком-то смысле довольно мало). А в самом первом сообщении этой ветки Вы писали: любой даже самый глубокий результат (если речь идёт о доказательстве) можно рассматривать как замаскированную тавтологию. Если мы, используя аксиомы A_1, ..., A_m, вывели утверждение B,
то этим мы доказали ТАВТОЛОГИЮ A_1 & ... & A_m => B.И ещё: Однако, часто надо "доказать" (здесь "доказательство" и формальный вывод не тождественны), что та или иная формула НЕ ЯВЛЯЕТСЯ ТАВТОЛОГИЕЙ. Вот здесь творческое усилие является решающим.Не могли бы Вы дать пример какого-либо истинного утверждения в общепринятой математике, которое 1) не было бы тавтологией; 2) было бы тавтологией, но не совсем уж тривиальной? чтобы можно было бы прочувствовать разницу.
Мне кажется, мы близки к прояснению обсуждаемого предмета.
"Мало" и "много" - вещи относительные. Я привёл пример формулы, истинной для комплексных чисел и там же заметил, что при "левых" интерпретациях формула неверна. Попорбуйте выписать случайную формулу - Вы легко найдёте её интерпретацию, в которой она неверна.
Тавтологии встречаются столь же часто, как и содержательные математические результаты. Если A_1, ..., A_m - аксиомы геометрии, а B - формулировка теоремы Пифагора, то импликация "A_1 & ... & A_m влечёт B" - пример неочевидной тавтологии. Можно взять любую другую систему аксиом и любую теорему. Но содержательные результаты редки среди случайного набора знаков, и именно поэтому я сказал, что их "мало".
Пример "истинного" утверждения, не являющегося тавтологией, привести не так легко. Дело в том, что опять возникает зазор между формальным и содержательным понятием математики. То есть если я являюсь чистым формалистом, то я признаю только формальные выводы из произвольной системы аксиом и оцениваю их значимость по степени нетривиальности самого вывода. Такой взгляд, как я уже говорил, возможен. Но печальный факт состоит в том, что многие знаменитые математики за этими пределами не хотят ничего признавать. Скажем, я много полемизировал в своё время по этому поводу с А.А.Разборовым - математиком общепризнанным, но вряд ли понимавшим (IMHO) в процессе наших дискуссий саму постановку вопросов в области foundtations. К тому же по своему гуманитарно-философскому уровню он вряд ли перешагнул уровень Бертрана Рассела, Айзека Азимова или Стругацких. У меня последнее особенно вызывает почти что плач - такой мощнейший интеллект и, извините, какие-то никудышные "стругацкие".
Возвращаясь от лирического отступления к примеру. Итак, предположим, что мы формалистами не являемся, а взираем на вещи содержательно. В таком случае факт существования бесконечного множества, как бы его ни понимать, является для нас несомненно "истинным", но его по самой своей сути нельзя понимать как наличие какого-то "вывода". В самом лучшем случае мы просто сошлёмся на аксиому бесконечности теории ZF, предъявив вывод из одной формулы, являющейся аксиомой (каковую мы сами только что приняли из-за её "очевидности").
Возможны более содержательные примеры. Общеизвестной является теорема Париса - Харрингтона о математической неполноте формальной арифметики. Т.е. можно в ZF заменить аксиому бесконечности на её отрицание, и мы получим теорию конечных множеств (фактически, комбинаторику). В её рамках невозможно доказать (в этом состоит сама теорема) некий не такой уж сложный факт в духе теории Рамсея. Но он легко доказуем при помощи леммы Кёнига, использующей понятие бесконечного, но ничуть не менее убедительной, чем сама финитно-комбинаторная система. В этом смысле можно считать теорему "истинной" (с позиции естествоиспытателя). Другой пример - доказательство Герхарда Генцена (ученик Гильберта; погиб на войне) о непротиворечивости классической формальной арифметики при помощи индукции до ординала $\epsilon_0$ - ничуть не менее "конструктивной", чем обычная индукция до ординала "омега".
Пример тавтологии, не являющейся совсем тривиальной, я могу только повторить. Это любое утверждение, доказываемое содержательно как вывод из определённой аксиоматики, если в посылке взять конъюнкцию используемых аксиом, а в заключении - выводимое утверждение.
Всё теперь понятно, большое спасибо! Возвращаясь к исходному вопросу об эквивалентности истинных утверждений, становится понятно, что логическая эквивалентность не есть полная тождественность смыслов и несомой информации. В частности, сам вывод данной тавтологии представляет интерес как объект метаматематики или логики. И интересно получить наиболее короткие цепочки, как предлагал это делать ![[info]](http://lj.rossia.org/img/userinfo-lj.gif) svintusoid@lj. В этом и состоит разница между тривиальными и нетривиальными высказываниями. Спасибо за то, что помогли мне с этим разобраться!
Т.е. можно в ZF заменить аксиому бесконечности на её отрицание, и мы получим теорию конечных множеств (фактически, комбинаторику). В её рамках невозможно доказать (в этом состоит сама теорема) некий не такой уж сложный факт в духе теории Рамсея. Но он легко доказуем при помощи леммы Кёнига, использующей понятие бесконечного, но ничуть не менее убедительной, чем сама финитно-комбинаторная система. В этом смысле можно считать теорему "истинной" (с позиции естествоиспытателя).
Вот мне не очень понятно, почему эту еорему можно считать подтверждением "существования" бесконечного множества. Почему бы ей не свидетельствовать о том, что на самом деле неполно представление о конечном, что люди проглядели некоторые фундаментальные свойства конечных множеств?
Я как раз выступаю за то, чтобы рассматривать всевозможные допустимые подходы, а не ограничиваться "классикой". В конце концов, "классика" тоже была когда-то и кем-то придумана. Поэтому никому не запрещается развивать альтернативные подходы.
Косвенное свидетельство о "существовании" бесконечного множества имеет силу только в пределах некоторой уже принятой концепции. Оно ни в коей мере не является абсолютным. Более того, саму теорию множеств, которые мы называем "конечными", совсем не обязательно строить так, как это принято. Я выше уже приводил пример Вопенки, который всю математику построил на базе "конечного" в понимании, отличающемся от классического. В этом смысле я согласен с тем, что на вещи можно смотреть и так, как сказано в Вашей последней фразе.
В журнале юзера sowa есть довольно давний пост о теореме Лёвенгейма - Сколема. Его не так трудно найти, отмотав назад записей 20. В конце там у нас развернулась с Совой довольно интересная дискуссия вокруг близких вопросов. Загляните, если интересно. Дискуссию я хотел бы продолжить, но пока не могу выкроить достаточно времени, чтобы как-то упорядочить обсуждаемые темы и высказаться более развёрнуто.
![[User Picture Icon]](http://lj.rossia.org/userpic/31709/2147485505) |
|
|
|
некоторый оффтопик :)
|
(Link) |
|
Такой вопрос(может простой совсем):
Вот пусть у нас есть вложения:
A\subseteq B \subseteq k[x_1,...,x_l]
k-- некоторое поле, A, B -- под k-алгебры,
b_1,..,b_l -- мономы из B
Что можно тогда сказать об алгоритмической разрешимости следующей проблемы:
Существуют такие a_1,...,a_l из A, что:
\sum_{i=1}^la_i*b_i=0, при этом никакая подсумма нулю не равна.
![[User Picture Icon]](http://lj.rossia.org/userpic/4033/2147484947) |
| From: | ![[info]](http://lj.rossia.org/img/imported-profile.gif) falcao@lj |
|---|
| Date: |
August 4th, 2006 - 11:57 am |
|---|
|
|
уточнения
|
(Link) |
|
Поскольку речь об алгоритмической проблеме, надо уточнить, в каком виде задаётся k-подалгебра A. То есть, можно ли, скажем, считать, что она задана конечным набором порождающих? Существенно ли, что это именно подалгебра, а не просто k-подпространство (такой вопрос тоже имел бы смысл)?
Подалгебра B здесь вроде как лишняя -- если задана A и даны мономы, то в качестве B можно взять всю алгебру многочленов.
Ограничение на поле вряд ли очень важно, но формально это тоже надо оговорить, так как по умолчанию мы работаем с "финитными" объектами.
Я кажется немного наврал с формулировкой:
A,B-- конечно порождены. В B-- фиксирована конечная система образующих.
b_1,...,b_l-- мономы в B, относительно этой системы образующих B.
Поле $k$-- из какого-нибудь класса включающего алгебраически замкнутые характеристики 0.
B, кажется не лишняя, например-- для элементов каких-то подалгебр задача может быть разрешима, а для других нет?..
т.е. существенен ответ на вопрос типа "Алгоритмически разрешима ли проблема для любого набора мономов из B в заданной системе образующих"
Наконец, то что A-- подалгебра-- существенно. Все подалгебры предполагаются содержащими 1.
1 -- считается B-мономом
Так, кажется последнее: фиксирована система образующих B, как A-алгебры.
|
|
![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small}