Бесконечная гостиница (БГ) - гостиница с бесконечным количеством номеров (1,2,3,...) и бесконечным количеством постояльцев, живущих по одному в каждом номере

а) подселить 1 жильца так, чтобы все кто уже живет - продолжили жить в гостинице (возможно, переселившис....

Бесконечная гостиница (БГ) - гостиница с бесконечным количеством номеров (1,2,3,...) и бесконечным количеством постояльцев, живущих по одному в каждом номере

а) подселить 1 жильца так, чтобы все кто уже живет - продолжили жить в гостинице (возможно, переселившись в другой номер)
б) подселить 10 000 жильцов
в) подселить бесконечно много футбольных болельщиков (у каждого болельщика есть свой номер от 1 и далее, болельщики приехали по билетам)
г) подселить бесконечно много гастарбайтеров (они приехали из бесконечного множества других гостиниц, у каждой гостиницы есть свой номер, а у каждого гастарбайтера номер комнаты из той гостиницы, откуда он приехал)
1 - допускается чтобы какие-то номера при таком расселении пустовали
2 - все номера должны быть заняты

ОПРЕДЕЛЕНИЕ: сравнение бесконечных множеств основано на идее взаимнооднозначного соответствия, множества имеющие такое соответствие называются РАВНОМОЩНЫМИ, иначе НЕРАВНОМОЩНЫМИ

Доказать, что множество натуральных чисел равномощно
а) всем целым числам
....

ОПРЕДЕЛЕНИЕ: сравнение бесконечных множеств основано на идее взаимнооднозначного соответствия, множества имеющие такое соответствие называются РАВНОМОЩНЫМИ, иначе НЕРАВНОМОЩНЫМИ

Доказать, что множество натуральных чисел равномощно
а) всем целым числам
б) всем рациональным числам
в) всем алгебраическим уравнения с целыми коэффициентами a_n*xⁿ+a_n-1*x^n-1+ … +a₂*x²+a₁*x+a₀=0
г) всем алгебраическим числам (корням алгебраических уравнений n-ой степени с целыми коэффициентами) *уравнение n-ой степени имеет не более n корней
д) конечным наборам (a₁,...,a_n), где a_i - пробегает все натуральные числа
е) всевозможным попарно непересекающимся буквам Т произвольного размера на плоскости
ж) всевозможным попарно непересекающимся ВОСЬМЕРКАМ произвольного размера на плоскости подсказка: привязать фигуры к точкам с ОБОИМИ рациональными координатами

Доказать, что множество натуральных чисел равномощно
а) всем целым числам

Доказать, что множество натуральных чисел равномощно
а) всем целым числам

Доказать, что множество натуральных чисел равномощно
б) всем рациональным числам

Доказать, что множество натуральных чисел равномощно
б) всем рациональным числам

Доказать, что множество натуральных чисел равномощно
в) всем алгебраическим уравнения с целыми коэффициентами a_n * xⁿ + a_n-1 * x^n-1 + … + a₂ * x² + a₁*x + a_0....

Доказать, что множество натуральных чисел равномощно
в) всем алгебраическим уравнения с целыми коэффициентами a_n * xⁿ + a_n-1 * x^n-1 + … + a₂ * x² + a₁*x + a₀=0

Доказать, что множество натуральных чисел равномощно
г) всем алгебраическим числам (корням алгебраических уравнений n-ой степени с целыми коэффициентами) *уравнение n-ой степени имеет не более n корней

Доказать, что множество натуральных чисел равномощно
г) всем алгебраическим числам (корням алгебраических уравнений n-ой степени с целыми коэффициентами) *уравнение n-ой степени имеет не более n корней

Доказать, что множество натуральных чисел равномощно
д) конечным наборам (a₁,...,a_n), где a_i - пробегает все натуральные числа

Доказать, что множество натуральных чисел равномощно
д) конечным наборам (a₁,...,a_n), где a_i - пробегает все натуральные числа

Доказать, что множество натуральных чисел равномощно
е) всевозможным попарно непересекающимся буквам Т произвольного размера на плоскости

Доказать, что множество натуральных чисел равномощно
е) всевозможным попарно непересекающимся буквам Т произвольного размера на плоскости

Доказать, что множество натуральных чисел равномощно
ж) всевозможным попарно непересекающимся ВОСЬМЕРКАМ произвольного размера на плоскости подсказка: привязать фигуры к точкам с ОБОИМИ рациональными координатами

Доказать, что множество натуральных чисел равномощно
ж) всевозможным попарно непересекающимся ВОСЬМЕРКАМ произвольного размера на плоскости подсказка: привязать фигуры к точкам с ОБОИМИ рациональными координатами

ОПРЕДЕЛЕНИЕ: множества равномощные натуральным числам называются СЧЕТНЫЕ, иначе НЕСЧЕТНЫЕ

Доказать
а) Счетные множества самые маленькие из бесконечных (т.е. любое бесконечное множество имеет счетное подмножество)
б) Мощность бесконечного множества не из....

ОПРЕДЕЛЕНИЕ: множества равномощные натуральным числам называются СЧЕТНЫЕ, иначе НЕСЧЕТНЫЕ

Доказать
а) Счетные множества самые маленькие из бесконечных (т.е. любое бесконечное множество имеет счетное подмножество)
б) Мощность бесконечного множества не изменяется от прибавления к нему счетного множества
в) Мощность несчетного множества не меняется от удаления из него счетного множества

Из треста космических гостиниц пришел приказ составить заранее все возможные варианты заполнения номеров. Эти варианты потребовали представить в виде таблицы, каждая строка которой изображала бы один из вариантов. При этом заполненные номера должны были изображаться еди....

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

ОПРЕДЕЛЕНИЕ: множества, равномощные множеству всех бесконечных последовательностей из 0 и 1, называются множествами мощности КОНТИНУУМА

Доказать, что множество всех действительных чисел имеет мощность континуума

ОПРЕДЕЛЕНИЕ: множества, равномощные множеству всех бесконечных последовательностей из 0 и 1, называются множествами мощности КОНТИНУУМА

Доказать, что множество всех действительных чисел имеет мощность континуума

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

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

Доказать, что для любого множества всегда найдется множество большей мощности - достаточно взять множество всех подмножеств данного множества

Доказать, что для любого множества всегда найдется множество большей мощности - достаточно взять множество всех подмножеств данного множества

Доказать, что все отрезки равномощны

Доказать, что все отрезки равномощны

Доказать: что отрезок равномощен бесконечной прямой

Доказать: что отрезок равномощен бесконечной прямой

Доказать, что отрезок равномощен внутренности квадрата
а) вложить квадрат в отрезок и отрезок в квадрат

ОПРЕДЕЛЕНИЕ (нестрогое)
если точки соседние, то образы тоже соседние - непрерывное соответствие

б) показать, что отображение отрезка на квадр....

Доказать, что отрезок равномощен внутренности квадрата
а) вложить квадрат в отрезок и отрезок в квадрат

ОПРЕДЕЛЕНИЕ (нестрогое)
если точки соседние, то образы тоже соседние - непрерывное соответствие

б) показать, что отображение отрезка на квадрат не является непрерывным:
   1)найти 2 близких точки в квадрате, образы которых относительно далекие на отрезке
   2)2 близких точки на отрезке, прообразы которых в квадрате далеко

Доказать, что отрезок равномощен внутренности квадрата
а) вложить квадрат в отрезок и отрезок в квадрат

Доказать, что отрезок равномощен внутренности квадрата
а) вложить квадрат в отрезок и отрезок в квадрат

ОПРЕДЕЛЕНИЕ(нестрогое)
если точки соседние, то образы тоже соседние - непрерывное соответствие

б) показать, что отображение отрезка на квадрат не является непрерывным:
1)найти 2 близких точки в квадрате, образы которых относительно далекие на отрезке....

ОПРЕДЕЛЕНИЕ(нестрогое)
если точки соседние, то образы тоже соседние - непрерывное соответствие

б) показать, что отображение отрезка на квадрат не является непрерывным:
   1)найти 2 близких точки в квадрате, образы которых относительно далекие на отрезке
   2)2 близких точки на отрезке, прообразы которых в квадрате далеко

Доказать что квадрат равномощен плоскости

Доказать что квадрат равномощен плоскости

Доказать, что множество тогда и только тогда бесконечно, когда оно эквивалентно (взаимно однозначно) некоторому своему подмножеству.

Доказать, что множество тогда и только тогда бесконечно, когда оно эквивалентно (взаимно однозначно) некоторому своему подмножеству.

Доказать, что множество всех конечных подмножеств счетного множества счетно

Доказать, что множество всех конечных подмножеств счетного множества счетно

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

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

Существует ли множество промежуточной мощности между счетным и континуумом?

Существует ли множество промежуточной мощности между счетным и континуумом?

Сколько существует всевозможных функций из конечного множества, содержащего m элементов в конечное множество, содержащее n элементов?

Сколько существует всевозможных функций из конечного множества, содержащего m элементов в конечное множество, содержащее n элементов?

ОПРЕДЕЛЕНИЕ: Мощность множества всех функций из произвольного множества B в произвольное множество A будем обозначать A^B

