Форум программистов, компьютерный форум, киберфорум
Наши страницы
Дискретная математика
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
oobarbazanoo
3 / 26 / 8
Регистрация: 13.05.2015
Сообщений: 1,820
#1

Доказать счётность множества

30.01.2016, 18:03. Просмотров 658. Ответов 11
Метки нет (Все метки)

Множество всех конечных подмножеств счётного множества счётно.

Добавлено через 15 минут
Пускай имеем множество A = {a1, a2, ... , ak, ...}. Оно счётно по условию. Тогда построим биекцию между множеством всех его подмножеств и множеством натуральных чисел следующим образом. Каждое подмножество A можно задать последовательностью из нулей и единиц. Ноль ставим на n-й позиции последовательности, если елемент множества А под номером n не принадлежит подмножеству А и единицу, если принадлежит. Теперь имеем множество последовательностей из нулей и единиц, которое есть счётным. Данная счётность доказывается таким образом. Берём последовательность, считываем её начиная с последней единицы справа на лево и переводим данную запись как из двоичной системы в десятичную. Правильный подход? Если можно проще, то объясните как, пожалуйста.

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2016, 18:03
Ответы с готовыми решениями:

Множества. Доказать, что
Доказать, что (A\bigcup B)*(C\bigcup D)= (A*C)\bigcup (B*C)\bigcup (A*D)\bigcup...

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

Конечные множества, бесконечные числовые множества, универсумы
Помогите найти больше информации по данной теме, как правило представлены...

Доказать компактность множества
привет всем. помогите с задачкой. доказать, что множество функций, имеющих...

Доказать выпуклость множества
Как доказать выпуклость множества в {R}^{2}? X={x|{{x}_{1}}^{2}\leq...

11
iifat
2342 / 1497 / 130
Регистрация: 05.06.2011
Сообщений: 4,161
30.01.2016, 20:28 #2
В общем-то, да. Перевод в десятичную вычеркнуть, он ничего не даёт. Упомянуть, что вследствие конечности подмножеств получаем конечное число единиц, и, стало быть, натуральное число. Возможно, стоит добавить доказательство взаимной однозначности и полноты соответствия.
1
kabenyuk
1719 / 1298 / 308
Регистрация: 19.11.2012
Сообщений: 2,541
31.01.2016, 09:47 #3
Цитата Сообщение от oobarbazanoo Посмотреть сообщение
Теперь имеем множество последовательностей из нулей и единиц, которое есть счётным.
1) Множество последовательностей из нулей и единиц вовсе не является счетным. У вас дополнительное условие: число единичек в последовательности конечно, что и упоминает iifat.
2) Можно конечно в десятичную запись и не переводить, но тут есть одна проблема. Например, две последовательности 01 и 001 дают одно и то же число. Надо это как-то побороть. Не буду лишать вас удовольствия самому сообразить как справиться с этой неприятностью.
1
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
31.01.2016, 11:17 #4
Цитата Сообщение от kabenyuk Посмотреть сообщение
Не буду лишать вас удовольствия самому сообразить как справиться с этой неприятностью.
Как я понял, ТС выводит последовательность в обратном порядке и она всегда начинается с 1.
1
kabenyuk
1719 / 1298 / 308
Регистрация: 19.11.2012
Сообщений: 2,541
31.01.2016, 11:22 #5
Цитата Сообщение от zer0mail Посмотреть сообщение
выводит последовательность в обратном порядке и она всегда начинается с 1
Точно. Это значит я его не сразу понял. Тогда в этом месте все в порядке.
1
iifat
2342 / 1497 / 130
Регистрация: 05.06.2011
Сообщений: 4,161
31.01.2016, 12:49 #6
Цитата Сообщение от zer0mail Посмотреть сообщение
Как я понял, ТС выводит последовательность в обратном порядке и она всегда начинается с 1
О! Не заметил. Действительно:
Цитата Сообщение от oobarbazanoo Посмотреть сообщение
считываем её начиная с последней единицы справа налево
И вот это как раз ошибка, которая не даст построить взаимно-однозначное соответствие. Надо честно справа налево как есть.
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
31.01.2016, 13:41 #7
Цитата Сообщение от iifat Посмотреть сообщение
И вот это как раз ошибка, которая не даст построить взаимно-однозначное соответствие. Надо честно справа налево как есть.
Да нет тут ошибки
Из последовательности
001100010000...
получается число
10001100
0
iifat
2342 / 1497 / 130
Регистрация: 05.06.2011
Сообщений: 4,161
31.01.2016, 13:55 #8
ТС, как мне указали, предлагал из 0011000100... делать 100011 — начиная с первой единицы. Я-то как раз и предлагаю твой способ.
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
31.01.2016, 13:59 #9
Это где указали, в каком месте? Если kabenyuk, то он поправился, а у ТС все было правильно изначально...
0
iifat
2342 / 1497 / 130
Регистрация: 05.06.2011
Сообщений: 4,161
31.01.2016, 14:03 #10
Вот:
Цитата Сообщение от oobarbazanoo Посмотреть сообщение
Берём последовательность, считываем её начиная с последней единицы справа на лево
Хм. Как-то перестал понимать, что тут имеется в виду. То ли ТС предлагает из 0011000100... делать 00110001? Это тоже не подходит.
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
31.01.2016, 14:05 #11
Имхо, ТС предлагает так, как я написал в примере.
0
iifat
2342 / 1497 / 130
Регистрация: 05.06.2011
Сообщений: 4,161
31.01.2016, 14:46 #12
Надеюсь, что так, просто изложено как-то непонятно
0
31.01.2016, 14:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.01.2016, 14:46

Доказать компактность множества
Помогите пожалуйста решить задания по функциональному анализу, бился все...

Множества. Доказать тождество.
Подскажите пожалуйста как доказать это тождество. X, Y, Z - множества.

Множества, доказать тождество
ПОМОГИТЕ РЕШИТЬ ДОКАЗАТЬ ТОЖДЕСТВО А\В=А\bigcup В (ОБЪЕДИНЕНИЕ) палочки...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru