 Концептуальное математическое искусство. | Oct. 14th, 2005 @ 11:14 pm  |
|---|
Вот via ![[info]](http://lj.rossia.org/img/userinfo-lj.gif) archernikov@lj я нашел следующую, довольно интересную, на мой взгляд статью:
"Commutative Diagrams in the Fine Arts", Karl Heinrich Hofmann.
В связи с этим вспомнилась мне такая моя довольно давняя мысль:
нужно взять какое-нибудь совершенно тривиальное математическое утверждение(тривиальное вплоть до потери смысла) и создать некий набор красивых и заведомо более сложных, чем само утверждение доказательств. Создать из всего этого художественную выставку. В которой тексты доказательств будут экспонатами.
Еще один, еще более чистый вариант-- заменить обычные математические доказательства при этом формальными выводами, эстетическим критерием при этом должна являться также и красота собственно графическая.Current Mood: busy Current Music: Black Lung Theme From the Black Lung pt 1 |
Это интересно, только почему доказательства должны быть слишком сложные, красота может быть и в простоте. Так, например, существует же не менее 100 доказательств теоремы Пифагора. Наверное есть книжка, но хотелось бы сходить на выставку, где это было бы красиво оформлено. 
Сложные по сравнению с утверждением. Тривиальным до бессмысленности. А сами по сбе должны умещаться на страницу, чтобы можно было повесить на стену.
Цель -- отделить эстетику математики от ее содержания.
Интересно узнать какое-нибудь тривиальное утверждение и план его сложного доказательства.
В математике все истинные утверждения логически эквивалентны друг другу. В этом смысле Великая Теорема Ферма эквивалентна утверждению 0=0.
| From: | (Anonymous) |
|---|
| Date: |
October 16th, 2005 - 04:22 am |
|---|
|
|
|
|
(Link) |
|
Истина, она и на Туме истина. Только то, что 0=0 это скорее определение.
Ну, мне кажется, провокации основанные на смешении выводимости(и ее сложности) и логической эквивалентности непродуктивны. Просто имеет смысл заметить, что второе тривиально и не особенно осмысленно.
Это не столько провокация, сколько моё искреннее изумление. Я до сих пор толком не понимаю, почему столь глубокие результаты оказываются эквивалентны тавтологиям.
Ну, мне опять же, кажется, что дело в неправильном определении отношения эквивалентности на математических результатах.
Если пофантазировать на эту тему то, первое, что приходит в голову следующее: можно, например, брать верное утверждение A и верное утверждение B. Рассматривать "наибольшее ослабление", скажем, NGB+A в котором B выводимо и рассматривать минимальную длину формального вывода. Такая вот, например, мера равносильности.
Верные в NGB(или к-л ее расширении), то есть
![[User Picture Icon]](http://lj.rossia.org/userpic/31709/2147485505) |
|
|
|
Продолжаем фантазировать(я, правда, не специалист в ло
|
(Link) |
|
О смысле "максимального ослабления":
Возьмем множество утверждений истинных в NGB+A и будем рассматривать его подмножества содержащие A и B такие, что существует некоторая конечная система аксиом порождающая данное подмножество не содержащая B. Будем рассматривать такие системы аксиом минимальной длины и выберем такую, что длина минимального вывода B в ней будет максимальна. Будем тогда называть эту длину расстоянием от утверждения A до утверждения B.
Поскольку нас интересует эквивалентность разумно выбрать максимум из 2 возникающих расстояний.
Получающееся отношение симметрично, расстояние от утверждения до него самого можно положить равным нулю, неравенство треугольника, кажется тоже имеется( типа доказываем из A B, а потом C, правда тут есть очевидный пробел, так что неясно, конечно).
Ура! :-) Получили метрику на множестве верных в NGB(ну или вообще в некоторой конечной системе аксиом) утверждений. :)
![[User Picture Icon]](http://lj.rossia.org/userpic/3556/2147484333) |
| From: | ![[info]](http://lj.rossia.org/img/imported-profile.gif) ignat@lj |
|---|
| Date: |
October 16th, 2005 - 07:22 am |
|---|
|
|
Re: Продолжаем фантазировать(я, правда, не специалист в
|
(Link) |
|
Возьмем множество утверждений истинных в NGB+A и будем рассматривать его подмножества содержащие A и B такие, что существует некоторая конечная система аксиом порождающая данное подмножество не содержащая B.
Конечных может и не быть. Насколько я понимаю, аксиома индукции сама по себе представляет собой бесконечное число аксиом. Хотя, возможно, я и не прав.
|
|
|
|
Re: Продолжаем фантазировать(я, правда, не специалист в
|
(Link) |
|
Ну мы ограничиваемся только конечными. Это условие на подмножество. NGB, вроде бы, сама по себе конечна. Я так помню. И Вики, вроде, подтверждает. :))
|
|
|
|
Re: Продолжаем фантазировать(я, правда, не специалист в
|
(Link) |
|
Да, именно так, собственно затем ее и построили.
![[User Picture Icon]](http://lj.rossia.org/userpic/4033/2147484947) |
| From: | falcao@lj |
|---|
| Date: |
October 22nd, 2005 - 09:35 pm |
|---|
|
|
Re: Продолжаем фантазировать(я, правда, не специалист в
|
(Link) |
|
При построении NGB ухитрились построить конечную аксиоматику для теории множеств, где само число аксиом конечно (в отличие от ZF, где конечно лишь число схем аксиом).
В рамках NGB легко определяются натуральные числа (по фон Нейману), а принцип индукции для них следует как теорема (для любого предиката).
см. рассуждения Канта про
априорные суждения vs. априорные синтетические суждения.
ну я просто имел в виду самые известные мысли Канта про то, как же возможно истинное знание.
Типа, по Канту, закон всемирного тяготения к истинному знанию не принадлежит, поскольку он может завтра прекратить работать, кто его знает.. а знания типа 1=1 достоверно (в его терминах, "априорно") но не интересно. А бывают ли и априорные, и интересные суждения? да, говорит Кант, например, что сумма углов треугольника 180 градусов. Это и априорное, и синтетическое (то есть, не банальное, интересное) суждение.
Мне кажется, в такой форме мысль несколько устарела, но эту же идею хорошо проиллюстрировал Пуанкаре в одной из своих ранних статей (она есть в начале сборника "О науке"). По сути дела, речь там идёт об индукции.
Я пока не вник до конца в суть дискуссии, поэтому могу сказать что-то не совсем в тему. Однако ясно, что любой даже самый глубокий результат (если речь идёт о доказательстве) можно рассматривать как замаскированную тавтологию. Если мы, используя аксиомы A_1, ..., A_m, вывели утверждение B,
то этим мы доказали ТАВТОЛОГИЮ A_1 & ... & A_m => B.
Творческая сущность математики проявляется совсем в другой сфере. Я пока
высказываю это как тезис, но при необходимости могу развернуть.
Добрый день!
Да, я вроде понимаю хорошо, в чём творческая сущность математики проявляется. Однако, я никак не мог смириться с мыслью о том, что даже самые глубокие результаты эквивалентны банальной бессмыслице.
Рад Вас слышать, Игнат!
Мой тезис сводился к тому, что тавтологии as they are нельзя приравнивать к тривиальностям. Само утверждение, что тавтологии суть нечто тривиальное, неверно. Это касается только очень простых тавтологий вроде "A влечёт A", но не тавтологий вообще. Любое доказательное утверждение можно приравнять к выводу той или иной тавтологии в чистом исчислении предикатов. Сам поиск доказательства (доказательства именно тавтологии) является уже вещью творческой. Это один аспект.
Второй аспект ещё важнее. Если я хочу что-то доказать, т.е. показать, что та или иная формула ИП (исчисления предикатов) есть тавтология, то я могу просто предъявить сам вывод, который обязан существовать по теореме Гёделя о полноте (которая не менее важна по своей философской сути, нежели теорема о неполноте). Однако, часто надо "доказать" (здесь "доказательство" и формальный вывод не тождественны), что та или иная формула НЕ ЯВЛЯЕТСЯ ТАВТОЛОГИЕЙ. Вот здесь творческое усилие является решающим.
В самом деле, возьмём какое-либо утверждение, которое справедливо для всех конечных моделей. Простейший пример - наличие минимального элемента в частично-упорядоченном множестве. Мы просто ПРЕДСТАВЛЯЕМ СЕБЕ бесконечное множество, и на этом основании заключаем, что некая формула тавтологией не является. Список здесь можно продолжить, и потому чем больше имеется у нас полезных и правдоподобных мифологем (термин Ю.И.Манина), тем больше возникает ситуаций, когда про ту или иную формулу мы можем утверждать, что она тавтологией не будет. Здесь нет формальных ограничений; мы здесь на берегу океана творчества.
Было бы интересно знать Выше мнение насчёт высказанного выше. Я сейчас чуть-чуть спешу из-за срочных дел, но уже с завтрашнего дня буду так или иначе свободен для дискуссий. В любом случае, я всегда готов повторить, что я очень люблю решать математические задачи (сам процесс интересен), а сама математика как таковая мне интересна постольку-поскольку. А вот основания математики интересны в полной мере. Ну, филология тоже, конечно.
Спасибо! Очень интересные мысли.
У меня, к сожалению, выдалась напряжённая неделя, и я не мог сконцентрироваться в эти дни.
Мне, по-видимому, сперва следует ликвидировать собственную безграмотность по следующим вопросам:
- что такое теорема Гёделя о полноте? Что она нам говорит и даёт?
- что такое собственно тавтология? И чем она отличается от эквивалентности двух утверждений.
Где посоветуете подчитать? Или, может, поясните тут?
Пояснить это очень просто. Тавтологией, по определению, называется тождественно истинное высказывание ИП (т.е. его можно записать при помощи логических связок и кванторов). Оно должно быть истинно в любой интерпретации. Как я уже говорил, любое содержательное доказательство можно конвертировать в вывод некотрой тавтологии.
Теорема Гёделя о полноте исчисления предикатов утверждает, что любая тавтология выводима из ряда очень простых логических аксиом при помощи двух правил вывода. Каждая из аксиом есть один из часто используемых в рассуждениях приёмов (наподобие доказательства "от противного" или перехода от общего суждения к частному), а правила вывода - это всем известный modus ponens (который по сути есть содержательное истолкование импликации) и правило Gen, которое позволяет навешивать квантор всеобщности (т.е. оно есть содержательное истолкование квантора всеобщности).
В деталях это описание есть во многих учебниках, но я предпочитаю известный курс Мендельсона. Там уже используется вполне современный язык, хотя книга старая.
Значение теоремы о полноте в том, что любое доказательство может быть интерпретировано как построение чисто логического вывода в ИП. В этом смысле математика как бы сводится к логике. Другое дело, что проблема тавтологичности высказываний алгоритмически неразрешима (результат А.Чёрча, 1936 г.).
На эту тему вообще-то есть что ещё сказать.
А какая разница между "тождественно истинными" высказываниями и просто "истинными" высказываниями?
Непонятно, почему теорема Гёделя о полноте называется теоремой. Разве тавтология, по определению, не есть то, что выводимо? Или здесь сужается арсенал правил логического вывода до двух?
Если результат истинный, но не выводимый, то как мы узнали, что он истинный? Не правильнее было бы считать истинность недоказуемых утверждений неопределённой?
Истинным высказывание может быть лишь в той или иной интерпретации. Просто "истинных" утверждений не бывает, то есть я согласен с тем, что не доказанные утверждения если и следует считать истинными, то с большой натяжкой (см., правда, некотрое "возражение" в конце).
Тавтология есть то, что истинно всегда. Теорема Гёделя предполагает чисто семантическое определение тавтологичности через понятие истины (в заданной интерпретации) и доказывает, что оно эквивалентно синтаксическому. В этом значение теоремы - она показывает, что нечто весьма туманное, связанное с "истинностью", имеет вполне определённый формальный смысл.
Мы не можем определить тавтологию как нечто выводимое, так как неясно, из чего выводить. Если расследовать эту ситуацию, то речь должна идти о выводе из общелогических аксиом. Гёдель это и делает. Число правил вывода является условностью. Их могло быть не два, а семь. Важно, чтобы эти правила обладали свойством полноты. Если уже два годятся, то бОльшего и не надо.
На всякий случай я хотел бы сформулировать ещё раз. Смысл теормы Гёделя о полноте состоит в том, что данных конкретных пяти простых аксиом и двух правил вывода достаточно, чтобы вывести всё "глобально выводимое". Представьте себе, что какую-то из аксиом не учли. Тогда это будет уже не так.
Зазор между истиной и доказуемостью можно понять на примере, который я уже приводил. Если взять утверждение A о существовании максимального элемента в любом частично-упорядоченном множестве, то достаточно представить себе натуральный ряд для того, чтобы понять, что в этой интерпретации истинно отрицание A. Здесь истинность мы понимаем как непосредственное наблюдение, а не вывод. Если мы не верим в существование бесконечности, то для нас A должно быть истинным всегда. В этом случае должен иметься его вывод из общелогических аксиом. Коль скоро никто такого вывода предъявить не может, это косвенно свидетельствует о том, что бесконечные множества-таки имеются :)
Спасибо Вам за развёрнутый ответ!
Но я по-прежнему не понимаю разницу между понятиями:
- истинный
- истинный всегда
- истинный в интерпретации
да и понятие "интерпретация" само по себе.
В моём, возможно, неправильном, представлении, мы имеем изначально систему аксиом некоторой теории, скажем, теории множеств Цермело-Френкеля. И правила логического вывода. Далее, мы можем попытаться раскрасить все утверждения нашей теории в два цвета: "истина" и "ложь" в зависимости от того, выводимо ли данное утверждение из аксиом с помощью данных правил вывода. Если выводимо, то пишем "истина", если выводимо его отрицание, то пишем "ложь". Некоторые утверждения мы не сможем раскрасить, как бы мы не старались (теорема Гёделя о неполноте).
При таком подходе совершенно непонятно, зачем нужна теорема Гёделя о полноте. Ведь она попросту повторяет определение истинности. Что такое "глобально выводима"? Мы можем задаться вопросом о том, что же выводимо из любого подмножества аксиом, пусть не из пяти, а из четырёх аксиом. Это тоже будет математикой.
Последний абзац я не понял вообще. Что значит, "в этой интерпретации", "не верим в существование"? Натуральный ряд существует ввиду существования пустого множества и вполне конструктивной процедуры его порождения. Это строгие рассуждения, не зависящие ни от каких "интерпретаций" (кстати, что это такое?).
Трудность состоит в том, что мы всё время перескакиваем с одного уровня понимания вещей на другой, причём это специально не оговаривается. Скажем, если мы занимаем чисто формальную позицию, то "истина" не имеет смысла вообще. При этом выводимые утверждения будут приравниваться к истинным, а те, у которых выводимо отрицание - к ложным. Такой подход возможен, но он не вынужден, т.е., признавая его актуальность, можно пытаться выходить и за пределы. Причину необходимости выхода за пределы объяснить легко. Выводимость подразумевается из данного множества аксиом типа теории множеств. Когда-то теории множеств не было. Завтра я или Вы можем предложить новую удовлетворяющую всех аксиоматику. При этом "пределы видимости" будут всё время меняться. Это говорит об условности данного подхода, так как он привязан к текущей (пусть даже общепринятой) конъюнктуре.
О понятиях. Формула - это правильно составленный набор знаков, т.е. объект чисто семантический. Интерпретация - это непустое множество + конкретное сопоставление а) предметным константам формулы некоторых элементов множества, б) функциональным символам формулы - операций на этом множестве, в) предикатным символам формулы - отношений на множестве. Если я возьму формулу \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$ - ничуть не менее "конструктивной", чем обычная индукция до ординала "омега".
Пример тавтологии, не являющейся совсем тривиальной, я могу только повторить. Это любое утверждение, доказываемое содержательно как вывод из определённой аксиоматики, если в посылке взять конъюнкцию используемых аксиом, а в заключении - выводимое утверждение.
Всё теперь понятно, большое спасибо! Возвращаясь к исходному вопросу об эквивалентности истинных утверждений, становится понятно, что логическая эквивалентность не есть полная тождественность смыслов и несомой информации. В частности, сам вывод данной тавтологии представляет интерес как объект метаматематики или логики. И интересно получить наиболее короткие цепочки, как предлагал это делать svintusoid@lj. В этом и состоит разница между тривиальными и нетривиальными высказываниями. Спасибо за то, что помогли мне с этим разобраться!
Т.е. можно в ZF заменить аксиому бесконечности на её отрицание, и мы получим теорию конечных множеств (фактически, комбинаторику). В её рамках невозможно доказать (в этом состоит сама теорема) некий не такой уж сложный факт в духе теории Рамсея. Но он легко доказуем при помощи леммы Кёнига, использующей понятие бесконечного, но ничуть не менее убедительной, чем сама финитно-комбинаторная система. В этом смысле можно считать теорему "истинной" (с позиции естествоиспытателя).
Вот мне не очень понятно, почему эту еорему можно считать подтверждением "существования" бесконечного множества. Почему бы ей не свидетельствовать о том, что на самом деле неполно представление о конечном, что люди проглядели некоторые фундаментальные свойства конечных множеств?
Я как раз выступаю за то, чтобы рассматривать всевозможные допустимые подходы, а не ограничиваться "классикой". В конце концов, "классика" тоже была когда-то и кем-то придумана. Поэтому никому не запрещается развивать альтернативные подходы.
Косвенное свидетельство о "существовании" бесконечного множества имеет силу только в пределах некоторой уже принятой концепции. Оно ни в коей мере не является абсолютным. Более того, саму теорию множеств, которые мы называем "конечными", совсем не обязательно строить так, как это принято. Я выше уже приводил пример Вопенки, который всю математику построил на базе "конечного" в понимании, отличающемся от классического. В этом смысле я согласен с тем, что на вещи можно смотреть и так, как сказано в Вашей последней фразе.
В журнале юзера sowa есть довольно давний пост о теореме Лёвенгейма - Сколема. Его не так трудно найти, отмотав назад записей 20. В конце там у нас развернулась с Совой довольно интересная дискуссия вокруг близких вопросов. Загляните, если интересно. Дискуссию я хотел бы продолжить, но пока не могу выкроить достаточно времени, чтобы как-то упорядочить обсуждаемые темы и высказаться более развёрнуто.
|
|
|
|
некоторый оффтопик :)
|
(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, при этом никакая подсумма нулю не равна.
|
| From: | 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-алгебры.
|
| From: | falcao@lj |
|---|
| Date: |
August 5th, 2006 - 08:45 am |
|---|
|
|
формулировка
|
(Link) |
|
Я всё ещё не до конца понимаю условие. Во-первых, первоначально я воспринял информацию, что b_i -- мономы как то, что они являются произведениями переменных. Если так, то алгебра B не нужна. Но Вы, как я понимаю, имеете в виду "B-мономы", то есть произведения заданных порождающих алгебры B. Попробую сформулировать теперь то, что у меня вырисовывается, а Вы скажите, верно ли я понимаю.
Есть ещё такой момент. Поскольку каждая из алгебр A, B как-то по-своему задана, то встаёт вопрос, откуда мы знаем, что A содержится в B. Это обстоятельство надо либо проверять (что является отдельной проблемой), либо игнорировать (считая, что алгоритм должен работать правильно только при этом условии), либо задать алгебры так, чтобы включение имело место. Один из способов -- это считать, что система порождающих для B содержит систему порождающих для A. Второе толкование см. ниже.
Дано "хорошее" поле k (это можно при необходимости уточнить; скажем, можно взять поле алгебраических чисел над Q). Пусть U -- алгебра всех полиномов над k. Дан конечный набор P_1,...,P_s элементов из U, порождающих k-подалгебру B. Дан конечный набор F_1,...,F_t элементов из B, порождающий k-подалгебру A в B. То есть каждый элемент этого набора задан как полином от P_1,...,P_s. Кроме того, задана конечная система "B-мономов" b_1,...,b_r, т.е. элементов полугруппы с единицей, порождённой P_1,...,P_s. Далее спрашивается, можно ли найти a_1,...,a_r из A такие, что \sum_{i=1}^ra_i*b_i=0, и этом никакая подсумма нулю не равна.
Это то, что Вы имели в виду?
Можно считать, что система образующих A содержится в системе образующих B.
Т.е. дано "хорошее" поле k. U-- алгебра всех полиномов над k. Дан конечный наборы элементов
Q_1,..,Q_l -- порождающих k-подалгебру A; Q_1,...,Q_l,P_1,..,P_s -- порождающих k-подалгебру B(т.е. система образующих содержится в системе образующих B).
Кроме того, задана конечная система "B-мономов" b_1,..,b_r, т.е. элементов полугруппы с единицей, порожденной P_1,..,P_s(т.е. можно предполагать, кроме того, что если, для некоторого i, b_i принадлежит A, то b_i=1).
Далее спрашивается, каким условиям должны удовлетворять заданные указанным выше образом, подалгебры A и B, чтобы для любой системы "B-мономов" описанного выше вида была алгоритмически разрешима следующая задача:
Существуют ли такие a_1,..,a_r из A такие, что \sum_{i=1}^r a_i*b_i=0 и при этом никакая подсумма нулю не равна.
Т.е. нужна алгоритмическая разрешимость задачи о существовании таких a_i, задача о алгоритмической разрешимости задачи о поиске конкретных a_i удовлетворяющих этим условиям не стоит.
|
|
![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small}