1)Показать, что 2^N>N, где N - счетное множество (т.е. предложить множество ф-ий принимающих ровно 2 значения на элементах множества N, кот....

ОПРЕДЕЛЕНИЕ: Мощность множества всех функций из произвольного множества B в произвольное множество A будем обозначать A^B

1)Показать, что 2^N>N, где N - счетное множество (т.е. предложить множество ф-ий принимающих ровно 2 значения на элементах множества N, которое мощнее N)
2)Показать, что 2^X>X, где X - произвольное множество. Указание: рассмотреть множество всех функций, принимающих значения 0 и 1 на элементах множества X
3)N<2^N=C<2^C=F<.... Где N - счетная мощность, С-мощность континуума, F - мощность всех функций, заданных на континууме принимающих значения 0 и 1 и т.д. Проверить, существуют ли в этой цепочке между некоторыми мощностями промежуточные (например, между С и F)

1)Показать, что 2^N>N, где N - счетное множество (т.е. предложить множество ф-ий принимающих ровно 2 значения на элементах множества N, которое мощнее N)

1)Показать, что 2^N>N, где N - счетное множество (т.е. предложить множество ф-ий принимающих ровно 2 значения на элементах множества N, которое мощнее N)

2)Показать, что 2^X>X, где X - произвольное множество. Указание: рассмотреть множество всех функций, принимающих значения 0 и 1 на элементах множества X

2)Показать, что 2^X>X, где X - произвольное множество. Указание: рассмотреть множество всех функций, принимающих значения 0 и 1 на элементах множества X

3)N<2^N=C<2^C=F<.... Где N - счетная мощность, С-мощность континуума, F - мощность всех функций, заданных на континууме принимающих значения 0 и 1 и т.д. Проверить, существуют ли в этой цепочке между некоторыми мощностями промежуточные (например, между С и F)

3)N<2^N=C<2^C=F<.... Где N - счетная мощность, С-мощность континуума, F - мощность всех функций, заданных на континууме принимающих значения 0 и 1 и т.д. Проверить, существуют ли в этой цепочке между некоторыми мощностями промежуточные (например, между С и F)

Построить ЧП множество, у которого нет наименьшего элемента, но есть ровно 1 минимальный

Построить ЧП множество, у которого нет наименьшего элемента, но есть ровно 1 минимальный

Построить все различные ЧП множества, состоящие ровно из 3-х элементов

Построить все различные ЧП множества, состоящие ровно из 3-х элементов

1. Проверить, что отношение порядка = (равенство чисел) не является ЛП на R, но является ЧП

2. Проверить, что отношение порядка КРАТНОСТЬ (одно число кратно другому) не является ЛП, но является ЧП на множестве N (натуральных чисел)

1. Проверить, что отношение порядка = (равенство чисел) не является ЛП на R, но является ЧП

2. Проверить, что отношение порядка КРАТНОСТЬ (одно число кратно другому) не является ЛП, но является ЧП на множестве N (натуральных чисел)

Построить линейный порядок на множестве всех подмножеств натуральных чисел

Построить линейный порядок на множестве всех подмножеств натуральных чисел

Доказать, что любое ЧП множество А соответствует некоторой системе подмножеств множества А, упорядоченных отношением включения

Доказать, что любое ЧП множество А соответствует некоторой системе подмножеств множества А, упорядоченных отношением включения

ОПРЕДЕЛЕНИЕ: множество называется вполне упорядоченным ВП, если оно ЛП и каждое его подмножеств имеет наименьший элемент

Являются ли следующие множества ВП
а) натуральные числа
б) целые числа
г) рациональные числа

ОПРЕДЕЛЕНИЕ: множество называется вполне упорядоченным ВП, если оно ЛП и каждое его подмножеств имеет наименьший элемент

Являются ли следующие множества ВП
а) натуральные числа
б) целые числа
г) рациональные числа

Доказать теорему о том, что все натуральные числа интересные, Указание: рассуждать от противного, рассмотреть множество всех неинтересных натуральных чисел и воспользоваться свойствами ВП множеств (задача - шутка)

Доказать теорему о том, что все натуральные числа интересные, Указание: рассуждать от противного, рассмотреть множество всех неинтересных натуральных чисел и воспользоваться свойствами ВП множеств (задача - шутка)

Шеренга новобранцев стоит перед старшиной. Он командует “налево”. По неопытнсоти часть солдат поворачивается налево, а часть - направо. После этого каждую секунду происходит следующее: солдаты, оказавшиеся друг к другу лицом понимают, что произошла ошибка, и поворачиваю....

Шеренга новобранцев стоит перед старшиной. Он командует “налево”. По неопытнсоти часть солдат поворачивается налево, а часть - направо. После этого каждую секунду происходит следующее: солдаты, оказавшиеся друг к другу лицом понимают, что произошла ошибка, и поворачиваются кругом. В следующую секунду ситуация повторяется. Доказать, что рано или поздно солдаты встанут так, что поворачиваться будет не нужно.

