Теория множеств, счетность и континуум Опции

[Надин]

Мне опять приходится обращаться к Вам за помощью. Чем ближе к сессии, тем глупее я себя чувствую, в голове либо слишком много всего, либо совсем пусто. Не знаю, что делать... Помогите, пожалуйста!!!! Мой препод по матлогу меня не любит и специально дает задачи, к которым я не знаю с какой стороны подступиться!!! ПОЖАЛУЙСТА!!!!!

1.Доказать, что множество всех типов вида n/(2)^k + m/(3)^r, где n,m,r,k-натуральные числа, счетно.
2.Доказать, что множество всех бесконечных неубывающих последовательностей натуральных чисел имеет мощность континуума.

На интуитивном уровне все дейтсвительно понятно, но как объяснить это преподу.

[Lapp]

Надин, пожалуйста, не вали все в одну тему, создавай новые.

1. Что значит "типов"? Если речь идет про числа такого вида, то конечно, они счетны, поскольку натуральные счетны.. Уточни, пожалуйста.

[Надин]

С удовольствием уточнила бы, но препод со мной разговаривать сегодня не собирался...
Но кроме как множество всех чисел вида и т.д, ничего в голову не приходит.

Т.е существует взаимнооднозначное соответсвие между числами подобного типа и множеством натуральных чисел, которое счетно...
Или числа данного типа взаимнооднозначно отображаются в подмножество рациональных чисел, которое счетно.Подмножество счетного множества,не более, чем счетно. Конечным оно быть не может,т.к. нутаральных чисел бесконечно много...

[Lapp]

кроме как множество всех чисел вида и т.д, ничего в голову не приходит.

Ну, если это просто числа такого вида, то все очень просто. Их можно отобразить на множество целых положительных точек в четырехмерном пространстве в декартовых координатах. Для начала представь себе двумерное (что, кстати, соответствует просчету пар, то есть доказывает счетность рациональных чисел). Это выглядит примерно так:

^
| . . . . . . . . .
| . . . . . . . . .
| . . . . . . . . .
| . . . . . . . . .
| . . . . . . . . .
| . . . . . . . . .
+------------------->

- их можно пересчитать с помощью уже известной тебе змейки. Попробуй представить себе, как ляжет змейка в трехмерном пространстве - это неплохая разминка для пространственого воображения. Далее, если преп поверит тебе на слово, что ты можешь сделать змейку в четырехмерном пространстве ("У каждой женщины должна быть змея.." © Аквариум), то все ок, если нет - то дай ему такой агоритм:

1 1 1 1
2 1 1 1
1 2 1 1
1 1 2 1
1 1 1 2
2 2 1 1
2 1 2 1
2 1 1 2
2 2 2 1
2 2 1 2
2 2 2 2
3 1 1 1
3 2 1 1
3 1 2 1
3 1 1 2
3 2 2 1
3 2 1 2
3 2 2 2
3 3 1 1
3 3 2 1
3 3 1 2
3 3 2 2
3 3 3 1
3 3 3 2
3 3 3 3
4 1 1 1
4 2 1 1
. . . .
- ой, я, кажется, увлекся.. Затягивает, как семечки
Короче, все это хозяйство пересчитывается легко.

2.Доказать, что множество всех бесконечных неубывающих последовательностей натуральных чисел имеет мощность континуума.

А тут тебе нужно использовать Канторову диагональ, но несколько модифицированную. Начать надо с того, что сузить данное множество. Возьмем только те последовательности, которые не имеют предела (или их предел равен плюс бесконечности). Далее от противного: предположим, что их множество счетно. Расположим их в том порядке, в котором они просчитаны:

1.  a1  a2  a3  a4  a5  a6  a7  a8 ...
2.  b1  b2  b3  b4  b5  b6  b7  b8 ...
3.  c1  c2  c3  c4  c5  c6  c7  c8 ...
4.  d1  d2  d3  d4  d5  d6  d7  d8 ...
5.  e1  e2  e3  e4  e5  e6  e7  e8 ...
6.  ............
..........

Теперь составим номую последовательность {Xn}. Первый элемент возьмем такой
x1 = a1 + 1
Далее переходим ко второй последовательности, {Bn}, и действем по такому правилу:
- начинаем со второго элемента, b2.
- если он больше либо равен x1, то полагаем x2 = b2 + 1,
- если нет, то x2 = x1 и переходим к b3.
- так находим элемент последовательности {B}, больше либо равный x1, по пути заполняя пустые места значением x1. Означенный элемент должен найтись обязательно в соотвествии с определением предела (мы взяли только те последовательности, которые стремятся к бесконечности). Обозначим его номер в {B} как n2. Полагаем xn2=bn2+1.
- Теперь переходим к последовательности {C}, начав с элемента n2+1, и проводим с ней те же самые действия, найдя таким образом элемент n3, для которого cn3>=xn2, и полагаем xn3=cn3+1.
- Повторяем эту процедуру по порядку до бесконечности.

В результате мы получим последовательность {Xn}, которая, во-первых, неубывающая, а во-вторых она отличается от всех присутствующих в изначальном списке последовательностей (по построению), то есть она оказалась непросчитанной. Полученное противоречие доказывает несчетность множества стремящихся к бесконечности неубывающих последовательностей. А поскольку это есть подмножество данного нам множества, то заключаем, что оно также несчетно. Это оценка снизу.

Далее, данное множество в свою очередь является подмножеством множества всех последовательностей натуральных чисел, которое имеет мощность континуума. Это оценка сверху.

Все. Думаю, преп не станет просить тебя доказывать отсутствие промежуточных мощностей...

[Надин]

Огромнейшее спасибо!!!!!
У меня уже не хватает сил спорить с преподом и доказывать,что я что-то знаю. ЧЕм больше я с ним спорю,тем больше у меня складывается впечатление, что игра не стиоит свеч,т.к. я полный ноль...

Спасибо большое за помощь!!!!!!!!!!!
P.S: змейка получилась классная,обязательно заведу себе такую)))

[Lapp]

Перечитал, и решил, что не хватает картинки-иллюстрации к методу создания последовательности {Xn}. Вот она:

1.  a1   a2   a3   a4   a5   a6   a7   a8   a9   a10   a11   ...
       \
2.  b1   b2 - b3 - b4   b5   b6   b7   b8   b9   b10   b11   ...        (b4 >= a1+1)
                      \
3.  c1   c2   c3   c4   c5 - c6 - c7 - c8   c9   c10   c11   ...        (c8 >= b4+1)
                                          \  
4.  d1   d2   d3   d4   d5   d6   d7   d8   d9 - d10   d11   ...        (d10 >= c8+1)
                                                     \
5.  e1   e2   e3   e4   e5   e6   e7   e8   e9   e10   e11   ...        (e11 >= d10+1)
                                                           \
6.  ............

    x1   x2   x3   x4   x5   x6   x7   x8   x9   x10   x11
    a1+1 a1+1 a1+1 b4+1 b4+1 b4+1 b4+1 c8+1 c8+1 d10+1 e11+1 ...

"Книжка без картинок .. - книжка неинтересная" © Алиса в Стране Чудес

[Надин]

Еще раз огромное спасибо от меня и от половины моей группы!!!!
С твоей помощью я получила зачет и помогла своим ребятам!!!! СПАСИБО!!!!!!!!!!!!!!

[Lapp]

Сообщение Кошки выделено в отдельную тему - Счетность, континуум, биекция

[Michael_Rybak]

2.Доказать, что множество всех бесконечных неубывающих последовательностей натуральных чисел имеет мощность континуума.

Это можно совсем просто показать.
Закодируем все числа от нуля до единицы по такой нехитрой системе: к знаку добавляем номер, умноженный на 10.

Например, число 0.27644 закодируем такой последовательностью:
2 + 0*10, 7 + 1*10, 6 + 2*10, 4 + 3*10, 4 + 4*10

Получаем:
2, 17, 26, 34, 44

Таким образом, мы закодировали числа от 0 до 1 некоторым подмножеством бесконечных неубывающих последовательностей натуральных чисел

[мисс_граффити]

...некрофил. на дату посмотрел бы.

[Michael_Rybak]

Смотрел. И что?

[Lapp]

на дату посмотрел бы.

Не вижу причин закрывать тему. Если есть красивые или интересные решения, ценные замечания, исправления - you're welcome!
Ограничение по времени может быть уместно кое-где в программировании, но математика не стареет (по крайней мере на протяжении нашей недолгой жизни). Иначе действительно получится, что после того, как спросивший сдал зачет, он сразу все забывает - и все. Я был бы только рад, если бы авторы вопросов возвращались к пройденному и не забывали ни теорию, ни задачи. И последнее: мне самому, как и некоторым другим участникам, это тоже интересно.. Этого мало?

Решение демонстрирует другой подход, который наряду с использованной выше Канторовой диагональю может быть взять на вооружение. Надин, рекомендую разобраться!

[-Hex-]

2Lapp

1.Доказать, что множество всех типов вида n/(2)^k + m/(3)^r, где n,m,r,k-натуральные числа, счетно.

На лекции разбирали подобного рода задачу, на сколько я понял суть ее сводится к доказательству, что отношение формирующее заданое множество М есть взаимно однозначное соответствие. И только после этого ссылаясь на эквивалентность множеств М и N^4, мы можем заключить что М счетно.
В вашем доказательстве я не вижу где доказывается что n/(2)^k + m/(3)^r это взаимно однозначное соответсвие. Мало того, взяв за n,m,r,k числа 2,1,3,4 мы построим тот же элемент множества М что и при числах 4,2,3,4. Из чего следует что данное отношение не взаино однозначно.
Обьясните мне где я не догоняю??

[Гость]

извеняюсь, не верно указал порядок чисел, надо читать так:
n,k,m,r - 2,1,3,4 и n,k,m,r, - 4,2,3,4

[-Hex-]

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

C={c: c=n/(2)^k + m/(3)^r)

f:C -> N^4
n/(2)^k + m/(3)^r -> (n,k,m,r) перепишем в виде: (n*3^r+m*2^k)/(2^k*3^r) -> (n,k,m,r)
Отсюда видно что доказательство анологично доказательству счетности множества Q, посколько каждый элемент С представлен приведенной дробью типа p/q. (где p = n*3^r+m*2^k, q=2^k*3^r)
Неоходимо лишь доказать, что либо числитель, либо знаменатель могут быть заданы лишь одним единственным способом, тогда и результат от деления может быть задан одним способом. Очвидно что функция р многозначна, докажем что q взаимно обратна.
допустим
2^k*3^r = 2^a*3^b
2^k = 2^a*3^(b-r), числа 2 и 3 простые, поскольку степень простого числа может делится лишь на само простое число(либо произведение n простых чисел), то следовательно b-r = 0, b = r. Аналогично k = a. Отсюда: q=2^k*3^r - взаимно обратна и f тоже взаино обратна.
С~f^-1© и f^-1© содердится в N^4, N^4 - счетна, следовательно и С счетна.

[Lapp]

Гость, что ты мудришь?.. Мне кажется, ты не только себя, ты всех запутал ).
Зачем какие-то p и q? Зачем их делить??.. При чем тут они вообще?
Доказательство я привел выше. Могу сделать еще несколько пояснений, если хочешь.

Во-первых, будем считать, что в условии ошибка, и будем говорить о "числах вида", а не о "типах вида". Далее, если мы поставим в соответствие каждой четверке натуральных чисел число указанного вида, то соответствие не будет взаимно однозначным, так как возможно, что одному числу соответствует несколько таких четверок. Но тогда все числа такого вида однозначно отображаются в подмножество четверок натуральных чисел. И если мы докажем, что множество "четверок" счетно, то любое его подмножество тоже будет не более, чем счетно. С другой стороны ясно, что множество этих чисел бесконечно. Таким образом, ему остается только быть счетным.

