Неизменно промахиваясь - Концептуальное математическое искусство.

From: ignat@lj Date: October 23rd, 2005 - 12:23 am (Link)

Спасибо! Сейчас уже гораздо понятнее.

Но про тавтологии ещё не до конца понятно. Сейчас Вы пишете, что:
Истинное всегда = истинное в ЛЮБОЙ интерпретации (т.е. таких формул в каком-то смысле довольно мало).

А в самом первом сообщении этой ветки Вы писали:
любой даже самый глубокий результат (если речь идёт о доказательстве) можно рассматривать как замаскированную тавтологию. Если мы, используя аксиомы A_1, ..., A_m, вывели утверждение B,
то этим мы доказали ТАВТОЛОГИЮ A_1 & ... & A_m => B.

И ещё:
Однако, часто надо "доказать" (здесь "доказательство" и формальный вывод не тождественны), что та или иная формула НЕ ЯВЛЯЕТСЯ ТАВТОЛОГИЕЙ. Вот здесь творческое усилие является решающим.

Не могли бы Вы дать пример какого-либо истинного утверждения в общепринятой математике, которое
1) не было бы тавтологией;
2) было бы тавтологией, но не совсем уж тривиальной?
чтобы можно было бы прочувствовать разницу.

(Reply to this) (Parent) (Thread)

From: falcao@lj Date: October 23rd, 2005 - 02:29 am (Link)

Мне кажется, мы близки к прояснению обсуждаемого предмета.

"Мало" и "много" - вещи относительные. Я привёл пример формулы, истинной для комплексных чисел и там же заметил, что при "левых" интерпретациях формула неверна. Попорбуйте выписать случайную формулу - Вы легко найдёте её интерпретацию, в которой она неверна.

Тавтологии встречаются столь же часто, как и содержательные математические результаты. Если A_1, ..., A_m - аксиомы геометрии, а B - формулировка теоремы Пифагора, то импликация "A_1 & ... & A_m влечёт B" - пример неочевидной тавтологии. Можно взять любую другую систему аксиом и любую теорему. Но содержательные результаты редки среди случайного набора знаков, и именно поэтому я сказал, что их "мало".

Пример "истинного" утверждения, не являющегося тавтологией, привести не так легко. Дело в том, что опять возникает зазор между формальным и содержательным понятием математики. То есть если я являюсь чистым формалистом, то я признаю только формальные выводы из произвольной системы аксиом и оцениваю их значимость по степени нетривиальности самого вывода. Такой взгляд, как я уже говорил, возможен. Но печальный факт состоит в том, что многие знаменитые математики за этими пределами не хотят ничего признавать. Скажем, я много полемизировал в своё время по этому поводу с А.А.Разборовым - математиком общепризнанным, но вряд ли понимавшим (IMHO) в процессе наших дискуссий саму постановку вопросов в области foundtations. К тому же по своему гуманитарно-философскому уровню он вряд ли перешагнул уровень Бертрана Рассела, Айзека Азимова или Стругацких. У меня последнее особенно вызывает почти что плач - такой мощнейший интеллект и, извините, какие-то никудышные "стругацкие".

Возвращаясь от лирического отступления к примеру. Итак, предположим, что мы формалистами не являемся, а взираем на вещи содержательно. В таком случае факт существования бесконечного множества, как бы его ни понимать, является для нас несомненно "истинным", но его по самой своей сути нельзя понимать как наличие какого-то "вывода". В самом лучшем случае мы просто сошлёмся на аксиому бесконечности теории ZF, предъявив вывод из одной формулы, являющейся аксиомой (каковую мы сами только что приняли из-за её "очевидности").

Возможны более содержательные примеры. Общеизвестной является теорема Париса - Харрингтона о математической неполноте формальной арифметики. Т.е. можно в ZF заменить аксиому бесконечности на её отрицание, и мы получим теорию конечных множеств (фактически, комбинаторику). В её рамках невозможно доказать (в этом состоит сама теорема) некий не такой уж сложный факт в духе теории Рамсея. Но он легко доказуем при помощи леммы Кёнига, использующей понятие бесконечного, но ничуть не менее убедительной, чем сама финитно-комбинаторная система. В этом смысле можно считать теорему "истинной" (с позиции естествоиспытателя). Другой пример - доказательство Герхарда Генцена (ученик Гильберта; погиб на войне) о непротиворечивости классической формальной арифметики при помощи индукции до ординала $\epsilon_0$ - ничуть не менее "конструктивной", чем обычная индукция до ординала "омега".

Пример тавтологии, не являющейся совсем тривиальной, я могу только повторить. Это любое утверждение, доказываемое содержательно как вывод из определённой аксиоматики, если в посылке взять конъюнкцию используемых аксиом, а в заключении - выводимое утверждение.