Указание: Будем кодировать положение солдат с помощью последовательности букв Л и П, и рассматривать последовательности этих букв с точки зрения алфавитного порядка.

Пусть A и B - для произвольных множеств. Если существуют взаимно однозначное отображение f множества A на подмножество B_1 множества B и взаимно однозначное отображение g множества B на подмножество A_1 множества A, то A и B эквивалентны.

Пусть A и B - для произвольных множеств. Если существуют взаимно однозначное отображение f множества A на подмножество B_1 множества B и взаимно однозначное отображение g множества B на подмножество A_1 множества A, то A и B эквивалентны.

Можно ли
а) вполне упорядочить все рациональные числа?
б) вполне упорядочить континуум?

Для вполне упорядоченности произвольного множества Цермело придумал Аксиому Выбора.

Можно ли
а) вполне упорядочить все рациональные числа?
б) вполне упорядочить континуум?

Для вполне упорядоченности произвольного множества Цермело придумал Аксиому Выбора.

Формулировка АКСИОМЫ ВЫБОРА

ОПРЕДЕЛЕНИЕ 1:
Если дано бесконечное множество бесконечных множеств, то из каждого множества можно выбрать по одному элементу, не указывая заранее закона выбора. И то что получится в результате тоже будет множеством.

ОПР....

Формулировка АКСИОМЫ ВЫБОРА

ОПРЕДЕЛЕНИЕ 1:
Если дано бесконечное множество бесконечных множеств, то из каждого множества можно выбрать по одному элементу, не указывая заранее закона выбора. И то что получится в результате тоже будет множеством.

ОПРЕДЕЛЕНИЕ 2:
Есть произвольный набор множеств M={A,B,C...}, тогда существует такая функция на этом наборе f, которая f(A)=a, f(B)=b, f(C)=c,... тогда набор K из элементов {a,b,c, ... } тоже будет множеством.

ЕЩЕ РАЗ 2 ОПРЕДЕЛЕНИЯ+ОДНО

1. Максимальный элемент - тот, больше которого в данном ЧП не существует (утрируя: если взять множество попарно несравнимых элементов, то каждый из них будет максимальным в этом ЧП (и, к слову, минимальным))
2. Наибольший - ....

ЕЩЕ РАЗ 2 ОПРЕДЕЛЕНИЯ+ОДНО

1. Максимальный элемент - тот, больше которого в данном ЧП не существует (утрируя: если взять множество попарно несравнимых элементов, то каждый из них будет максимальным в этом ЧП (и, к слову, минимальным))
2. Наибольший - единственный (возможный) элемент, который больше всех остальных. Ну, к примеру, в ЧП "множество всех подмножеств множества А", упорядоченном по включению, это элемент, равный самому A.
3. Верхняя грань ЛП в данном контексте - какой-либо из элементов ЧП, больший всех элементом этого ЛП. Ну, т.е., пусть дан ЧП X и принадлежащий ему ЛП Y, так вот верхней гранью будет любой элемент из X/Y, больший любого элемента Y.

Задача

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

(Верхняя грань не обязана принадлежать рассматриваемой части ЧП. Это её отличает от наибольшего элемента)

Аксиома выбора эквивалента следующим 3-м утверждениям

1. Теорема Цермело (любое множество можно вполне упорядочить)

2. Лемма Цорна. Если в частично упорядоченном множестве M для всякого линейного упорядоченного подмножества существует верхняя грань, то....

Аксиома выбора эквивалента следующим 3-м утверждениям

1. Теорема Цермело (любое множество можно вполне упорядочить)

2. Лемма Цорна. Если в частично упорядоченном множестве M для всякого линейного упорядоченного подмножества существует верхняя грань, то в M существует максимальный элемент

3. Принцип Максимума Хаусдорфа: В любом частично упорядоченном множестве существует максимальное линейно упорядоченное подмножество по включению.

Следствия из Аксиомы Выбора

1) Любое множество можно вполне упорядочить
2) Любое множество U равномощно декартову квадрату UxU
3) АВ ведёт себя как гипотеза континнуума с точки противоречивости другим аксиомам
4) Континуум-гипотеза остается нерешенн....

Следствия из Аксиомы Выбора

1) Любое множество можно вполне упорядочить
2) Любое множество U равномощно декартову квадрату UxU
3) АВ ведёт себя как гипотеза континнуума с точки противоречивости другим аксиомам
4) Континуум-гипотеза остается нерешенной при принятии АВ
5) Существую неизмеримые по Лебегу множества
6) Парадокс Банаха-Тарского (на основе неизмеримого по Лебегу множества)
7) Счетная аксиома выбора (набор множеств из которых мы дергаем по одному элементу - счетный)

Лайтовая версия Аксиомы Выбора.

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

Лайтовая версия Аксиомы Выбора.

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