Так что осталось только доказать, что множество четверок натуральных чисел счетно. Доказать это нетрудно простым пересчетом. Я привел алгоритм пересчета выше. Он основывается на "змейке", которую легко продемонстрировать на "двойках" чисел, при этом ясно, что способ легко распространяется на "тройки", четверки" и вообще "n-ки" натуральных чисел. Пересчет "змейкой" начинается с элемента (1,1) и дальше идет серпантином (serpent - змея).

Код

11-12 13-14 15- ...
  /  /  /  /  /
21 22 23 24 25 ...
| /  /  /  /  /
31 32 33 34 35 ...
  /  /  /  /  /
41 42 43 44 45 ...
| /  /  /  /  /
51 52 53 54 55 ...
  /  /  /  /  /

то есть 11, 12, 21, 31, 22, 13, 14, 23, 32, 41, 51, 42, 33 ...
- это все не двузначные числа, а пары однозначных чисел; я не стал ставить разделители между цифрами, чтоб не загромождать картинку.

Для иллюстрации также можешь глянуть на мое фото http://forum.pascal.net.ru/index.php? s=&showtopic=6163&view=findpost&p=67617 . Кроме того, можешь посмотреть сюда: Математическая логика - и сюда: Биекция (в последней ссылке вариант змейки немного другой, но это несущественно).

Если еще что-то неясно - спрашивай .

[-Hex-]

2Lapp
Да проблеммы у меня вобшем то две. Во-первых, у нас просто не примут доказательство в таком виде как ты даеш. На слова типа "можем отобразить, можем пересчитать" препод тупо скажет -"не можем! если не согласен, докажи что можем". Вобщем в задачах на доказательство требуют чтоб любое высказывание было математически подтверждено.
Во-вторых, я учусь не на русском, поэтому может гдето не совсем улавливаю смысл русских терминов. Вот к примеру ты пишеш:

Но тогда все числа такого вида однозначно отображаются в подмножество четверок натуральных чисел.

все числа - это надо понимать так что f:C->N^4 опеределена для ВСЕХ с? если так, то согласен, это логично.
а однозначно отображаются - f( c)->(m,n,k,r), так что каждому c соответствует один единственный набор (m,n,k,r)? Но ведь это не так?! ведь ты сам строкой выше сказал - "возможно, что одному числу соответствует несколько таких четверок". Вот тут вот я путаюсь...

Обьясни плиз это


и, кстати спасибо, ты мне подсказал вообще элементарное решение))

Зачем какие-то p и q? Зачем их делить??.. При чем тут они вообще?

а вот зачем: в выражении n/(2)^k + m/(3)^r, все переменные - целые числа, (2)^k и (3)^r тоже целые, следовательно дроби n/(2)^k и m/(3)^r имеют вид p/q и принадлежат Q, то есть рациональным числами. Сумма двух рационалных чисел также является числом рациональным. Следовательно множество С является подмножеством множества Q и обладает мошьностью a<=алеф-ноль. С другой стороны очевидно что множество С бесконечно, следовательно мошьность a>=алеф-ноль. Из пересечения последних условий следует a=алеф-ноль. С счетно.

[Lapp]

Во-первых, у нас просто не примут доказательство в таком виде как ты даеш. На слова типа "можем отобразить, можем пересчитать" препод тупо скажет -"не можем! если не согласен, докажи что можем".

Hex, из того, что ты не понял доказательства не нужно делать вывод, что оно неполное. На месте твоего препода я бы сказал абсолютно то же самое, если бы мне преподнесли утверждение без доказательства. В моем решении есть доказательства почти всех утверждений (одно опущенное привожу ниже), которые таковых доказательств требуют. Например, я не говорю просто "можно пересчитать", а говорю "можно пересчитать с помошью змейки". "Змейка" выступает в качестве явного алгоритма пересчета, что и есть в данном случае доказательство возможности пересчета!

Вобщем в задачах на доказательство требуют чтоб любое высказывание было математически подтверждено.

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

