04.11.2004 00:52 roll | ещё http://www.mathforum.ru/forum/read/1/1600/1600/#1600
|
04.11.2004 02:19 Дата регистрации:
7 лет назад Посты: 398 | принцип Дирихле конструктивен Если предполагается, что для каждой клетки можно узнать число содержащихся в ней кроликов, то принцип Дирихле можно доказать с помощью принципа Маркова ("ленинградского принципа"): если неверно, что p(n) неверно для всех натуральных n, то можно найти такое n, что p(n) истинно. Насколько я понимаю, этот принцип Маркова не выводится без снятия двойного отрицания, но всё же может считаться конструктивным: проверяя p(n) для последовательных натуральных n, мы когда-нибудь встретим такое n, для которого p(n) истинно. Цитата
Игорь Абрамов писал:
Что с того, что бесконечное множество это довольно сильная абстракция, мнимые числа или многомерные пространства ничем не хуже.
С большим удовольствием вижу очередной крах своих заблуждений: я думал, что именно для тех, кто профессионально разбирается и в математике, и в программировании, наиболее естественна и важна разница между неконструктивными и конструктивными абстракциями, между конечным числом операций (как в принципе Дирихле) и бесконечным числом операций (как в доказательстве теоремы Больцано-Вейерштрасса). Тут ещё был такой диалог: Цитата
Гастрит:
Объясните мне, дураку, на пальцах, что это за вещь такая - "произвольное подмножество бесконечного множества A".
Свинтус:
Как что? Это набор букв такой.
Да, фраза Гастрита - набор букв. Но сами подмножества бесконечного множества, к сожалению, не всегда можно описать в виде набора букв. Чтобы частично оправдать оффтопик, задам вопрос, связанный и с Кантором, и с конструктивизмом: можно ли как-нибудь исхитриться и применить диагональную конструкцию Кантора к последовательности всех конструктивных действительных чисел (КДЧ)? Нутром чую, что нельзя (нового КДЧ никак не получишь), но полной ясности нет.
|
04.11.2004 12:09 Игорь Абрамов | да, конечно Про Дирихле конечно так. Цитата
egor писал(а) : Цитата
Игорь Абрамов писал:
Что с того, что бесконечное множество это довольно сильная абстракция, мнимые числа или многомерные пространства ничем не хуже.
... думал, что именно для тех, кто профессионально разбирается и в математике, и в программировании, наиболее естественна и важна разница между неконструктивными и конструктивными абстракциями, между конечным числом операций (как в принципе Дирихле) и бесконечным числом операций (как в доказательстве теоремы Больцано-Вейерштрасса).
А вот еще почитайте работы по квантовым вычислениям. С одной стороны, вроде, напоминает программирование, а с другой --- функан. И актуально бесконечные множества там то и дело проскакивают. Но чисто дискретная интуиция не очень работает. (У меня, правда, нет уверенности, что у нас скоро будут реальные универсальные квантовые компьютеры и мы будем писать для них квантовые программы и флеймить в квантовых форумах :) )
|
04.11.2004 17:23 Дата регистрации:
7 лет назад Посты: 78 | И что? Цитата
Цитата
Гастрит:
Объясните мне, дураку, на пальцах, что это за вещь такая - "произвольное подмножество бесконечного множества A".
Свинтус:
Как что? Это набор букв такой.
Да, фраза Гастрита - набор букв. Но сами подмножества бесконечного множества, к сожалению, не всегда можно описать в виде набора букв.
Конкретные подмножества да не всегда можем описать, точнее почти всегда не можем- ну и что. Произольное-то подмножество описывается в виде набора букв. С уважением, Свинтус
|
04.11.2004 21:14 Бойко | Немного ясности Egor писал: Цитата
можно ли как-нибудь исхитриться и применить диагональную конструкцию Кантора к последовательности всех конструктивных действительных чисел (КДЧ)? Нутром чую, что нельзя (нового КДЧ никак не получишь), но полной ясности нет.
Очевидно, что все эти КДЧ не удастся даже в последовательность выписать (если подходить конструктивно). Потому и нельзя. С уважением, Бойко
|
04.11.2004 22:30 Дата регистрации:
7 лет назад Посты: 398 | в последовательность можно Цитата
Бойко писал:
Очевидно, что все эти КДЧ не удастся даже в последовательность выписать (если подходить конструктивно). Потому и нельзя.
Одно из определений КДЧ: КДЧ - это программа (более строго можно определить через рекурсивные функции, машины Тьюринга, алгорифмы Маркова и т. д.), которая для любого натурального n строит рациональное a_n, причём выполняется свойство: |a_n-a_m|\leq 2^{-n} при m>n. Программы, обладающие этим свойством, можно представить в виде слов, лексикографически упорядочить и пересчитать в виде последовательности: каждому натуральному числу сопоставить свою программу (=своё КДЧ). Похоже, мы уклоняемся от темы. Быть может, имеет смысл создать отдельную тему для очередного обсуждения конструктивизма.
|
05.11.2004 00:00 Дата регистрации:
7 лет назад Посты: 398 | палец без луны Цитата
Свинтус писал:
Конкретные подмножества да не всегда можем описать, точнее почти всегда не можем- ну и что. Произольное-то подмножество описывается в виде набора букв.
Возможно, Вы правы. А может, точнее будет так: с помощью букв определяется значок "быть подмножеством" и значок "множество всех подмножеств". Я просто хотел подчеркнуть то, что Вы сказали в первом предложении.
|
05.11.2004 03:53 Бойко | На новый лад Если большинство разделов математики можно изложить конструктивно, то ведь должен же был кто-то это сделать. Книги то есть? Укажите все книги, какие знаете. Очень хочу почитать. С уважением, Бойко
|
05.11.2004 10:40 Дата регистрации:
7 лет назад Посты: 398 | поддерживаю Цитата
Бойко писал:
Если большинство разделов математики можно изложить конструктивно, то ведь должен же был кто-то это сделать. Книги то есть?
Укажите все книги, какие знаете. Очень хочу почитать.
Полностью поддерживаю Вашу просьбу (видимо, тут нужно обращаться к Гастриту). На сайте конструктивистов материалов очень мало. По конструкт. логике, с небольшими добавлениями анализа, книги есть (Марков, Новиков, Гудстейн, Клини и Весли), но читать их непросто. Возможно, есть смысл сначала просмотреть Верещагин и Шень "Вычислимые функции" (неформально и кратко изложены многие идеи). По конструкт. мат. анализу я нашёл только книгу Куммера (не в сети) и статью Шанина (см. http://logic.pdmi.ras.ru/~shanin/article.html). Видимо, какую-то часть алгебры 1 курса можно изложить конструктивно, если работать с простыми полями и их конечными расширениями. Если же перейти к действительным и комплексным числам, то сразу появятся кое-какие проблемы: не всегда вычисляется ранг матрицы; непонятно (для меня), как красиво разобраться с кратными корнями и жордановыми формами. В обычных курсах алгебры эти проблемы редко обсуждаются. Особенно интересно было бы посмотреть на подробную и достаточно полную конструктивную версию линейного функционального анализа, хотя бы для гильбертова пространства. Впрочем, я подозреваю, что наши просьбы тщетны. Видимо, агитация Гастрита как раз на то и направлена, чтобы кто-нибудь (например, Вы) через пару десятков лет написал такие учебники. :)
|
05.11.2004 14:54 Дата регистрации:
8 лет назад Посты: 303 | О квантовой болтологии Цитата
Игорь Абрамов писал(а) :
(У меня, правда, нет уверенности, что у нас скоро будут
реальные универсальные квантовые компьютеры и мы будем
писать для них квантовые программы и флеймить в квантовых форумах :) )
Вот то-то и оно-то... :) С уважением, Гастрит
|
05.11.2004 14:57 Дата регистрации:
8 лет назад Посты: 303 | И то Цитата
Свинтус писал(а) :
Конкретные подмножества да не всегда можем описать, точнее почти всегда не можем- ну и что.
А то, что их вообще нету :) Цитата
Произольное-то подмножество описывается в виде набора букв.
С уважением, Свинтус
Множество всех наборов букв - с Вашей же точки зрения - счётно. А "множество всех произвольных подмножеств счётного множества", как "доказано" Кантором, "имеет" большую мощность. Как быть? :) С уважением, Гастрит
|
05.11.2004 15:11 Дата регистрации:
8 лет назад Посты: 303 | варианты Цитата
Бойко писал:
Если большинство разделов математики можно изложить конструктивно, то ведь должен же был кто-то это сделать. Книги то есть?
Укажите все книги, какие знаете. Очень хочу почитать.
Например: Р.Л.Гудстейн. Рекурсивный математический анализ. М., 1970. Б.А.Кушнер. Лекции по конструктивному математическому анализу. М., 1973. Честно говоря, я бы изложил соответствующие вещи иначе, но что есть, то есть... Цитата
egor писал(а):
По конструкт. логике, с небольшими добавлениями анализа, книги есть (Марков, Новиков, Гудстейн, Клини и Весли), но читать их непросто.
Увы, да... Цитата
Видимо, какую-то часть алгебры 1 курса можно изложить конструктивно, если работать с простыми полями и их конечными расширениями.
2 курса, кстати, тоже. Собственно, само понятие нормального алгорифма имеет чисто алгебраические корни: выработано в процессе доказательства неразрешимости проблемы Туэ (о конечнопорождённых и конечноопределённых полугруппах). Не верите - спросите Латышева ;) Цитата
Если же перейти к действительным и комплексным числам, то сразу появятся кое-какие проблемы: не всегда вычисляется ранг матрицы; непонятно (для меня), как красиво разобраться с кратными корнями и жордановыми формами.
Оставайтесь в рамках рациональных (вариант: алгебраических) чисел - и будет Вам счастье :) А "произвольные" матрицы можно потом рассматривать аппроксимативно, в духе Гудстейна и Шанина. Цитата
Особенно интересно было бы посмотреть на подробную и достаточно полную конструктивную версию линейного функционального анализа, хотя бы для гильбертова пространства.
Н.А.Шанин. Конструктивные вещественные числа и конструктивные функциональные пространства// Труды МИАН им. В.А.Стеклова, 1962, т.67, стр.15-294. Нечитаемо, конечно, но опять же - что есть, то есть... :( Цитата
Впрочем, я подозреваю, что наши просьбы тщетны. Видимо, агитация Гастрита как раз на то и направлена, чтобы кто-нибудь (например, Вы) через пару десятков лет написал такие учебники. :)
Боюсь, придётся самому :( :( :( С уважением, Гастрит
|
05.11.2004 16:07 Дата регистрации:
7 лет назад Посты: 78 | Никак. Все вроде бы довольно очевидно О том я и писал, когда писал о том, что конкретные подмножества можем описать не всегда. Но утверждения типа \forall x\in P(A) верно то то и то то и \exists x\in P(A) верно то то и то то, мы формулировать и доказывать можем- это и означает, что мы хотя и не умеем описывать почти все конкретные множества можем описывать произвольные, в том числе не поддающиеся конкретному описанию то есть множества подмножеств -- некоторые эл-ты из P(P(A)). С уважением, Свинтус
|
05.11.2004 17:48 Какоткин Р. В. | Посмотрите здесь... http://inwar.ru/01/03/4.html С уважением! Какоткин Р. В.
|
08.11.2004 00:39 Бойко | Не исхитриться Egor писал: Цитата
можно ли как-нибудь исхитриться и применить диагональную конструкцию Кантора к последовательности всех конструктивных действительных чисел (КДЧ)? Нутром чую, что нельзя (нового КДЧ никак не получишь), но полной ясности нет.
Исхитриться не получится. Ибо тогда получится, что КДЧ больше, чем счётно. А их, как легко узреть, счётно. С уважением, Бойко
|
08.11.2004 02:03 Бойко | Где ошибка? Цитата
Далее, на основе алгоритмов теории можно определить понятие конструктивной последовательности КДЧ. Для всякой такой последовательности оказывается возможным построить КДЧ, не равное ни одному члену этой последовательности. Это — конструктивный аналог теоремы Кантора о несчётности континуума.
Это отрывок из короткой статьи о конструктивизме из инета. Источник привести не могу. Я озадачен! Как такое может быть? Смотрите: выпишем все конструктивные числа в последовательность. Отрывок заявляет, что можно построить КДЧ не равное ни одному члену последовательности. Противоречие. Неужели в последовательность нельзя выписать ВСЕ КДЧ? Так ведь выше было указано Egor`ом, как это сделать. С уважением, Бойко
|
09.11.2004 13:21 Дата регистрации:
8 лет назад Посты: 303 | В самом начале Цитата
Бойко писал(а) :
Смотрите: выпишем все конструктивные числа в последовательность.
Выпишите, дорогой, выпишите. Флаг Вам в руки :) :) :) Цитата
Неужели в последовательность нельзя выписать ВСЕ КДЧ? Так ведь выше было указано Egor`ом, как это сделать.
В рассуждении egor'а ошибочка: свойство алгорифма задавать КДЧ является неразрешимым :( А потому конструктивно "лексикографически упорядочить и пересчитать" не удастся :( Так что Ваше первоначальное мнение было справедливым. С уважением, Гастрит
|
09.11.2004 19:26 Дата регистрации:
7 лет назад Посты: 398 | Спасибо за разъяснение Цитата
Гастрит писал:
В рассуждении egor'а ошибочка: свойство алгорифма задавать КДЧ является неразрешимым :( А потому конструктивно "лексикографически упорядочить и пересчитать" не удастся :(
Да, я об этом не подумал, а учебник Куммера так и не посмотрел (он у нас в хранилище). Получается, Бойко был прав ("Не исхитриться"). Спасибо, теперь кое-что проясняется.
|
09.11.2004 19:41 Дата регистрации:
8 лет назад Посты: 303 | Всегда рад :) Цитата
egor писал(а) :
Да, я об этом не подумал, а учебник Куммера так и не посмотрел (он у нас в хранилище).
Куммер - это который немецкий теоретико-числовик XIX века? ;) Вы его, случайно, с Кушнером не спутали? Цитата
Получается, Бойко был прав ("Не исхитриться" ). Спасибо, теперь кое-что проясняется.
Вообще-то, Бойко был прав немного раньше - в посте "не исхитриться" как раз ошибки (см. его же пост "Где ошибка?" ). Поставившее его в тупик утверждение о продуктивности класса КДЧ (т.е. об осуществимости алгорифма, перерабатывающего любую конструктивную последовательность КДЧ в такое КДЧ, которое не равно ни одному члену последовательности) доказывается как раз на основе диагональной процедуры :) С уважением, Гастрит P.S.: Уважаемый Бойко, а с чего Вы взяли, что в конструктивной математике справедлива "теорема" Кантора-Бернштейна? ;)
|
09.11.2004 19:50 Дата регистрации:
7 лет назад Посты: 398 | Да, я опять перепутал Цитата
Гастрит писал:
Куммер - это который немецкий теоретико-числовик XIX века? ;) Вы его, случайно, с Кушнером не спутали?
...
Вообще-то, Бойко был прав немного раньше - в посте "не исхитриться" как раз ошибки (см. его же пост "Где ошибка?" ).
Учебник, конечно, Кушнера (а не Куммера), а Бойко был прав в сообщении "Немного ясности". Очередной раз убеждаюсь на собственном опыте, что иногда нужно подумать, прежде чем сказать (или написать).
|
