Доказать: N - бесконечно
Rostislav Chebykin
Как доказать, что множество натуральных чисел бесконечно?
--
Rostislav Chebykin <phil...@master.elserv.msk.su>
http://www.philigon.ru/
http://www.livejournal.com/users/philigon/
Sergey Glazyrin
допустим оно конечно
пусть чисел k
тогда максимальное тоже k
рассмотрим число k+1, очевидно, что оно тоже натуральное
по идее так
--
Sergey Glazyrin aka idler
Rostislav Chebykin
SG> допустим оно конечно
SG> пусть чисел k
SG> тогда максимальное тоже k
SG> рассмотрим число k+1, очевидно, что оно тоже натуральное
Нет, тут мы опираемся на то, что N - упорядоченное, а надо бы обойтись без
этого.
Кстати, я придумал формулировку, которая, кажется, эквивалентна исходной
задаче: доказать, что множество {0, 1, ..., n} не равномощно множеству {0,
1, ..., n, n+1}. (В смысле, что между ними невозможно установить взаимно
однозначное соответствие.)
Откровенно говоря, я подозреваю, что я туплю на пустом месте и ларчик
открывается как-то совершенно элементарно. Надеюсь, что знающий народ в этой
конференции поможет мне победить собственное невежество.
P.S. Отчего вообще возник исходный вопрос: я просмотрел несколько учебников
по математической логике и дискретной математике - и везде множество N
объявляется бесконечным без всякого доказательства. Причем в большинстве
учебников - даже без четкого разделения между конечными и бесконечными
множествами...
Sergey Glazyrin
> этого.
а почему бы нам не опираться на это, если это следует из определения N?
(хотя, возможно, есть какие-нить извращенные определения, из которых это не
будет следовать)
> Кстати, я придумал формулировку, которая, кажется, эквивалентна исходной
> задаче: доказать, что множество {0, 1, ..., n} не равномощно множеству {0,
> 1, ..., n, n+1}. (В смысле, что между ними невозможно установить взаимно
> однозначное соответствие.)
хм, а что тут n? если какое-то конкретное число, то не сказал бы что
формулировка эквивалентная...
> P.S. Отчего вообще возник исходный вопрос: я просмотрел несколько
учебников
> по математической логике и дискретной математике - и везде множество N
> объявляется бесконечным без всякого доказательства. Причем в большинстве
> учебников - даже без четкого разделения между конечными и бесконечными
> множествами...
ну я читал (или слушал на лекции) именно то доказательство, что привёл в
первом письме
Victor Sedyakin
29 Июн 04 00:16, Rostislav Chebykin wrote to All:
RC> Как доказать, что множество натуральных чисел бесконечно?
От противного.
Your sincerely Victor Sedyakin.
Rostislav Chebykin
SG> а почему бы нам не опираться на это, если это следует из определения
SG> N?
Позвольте-позвольте, какое-такое "определение N"? Можно увидеть это
определение?
Мне известны два определения N - через аксиомы Пеано (аксиоматическое) и
через пустые множества (конструктивное - см., например,
http://webtest.philigon.ru/college/muth/natural.html, а ещё лучше -
какую-нибудь хорошую серьёзную книжку.) В обоих определениях - ни слова про
упорядоченность.
RC>> доказать, что множество {0, 1, ..., n} не равномощно множеству {0,
RC>> 1, ..., n, n+1}. (В смысле, что между ними невозможно установить
RC>> взаимно однозначное соответствие.)
SG> хм, а что тут n? если какое-то конкретное число, то не сказал бы что
SG> формулировка эквивалентная...
Если это доказать - автоматически докажется, что никакое конечное множество
не равномощно себе минус один элемент. С другой стороны, N равномощно N \
{0}. Следовательно, N не является конечным.
Andrei Protasovitski
Rostislav Chebykin пишет:
> Как доказать, что множество натуральных чисел бесконечно?
Методом математической индукции.
--
Andrei Protasovitski mailto:andrei()siliconmaterials.com
JS "KamSil" http://www.siliconmaterials.com/
137, Brestskaya str., ICQ: 75725244
225710, Pinsk, Belarus
Stanislav Bereznyuk
RC> Как доказать, что множество натуральных чисел бесконечно?
А на какое определение "бесконечности" будем опираться?
Есть, к примеру, такой удобный в данном случае критерий: множество бесконечно
тогда и только тогда, когда оно равномощно своему СОБСТВЕHHОМУ подмножеству.
Строим взаимно-однозначное соответствие между натуральными числами и, скажем,
четными числами (x -> 2x). Так как число "3" является натуральным и не
является четным, то множество четных чисел является собственным подмножеством
N. Значит N бесконечно.
Stanislav Bereznyuk (Novosibirsk, Russia)
Rostislav Chebykin
SB> Есть, к примеру, такой удобный в данном случае критерий: множество
SB> бесконечно тогда и только тогда, когда оно равномощно своему
SB> СОБСТВЕHHОМУ подмножеству.
А это откуда следует?
Rostislav Chebykin
RC>> Как доказать, что множество натуральных чисел бесконечно?
> Методом математической индукции.
Сомневаюсь.
Rostislav Chebykin
RC>> Как доказать, что множество натуральных чисел бесконечно?
VS> От противного.
Не вижу, в каком месте будет противоречие.
Andrei Protasovitski
Rostislav Chebykin пишет:
> RC>> Как доказать, что множество натуральных чисел бесконечно?
>>Методом математической индукции.
> Сомневаюсь.
См. первое сообщение Сергея Глазырина.
Rostislav Chebykin
>>> Методом математической индукции.
RC>> Сомневаюсь.
> См. первое сообщение Сергея Глазырина.
См. мой ответ на это сообщение. Мы не можем использовать в доказательстве
понятия "максимальный".
Alex Besogonov
"Rostislav Chebykin" <philigo...@relcom.ru> wrote in message
news:cbr7sa$15pa$1...@ddt.demos.su...
> SB> Есть, к примеру, такой удобный в данном случае критерий: множество
> SB> бесконечно тогда и только тогда, когда оно равномощно своему
> SB> СОБСТВЕHHОМУ подмножеству.
> А это откуда следует?
Это определение: множество называется бесконечным, если существует
биекция этого множества на его собственное подмножество. Биекцию
постройте сами :)
С уважением,
Alex Besogonov (al...@izh.com)
Rostislav Chebykin
RC>> А это откуда следует?
AB> Это определение: множество называется бесконечным, если существует
AB> биекция этого множества на его собственное подмножество.
Это далеко не единственно возможное определение. Я предпочитаю исходить из
того, что множество называется _конечным_, если оно равномощно некоторому
подмножеству {0, 1, ..., k} множества N, и бесконечным - в противном случае.
Возможно ли доказать, что это определение эквивалентно твоему?
Victor Sedyakin
29 Июн 04 12:16, Rostislav Chebykin wrote to Victor Sedyakin:
RC>>> Как доказать, что множество натуральных чисел бесконечно?
VS>> От противного.
RC> Hе вижу, в каком месте будет противоречие.
Изначально предполагаем конечность этого множества. Тогда из его элементов
составляем число, являющееся натуральным, и не входящее в это множество.
Hапример, если предполагаемое множество натуральных чисел {a1,a2,...,an}, то в
качестве такого числа подойдет max{ai}+1 или a1*a2*...*an+1. Это число не
входит в предполагаемое конечное множество натуральных чисел, но с другой
стороны, оно, очевидно, натуральное. Противоречие.
Your sincerely Victor Sedyakin.
Andrei Protasovitski
Rostislav Chebykin пишет:
>>>>Методом математической индукции.
> RC>> Сомневаюсь.
>>См. первое сообщение Сергея Глазырина.
> См. мой ответ на это сообщение. Мы не можем использовать в доказательстве
> понятия "максимальный".
А ты введи на множестве N алгебраическую операцию "сложение",
Основываясь на этой операции введи отношения порядка, а там и до
определения максимального элемента рукой подать.
Схематично:
1. Сложение:
1) n + 1 = S(n);
2) n + k = S(S(S(...S(n)...))) (k вложений функции S)
2. Отношения порядка:
1) n > m <=> существует k: m + k = n;
2) n < m <=> существует k: n + k = m;
3. Максимальный и минимальный элемент:
1) a_k есть максимальный элемент множества A = {a_1, a_2, ..., a_n},
если для a_k > a_i, i <> k;
2) a_k есть минимальный элемент множества A = {a_1, a_2, ..., a_n},
если для a_k < a_i, i <> k.
Здесь n, m, k - элементы множества N; S(n) - элемент, следующий за n; A
- подмножество N. Если в определении N утверждается, что 0 -
натуральное, то нужно дополнительно указать: n + 0 = n, k <> 0.
Rostislav Chebykin
VS> Изначально предполагаем конечность этого множества. Тогда из его
VS> элементов составляем число, являющееся натуральным, и не входящее в
VS> это множество. Hапример, если предполагаемое множество натуральных
VS> чисел {a1,a2,...,an}, то в качестве такого числа подойдет max{ai}+1
VS> или a1*a2*...*an+1.
Опять плохо. Не годится ни понятие максимума, ни арифметические операции.
Меня интересует не школьная математика, а методы строгой теории множеств.
Andrei Protasovitski
Victor Sedyakin пишет:
> RC>>> Как доказать, что множество натуральных чисел бесконечно?
> VS>> От противного.
> RC> Hе вижу, в каком месте будет противоречие.
> Изначально предполагаем конечность этого множества. Тогда из его элементов
> составляем число, являющееся натуральным, и не входящее в это множество.
Нужно определить правила составления этого числа.
> Hапример, если предполагаемое множество натуральных чисел {a1,a2,...,an}, то в
> качестве такого числа подойдет max{ai}+1 или a1*a2*...*an+1.
Что есть max{ai}? Что есть "+1"? Что есть a1*a2? Это все нужно
определить, а потом уже составлять число.
> Это число не
> входит в предполагаемое конечное множество натуральных чисел, но с другой
> стороны, оно, очевидно, натуральное. Противоречие.
Это все еще нужно доказать, основываясь на правилах составления числа. И
вовсе это не очевидно.
Sashka Yackubtchick
29 Jun 04 01:39, Rostislav Chebykin писАл(а) к Sergey Glazyrin:
RC> Sergey Glazyrin wrote:
SG>> допустим оно конечно
SG>> пусть чисел k
SG>> тогда максимальное тоже k
SG>> рассмотрим число k+1, очевидно, что оно тоже натуральное
RC> Hет, тут мы опираемся на то, что N - упорядоченное, а надо бы обойтись без
RC> этого.
Это необязательно следует из предложенного варианта.
Из предложенного варианта следует, что мощность множества натуральных чисел
равно максимальному значению элемента этого множества.
Исходя из того что натуральное число - это собрание единиц, то сколько единиц
имеем столь же и "собраний" т.е. натуральных чисел.
Максимальное же число само по себе собрание "всех единиц" и колличества
собраний столь же сколько всех единиц.
Пока!
Sashka, The Svin.
Micron Umbarov
>
> RC>> А это откуда следует?
> AB> Это определение: множество называется бесконечным, если существует
> AB> биекция этого множества на его собственное подмножество.
>
> Это далеко не единственно возможное определение. Я предпочитаю исходить из
> того, что множество называется _конечным_, если оно равномощно некоторому
> подмножеству {0, 1, ..., k} множества N, и бесконечным - в противном
случае.
> Возможно ли доказать, что это определение эквивалентно твоему?
>
Определение натурального ряда N предполагает, что это множество уже
снабжено некоторой "структурой": 1) для каждого элемента n определён
непосредственно следующий за ним n', 2) различные элементы имеют различные
следующие за ними и 3) существует элемент 0, не имеющий предшественника (то
есть, n'<>0 ни для какого элемента n). Этого уже достаточно, чтобы доказать
бесконечность натурального ряда в смысле существования биекции на
собственное подмножество, ибо операция ' и есть эта биекция.
Бесконечность в смысле другого определения (неравномощность N никакому
начальному интервалу [0,k), включая и пустой интервал [0,0)) также
доказывается (можно использовать следующую теорему из теории множеств: если
множество A равномощно некоторому подмножеству множества B, а множество B
равномощно некоторому подмножеству множества A, то множества A и B
равномощны; если не ошибаюсь, аксиома выбора в доказательстве не
используется).
Однако доказательство равносильности этих двух определений бесконечного
множества требует некоторой формы аксиомы выбора, а без аксиомы выбора
вполне может случиться так, что множество не будет равномощно никакому
интервалу натурального ряда, и в то же время не будет содержать никакого
равномощного ему собственного подмножества.
Впрочем, без аксиомы выбора, видимо, появляется много неэквивалентных
определений бесконечного множества. Специалисты по теории множеств могут
рассказать об этом гораздо больше, чем я.
--
--
Всего наилучшего. Someone.
mailto:um...@newmsk.tula.net
http://www.someoneltd.boom.ru/ http://home.tula.net/frazez/
Rostislav Chebykin
RC>> Это далеко не единственно возможное определение. Я предпочитаю
RC>> исходить из того, что множество называется _конечным_, если оно
RC>> равномощно некоторому подмножеству {0, 1, ..., k} множества N, и
RC>> бесконечным - в противном случае. Возможно ли доказать, что это
RC>> определение эквивалентно твоему?
MU> Определение натурального ряда N предполагает, что это множество уже
MU> снабжено некоторой "структурой": 1) для каждого элемента n определён
MU> непосредственно следующий за ним n', 2) различные элементы имеют
MU> различные следующие за ними и 3) существует элемент 0, не имеющий
MU> предшественника (то есть, n'<>0 ни для какого элемента n). Этого уже
MU> достаточно, чтобы доказать бесконечность натурального ряда в смысле
MU> существования биекции на собственное подмножество, ибо операция ' и
MU> есть эта биекция.
Опять же, это нисколько не помогает доказать эквивалентность двух
определений бесконечного множества.
Кроме того, если отталкиваться от наиболее "теоретико-множественного"
определения натурального ряда, то придется немало попотеть, прежде чем
вывести из него вышеупомянутую "структуру". Я, помнится, попотел над этим в
своей статье (адрес недавно приводился), и то допустил кучу вольностей и
ляпов разного калибра. Шенфилд попотел над тем же самым в "Справочной книге
по математической логике" - в отличие от меня, попотел профессионально, но
приплел в процессе доказательства практически всю ZFC.
Мне бы хотелось обойтись без лишних сущностей. Определим множество
натуральных чисел стандартным индуктивным методом. Пусть * - пустое
множество, тогда 0 есть *, а каждое следующее множество - это множество всех
подмножеств предыдущего, то есть 1 есть {*} (то есть {0}), 2 есть {*, {*}}
(то есть {0, 1}), ..., n есть {0, 1, 2, ..., n-1}.
Теперь надо как можно более легко и беззаботно доказать, что множество всех
множеств, которые можно построить таким образом, не равномощно никакому из
множеств {0, 1, ..., n}.
MU> Бесконечность в смысле другого определения (неравномощность N
MU> никакому начальному интервалу [0,k), включая и пустой интервал [0,0))
MU> также доказывается (можно использовать следующую теорему из теории
MU> множеств: если множество A равномощно некоторому подмножеству
MU> множества B, а множество B равномощно некоторому подмножеству
MU> множества A, то множества A и B равномощны; если не ошибаюсь, аксиома
MU> выбора в доказательстве не используется).
Увы, но мне всё еще непонятно, как это доказать. Упомянутая теорема
(Кантора-Бернштейна, если я правильно ошибаюсь) позволяет доказать, что два
каких-нибудь множества равномощны, а вот как доказать с ее помощью,
наоборот, неравномощность - непонятно.
MU> Специалисты по теории множеств могут рассказать об этом гораздо
MU> больше, чем я.
А здесь таковые водятся?
Ivan Boldyrev [e-mail is defunct]
RC> Как доказать, что множество натуральных чисел бесконечно?
Всё зависит от того, как ты определяешь бесконечное множество.
Например, можно воспользоваться таким определением:
,----
| Множество бесконечно, если в нём есть равномощное ему собственное
| подмножество.
`----
И в самом деле, в N содержится 2N, которое ему равномощно.
--
Ivan Boldyrev
Дадим суровый отпор врагам мирового империализма!
Rostislav Chebykin
IBe> Всё зависит от того, как ты определяешь бесконечное множество.
Я тут уже писал определения, от которых хотелось бы отталкиваться.
Ряд натуральных чисел определяется следующим образом:
0 есть * (* - пустое множество)
1 есть {*} (т. е. 1 = {0})
2 есть {*, {*}} (т. е. 2= {0, 1})
...
n есть {0, 1, ..., n-1}
Каждый следующий элемент - множество всех подмножеств предыдущего.
Конечное множество есть множество, равномощное некоторому из
вышеперечисленных n (то есть какому-нибудь множеству {0, 1, ..., n}).
Бесконечное множество есть множество, не являющееся конечным.
Вот, танцуя отсюда, и надо доказать, что множество всех натуральных чисел не
равномощно никакому своему подмножеству {0, 1, ..., n}.
Как бы это сделать?
Micron Umbarov
>
> MU> Определение натурального ряда N предполагает, что это множество уже
> MU> снабжено некоторой "структурой": 1) для каждого элемента n определён
> MU> непосредственно следующий за ним n', 2) различные элементы имеют
> MU> различные следующие за ними и 3) существует элемент 0, не имеющий
> MU> предшественника (то есть, n'<>0 ни для какого элемента n). Этого уже
> MU> достаточно, чтобы доказать бесконечность натурального ряда в смысле
> MU> существования биекции на собственное подмножество, ибо операция ' и
> MU> есть эта биекция.
>
> Опять же, это нисколько не помогает доказать эквивалентность двух
> определений бесконечного множества.
>
Я же и говорю, что эти определения, вообще говоря, не эквивалентны.
Однако, если принимаем аксиому выбора (что обычно и делается), то
эквивалентность доказать можно, ибо в этом случае каждое множество можно
вполне упорядочить. А если вполне упорядоченное множество не равномощно
никакому интервалу [0,k), то оно содержит подмножество, равномощное
натуральному ряду, и, следовательно, на нём требуемую биекцию указать
нетрудно. Если же оно такую биекцию имеет, то оно не может быть равномощно
интервалу [0,k), поскольку интервал такой биекции не имеет. Если Вы хотите
доказывать всё это строго формально, явно указывая все используемые аксиомы
и правила вывода, то получится, вероятно, довольно длинно, и у меня нет ни
малейшего желания этим заниматься (если не ошибаюсь, в своё время
В.Серпинский написал подобное доказательство теоремы Пифагора; текст занял
несколько десятков страниц).
>
> Кроме того, если отталкиваться от наиболее "теоретико-множественного"
> определения натурального ряда, то придется немало попотеть, прежде чем
> вывести из него вышеупомянутую "структуру". Я, помнится, попотел над этим
в
> своей статье (адрес недавно приводился), и то допустил кучу вольностей и
> ляпов разного калибра. Шенфилд попотел над тем же самым в "Справочной
книге
> по математической логике" - в отличие от меня, попотел профессионально, но
> приплел в процессе доказательства практически всю ZFC.
>
> Мне бы хотелось обойтись без лишних сущностей. Определим множество
> натуральных чисел стандартным индуктивным методом. Пусть * - пустое
> множество, тогда 0 есть *, а каждое следующее множество - это множество
всех
> подмножеств предыдущего, то есть 1 есть {*} (то есть {0}), 2 есть {*, {*}}
> (то есть {0, 1}), ..., n есть {0, 1, 2, ..., n-1}.
>
Стоп-стоп-стоп! Во-первых, есть натуральный ряд, а есть его
теоретико-множественная модель. Если Вы хотите доказывать бесконечность
натурального ряда, то на нём операция "следующий элемент" с нужными
свойствами есть по определению. Во-вторых, упомянутая Вами модель в качестве
операции "следующий элемент" использует всё-таки не операцию взятия степени
(множество подмножеств), а операцию n'=nU{n}. В-третьих, у Шенфилда краткие
пояснения занимают чуть больше половины страницы, и не складывается
впечатление, что он "попотел". Хотя, разумеется, если делать полную проверку
аксиом Пеано, то текст разрастётся, и придётся использовать некоторое
количество аксиом теории множеств.
>
> MU> Бесконечность в смысле другого определения (неравномощность N
> MU> никакому начальному интервалу [0,k), включая и пустой интервал [0,0))
> MU> также доказывается (можно использовать следующую теорему из теории
> MU> множеств: если множество A равномощно некоторому подмножеству
> MU> множества B, а множество B равномощно некоторому подмножеству
> MU> множества A, то множества A и B равномощны; если не ошибаюсь, аксиома
> MU> выбора в доказательстве не используется).
>
> Увы, но мне всё еще непонятно, как это доказать. Упомянутая теорема
> (Кантора-Бернштейна, если я правильно ошибаюсь) позволяет доказать, что
два
> каких-нибудь множества равномощны, а вот как доказать с ее помощью,
> наоборот, неравномощность - непонятно.
>
Наверное, от противного. Если мы предположим, что весь натуральный ряд N
равномощен некоторому интервалу [0,k), то из упомянутой теоремы следует, что
интервал [0,k') равномощен интервалу [0,k), а невозможность этого должна
выводиться из свойств операции "следующий элемент".
>
> MU> Специалисты по теории множеств могут рассказать об этом гораздо
> MU> больше, чем я.
>
> А здесь таковые водятся?
>
А неужели никого нет? Мне всё время казалось, что есть. Ну пусть не
специалисты по теории множеств как таковой, но люди, серьёзно разбирающиеся
в теории множеств, точно есть.
--
--
Всего наилучшего. Someone.
mailto:um...@newmsk.tula.net
http://www.someoneltd.boom.ru/ http://home.tula.net/frazez/
P.S. Мне как-то смутно вспоминается, что что-то подобное мы уже обсуждали.
Rostislav Chebykin
RC>> Пусть * - пустое множество, тогда 0 есть *, а каждое следующее
RC>> множество - это множество всех подмножеств предыдущего, то есть 1
RC>> есть {*} (то есть {0}), 2 есть {*, {*}} (то есть {0, 1}), ..., n
RC>> есть {0, 1, 2, ..., n-1}.
MU> Стоп-стоп-стоп! Во-первых, есть натуральный ряд, а есть его
MU> теоретико-множественная модель.
Ну, опять же, в ZF доказывается, что "теоретико-множественная модель"
натурального ряда вполне удовлетворяет аксиомам Пеано, так что ничто не
мешает считать её натуральным рядом.
MU> Если Вы хотите доказывать бесконечность натурального ряда, то на нём
MU> операция "следующий элемент" с нужными свойствами есть
MU> по определению.
Не совсем. Если танцевать от предложенной мной теоретико-множественной
печки, то там придется еще долго и нудно объяснять, что такое "следующий" и
"операция". Вот "множество всех подмножеств" - это ясно что такое, а
"следующий элемент" - это вещь совсем не очевидная...
MU> Во-вторых, упомянутая Вами модель в качестве операции "следующий
MU> элемент" использует всё-таки не операцию взятия степени (множество
MU> подмножеств), а операцию n'=nU{n}.
Позвольте, возможно, я чего-то недопонимаю, но разве для данной
последовательности множеств это не одно и то же? Если нет - то в чём
разница? Пустое множество - *, единственное его подмножество - оно само,
следовательно, множество всех подмножеств - {*}. У этого множества, в свою
очередь, два подмножества - пустое множество и оно само; значит, множество
всех подмножеств - {*, {*}}. И так далее. Или я в чем-то заблуждаюсь?
MU> В-третьих, у Шенфилда краткие пояснения занимают чуть больше половины
MU> страницы, и не складывается впечатление, что он "попотел".
Подозреваю, что прежде чем написать эти полстраницы, он приложил немало
интеллектуальных усилий.
Вообще, многие разделы "Справочной книги по математической логике"
напоминают мне анекдот, который рассказывали про Ландау и Лифшица. Студент
подходит к Лифшицу с учебником Ландау-Лифшица по квантовой механике и просит
разъяснить: "У вас тут написано, что из [1] очевидно следует [2]. А мне
непонятно, почему оно очевидно". Лифшиц смотрит в собственный учебник,
задумывается, на лице его проступает недоумение, и он предлагает студенту
подойти к нему завтра, когда он будет готов ответить на его вопрос. Назавтра
зелёный и невыспавшийся Лифшиц выдаёт студенту стопку листов с
математическими выкладками, объясняющими переход от [1] к [2], сообщая при
этом: "Очевидно, это было очевидно для Ландау".
MU> А неужели никого нет? Мне всё время казалось, что есть. Ну пусть не
MU> специалисты по теории множеств как таковой, но люди, серьёзно
MU> разбирающиеся в теории множеств, точно есть.
Такое впечатление, что они все попрятались...
Ivan Boldyrev [e-mail is defunct]
RC> Меня интересует не школьная математика, а методы строгой теории множеств.
В строгой теории множеств N (точнее, \omega) -- это первый
(наименьший) бесконечный ординал. Так что оно бесконечно по
определению.
Короче, давай определение N и определение бесконечности, тогда тебе
смогут помочь. А подземный стук тут не лечат.
--
Ivan Boldyrev
Весна.
Кровати скрип
Мешает спать соседям.
Rostislav Chebykin
IBe> Короче, давай определение N и определение бесконечности, тогда тебе
IBe> смогут помочь. А подземный стук тут не лечат.
Уже дал. Мало того, уже сам, кажется, доказал. Хотя и опасаюсь, что
доказательство а) чрезмерно громоздко; б) может содержать ляпы.
Ivan Boldyrev [e-mail is defunct]
IBe>> Всё зависит от того, как ты определяешь бесконечное множество.
RC> Конечное множество есть множество, равномощное некоторому из
RC> вышеперечисленных n (то есть какому-нибудь множеству {0, 1, ..., n}).
RC> Бесконечное множество есть множество, не являющееся конечным.
RC> Вот, танцуя отсюда, и надо доказать, что множество всех
RC> натуральных чисел не равномощно никакому своему подмножеству {0,
RC> 1, ..., n}.
Предположим противное: N равномощно M={1,..,n}, т.е. существует
взаимно-однозначное отображение f: M -> N. Однако образ M состоит из n
элементов, тогда как в N мы можем предъявить n+1 элемент.
Т.о. отображение не взаимно-однозначное. Противоречие?
Я тут предположил, что множества равномощны, если существует их
взаимно-однозначное отображение. У тебя такое же определение?
--
Ivan Boldyrev
Форт (Forth) -- язык программирования, на котором написана
ОС Форточки 95 (Forthochky 95).
Micron Umbarov
>
> MU> Если Вы хотите доказывать бесконечность натурального ряда, то на нём
> MU> операция "следующий элемент" с нужными свойствами есть
> MU> по определению.
>
> Не совсем. Если танцевать от предложенной мной теоретико-множественной
> печки, то там придется еще долго и нудно объяснять, что такое "следующий"
и
> "операция". Вот "множество всех подмножеств" - это ясно что такое, а
> "следующий элемент" - это вещь совсем не очевидная...
>
Я об этом и говорю. Если речь идёт о натуральном ряде, который уже есть,
то операция "следующий элемент" на нём есть (а если её нет, то есть операция
сложения, или какая-нибудь ещё), поэтому строить эту операцию не надо, можно
сразу ей пользоваться. Если же Вы говорите о своей собственной модели, то
Вам нужно доказать, что она действительно есть модель натурального ряда,
который есть не просто некоторое множество, а множество с определённой
операцией, удовлетворяющей определённым условиям. После того, как Вы это
докажете, Вы получите право говорить, что "эта модель и есть натуральный
ряд". Как только это будет сделано, мы попадём в ситуацию, описанную в
начале абзаца: имеется натуральный ряд с операцией "следующий элемент (или
другой, типичной для натуральных чисел), и мы може сразу же ей
воспользоваться, не обременяя себя повторным её построением и хождением по
кругу.
>
> MU> Во-вторых, упомянутая Вами модель в качестве операции "следующий
> MU> элемент" использует всё-таки не операцию взятия степени (множество
> MU> подмножеств), а операцию n'=nU{n}.
>
> Позвольте, возможно, я чего-то недопонимаю, но разве для данной
> последовательности множеств это не одно и то же? Если нет - то в чём
> разница? Пустое множество - *, единственное его подмножество - оно само,
> следовательно, множество всех подмножеств - {*}. У этого множества, в свою
> очередь, два подмножества - пустое множество и оно само; значит, множество
> всех подмножеств - {*, {*}}. И так далее. Или я в чем-то заблуждаюсь?
>
Заблуждаетесь. Следующий шаг - множество подмножеств множества {*,
{*}} - даёт 4 элемента, а не 3: {*,{*},{{*}},{*, {*}}}. А нужны именно 3:
{*,{*},{*, {*}}}={*, {*}}U{{*, {*}}}.
--
--
Всего наилучшего. Someone.
mailto:um...@newmsk.tula.net
http://www.someoneltd.boom.ru/ http://home.tula.net/frazez/
P.S. Вообще, множество, содержащее n элементов, имеет 2^n подмножеств, а не
n+1. И совершенно независимо от того, какие у него элементы.
Rostislav Chebykin
IBe> Предположим противное: N равномощно M={1,..,n}, т.е. существует
IBe> взаимно-однозначное отображение f: M -> N. Однако образ M состоит
IBe> из n элементов, тогда как в N мы можем предъявить n+1 элемент.
IBe> Т.о. отображение не взаимно-однозначное. Противоречие?
Но тогда придется еще доказывать, что n не равно n+1...
Sashka Yackubtchick
01 Jul 04 03:03, Rostislav Chebykin писАл(а) к Ivan Boldyrev [e-mail is
defunct]:
IBe>> Предположим противное: N равномощно M={1,..,n}, т.е. существует
IBe>> взаимно-однозначное отображение f: M -> N. Однако образ M состоит
IBe>> из n элементов, тогда как в N мы можем предъявить n+1 элемент.
IBe>> Т.о. отображение не взаимно-однозначное. Противоречие?
RC> Hо тогда придется еще доказывать, что n не равно n+1...
?
n часть n+1 -определение части
n меньше n+1 -часть меньше целого
n не может быть
равно n+1 поскольку уже
доказано что она меньше -аксиома трихотомии (либо меньше, либо больше, либо
равно)
Пока
Sashka, The Svin.
Sergej Malev
29 июн 04 00:16, Rostislav Chebykin -> All:
RC> Как доказать, что множество натуральных чисел бесконечно?
Очевидно следует из аксиомы бесконечного множества.
До новых встреч, Rostislav!
np: nothing
... Teams: [SPBFML239 - 15-1], [СПБГУ Мат-Мех], [Геометpия]
Sergej Malev
29 июн 04 02:05, Sergey Glazyrin -> Rostislav Chebykin:
>> Hет, тут мы опираемся на то, что N - упорядоченное, а надо бы
>> обойтись без этого.
SG> а почему бы нам не опираться на это, если это следует из определения
SG> N? (хотя, возможно, есть какие-нить извращенные определения, из
SG> которых это не будет следовать)
Если уж Вы вспоминаете определение N, то не забывайте, пожалуйста, что
определяется оно аксиомой бесконечного множества.
До новых встреч, Sergey!
Rostislav Chebykin
MU> Заблуждаетесь. Следующий шаг - множество подмножеств множества {*,
MU> {*}} - даёт 4 элемента, а не 3: {*,{*},{{*}},{*, {*}}}. А нужны
MU> именно 3: {*,{*},{*, {*}}}={*, {*}}U{{*, {*}}}.
Согласен, я ошибался.
Rostislav Chebykin
RC>> Hо тогда придется еще доказывать, что n не равно n+1...
SY> ?
SY> n часть n+1 -определение части
SY> n меньше n+1 -часть меньше целого
Нет в теории множеств никакого понятия "части". Я уже не говорю о том, что
"часть меньше целого" - это вообще ерунда. Например, отрезок [0,1] является
частью отрезка [0,10]. И при этом между точками этих отрезков можно
установить взаимно однозначное соответствие.
Rostislav Chebykin
RC>> Как доказать, что множество натуральных чисел бесконечно?
SM> Очевидно следует из аксиомы бесконечного множества.
Так-так. А теперь вспоминаем ту самую аксиому бесконечности и смотрим, что
же именно она утверждает. Из нее никак не следует, что множество N не
равномощно никакому своему подмножеству {1, ..., n}.
Sashka Yackubtchick
01 Jul 04 12:01, Rostislav Chebykin писАл(а) к Sashka Yackubtchick:
RC>>> Hо тогда придется еще доказывать, что n не равно n+1...
SY>> ?
SY>> n часть n+1 -определение части
SY>> n меньше n+1 -часть меньше целого
RC> Hет в теории множеств никакого понятия "части".
Hе совсем так. Есть понятие истинного подмножества.
Если A включено в B и А не равно B. Т.е. вилка без палки :)
Hо это не главное.
Если ты определяешь, что существует такое натуральное n что выполняются условия
эквивалентности двух определениq множества X
а именно.
X{x E N) и X{x E N|0 < x <= n}
то n+1 не принадлежит X по последнему определению.
А значит n+1 не принадлежит N. Hо это противоречит определению натурального
числа, как собрания единиц. Если n натуральное то и n+1 натуральное.
Тут тебе приходится говорить уже используя арифметику из которой пришло само
понятие, что такое натуральное число.
Само понятие "множество" никак чётко не определено, кроме чего-то типа собрания
элементов. И принадлежность к множеству может быть определено хоть с помощью
классификации Линея, хоть таблицы Менделеева, хоть системы рейтингов
хит-парадов попсы.
Поэтому если мы множество определяем с помощью другой сферы математики
(здесь в частности как принадлежность к Hатуральным числам в первом
определении, и дополнительно как 0 < x <=n во втором определении)
то нам для определения принадлежности n+1 приходится обращаться к правилам и
инструментам той сферы из которой мы сами эти определения взяли.
Если ты определишь множество X{x E животные | x парнокопытное} то для
того чтобы определить принадлежит что-то к этому множеству тебе нужно будет
использовать зоологию, хотя в теории множеств нет никакого такого понятия
"парнокопытное".
RC> Я уже не говорю о том, что
RC> "часть меньше целого" - это вообще ерунда.
Это аксиома без которой в арифметике и геометрии мало чего смогли бы доказать.
Выкинь её и тебе прийдётся выкинуть на свалку кучу доказанных лемм.
И станут спорными тучка других аксиом типа, сложение, вычитание, умножение и
деление равенств. И вся алгебра как наука о тождествах окажется
несостоятельной.
RC> Hапример, отрезок [0,1]
RC> является частью отрезка [0,10]. И при этом между точками этих
RC> отрезков
RC> можно установить взаимно однозначное соответствие.
Hо у тебя не отрезки а натуральные числа.
И мощность X{x E N; x <=n} равна n. При этом n+1 натуральное если n
натуральное. Получаем что X{x E N; x <=n} не равно X{x E N) при этом строго
включено в X{x E N} а значит является его истинным подмножеством (что я назвал
частью)
Пока!
Sashka, The Svin.
Sashka Yackubtchick
01 Jul 04 12:01, Rostislav Chebykin писАл(а) к Sashka Yackubtchick:
RC> Hет в теории множеств никакого понятия "части".
Вот тебе тогда на языке множеств:
X{x E N) = X1{x E N| 0 < x <= n} U X2{x E N| x > n}
и при этом X1{x E N| 0 < x <= n} ^ X2{x E N| x > n} = 0/
Здесь я использовал U как объединение, а ^ как знак пересечения.
0/ - пустое множество.
Если кто-то может научить как в ASCII принято заменять знаки из синтаксиса в
теории множеств - буде черезвычайно благодарен.
Пока!
Sashka, The Svin.
Dmitriy Karlovskiy
RC>> Как доказать, что множество натуpальных чисел бесконечно?
IBe> Всё зависит от того, как ты опpеделяешь бесконечное множество.
IBe> Hапpимеp, можно воспользоваться таким опpеделением:
IBe> ,----
IBe> | Множество бесконечно, если в нём есть pавномощное ему собственное
IBe> | подмножество.
IBe> `----
IBe> И в самом деле, в N содеpжится 2N, котоpое ему pавномощно.
А множество {1,2,3} pавномощно своему подмножеству {1,2,3}
хоpошее опpеделение :)))
С вами был великий и ужасный...
Dmitriy Karlovskiy
RC> Ряд натуpальных чисел опpеделяется следующим обpазом:
RC> 0 есть * (* - пустое множество)
RC> 1 есть {*} (т. е. 1 = {0})
RC> 2 есть {*, {*}} (т. е. 2= {0, 1})
3 есть {*, {*}, {{*}}, {*,{*}}} (т. е. 3= {0, 1, x, 2})
Alex Besogonov
"Dmitriy Karlovskiy" <Dmitriy.K...@p42.f659.n5030.z2.fidonet.org>
wrote in message news:10886...@p42.f659.n5030.z2.ftn...
> RC>> Как доказать, что множество натуpальных чисел бесконечно?
> IBe> Всё зависит от того, как ты опpеделяешь бесконечное множество.
> IBe> Hапpимеp, можно воспользоваться таким опpеделением:
> IBe> ,----
> IBe> | Множество бесконечно, если в нём есть pавномощное ему собственное
> IBe> | подмножество.
> IBe> `----
> IBe> И в самом деле, в N содеpжится 2N, котоpое ему pавномощно.
> А множество {1,2,3} pавномощно своему подмножеству {1,2,3}
> хоpошее опpеделение :)))
Оно {1,2,3} - это несобственное подмножества множества {1,2,3}.
С уважением,
Alex Besogonov (al...@izh.com)
Ivan Boldyrev [e-mail is defunct]
IBe>> Предположим противное: N равномощно M={1,..,n}, т.е. существует
IBe>> взаимно-однозначное отображение f: M -> N. Однако образ M состоит
IBe>> из n элементов, тогда как в N мы можем предъявить n+1 элемент.
IBe>> Т.о. отображение не взаимно-однозначное. Противоречие?
RC> Но тогда придется еще доказывать, что n не равно n+1...
Они не равны, поскольку n+1 содержит элемент n, который не содержится
в n. Это сложно? :)
--
Ivan Boldyrev
Today is the first day of the rest of your life.
Ivan Boldyrev [e-mail is defunct]
IBe>> ,----
IBe>> | Множество бесконечно, если в нём есть pавномощное ему собственное
IBe>> | подмножество.
IBe>> `----
DK> А множество {1,2,3} pавномощно своему подмножеству {1,2,3}
DK> хоpошее опpеделение :)))
Насколько я помню, "собственное подмножество" -- это подмножество, не
равное пустому и самому множеству. У тебя подмножество не
собственное. В след. раз читай внимательнее.
--
Ivan Boldyrev
Нельзя опрять неопрятное.
Stanislav Bereznyuk
DK> Пpиветствую тебя, Rostislav!
RC>> Ряд натуpальных чисел опpеделяется следующим обpазом:
RC>> 0 есть * (* - пустое множество)
RC>> 1 есть {*} (т. е. 1 = {0})
RC>> 2 есть {*, {*}} (т. е. 2= {0, 1})
DK> 3 есть {*, {*}, {{*}}, {*,{*}}} (т. е. 3= {0, 1, x, 2})
Hасколько мне помнится, 3 = {*, {*}, {*, {*}} }
Stanislav Bereznyuk
Stanislav Bereznyuk
defunct]:
RC>>> Как доказать, что множество натуpальных чисел бесконечно?
IBe>> Всё зависит от того, как ты опpеделяешь бесконечное множество.
IBe>> Hапpимеp, можно воспользоваться таким опpеделением:
IBe>> ,----
IBe>> | Множество бесконечно, если в нём есть pавномощное ему собственное
IBe>> | подмножество.
IBe>> `----
IBe>> И в самом деле, в N содеpжится 2N, котоpое ему pавномощно.
DK> А множество {1,2,3} pавномощно своему подмножеству {1,2,3}
DK> хоpошее опpеделение :)))
Оно не является своим СОБСТВЕHHЫМ подмножеством
Stanislav Bereznyuk
Rostislav Chebykin
IBe>>> Однако образ M состоит из n элементов, тогда как в N мы можем
IBe>>> предъявить n+1 элемент. Т.о. отображение не взаимно-однозначное.
IBe>>> Противоречие?
RC>> Но тогда придется еще доказывать, что n не равно n+1...
IBe> Они не равны, поскольку n+1 содержит элемент n, который не содержится
IBe> в n. Это сложно? :)
Конечно. Нам же важно не то, какие элементы содержатся в множествах, а то,
равномощны ли эти множества. Так что придется доказывать, что {0, 1, ..., n}
неравномощно {0, 1, ..., n, n+1}. На этот момент у нас еще нет понятий
"больше", "меньше" и "равно" для чисел.
Rostislav Chebykin
RC>> Hет в теории множеств никакого понятия "части".
SY> Hе совсем так. Есть понятие истинного подмножества.
SY> Если A включено в B и А не равно B. Т.е. вилка без палки :)
Ох... То, что ты пишешь далее по этому поводу - как бы сказать... находится,
что ли, несколько в стороне от того, что обычно относят к теории множеств.
Например, то, что ты только что определил, обычно называют не "истинным", а
"собственным" подмножеством. Далее, ты пишещь: "...это противоречит
определению натурального числа, как собрания единиц". Но ведь не бывает
такого определения! Натуральные числа стандартно определяются системой
аксиом Пеано, в которых нет ничего похожего на "собрание единиц". Также
натуральные числа можно определить на языке теории множеств - так, как тут
уже было продемонстрировано. (Кстати, еще раз спасибо уважаемому Micron
Umbarov'у - сам не знаю, что за бес меня попутал перепутать множество всех
подмножеств с x U {x}. Это позор просто; я же сам, помнится, кому-то
объяснял ровно ту же самую ошибку...)
Это же касается многих других аспектов того, о чем ты пишешь. К сожалению,
это сложно воспринимать, так как система понятий и терминология там
несколько отличается от того, к чему я привык по университетским учебникам и
прочей литературе. Возможно, это у тебя своя собственная теория множеств, но
тогда мне нечего сказать, поскольку я не профессиональный математик и не
могу оценивать чужие нестандартные теории.
(to All) На всякий случай я повторю и уточню исходную задачу - может быть, у
кого-то возникнут дополнительные соображения.
Итак, мы находимся в "голой" теории множеств. У нас есть только ZF (хотелось
бы даже без аксиомы выбора), и больше ничего. Теперь мы берем то самое
множество, которое существует по аксиоме бесконечности и хотим доказать, что
оно не равномощно никакому своему подмножеству {0, 1, ..., n}. Чтобы не
возникло новой путаницы и расхождения в понятиях, можно даже не пользоваться
терминами "конечный"/"бесконечный".
Мне кажется, что мое собственное доказательство, приведенное тут, не
идеально, и можно придумать лучше. Хотелось бы услышать мнения специалистов.
Dmitriy Karlovskiy
>> RC>> Как доказать, что множество натуpальных чисел бесконечно?
>> IBe> Всё зависит от того, как ты опpеделяешь бесконечное множество.
>> IBe> Hапpимеp, можно воспользоваться таким опpеделением:
>> IBe> ,----
>> IBe> | Множество бесконечно, если в нём есть pавномощное ему
>> собственное IBe> | подмножество.
>> IBe> `----
>> IBe> И в самом деле, в N содеpжится 2N, котоpое ему pавномощно.
>> А множество {1,2,3} pавномощно своему подмножеству {1,2,3}
>> хоpошее опpеделение :)))
AB> Оно {1,2,3} - это несобственное подмножества множества {1,2,3}.
не собственное? а чье же? %)
коpоче, я понял, но мне больше импониpует понятие "стpогое подмножество", чем
некое "несобственное подмножество".
Micron Umbarov
>
> А множество {1,2,3} pавномощно своему подмножеству {1,2,3}
> хоpошее опpеделение :)))
>
В определении говорится, что множество равномощно своему СОБСТВЕННОМУ
подмножеству, то есть, не совпадающему с самим этим множеством. Здесь слово
"собственное" употребляестя во вполне определённом смысле, не имеющем
отношения к бытовому употреблению этого же слова.
Micron Umbarov
>
> Насколько я помню, "собственное подмножество" -- это подмножество, не
> равное пустому и самому множеству. У тебя подмножество не
> собственное. В след. раз читай внимательнее.
>
Маленькая поправочка: собственное подмножество - не совпадающее с самим
множеством. Быть пустым как раз не запрещается.
Micron Umbarov
>
> Итак, мы находимся в "голой" теории множеств. У нас есть только ZF
(хотелось
> бы даже без аксиомы выбора), и больше ничего. Теперь мы берем то самое
> множество, которое существует по аксиоме бесконечности и хотим доказать,
что
> оно не равномощно никакому своему подмножеству {0, 1, ..., n}. Чтобы не
> возникло новой путаницы и расхождения в понятиях, можно даже не
пользоваться
> терминами "конечный"/"бесконечный".
>
Стоп. Это совершенно другая задача. И вся предшествующая дискуссия, по
существу, бессмысленна, поскольку все поверили, что Вы говорите о
натуральном ряде, а оказалось, что Вы имеете в виду совсем другое множество.
И всё из-за того, что Вы неправильно сформулировали задачу.
Множество, существование которого постулируется аксиомой бесконечности,
НЕ ЕСТЬ натуральный ряд и даже не обязано быть ему равномощно. И Вы на самом
деле хотите доказать, что это множество не равномощно никакому из множеств
X(0)=O (так обозначим пустое множество), X(1)={O}, X(2)={O,{O}},...,
которые, начиная с X(1), строятся по правилу X(n+1)=X(n)'=X(n) U {X(n)}.
Rostislav Chebykin
MU> Множество, существование которого постулируется аксиомой бесконечности,
MU> НЕ ЕСТЬ натуральный ряд и даже не обязано быть ему равномощно.
Вполне возможно, что я опять ошибаюсь, но почему же оно - не натуральный
ряд? Тот же Шенфилд, например, говорит именно о таком множестве как о
натуральном ряде:
=== начало цитаты ===
Очевидно, что каждое натуральное число n должно быть отождествлено с
каким-нибудь множеством; какое же множество целесообразнее выбрать?
Естественным является выбор n-элементного множества, а из таких множеств
напрашивается выбор множества всех натуральных чисел, меньших, чем n. Таким
образом, 0 отождествляется с пустым множеством *, 1 отождествляется с {0}, 2
с {0, 1} и т. д. При этом операция перехода к следующему натуральному числу
должна быть определена так:
Sc(x) = x U {x}.
Будем говорить, что множество является индуктивным, если оно содержит 0 и
замкнуто относительно операции Sc.
_Натуральным_ _числом_ назовём кажде множество, принадлежащее любому
индуктивному множеству.
=== конец цитаты ===
Шенфилд ошибается? Или я его неправильно понял? Если так, то надеюсь, что вы
укажете мне на мои заблуждения...
MU> И Вы на самом деле хотите доказать, что это множество не равномощно
MU> никакому из множеств X(0)=O (так обозначим пустое множество), X(1)={O},
MU> X(2)={O,{O}},..., которые, начиная с X(1), строятся по правилу
MU> X(n+1)=X(n)'=X(n) U {X(n)}.
Да, именно так.
Ivan Boldyrev [e-mail is defunct]
IBe>>>> Однако образ M состоит из n элементов, тогда как в N мы можем
IBe>>>> предъявить n+1 элемент. Т.о. отображение не взаимно-однозначное.
IBe>>>> Противоречие?
RC>>> Но тогда придется еще доказывать, что n не равно n+1...
Не нужно. Смысл моей фразы в том, что найдётся элемент, который не
содержится в образе M. Потому что N содержит все элементы из M плюс
{M, {M}} и так далее.
--
Ivan Boldyrev
XML -- new language of ML family.
Rostislav Chebykin
RC>>>> Но тогда придется еще доказывать, что n не равно n+1...
IBe> Не нужно. Смысл моей фразы в том, что найдётся элемент, который не
IBe> содержится в образе M.
...при _данном_ отображении. Это всего лишь докажет, что _данное_
отображение не является взаимно однозначным. А нам надо доказать, что не
существует _никакого_ взаимооднозначного отображения между указанными
множествами.
Andrei Protasovitski
Stanislav Bereznyuk пишет:
> А на какое определение "бесконечности" будем опираться?
>
> Есть, к примеру, такой удобный в данном случае критерий: множество бесконечно
> тогда и только тогда, когда оно равномощно своему СОБСТВЕHHОМУ подмножеству.
> Строим взаимно-однозначное соответствие между натуральными числами и, скажем,
> четными числами (x -> 2x). Так как число "3" является натуральным и не
> является четным, то множество четных чисел является собственным подмножеством
> N. Значит N бесконечно.
По-моему, не совсем корректный пример. Во-первых, не определено, что
такое 2x. Во-вторых, не доказано, что 2x есть натуральное.
По определению для любого n из N существует S(n) из N (S(n) - следующий
элемент), причем n<>S(n). Т.е. в самом определении заложено взаимно
однозначное соответствие n->S(n). Т.о. формально можно утверждать, что N
равномощно S(N).
Думаю, так будет корректнее.
--
Andrei Protasovitski mailto:and...@siliconmaterials.com
JS "KamSil" http://www.siliconmaterials.com/
137, Brestskaya str., ICQ: 75725244
225710, Pinsk, Belarus
Alex Kozhushko
>> А на какое определение "бесконечности" будем опираться?
>> Есть, к примеру, такой удобный в данном случае критерий: множество
>> бесконечно тогда и только тогда, когда оно равномощно своему
>> СОБСТВЕHHОМУ подмножеству.
>> Строим взаимно-однозначное соответствие между натуральными числами и,
>> скажем, четными числами (x -> 2x). Так как число "3" является
>> натуральным и не является четным, то множество четных чисел является
>> собственным подмножеством
>> N. Значит N бесконечно.
AP> По-моему, не совсем корректный пример. Во-первых, не определено, что
AP> такое 2x. Во-вторых, не доказано, что 2x есть натуральное.
Определяем:
Double(0) = 0
Double(S(N))=S(S(Double(N)).
Теперь 2x=Double(x) определено. И натуральным является - по определению.
--
С уважением,
Алексей
Sashka Yackubtchick
03 Jul 04 20:26, Rostislav Chebykin писАл(а) к Sashka Yackubtchick:
RC> Множество N (множество натуральных чисел) является подмножеством множества
RC> Z (целых чисел). Это собственное подмножество (в твоей терминологии
RC> - "истинное"). Вместе с тем, N равномощно Z. Вот и получается, что
RC> собственное подмножество вполне может быть равномощно множеству.
Вобщем прав ты тут. Может, но только тогда когда бесконечно.
Точная цитата, для того чтобы поставить все точки на i, в вопросах
равномощности подмножеств:
В каждом бесконечном множестве А имеется собственное подмножетство В,
равномощное всему А, в то же время как ни в одном конечном множестве такой
Правильной Части найти нельзя.
Поэтому наличие Правильной Части, равномощной Целому, можно принять за
определение Бесконечного множества.
Пока!
Sashka, The Svin.
Ivan Boldyrev [e-mail is defunct]
RC> отображение не является взаимно однозначным. А нам надо доказать, что не
RC> существует _никакого_ взаимооднозначного отображения между указанными
RC> множествами.
Мы предполагаем, что данное отображение взаимооднозначно. Ты знаешь,
что такое доказательство от противного?
Rostislav Chebykin
IBe> Мы предполагаем, что данное отображение взаимооднозначно. Ты знаешь,
IBe> что такое доказательство от противного?
Я еще раз просмотрел твое доказательство. Ты писал:
IBe> Предположим противное: N равномощно M={1,..,n}, т.е. существует
IBe> взаимно-однозначное отображение f: M -> N. Однако образ M состоит
IBe> из n элементов,
Вот! Что такое "n элементов"? Мы пока не знаем такого понятия, как
количество элементов множества.
Sashka Yackubtchick
04 Jul 04 19:13, Rostislav Chebykin писАл(а) к Ivan Boldyrev [e-mail is
defunct]:
RC> Вот! Что такое "n элементов"? Мы пока не знаем такого понятия, как
RC> количество элементов множества.
А что же такое по твоему мощность множества?
Пока!
Sashka, The Svin.
Rostislav Chebykin
RC>> Вот! Что такое "n элементов"? Мы пока не знаем такого понятия, как
RC>> количество элементов множества.
SY> А что же такое по твоему мощность множества?
Класс множеств, равномощных данному. (По крайней мере, для конечных множеств
это определение корректно.)
Micron Umbarov
Вы недостаточно внимательно прочли последнюю процитированную Вами фразу
Шенфилда. Там сказано: "... принадлежащее ЛЮБОМУ индуктивному множеству".
Это означает, что множество "натуральных чисел" (в этом определении)
является подмножеством КАЖДОГО индуктивного множества, то есть, является (в
этом смысле) наименьшим индуктивным множеством. Это важдо для того, чтобы
можно было пользоваться методом полной математической индукции по
натуральным числам.
Произвольно взятое индуктивное множество, кроме "натуральных чисел",
может содержать много других элементов, и индукцию по элементам этого
множества проводить будет нельзя.
Эти вопросы обсуждаются также в книге К.Куратовского и А.Мостовского
"Теория множеств". У них отличие состоит в том, что они (совершенно
сознательно) не включают в список аксиом теории множеств так называемую
аксиому регулярности, которая, в частности, запрещает множеству быть
собственным элементом, запрещает бесконечные последовательности множеств, в
которых каждое следующее является элементом предыдущего, и запрещает циклы,
в которых второе множество является элементом первого, третье - элементом
второго,..., последнее - элементо предпоследнего, а первое - элементом
последнего. Отказ от этой аксиомы создаёт некоторые проблемы (например,
приходится специально доказывать, что "натуральное число" не является своим
собственным элементом), но не слишком существенные. Кроме того, они
специально отслеживают все случаи использования аксиомы выбора, что может
оказаться интересным.
Sashka Yackubtchick
05 Jul 04 22:20, Rostislav Chebykin писАл(а) к Sashka Yackubtchick:
RC>>> Это не определение. Поскольку непонятно, что такое "обобщение" и
RC>>> "число элементов".
Обобщение на произвольное понятие множества означает, что такое значение "число
элементов" слово "мощность" подразумевает применимо к понятию "множество".
Чтобы ты не путал "мощность множества" с "мощностью двигателя" например.
SY>> А что такое "элементы множества" понятно?
RC> Да, это понятие определяется через первичные "множество" и "принадлежать".
RC> А как определить "число элементов", всё ещё неясно.
Значит "элемент" - пронятно", а "число элементов" - непонятно?
Огурец - понятно, число огурцов - непонятно.
Т.е. тоже непонятно что можность пустого множества - 0?
Что можность A{1,2,3} - 3и?
И что A{огурец, помидор} равномощна B{божий дар, яишница}?
И нужны доказательства вышеперечисленных утверждений через единственное
понятное понятие относящееся к мощности "классы равномощных" каким-то образом?
Пока!
Sashka, The Svin.
Sashka Yackubtchick
05 Jul 04 12:58, Rostislav Chebykin писАл(а) к Sashka Yackubtchick:
RC> Hа всякий случай еще раз:
RC> (1) Множество называется конечным, если оно равномощно некоторому
RC> подмножеству {0, 1, ..., n} множества N.
RC> (2) Множество называется бесконечным, если оно не является конечным по
RC> (1).
RC> Твоё определение (множество бесконечно, если оно содержит равномощное себе
RC> собственное подмножество) эквивалентно (2), но чтобы на него опираться,
RC> эту эквивалентность ещё надо доказать.
Это доказывалось (не мной :) по тому что либо множество конечно, либо
бесконечно. Т.е. дихотомически по логике.
Далее доказывалось, ни в одном конечном множестве нельзя установить взаимное
соответсвие между элементами его любого собственного подмножества.
Если же подобное взаимное соответсвие удавалось установить, получалось
что множество HЕ конечно, что по дихотомии получалось БЕСКОHЕЧHОЕ.
например между X {n E N} и X'{n E N| n > 1} можно установить взаимосоответствие
n'<->n+1
как X[n]=X'[n]+1 X'[n]=X[n]-1.
Hо второе множество не содержит 1 хотя строго включено в X. Получается что оно
подмножество, но такое что устанавливается взаимное соответсвие между его
элементами и элементами множества.
Значит оно Hе конечно, а Hе конечное - Бесконечное.
Пока!
Sashka, The Svin.
Micron Umbarov
>
> RC>> Вот! Что такое "n элементов"? Мы пока не знаем такого понятия, как
> RC>> количество элементов множества.
>
> SY> А что же такое по твоему мощность множества?
>
> Класс множеств, равномощных данному. (По крайней мере, для конечных
множеств
> это определение корректно.)
>
Не может быть. Во-первых, в теориях множеств типа ZFC никаких классов
нет, так что придётся оперировать с несуществующими объектами. Во-вторых, в
тех теориях, в которых классы есть, нельзя образовывать множества классов
(классы от множеств по определению отличаются как раз этим: множество может
быть элементом множества или класса, а класс - не может).
В действительности термин "мощность множества" можно вообще не
использовать, обходясь понятием равномощности. Однако этот термин удобен, и
желательно иметь объект, который можно было бы назвать мощностью множества.
Для этого можно, например, выбрать некоторое каноническое множество,
равномощное данному, и называть его мощностью. В теориях множеств с аксиомой
выбора для этого обычно используются кардиналы. Соответствующую теорию здесь
излагать неуместно, интересующимся следует почитать литературу по теории
множеств (желательно серьёзную, а не издающиеся во множестве ВУЗов пособия с
объяснениями "на пальцах", часто не очень грамотными).
Dmitry Grebeniuk
MU> Эти вопросы обсуждаются также в книге К.Куратовского и А.Мостовского
MU> "Теория множеств". У них отличие состоит в том, что они (совершенно
MU> сознательно) не включают в список аксиом теории множеств так называемую
MU> аксиому регулярности, которая, в частности, запрещает множеству быть
MU> собственным элементом, запрещает бесконечные последовательности
MU> множеств, в которых каждое следующее является элементом предыдущего, и
MU> запрещает циклы, в которых второе множество является элементом первого,
MU> третье - элементом второго,..., последнее - элементо предпоследнего, а
MU> первое - элементом последнего. Отказ от этой аксиомы создаёт некоторые
MU> проблемы (например, приходится специально доказывать, что "натуральное
MU> число" не является своим собственным элементом), но не слишком
MU> существенные.
Hавеpное, кpоме пpоблем у этого подхода есть и какие-то пpеимущества? Если
да, то какие?
Как-то давно (что уже и не помню) я читал, что pаньше существовал какой-то
паpадокс в теоpии множеств, возможный только из-за того, что множество может
быть собственным элементом. И до тех поp, пока не постановили обpатного
(возможно в виде этой самой аксиомы pегуляpности, возможно пpосто не
pассматpивая такие множества), паpадокс пpодолжал омpачать умы. Hе помните,
случаем, как точно там начиналось и чем закончилось? У меня в памяти все
попуталось, а освежать эти знания как-то не было необходимости...
bye
| Двух мнений быть не есть!
Andrei Protasovitski
Alex Kozhushko пишет:
> AP> По-моему, не совсем корректный пример. Во-первых, не определено, что
> AP> такое 2x. Во-вторых, не доказано, что 2x есть натуральное.
> Определяем:
> Double(0) = 0
> Double(S(N))=S(S(Double(N)).
> Теперь 2x=Double(x) определено. И натуральным является - по определению.
Ну, так ему ж нужно было без лишних телодвижений. Я там выше по треду
операцию сложения вводил - не понравилось.
Sashka Yackubtchick
06 Jul 04 18:18, Micron Umbarov писАл(а) к Sashka Yackubtchick:
>> Кстати по поводу "части" и "истинности" БУКВАЛЬHО определение из Мат.
>> Энциклопедии. группы академика Александрова:
>> "Всякое HЕПУСТОЕ подмножество А данного множества В, называют ПРАВИЛЬHОЙ
>> (истинной) ЧАСТЬЮ или собственным подмножеством."
>>
MU> Hельзя ли уточнить, где именно в математической энциклопедии имеется
MU> такое определение? Дело в том, что я как раз происхожу из школы академика
MU> П.С.Александрова, но это определение кажется мне весьма удивительным.
Это купированное определение из БЭС Математика, тут моя мелкая вина - пропустил
многоточие, т.е. я просто опустил слова "отличное от множества В" но не показал
это. Мне не определение нужно было дать а показать использование терминов, что
же такое "часть", "истинное подмножество", "собственное подмножество" мы уже
договорились в предыдущих постах. Дело в том что до этого уже несколько раз я
давал определения о "подмножестве, строго включённом в А но HЕ РАВHОМ А".
Цитата была сделана с единственной целью - мне было заявлено что применяю
придуманные мною слова и термины в области матемаматики где эти термины
отсутсвуют или не применяются. А в частности ИСТИHHОЕ подмножество, ЧАСТЬ,
ЦЕЛОЕ и т.п. Эта цитата должна была показать что они на самом деле "не мной
одним" :) используются, но и дяденьками, которые пишут энциклопедии.
Пока!
Sashka, The Svin.
Micron Umbarov
Вы поступили некорректно, взяв некий текст из одного источника, изменив
его и приписав другому.
Разумеется, Вы имеете право сформулировать собственное определение
собственного подмножества (каламбур, однако...), но уж тогда говорите, что
это Ваше определение. Потому что в общепринятом определении не требуется,
чтобы собственное подмножество множества A было непустым, а зато требуется,
чтобы оно не совпадало с A (такое определение сформулировано, например, в
параграфе 3 главы I книги К.Куратовского и А.Мостовского "Теория множеств").
Употреблять слова "часть" и "целое" в теории множеств не запрещается, но
не следует ожидать, что обозначаемые ими понятия для бесконечных множеств
будут обладать такими же свойствами, как и для конечных.
--
--
Всего наилучшего. Someone.
mailto:um...@newmsk.tula.net
http://www.someoneltd.boom.ru/ http://home.tula.net/frazez/
P.S. Я всё пытаюсь понять, откуда могло взяться (совершенно ненужное)
требование непустоты собственного подмножества? Например, собственное
линейное подпространство линейного пространства не только не совпадает со
всем линейным пространством, но и непусто. Однако линейное пространство (и,
соответственно, любое его линейное подпространство) вообще не может быть
пустым, так как по определению должно содержать нулевой вектор. Но к
произвольным множествам это отношения не имеет.
P.P.S. "Никогда нельзя цитировать по памяти". (Академик
П.С.Александров).
Micron Umbarov
Парадокс, о котором Вы вспоминаете, связывается с именем Рассела и
вызван не столько отсутствием аксиомы регулярности (кстати, если в
аксиоматической теории нет противоречия при наличии какой-нибудь аксиомы, то
его не будет и при отсутствии оной), сколько допущением "слишком больших"
множеств, таких, как множество всех множеств. Аксиома регулярности,
разумеется, запрещает такое множество, ибо оно должно быть своим собственным
элементом, но если эту аксиому отбросить, то это само по себе не приведёт к
появлению подобного множества.
Парадокс этот состоит в следующем. Назовём множество хорошим, если оно
не является своим элементом. Рассмотрим множество всех хороших множеств. В
отношении него естественно спросить, хорошее оно или же нет? Любой ответ на
этот вопрос приводит к противоречию: если это множество хорошее, то оно
должно содержать себя в качестве элемента, что противоречит определению
хорошего множества; если же оно не хорошее, то оно не содержит себя в
качестве элемента и, слодовательно, хорошее.
Существуют варианты теории множеств, в которых, кроме множеств, есть ещё
и классы. В таких теориях допустимо рассматривать класс всех множеств или
класс хороших множеств (в смысле предыдущего абзаца), но классы не могут
быть элементами множеств или классов, поэтому противоречий не возникает.
Вообще, аксиомы теории множеств подобраны так, чтобы сделать возможными
(осуществимыми) все основные конструкции множеств, применяемые в математике,
и в то же время избежать конструкций, приводящих к противоречию. Поэтому,
например, аксиома суммы, требующая существования объединения произвольного
множества множеств, в теории множеств есть, а аксиомы, утверждающей
существование множества всех множеств, нет, поскольку такая аксиома привела
бы к противоречию.
Что касается конкретно аксиомы регулярности, то К.Куратовский и
А.Мостовский в книге "Теория множеств" (глава II, параграф 2) называют эту
аксиому интуитивно очевидной теоремой, независимой от перечисленных ими
аксиом (и говорят о том, что это утверждение в некоторых изложениях теории
множеств принимается в качестве аксиомы), однако сами её не используют.
Причины этого они не объясняют. Скорее всего, просто не хотят вводить
аксиому, которая кажется им не очень нужной.
С другой стороны, трудно придумать математическую задачу, в которой были
бы необходимы множества, содержащие себя в качестве элементов. Поэтому я не
берусь приводить какие-либо доводы в пользу отказа от аксиомы регулярности.
Raoul & Natalia Nakhmanson-Kulish
В твоем письме от Tue, 06 Jul 2004 16:31:56 +0400 было написано:
> Как-то давно (что уже и не помню) я читал, что pаньше существовал какой-то
>паpадокс в теоpии множеств, возможный только из-за того, что множество может
>быть собственным элементом. И до тех поp, пока не постановили обpатного
>(возможно в виде этой самой аксиомы pегуляpности, возможно пpосто не
>pассматpивая такие множества), паpадокс пpодолжал омpачать умы. Hе помните,
>случаем, как точно там начиналось и чем закончилось? У меня в памяти все
>попуталось, а освежать эти знания как-то не было необходимости...
Это известный парадокс Рассела - "парадокс брадобрея". Назовем множества,
которые содержат сами себя в качестве элемента, автоинклюзивными, а не
содержащие - автоэксклюзивными. Очевидно, что таким образом мы делим все
множества на два класса. Вопрос - к какому классу принадлежит множество
автоэксклюзивных множеств?
Деревенский брадобрей бреет тех жителей деревни, кто не бреется сам. Бреет ли
брадобрей сам себя?
--
Счастливой Пачи - Myr
PGP DH/DSS Key ID 0x11807439, Fingerprint dhgGjJy7vbTzfdp+97vZ8hGAdDk=
Текст данного сообщения может свободно копироваться, распространяться
и использоваться в любых целях при соблюдении условий лицензии GNU FDL.
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
Comoderator of Ru.Math
MU> From: "Micron Umbarov" <micr...@newmsk.tula.net>
Стаpайтесь цитиpовать только _действительно_ необходимое, всё-таки не очень
удобно читать Ваше письмо только со втоpой стpаницы.
Bye
Sashka Yackubtchick
07 Jul 04 10:59, Micron Umbarov писАл(а) к Sashka Yackubtchick:
MU> P.S. Я всё пытаюсь понять, откуда могло взяться (совершенно ненужное)
MU> требование непустоты собственного подмножества?
Может быть для того чтобы множества пересечением которых является пустое
подмножество не имели одинаковых Собственных подмножеств?
Пока!
Sashka, The Svin.
Rostislav Chebykin
RC>> Класс множеств, равномощных данному. (По крайней мере, для конечных
RC>> множеств это определение корректно.)
MU> Не может быть.
Согласен.
Кстати, хороший материал на эту тему обнаружился в: Н. Верещагин, А. Шень.
Лекции по математической логике и теории алгоритмов. Теория множеств. М.:
МЦНМО, 2002.
MU> Соответствующую теорию здесь излагать неуместно, интересующимся
MU> следует почитать литературу по теории множеств (желательно серьёзную,
MU> а не издающиеся во множестве ВУЗов пособия с объяснениями "на
MU> пальцах", часто не очень грамотными).
А кстати, какую конкретно литературу посоветовали бы вы?
Вообще говоря, изначальный вопрос про бесконечность N вызван как раз тем,
что я просмотрел несколько вузовских учебников по дискретной математике и
обнаружил, что в них после определения конечных и бесконечных множеств
говорится о бесконечности N как о чём-то само собой разумеющемся, без
какого-либо доказательства.
MU> Без аксиомы выбора может случиться так, что некоторое множество не
MU> будет равномощно никакому множеству вида {0,1,...,n-1} (отнимать
MU> единицу нужно для того, чтобы мощность была равна n), и в то же время
MU> не будет содержать никакого равномощного ему собственного
MU> подмножества.
Это как? Мне пока непонятно.
Rostislav Chebykin
RC>> Да, это понятие определяется через первичные "множество" и
RC>> "принадлежать". А как определить "число элементов", всё ещё неясно.
SY> Значит "элемент" - пронятно", а "число элементов" - непонятно?
SY> Огурец - понятно, число огурцов - непонятно.
SY> Т.е. тоже непонятно что можность пустого множества - 0?
Разумеется. В аксиоматической теории любое понятие должно быть определено
через исходные.
Рекомендую, например, для общего ознакомления книгу: В. А. Успенский. Что
такое аксиоматический метод?
Micron Umbarov
>
> MU> P.S. Я всё пытаюсь понять, откуда могло взяться (совершенно
ненужное)
> MU> требование непустоты собственного подмножества?
>
> Может быть для того чтобы множества пересечением которых является пустое
> подмножество не имели одинаковых Собственных подмножеств?
>
Непонятно, почему такое условие может быть настолько важным, чтобы
требовать его для ВСЕХ случаев. Напротив, в упомянутой книге К.Куратовского
и А.Мостовского "Теория множеств" определение собственного подмножества
даётся без требования непустоты. Аналогичные определения можно найти в
следующих книгах:
Р.Энгелькинг, "Общая топология" (Введение, пункт I.1);
А.В.Архангельский, В.И.Пономарёв, "Основы общей топологии в задачах и
упражнениях" (Глава I).
Я был несколько удивлён, когда нашёл в книге П.С.Александрова "Введение
в теорию множеств и общую топологию" как раз Ваше определение собственного
подмножества: непустое и не совпадающее со всем множеством. Как ни странно,
собственные ученики П.С.Александрова (А.В.Архангельский и В.И.Пономарёв) со
своим учителем в этом вопросе не согласны. А я - ученик В.И.Пономарёва.
Вообще, определение собственного подмножества встречается далеко не в
каждой книге, посвящённой теории множеств или её применениям. Видимо,
понятие это хотя и часто встречающееся, но не обязательное. И, как это часто
бывает в подобных случаях, существуют неэквивалентные определения, причём,
один из вариантов встречается в подавляющем большинстве случаев, а второй
относительно редок. Сказанное, естественно, не означает, что такое
соотношение будет всегда.
Думаю, дискуссию на эту тему пора заканчивать. Вряд ли к ней можно
добавить что-нибудь существенное.
--
--
Всего наилучшего. В.М.Ульянов AKA Someone.
Micron Umbarov
>
> А кстати, какую конкретно литературу посоветовали бы вы?
>
Ну, я не большой знаток литературы по теории множеств. У меня есть,
например, "Справочная книга по математической логике", упоминавшаяся уже
здесь книга К.Куратовского и А.Мостовского, и ещё некоторая более
специальная литература. Возможно, специалисты по теории множеств укажут Вам
более подходящую литературу.
>
> Вообще говоря, изначальный вопрос про бесконечность N вызван как раз тем,
> что я просмотрел несколько вузовских учебников по дискретной математике и
> обнаружил, что в них после определения конечных и бесконечных множеств
> говорится о бесконечности N как о чём-то само собой разумеющемся, без
> какого-либо доказательства.
>
Термин "дискретная математика" меня несколько удивляет (это не означает,
что я его встречаю впервые). По-моему, сюда включают всё, что не использует
понятия производной.
>
> MU> Без аксиомы выбора может случиться так, что некоторое множество не
> MU> будет равномощно никакому множеству вида {0,1,...,n-1} (отнимать
> MU> единицу нужно для того, чтобы мощность была равна n), и в то же время
> MU> не будет содержать никакого равномощного ему собственного
> MU> подмножества.
>
> Это как? Мне пока непонятно.
>
Ситуация примерно такая.
Если некоторое множество X равномощно собственному подмножеству Y, то
существует взаимно однозначное отображение f: X -> Y. При этом существует
некоторый элемент a0, принадлежащий X, но не принадлежащий Y. Тогда можно
построить последовательность a1=f(a0), a2=f(a1),..., равномощную
натуральному ряду (пользуясь индукцией). Аксиома выбора здесь не нужна, так
как считается, что один элемент из непустого множества можно извлечь без
оной (если X\Y непусто, то существует элемент a0, принадлежащий X\Y; вот
его-то и берём).
Но без аксиомы выбора можно столкнуться со следующей ситуацией:
множество X содержит подмножество, равномощное каждому натуральному числу n
(рассматриваемому как множество {0,1,2,...,n-1}), но не содержит
подмножества, равномощного натуральному ряду. В самом деле, как можно было
бы построить такое подмножество? Например, так: берём a0 из X, потом a1 из
X\{a0}, потом a1 из X\{a0,a1}, и так далее. Любое конечное множество
элементов таким образом получается, но осуществить выбор из бесконечного
множества множеств без аксиомы выбора, пользуясь только остальными аксиомами
теории множеств, нельзя. Это рассуждение, естественно, не является
доказательством того, что "нельзя", но существуют модели теории множеств, в
которых действительно "нельзя".
Если же мы принимаем аксиому выбора, то проблема разрешается: можно
вполне упорядочить множество X; взяв наименьший элемент x0, которому
предшествует бесконечное множество элементов множества X, мы можем взять в
качестве подмножества, равномощного натуральному ряду, множество X0
элементов, предшествующих элементу x0. Теперь взаимно однозначное
отображение множества X на собственное подмножество получается очень просто:
каждому элементу x подмножества X0 сопосталяем следующий (в смысле
найденного только что полного порядка) элемент, а остальные элементы
множества X оставляем на месте (кстати, поскольку всё множество X вполне
упорядочено, можно вообще каждому его элементу сопоставлять следующий
элемент). Так как наименьший элемент не будет поставлен в соответствие
никакому элементу множества X, то получается взаимно однозначное отображение
на собственное подмножество.
Micron Umbarov
>
> множества X оставляем на месте (кстати, поскольку всё множество X вполне
> упорядочено, можно вообще каждому его элементу сопоставлять следующий
> элемент). Так как наименьший элемент не будет поставлен в соответствие
> никакому элементу множества X, то получается взаимно однозначное
отображение
> на собственное подмножество.
>
Сейчас сам перечитал и вижу, что, сформулировав оговорку в скобках,
сморозил глупость. Хорошо, если в множестве X нет последнего элемента. А что
делать, если он есть? Фокус, конечно, в том, что в этом случае, кроме
наименьшего, есть ещё хотя бы один элемент, не имеющий непосредственного
предшественника, и последний элемент можно отобразить в него, но это
совершенно ненужное осложнение.
Rostislav Chebykin
MU> Термин "дискретная математика" меня несколько удивляет (это не
MU> означает, что я его встречаю впервые). По-моему, сюда включают всё,
MU> что не использует понятия производной.
Насколько я могу судить, "дискретная математика" - это получается что-то
вроде общей математической грамотности. В эту дисциплину обычно собирают
начальные кусочки других, которые не изучаются (в данном институте, на
данном потоке и пр.) сами по себе. Например, на математическом факультете
МПГУ математическая логика и высшая алгебра - отдельные предметы, а в МИФИ
основы и того, и другого включены в дискретную математику. Также в
дискретной математике мне попадались основы теории множеств, теории чисел (в
частности, всё, что касается делимости, вычетов, простых чисел и пр.),
комбинаторики, теории графов, теории алгоритмов... Например, сейчас в
магазинах продается толстенный учебник Дж. Андерсона "Дискретная математика
и комбинаторика" - так там "с миру по нитке" от каждого раздела математики и
кибернетики - тут тебе и матрицы, и теория рекурсии, и производящие функции,
и раскрашивание карт, и сети Петри...
P.S. Спасибо за доказательство и сопутствующие разъяснения. Хотел бы я быть
таким "не специалистом в теории множеств", как вы о себе говорите...
Sashka Yackubtchick
12 Jul 04 22:00, Rostislav Chebykin писАл(а) к Micron Umbarov:
RC> Hасколько я могу судить, "дискретная математика" - это получается что-то
RC> вроде общей математической грамотности.
:)
Дискретная мат. изучает дискретные структуры.
В отличии от изучания непрерывных объектов (в основном) в классической
математике. Hа самом деле деление на дискретную и непрерывную математику
довольно условно. Методы "гуляют" туда-сюда. Кнут и Поташник отразили это в
названии своей книжки, объединив часть слов непрерывная и дискретная.
Пока!
Sashka
Micron Umbarov
>
> RC> Hасколько я могу судить, "дискретная математика" - это получается
что-то
> RC> вроде общей математической грамотности.
>
> Дискретная мат. изучает дискретные структуры.
> В отличии от изучания непрерывных объектов (в основном) в классической
> математике. Hа самом деле деление на дискретную и непрерывную математику
> довольно условно. Методы "гуляют" туда-сюда. Кнут и Поташник отразили это
в
> названии своей книжки, объединив часть слов непрерывная и дискретная.
>
Потрясающе. А что такое "дискретная" или "непрерывная" структура? Почему
вдруг теория множеств, алгебра и математическая логика попали в число
"дискретных"?
Было бы более или менее логично, если бы "дискретная математика"
ассоциировалась с конечными множествами и структурами, но реально в разных
пособиях и книгах по "дискретной математике" можно найти буквально что
угодно. Я просто выразил в связи с этим своё недоумение совершенно
неопределённым употреблением термина "дискретная математика", который таким
образом практически лишается смысла.
Боюсь, однако, что ограничение "дискретной математики" конечными
объектами реально приведёт к ликвидации такого понятия вообще (и я бы это
приветствовал). Даже если взять такой совершенно конечный объект, как
алгоритм (он конечный, так как записывается конечной последовательностью
символов), то правомерность его отнесения к дискретной математике как
теории, изучающей "дискретные" структуры, вызывает у меня большие сомнения.
Ибо такое отнесение автоматически сделает "дискретной" всю конструктивную
математику, а это нонсенс. Чем конструктивный вариант математического
анализа так радикально отличается от классического математического анализа,
что его нужно считать "дискретным", в то время как классический анализ -
"непрерывным"? Оба они содержат понятие непрерывной функции, производной,
интеграла и так далее.
В общем, разделение математики на "дискретную" и "непрерывную" выглядит
совершенно нелогичным и (в настоящее время) совершенно неопределённым. Я
всегда считал математику единой, несмотря на очевидное несходство отдельных
её ветвей. Но все они, несмотря на внешнее несходство, имеют некую общую
часть, а методы, как Вы совершенно справедливо заметили, "гуляют туда-сюда".
--
--
Всего наилучшего. Someone.
mailto:um...@newmsk.tula.net
http://www.someoneltd.boom.ru/ http://home.tula.net/frazez/
P.S. Объяснение Ростислава Чебукина меня вполне устроило.
Micron Umbarov
>
> Если же мы принимаем аксиому выбора, то проблема разрешается: можно
> вполне упорядочить множество X; взяв наименьший элемент x0, которому
> предшествует бесконечное множество элементов множества X, мы можем взять в
> качестве подмножества, равномощного натуральному ряду, множество X0
> элементов, предшествующих элементу x0. Теперь взаимно однозначное
> отображение множества X на собственное подмножество получается очень
просто:
> каждому элементу x подмножества X0 сопосталяем следующий (в смысле
> найденного только что полного порядка) элемент, а остальные элементы
> множества X оставляем на месте (кстати, поскольку всё множество X вполне
> упорядочено, можно вообще каждому его элементу сопоставлять следующий
> элемент). Так как наименьший элемент не будет поставлен в соответствие
> никакому элементу множества X, то получается взаимно однозначное
отображение
> на собственное подмножество.
>
Господи, как же неудачно у меня получилось. Явно теряю квалификацию.
Собственно говоря, почему должен существовать элемент, которому
предшествует бесконечное число элементов?
Вполне упорядочив множество X, не равномощное никакому натуральному
числу, мы можем получить два случая.
1) В множестве X нет наибольшего элемента. Тогда мы можем сопоставить
каждому элементу непосредственно следующий за ним (наименьший, который
больше рассматриваемого элемента). Так как наибольшего элемента нет,
получается взаимно однозначное отображение множества X на некоторое его
подмножество Y. Так как наименьший элемент X не принадлежит Y, то Y является
собственным подмножеством X (возможно, существуют и другие элементы
множества X, не принадлежащие Y).
2) В множестве X есть наибольший элемент. Обозначим его x1. Множество
элементов, меньших x1, бесконечно (в смысле - не равномощно никакому
натуральному числу). Обозначим X1 множество тех элементов y множества X, для
которых множество {x: x<y} бесконечно. Это множество непусто, так как
содержит x1. Пусть x0 - наименьший элемент множества X1 (такой элемент x0
существует, так как X вполне упорядочено), и пусть X0={x: x<x0}. Каждому
элементу множества X0 сопоставим непосредственно следующий за ним, а каждому
элементу x из X\X0 поставим в соответсвие сам x. Получается взаимно
однозначное отображение X на подмножество Y. Как и в первом случае, Y
является собственным подмножеством X, так как наименьший элемент X не
принадлежит Y.
Evgenij Masherov
>>
>> RC> Hасколько я могу судить, "дискретная математика" - это получается
MU> что-то
>> RC> вроде общей математической грамотности.
>>
>> Дискретная мат. изучает дискретные структуры.
>> В отличии от изучания непрерывных объектов (в основном) в классической
>> математике. Hа самом деле деление на дискретную и непрерывную математику
>> довольно условно. Методы "гуляют" туда-сюда. Кнут и Поташник отразили это
MU> в
>> названии своей книжки, объединив часть слов непрерывная и дискретная.
>>
MU> Потрясающе. А что такое "дискретная" или "непрерывная" структура?
MU> Почему вдруг теория множеств, алгебра и математическая логика попали в
MU> число "дискретных"?
MU> Было бы более или менее логично, если бы "дискретная математика"
MU> ассоциировалась с конечными множествами и структурами, но реально в
MU> разных пособиях и книгах по "дискретной математике" можно найти буквально
MU> что
MU> угодно. Я просто выразил в связи с этим своё недоумение совершенно
MU> неопределённым употреблением термина "дискретная математика", который
MU> таким образом практически лишается смысла.
MU> Боюсь, однако, что ограничение "дискретной математики" конечными
MU> объектами реально приведёт к ликвидации такого понятия вообще (и я бы это
MU> приветствовал). Даже если взять такой совершенно конечный объект, как
MU> алгоритм (он конечный, так как записывается конечной последовательностью
MU> символов), то правомерность его отнесения к дискретной математике как
MU> теории, изучающей "дискретные" структуры, вызывает у меня большие
MU> сомнения.
MU> Ибо такое отнесение автоматически сделает "дискретной" всю конструктивную
MU> математику, а это нонсенс. Чем конструктивный вариант математического
MU> анализа так радикально отличается от классического математического
MU> анализа, что его нужно считать "дискретным", в то время как классический
MU> анализ - "непрерывным"? Оба они содержат понятие непрерывной функции,
MU> производной, интеграла и так далее.
MU> В общем, разделение математики на "дискретную" и "непрерывную"
MU> выглядит совершенно нелогичным и (в настоящее время) совершенно
MU> неопределённым. Я всегда считал математику единой, несмотря на очевидное
MU> несходство отдельных
MU> её ветвей. Hо все они, несмотря на внешнее несходство, имеют некую общую
MU> часть, а методы, как Вы совершенно справедливо заметили, "гуляют
MU> туда-сюда".
ИМХО разделение математики на "непрерывную" и "дискретную" носит не
математический, а педагогический характер (впрочем, так же, как разделение
математики на "элементарную" и "высшую"). При этом речь идет не об обучении
математике как профессии, но как инструменту.
Скажем, традиционная инженерная подготовка (а также экономиста серьезного
уровня, исследователя в области медицины, физика...) требовала умения брать
интегралы, решать дифуравнения и т.п. Этот, превосходивший школьные
требования, уровень был наименован "высшей математикой". Объединяло его
дисциплины необходимость перехода к пределу. Однако инженеру понадобилась
матлогика, физику теория групп, экономисту комбинаторика и т.п.. Все эти
дисциплины не могли быть отнесены к "элементарной" математике, но не
использовали понятие предела вообще. Вот и ввели название "дискретная
математика" под которым во многих технических ВУЗах читается вводный курс, где
немного из теории множеств, немного из комбинаторики, немного из матлогики.
Если же есть потребность и возможность давать эти дисциплины всерьез - то
никакого курса "дискретной математики" не возникает, хотя, возможно, по
административным причинам создается кафедра "дискретной математики".
Существует набор методов
Евгений Машеров АКА СанитарЖеня
Raoul & Natalia Nakhmanson-Kulish
В твоем письме от Thu, 15 Jul 2004 13:25:20 +0000 (UTC) было написано:
> В общем, разделение математики на "дискретную" и "непрерывную" выглядит
>совершенно нелогичным и (в настоящее время) совершенно неопределённым.
Тем не менее отсутствие непрерывности прописалось в матфизике уже давно -
дельта-функция тому яркий пример.
Последние веяния в квантовой теории поля (квантовые петли, некоммутативная
геометрия) только усиливают эту тенденцию, делая явной ее тесную связь с
теорией информации (энтропия эквивалентна информации, а информация дискретна).
Micron Umbarov
>
> > В общем, разделение математики на "дискретную" и "непрерывную"
выглядит
> >совершенно нелогичным и (в настоящее время) совершенно неопределённым.
> Тем не менее отсутствие непрерывности прописалось в матфизике уже давно -
> дельта-функция тому яркий пример.
>
> Последние веяния в квантовой теории поля (квантовые петли, некоммутативная
> геометрия) только усиливают эту тенденцию, делая явной ее тесную связь с
> теорией информации (энтропия эквивалентна информации, а информация
дискретна).
>
Дельта-функция и прочие упомянутые Вами вещи, включая квантовую механику
и теорию информации, не имеют к обсуждаемому вопросу сколько-нибудь
существенного отношения. В особенности - дельта-функция. Та же квантовая
механика базируется на математическом аппарате, который к "дискретной"
математике можно отнести только при совершенно невероятной фантазии. Что
означает "дискретность" информации - не знаю. Если Вы хотите сказать, что
она измеряется целым числом (простите меня за это предположение), то Вы не
правы. Например, эксперимент с тремя равновероятными исходами даёт
количество информации, равное двоичному логарифму трёх - число не только не
целое, но даже не алгебраическое.
Я согласен с теми, кто считает "дискретную" математику явлением
педагогическим или организационным (так же, как "элементарную" или
"высшую"). К самой математике всё это отношения не имеет.
То, что со временем одни математические методы практически выходят из
употребления, а другие, напротив, становятся вдруг чрезвычайно нужными и
популярными, совершенно естественно. Также естественно то, что в математике
время от времени появляются новые методы и целые новые области.
Высказывая недоумение по поводу термина "дискретная математика", я вовсе
не хотел затевать какую-либо дискуссию. Не нужно мне доказывать, что в
математике есть какая-то совершенно особая часть, называемая "дискретной
математикой", радикально отличающаяся от всей прочей математики и никак с
ней не связанная. Я всё равно с этим не соглашусь.
Raoul & Natalia Nakhmanson-Kulish
В твоем письме от Fri, 16 Jul 2004 09:46:08 +0000 (UTC) было написано:
> Дельта-функция и прочие упомянутые Вами вещи, включая квантовую механику
>и теорию информации, не имеют к обсуждаемому вопросу сколько-нибудь
>существенного отношения. В особенности - дельта-функция. Та же квантовая
>механика базируется на математическом аппарате, который к "дискретной"
>математике можно отнести только при совершенно невероятной фантазии.
Это понятно :) но, скажем, теория конечных групп - вполне себе "дискретная"
математика и имеет прямое приложение в КТП.
>Что
>означает "дискретность" информации - не знаю. Если Вы хотите сказать, что
>она измеряется целым числом (простите меня за это предположение), то Вы не
>правы.
Разумеется нет :) но обмен информацией (=энтропией) - всегда дискретный
процесс.
Sashka Yackubtchick
15 Jul 04 17:25, Micron Umbarov писАл(а) к Sashka Yackubtchick:
MU> Потрясающе. А что такое "дискретная" или "непрерывная" структура?
Есть ещё Аристотелевское определение (Категории. Глава 6. Количество)
Hо тебе нужно наверно современное, такие даются в справочниках и энциклопедиях
которые, наверно, у нас обоих есть.
MU> Почему вдруг теория множеств, алгебра и математическая логика попали
MU> в
MU> число "дискретных"?
Классическую алгебру тоже причислили к дискретным?
Hаверно только методы спроецированные на решение конечных задач?
Или я что-то не понимаю...
MU> Hо все они, несмотря на внешнее
MU> несходство, имеют некую общую часть, а методы, как Вы совершенно
MU> справедливо заметили, "гуляют туда-сюда".
Дык :)
MU> P.S. Объяснение Ростислава Чебукина меня вполне устроило.
Моё дело было подчеркнуть что разницу в справочной литературе до сих пор
определяют через понятия "непрерывных" и "дискретных" объектов.
И хотя я с Санитаром Женей (по эмпирике) склонен согласится, само слово
"дискретная математика" это ведь не в нашем образовании появилось, оно и в
Страндфорде существует как и "непрерываная матеметика" и не только как способ
обозвать по разному кафедры. И так же в согласии с твоими словами - существует
и там "неуютность" и дисскуссии по поводу условности этого деления.
В книге о которой я упомянул "CONCRETE MATHEMATICS" отчасти отзвуки этих
дисскуссий, а также что понимают под этим по ту сторону океана.
Пока!
Sashka, The Svin.
Micron Umbarov
>
> MU> Потрясающе. А что такое "дискретная" или "непрерывная" структура?
>
> Есть ещё Аристотелевское определение (Категории. Глава 6. Количество)
> Hо тебе нужно наверно современное, такие даются в справочниках и
энциклопедиях
> которые, наверно, у нас обоих есть.
>
Посмотрел я статью В.Б.Кудрявцева в "Математической энциклопедии".
Основная идея - отнести к дискретной математике всё, что связано с конечными
множествами и структурами (может быть, понимая эту конечность в несколько
расширенном смысле). Эта идея просто "вырывает" из различных областей
математики отдельные фрагменты, которые, конечно, можно изучать в таком
виде, но, как показывает практика, при этом "кое-что" теряется. Например,
натуральные числа - объекты явно конечные, но при их изучении вдруг
откуда-то вылезает дзета-функция, а она в число "конечных" объектов никак не
вписывается. И обойтись без неё никак не удаётся. (Кстати, и наоборот - при
изучении бесконечных и "непрерывных" объектов появлются объекты явно
конечные и дискретные).
Другая идея - включение в дискретную математику так называемых
"дискретных" структур. Что это такое - никто, естественно, не знает (в том
смысле, что формального определения нет). Конечно, в топологии есть понятие
дискретного пространства, но почему непременно нужно связываться с
топологией? Может быть, считать дискретным любой объект, на котором не
определена никакая топология? Боюсь, что тогда дискретная математика
поглотит почти всё. К тому же, на топологии свет клином не сошёлся, и вполне
возможны структуры, в некотором смысле аналогичные топологии. В результате
ситуация становится совершенно неопределённой.
К тому же, можно проделать следующий фокус. Известно, что всю математику
целиком формализовать не удаётся. Однако каждый грамотный математик
понимает, как формализовать то, чем он занимается. Нужно, в общем-то,
немного: определить формальный язык и набор аксиом. В языке, скорее всего,
будет бесконечное множество формул, да и набор аксиом может быть бесконечным
(как, например, в теории множеств Цермело - Френкеля), но никакой топологии
на множестве формул или аксиом не требуется, да и сами эти множества как
таковые не нужны. При этом каждое утверждение теории и каждый её объект
будет описываться конечной последовательностью символов. И, поскольку
формальная теория имеет дело только с этими конечными последовательностями
символов, мы будем вынуждены ВСЮ математику считать дискретной.
Думаю, что со временем просто стабилизируется некоторый достаточно
произвольный перечень областей математики, которые будут относить к
дискретной математике - так же, как это произошло с элементарной
математикой.
>
> MU> Почему вдруг теория множеств, алгебра и математическая логика попали
> MU> в
> MU> число "дискретных"?
>
> Классическую алгебру тоже причислили к дискретным?
> Hаверно только методы спроецированные на решение конечных задач?
> Или я что-то не понимаю...
>
Я тоже не понимаю. Недавно мне показывали весьма объёмистое учебное
пособие "Дискретная математика", и там я обнаружил довольно много алгебры.
Конечно, теорию конечных групп или конечных булевых алгебр можно отнести к
дискретной математике (но термина "конечная группа" там не было,
рассматривались группы вообще и булевы алгебры вообще), однако там были и
такие вещи, как линейные пространства и линейные операторы.
>
> Моё дело было подчеркнуть что разницу в справочной литературе до сих пор
> определяют через понятия "непрерывных" и "дискретных" объектов.
>
Это просто апелляция к топологии. Мне, как топологу, может быть, и
приятно, что "водораздел" определяется топологией, но, как математику, повод
для размежевания кажется неубедительным.
>
> И хотя я с Санитаром Женей (по эмпирике) склонен согласится, само слово
> "дискретная математика" это ведь не в нашем образовании появилось, оно и в
> Страндфорде существует как и "непрерываная матеметика" и не только как
способ
> обозвать по разному кафедры. И так же в согласии с твоими словами -
существует
> и там "неуютность" и дисскуссии по поводу условности этого деления.
> В книге о которой я упомянул "CONCRETE MATHEMATICS" отчасти отзвуки этих
> дисскуссий, а также что понимают под этим по ту сторону океана.
>
"Неуютность" там явно коррелирует с моими "недоумениями" здесь.
Как я уже сказал, со временем "утрясётся".
Micron Umbarov
>
> >существенного отношения. В особенности - дельта-функция. Та же квантовая
> >механика базируется на математическом аппарате, который к "дискретной"
> >математике можно отнести только при совершенно невероятной фантазии.
> Это понятно :) но, скажем, теория конечных групп - вполне себе
"дискретная"
> математика и имеет прямое приложение в КТП.
>
Гораздо большее приложение в КТП имеет теория непрерывных групп.
>
> Разумеется нет :) но обмен информацией (=энтропией) - всегда дискретный
> процесс.
>
Вообще в квантовой механике взаимодействие носит дискретный характер, но
почему-то оно описывается главным образом с помощью существенно непрерывных
математических объектов.
Raoul & Natalia Nakhmanson-Kulish
В твоем письме от Mon, 19 Jul 2004 20:51:10 +0000 (UTC) было написано:
>> Это понятно :) но, скажем, теория конечных групп - вполне себе
>"дискретная"
>> математика и имеет прямое приложение в КТП.
> Гораздо большее приложение в КТП имеет теория непрерывных групп.
Ой ли? Примерчик можно? Обратных - навалом, начиная с хромодинамики и кончая
разными суперсимметричными конструкциями.
> Вообще в квантовой механике взаимодействие носит дискретный характер, но
>почему-то оно описывается главным образом с помощью существенно непрерывных
>математических объектов.
Типичная квантовомеханическая задача на расчет взаимодействия - поиск
стационарных состояний связанных систем, а они для подавляющего большинства
практически интересных задач - от кварков в адроне до молекулы ДНК -
описываются конечными матрицами.
Да и с фундаментальными взаимодействиями все не так просто, перенормировки
лишают всякой надежды на непрерывность котинуума. А ты думал, квантовые петли и
некоммутативную геометрию придумывают от хорошей жизни?
Alexey Popov
> > Гораздо большее приложение в КТП имеет теория непрерывных групп.
> Ой ли? Примерчик можно? Обратных - навалом, начиная с хромодинамики и кончая
> разными суперсимметричными конструкциями.
И где же там дискретные группы? В основном работа идёт с калибровочнымигруппами - все они
непрерывны. В хромодинамике - SU(3).
В суперсимметрии вообще особо групп нет, помимо обычных. Там в основном
одни алгебры.
> > Вообще в квантовой механике взаимодействие носит дискретный характер, но
> >почему-то оно описывается главным образом с помощью существенно непрерывных
> >математических объектов.
> Типичная квантовомеханическая задача на расчет взаимодействия - поиск
> стационарных состояний связанных систем,
Как раз таки это задача нетипичная, т.к. даже приближённые методы очень
трудоёмки,т.к. сводятся с системе бесконечного числа уравнений. В
основном вычисляют всякие амплитуды или сечения.
> а они для подавляющего большинства
> практически интересных задач - от кварков в адроне до молекулы ДНК -
> описываются конечными матрицами.
Как это конечными? Нужно искать собственные значения операторав гильбертовом пространстве. Где же
тут конечность? С учём ещё того
что спектр бывает и непрерывным.
> Да и с фундаментальными взаимодействиями все не так просто, перенормировки
> лишают всякой надежды на непрерывность котинуума.
С какой это кстати? Во первых, существуют теории свободные от расходимостей.Во вторых, из того что
какая то теория имеет расходимости совершенно не
следует каких то выводов о пространстве.
> А ты думал, квантовые петли и
> некоммутативную геометрию придумывают от хорошей жизни?
Хм, смелое заявление ;-) Некоммутативная геометрия - это вообще
убийца всякой дискретности в представлении о пространстве. ;-)
--
--- Home Page http://ok.novgorod.net/ap ---
Micron Umbarov
>
> >> Это понятно :) но, скажем, теория конечных групп - вполне себе
> >"дискретная"
> >> математика и имеет прямое приложение в КТП.
> > Гораздо большее приложение в КТП имеет теория непрерывных групп.
> Ой ли? Примерчик можно? Обратных - навалом, начиная с хромодинамики и
кончая
> разными суперсимметричными конструкциями.
>
А что, группа Лоренца в квантовой механике уже не нужна? Насколько я
помню, она вообще является основной, а все другие группы - конечные или
бесконечные, дискретные или непрерывные - уже связаны с более "конкретными"
вопросами. Но я не специалист в квантовой механике, тем более - в
современной КТП. Поэтому спорить с Вами всерьёз не берусь.
А какая конечная группа описывает, например, квантовую хромодинамику?
>
> описываются конечными матрицами.
>
А почему, собственно говоря, конечная матрица - дискретный объект? Разве
только в том смысле, что любой единичный объект, взятый сам по себе, без
связи с чем либо,
>
> Да и с фундаментальными взаимодействиями все не так просто, перенормировки
> лишают всякой надежды на непрерывность котинуума. А ты думал, квантовые
петли и
> некоммутативную геометрию придумывают от хорошей жизни?
>
Как устроено то, что Вы называете "континуумом" (то есть, "сплошным",
"непрерывным"), мы не знаем. То, с чем мы имеем дело в теории - всего лишь
математические модели, которые могут быть более или менее удачными.
Расходимости, перенормировки и прочие "прелести" скорее всего означают,
что адекватного математического аппарата пока нет. Разработать его не
берусь.
Вообще, дискуссия ушла куда-то в сторону. Я же никогда не утверждал, что
конечные группы ни для чего не нужны. Речь шла всего лишь о том, что объём
того, что называют "дискретной математикой", мне непонятен.
Sashka Yackubtchick
15 Jul 04 17:25, Micron Umbarov писАл(а) к Sashka Yackubtchick:
MU> Потрясающе. А что такое "дискретная" или "непрерывная" структура?
MU> Почему вдруг теория множеств, алгебра и математическая логика попали в
MU> число "дискретных"?
Hаведя по обыкновению справки "о корнях" термина, прихожу к выводу что
изначально термин был связан с вычислительной математикой и кибернетикой :)
Вот пара цитат, по теме
Колмогоров:
=== Cut ===
Hа основе задач теории управляющих систем, комбинаторного анализа, графов
теории, теории кодирования возникла дискретная, или конечная математика.
=== Cut ===
Успенский в статье о Колмогорове:
=== Cut ===
Hа Первой Всесоюзной Конференции (Симпозиуме) по Математической Логике в
Алма-Ате в июне 1969 года часовой обзорный доклад был сделан одним из лидеров
молодой тогда советской школы в математической кибернетике (позже вошёл в
употребление термин "дискретная математика"). === Cut ===
Вот из методички для преподователей информатики:
=== Cut ===
В настоящее время под дискретной математикой обычно понимают совокупность
математических средств, способных оказать эффективную помощь при исследовании
конечных множеств. Создание таких средств является весьма актуальной задачей.
Дело в том, что до сих пор основным методом дискретной математики остается
перебор. Однако очень часто при попытках решения комбинаторных оптимизационных
задач методом перебора мы сталкиваемся с эффектом, который математики назвали
"комбинаторным взрывом" (экспоненциальный рост числа перебираемых вариантов).
Иллюстрацией этому служит хорошо известная задача о коммивояжере. Разумеется,
перебрать все возникающие варианты не под силу даже самым мощным ЭВМ. Выход
заключается в сокращении перебора до разумных пределов. Если это удается
сделать, то достигается поразительный эффект. Примером служит метод
динамического программирования. Поэтому интерес к дискретной математике вполне
понятен. Однако при чтении курса по дискретной математике возникают
значительные трудности. Причина в том, что в дискретной математике отсутствует
ядро, подобное дифференциальному и интегральному исчислениям в математическом
анализе. Поэтому отбор основных понятий и методов, включаемых в читаемый курс,
в значительной мере зависит от того, кому этот курс предназначен. Предлагаемый
курс по дискретной математике в первую очередь адресован будущим учителям
информатики. Поэтому в нем значительное внимание уделено основополагающим
понятиям и решению связанных с этими понятиями задач.
=== Cut ===
Пока!
Sashka, The Svin.