Во-вторых, я учусь не на русском, поэтому может гдето не совсем улавливаю смысл русских терминов.

Я понял, на каком языке ты учишься (по ip), но я вижу, что русский у тебя на вполне нормальном уровне, достаточном для понимания (видел бы ты как тут иной раз пишут.. хоть стой хоть падай!). Что касается терминов, то я пока употребил не так много.. Но если тебе не ясны какие-то - спрашивай.

все числа - это надо понимать так что f:C->N^4 опеределена для ВСЕХ с? если так, то согласен, это логично.

Не все числа, а "все числа такого вида".
Когда ты начинаешь употреблять обозначения, которые ты не определил, это может внести только путаницу. Учти, что обозначения C, а также M и N - не такие уж и мировые стандарты. Говори словами (или определяй обозначения) - и все будет понятно.
Каждое число "такого вида" представляется хотя бы одним способом в виде n/(2)^k + m/(3)^r (по определению). Поэтому, конечно, базовое отображение определено для всех таких чисел. Другое дело, что одно и то же число, возможно, имеет не одно такое представление..

а однозначно отображаются - f( c)->(m,n,k,r), так что каждому c соответствует один единственный набор (m,n,k,r)? Но ведь это не так?! ведь ты сам строкой выше сказал - "возможно, что одному числу соответствует несколько таких четверок". Вот тут вот я путаюсь...

Я не говорил, что есть однозначное отображение на все множество "четверок" (N^4, если нравится). Я сказал, что есть однозначное отображение на его подмножество. Рассуждение такое (его я действительно опустил в расчете на то, что ты додумаешь)...
Если четверка (n,k,m,r) порождает то же самое число а, что и (n1,k1,m1,r1), то есть
n/(2)^k + m/(3)^r = n1/(2)^k1 + m1/(3)^r1 = а,
а также если таких четверок больше двух (включая бесконечное количество), то выберем из этих четверок ту, у которой минимально число n. Если таких четверок все равно больше одной - выберем из них ту, у которой второе число (то есть k) минимально, и так далее. В результате получится одна "четверка", которую и поставим в соответствие числу "а". Двум разным числам "а" будут соответствовать заведомо разные "четверки", так как если они будут одинаковые, то и число дадут одно и то же.
Это понятно?

и, кстати спасибо, ты мне подсказал вообще элементарное решение))

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

а вот зачем: в выражении n/(2)^k + m/(3)^r, все переменные - целые числа, (2)^k и (3)^r тоже целые, следовательно дроби n/(2)^k и m/(3)^r имеют вид p/q и принадлежат Q, то есть рациональным числами. Сумма двух рационалных чисел также является числом рациональным. Следовательно множество С является подмножеством множества Q и обладает мошьностью a<=алеф-ноль. С другой стороны очевидно что множество С бесконечно, следовательно мошьность a>=алеф-ноль. Из пересечения последних условий следует a=алеф-ноль. С счетно.

Все верно. Но дело в том, доказательство счетности рациональных чисел абсолютно идентично тому доказательству, которое привел я. То, что там вместо "чктверок" используются "пары" - согласись, не различие. И если ты умеешь доказывать, что множество рациональных чисел счетно - все в порядке, можешь доказывать этим способом. Я же, увы, не знал, что ты можешь использовать это в доказательстве и строил свое док-во от основ (аналогично доказательству счетности рациональных). Так это и есть то самое "элементарное решение"? Ну, я свое мнение уже высказал..

[-Hex-]

2Lapp

а также если таких четверок больше двух (включая бесконечное количество), то выберем из этих четверок ту, у которой минимально число n. Если таких четверок все равно больше одной - выберем из них ту, у которой второе число (то есть k) минимально, и так далее. В результате получится одна "четверка", которую и поставим в соответствие числу "а". Двум разным числам "а" будут соответствовать заведомо разные "четверки", так как если они будут одинаковые, то и число дадут одно и то же.

спасибо) теперь дошло)

[Lapp]

спасибо) теперь дошло)

ок
Регистрируйся и заходи почаще!