(Reply to this) (Parent) (Thread)

From: ignat@lj Date: October 23rd, 2005 - 10:23 am (Link)

Всё теперь понятно, большое спасибо!

Возвращаясь к исходному вопросу об эквивалентности истинных утверждений, становится понятно, что логическая эквивалентность не есть полная тождественность смыслов и несомой информации. В частности, сам вывод данной тавтологии представляет интерес как объект метаматематики или логики. И интересно получить наиболее короткие цепочки, как предлагал это делать svintusoid@lj. В этом и состоит разница между тривиальными и нетривиальными высказываниями.

Спасибо за то, что помогли мне с этим разобраться!

(Reply to this) (Parent)

From: svintusoid@lj Date: November 3rd, 2005 - 10:17 pm (Link)

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

Вот мне не очень понятно, почему эту еорему можно считать подтверждением "существования" бесконечного множества. Почему бы ей не свидетельствовать о том, что на самом деле неполно представление о конечном, что люди проглядели некоторые фундаментальные свойства конечных множеств?

(Reply to this) (Parent) (Thread)

From: falcao@lj Date: November 4th, 2005 - 05:18 am (Link)

Я как раз выступаю за то, чтобы рассматривать всевозможные допустимые подходы, а не ограничиваться "классикой". В конце концов, "классика" тоже была когда-то и кем-то придумана. Поэтому никому не запрещается развивать альтернативные подходы.

Косвенное свидетельство о "существовании" бесконечного множества имеет силу только в пределах некоторой уже принятой концепции. Оно ни в коей мере не является абсолютным. Более того, саму теорию множеств, которые мы называем "конечными", совсем не обязательно строить так, как это принято. Я выше уже приводил пример Вопенки, который всю математику построил на базе "конечного" в понимании, отличающемся от классического. В этом смысле я согласен с тем, что на вещи можно смотреть и так, как сказано в Вашей последней фразе.

В журнале юзера sowa есть довольно давний пост о теореме Лёвенгейма - Сколема. Его не так трудно найти, отмотав назад записей 20. В конце там у нас развернулась с Совой довольно интересная дискуссия вокруг близких вопросов. Загляните, если интересно. Дискуссию я хотел бы продолжить, но пока не могу выкроить достаточно времени, чтобы как-то упорядочить обсуждаемые темы и высказаться более развёрнуто.

(Reply to this) (Parent) (Thread)

From: svintusoid@lj Date: August 4th, 2006 - 11:14 am некоторый оффтопик :) (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, при этом никакая подсумма нулю не равна.

(Reply to this) (Parent) (Thread)

From: falcao@lj Date: August 4th, 2006 - 11:57 am уточнения (Link)

Поскольку речь об алгоритмической проблеме, надо уточнить, в каком виде задаётся k-подалгебра A. То есть, можно ли, скажем, считать, что она задана конечным набором порождающих? Существенно ли, что это именно подалгебра, а не просто k-подпространство (такой вопрос тоже имел бы смысл)?

Подалгебра B здесь вроде как лишняя -- если задана A и даны мономы, то в качестве B можно взять всю алгебру многочленов.

Ограничение на поле вряд ли очень важно, но формально это тоже надо оговорить, так как по умолчанию мы работаем с "финитными" объектами.

(Reply to this) (Parent) (Thread)

From: svintusoid@lj Date: August 4th, 2006 - 12:11 pm Re: уточнения (Link)

Я кажется немного наврал с формулировкой:
A,B-- конечно порождены. В B-- фиксирована конечная система образующих.
b_1,...,b_l-- мономы в B, относительно этой системы образующих B.
Поле $k$-- из какого-нибудь класса включающего алгебраически замкнутые характеристики 0.

B, кажется не лишняя, например-- для элементов каких-то подалгебр задача может быть разрешима, а для других нет?..

(Reply to this) (Parent)

From: svintusoid@lj Date: August 4th, 2006 - 12:13 pm Re: уточнения (Link)

т.е. существенен ответ на вопрос типа "Алгоритмически разрешима ли проблема для любого набора мономов из B в заданной системе образующих"

(Reply to this) (Parent)

From: svintusoid@lj Date: August 4th, 2006 - 12:20 pm Re: уточнения (Link)

Наконец, то что A-- подалгебра-- существенно. Все подалгебры предполагаются содержащими 1.
1 -- считается B-мономом

(Reply to this) (Parent)

From: svintusoid@lj Date: August 4th, 2006 - 12:21 pm Re: уточнения (Link)

Так, кажется последнее: фиксирована система образующих B, как A-алгебры.

(Reply to this) (Parent)