Теория множеств
[311/76%]Доказать:
(рефлексивность);
если и , то (транзитивность);
;
;
.
Доказать, что если есть множество корней уравнения и , то .
Доказать, что .
Доказать, что .
Доказать, что для любого :
;
если , то ; если , то ;
, , , .
Доказать, что существует лишь одно множество, не имеющее элементов.
Существуют ли такие множества , и , что
Доказать, что множество всех корней многочлена есть объединение множеств корней многочленов и .
Доказать, что пересечение множеств действительных корней многочленов и с действительными коэффициентами совпадает с множеством всех действительных корней многочлена .
Доказать, что
Доказать следующие тождества:
;
;
;
;
;
;
;
.
Доказать следующие тождества:
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
Доказать, что:
и ;
и ;
;
;
;
;
;
;
;
;
;
;
и .
Доказать тождества:
;
;
;
;
;
;
;
;
;
.
Доказать, что:
;
.
Доказать, что:
;
;
.
Определить операции через:
;
;
.
Доказать, что нельзя определить:
через и ;
через и .
Доказать, что множества образуют кольцо без единицы, где играет роль операции сложения, а играет роль операции умножения. Что является вычитанием в этом кольце?
Найти все подмножества множеств , , , .
Доказать, что множество из элементов имеет подмножеств.
Сколько подмножеств из элементов имеет множество из элементов ?
Доказать, что:
;
;
;
.
Доказать, что для любых , , ,
Какие из утверждений верны для всех , и :
если и , то ?
если и , то ?
если и , то ?
если и , то ?
если и , то ?
Доказать, что для любых ,
Для каждого положительного целого числа указать множество из элементов такое, что если , то или или .
Решить систему уравнений
где , и --- данные множества и .
Решить систему уравнений
где , и --- данные множества и , .
Пусть даны системы множеств и , где --- некоторое множество. Решить системы уравнений:
, ;
, .
При каких и эти системы имеют решения?
Решить систему уравнений
где , и --- данные множества и .
Показать, что:
;
любое уравнение относительно множества , в правой части которого стоит , равносильно уравнению , где и --- некоторые множества, в записи которых не содержится символ ;
система уравнений
имеет решение тогда и только тогда, когда ; при этом условии решением системы является любое множество такое, что
описать метод решения системы уравнений с одним неизвестным.
Пользуясь методом задачи I.1.31, решить следующие системы:
При каких , и эти системы имеют решение?
Доказать, что всякое множество есть:
объединение всех своих подмножеств;
объединение всех своих конечных подмножеств;
объединение всех своих одноэлементных подмножеств.
Пусть имеется последовательность множеств
Доказать, что пересечение любой бесконечной подпоследовательности этих множеств совпадает с пересечением всей последовательности.
Пусть имеется последовательность множеств
Доказать, что объединение любой бесконечной подпоследовательности этих множеств совпадает с объединением всей последовательности.
Доказать следующие тождества:
;
;
;
;
;
;
.
Доказать, что для любых , ,
Доказать, что в утверждении (а) включение нельзя заменить равенством.
Доказать, что:
если для всех , то ;
если для всех , то ;
если для всех , то и .
Доказать, что:
есть наименьшее множество, содержащее все множества ;
есть наибольшее множество, содержащееся во всех множествах .
Доказать, что если , то
где
Доказать, что для любой системы множеств существует система попарно непересекающихся множеств такая, что и .
Доказать, что существуют , и такие, что:
;
.
Найти геометрическую интерпретацию следующих множеств:
, где и --- отрезки действительной прямой ;
;
;
.
Доказать, что если , , и не пусты, то:
и ;
и .
Доказать, что:
;
.
Доказать, что . При каких , , и получается равенство?
Доказать, что:
;
;
;
;
;
, где и ;
;
;
.
Пусть и . Доказать, что .
Найти , , , , , для следующих отношений:
;
;
;
;
.
Доказать, что:
;
, ;
;
.
Доказать, что:
если , то ;
если , то .
Пусть --- бинарное отношение на . Доказать, что тогда и только тогда, когда для любого отношения на .
Доказать, что для любых бинарных отношений:
;
;
;
;
;
;
.
Для каких бинарных отношений справедливо ?
Пусть и --- конечные множества, состоящие из и элементов соответственно.
Сколько существует бинарных отношений между элементами множеств и ?
Сколько имеется функций из в ?
Сколько имеется 1--1-функций из в ?
При каких и существует взаимно однозначное соответствие между и ?
Доказать, что для любых бинарных отношений:
;
;
;
.
Доказать, что:
;
;
в утверждениях (а) и (б) включения нельзя заменить равенствами.
Образуют ли бинарные отношения группу относительно операций и ?
Доказать, что если , то:
;
;
.
Доказать, что:
если , то ;
.
Установить взаимно однозначное соответствие между и при .
Используя определение, описать множество , где --- множество действительных чисел.
Доказать, что если есть функция из в и есть функция из в , то есть функция из в .
Пусть и --- функции. При каких условиях:
является функцией;
является 1--1-функцией?
Пусть --- такие множества, что находится во взаимно однозначном соответствии с , а --- с . Показать, что можно установить взаимно однозначное соответствие:
между и ;
между и ;
между и , если и .
Доказать, что можно установить взаимно однозначное соответствие между множествами:
и ;
и ;
и ;
и ;
и , если ;
и , где --- подстановка множества ;
и , где и все попарно не пересекаются;
и , где и все попарно не пересекаются.
Пусть --- подстановка множества . Доказать, что --- подстановка множества .
Доказать, что множество подстановок множества образует группу.
Пусть --- взаимно однозначное соответствие. Доказать, что:
--- взаимно однозначное соответствие между и ;
;
.
Доказать, что для того, чтобы отношение было взаимно однозначным соответствием между и , необходимо и достаточно, чтобы и .
Доказать, что объединение (пересечение) двух функций и из в является функцией из в тогда и только тогда, когда .
Доказать, что для любой функции :
;
.
Доказать, что для любой функции :
;
,
и эти включения нельзя заменить равенствами.
Доказать, что удовлетворяет условию
тогда и только тогда, когда есть 1--1-функция.
Доказать, что для любой функции .
Доказать, что если в предыдущем примере есть 1--1-функция, то выполняется равенство.
Доказать, что если , то для любой функции .
Доказать, что для любой функции
Доказать следующие тождества для любой функции :
;
;
;
;
.
Доказать, что если , то для любой функции .
Доказать, что для любой функции
Доказать, что если и , то:
;
;
;
;
.
Пусть . Определим , так, что и . При каких условиях ? При каких условиях ?
В обозначениях предыдущей задачи доказать, что:
;
.
Пусть --- непустое множество. Для любого подмножества множества обозначим через следующую функцию (характеристическую функцию множества ):
Определим функцию следующим условием: для любого . Доказать, что есть взаимно однозначное соответствие между и .
Доказать, что введенная в предыдущей задаче функция удовлетворяет следующим условиям:
;
;
;
;
;
;
если , то ;
если , то .
Доказать свойства полной дистрибутивности:
;
.
Доказать, что , где для всех .
Пусть . Доказать, что:
, где , при ;
, где , при .
Доказать, что:
;
если при , то можно установить взаимно однозначное соответствие между и ;
можно установить взаимно однозначное соответствие между и .
Доказать, что если для всех , то (одна из формулировок аксиомы выбора).
Доказать, что между и можно установить взаимно однозначное соответствие, если и .
Доказать, что если отношения и рефлексивны, то рефлексивны отношения , , , .
Доказать, что если отношения и иррефлексивны, то иррефлексивны отношения , , . Показать, что произведение иррефлексивных отношений может не быть иррефлексивным.
Доказать, что если отношения и симметричны, то симметричны отношения , , , .
Доказать, что произведение симметричных отношений и симметрично тогда и только тогда, когда .
Доказать, что:
если отношения и антисимметричны, то антисимметричны также и ;
объединение антисимметричных отношений и на антисимметрично тогда и только тогда, когда .
Построить бинарное отношение:
рефлексивное, симметричное, не транзитивное;
рефлексивное, антисимметричное, не транзитивное;
рефлексивное, транзитивное, не симметричное;
антисимметричное, транзитивное, не рефлексивное.
Построить бинарное отношение, симметричное, транзитивное, но не рефлексивное.
Доказать, что если есть транзитивное и симметричное отношение на множестве и , то есть эквивалентность на .
Доказать, что любое отношение , симметричное и антисимметричное одновременно, является транзитивным.
Доказать, что отношение на множестве является одновременно эквивалентностью и частичным порядком в том и только том случае, когда .
На множествах и определим , , следующим образом:
делится на ;
;
Доказать, что , и являются отношениями эквивалентности.
Пусть --- множество всех прямых на плоскости. Являются ли эквивалентностями следующие отношения:
параллельность прямых;
перпендикулярность прямых?
На множестве действительных чисел определим отношение следующим образом:
Доказать, что есть эквивалентность.
Доказать, что если --- эквивалентность, то:
;
.
Доказать, что если есть эквивалентность, то есть также эквивалентность.
Пусть . Доказать, что
Доказать, что если и --- эквивалентности на , то:
;
.
Доказать, что существует взаимно однозначное соответствие между классом всех разбиений множества на непересекающиеся непустые подмножества и семейством всех отношений эквивалентности на . (Семейство называется разбиением , если и множества попарно не пересекаются.)
Доказать, что тогда и только тогда является отношением эквивалентности на множестве , когда существует система попарно непересекающихся множеств такая, что
Пусть --- произвольная функция. Положим
Доказать, что является эквивалентностью на и для отображения существует разложение
где --- естественное отображение на , т.е. , --- взаимно однозначное соответствие между и .
Доказать, что пересечение любой системы эквивалентностей на множестве есть эквивалентность на .
Доказать, что объединение эквивалентностей и является эквивалентностью тогда и только тогда, когда .
Доказать, что произведение двух эквивалентностей и тогда и только тогда является эквивалентностью, когда .
Доказать, что если и --- эквивалентности и , то , где --- наименьшее отношение эквивалентности, включающее .
Доказать, что для всякого семейства эквивалентностей существует эквивалентность такая, что и для всякого отношения эквивалентности , если , то .
Доказать, что
где --- число эквивалентностей на множестве из элементов.
Доказать, что множество всех подмножеств данного множества частично упорядоченно отношением включения .
Пусть и на множестве определяются обычным образом. Доказать, что ; ; .
Доказать, что есть частичный порядок на .
Пусть и делит . Считаем, что делит . Доказать, что --- частичный порядок на .
Доказать, что всякое частично упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента.
Доказать, что наибольший (наименьший) элемент частично упорядоченного множества является единственным максимальным (минимальным) элементом.
Построить пример частично упорядоченного множества, имеющего точно один минимальный элемент, но не имеющего наименьшего элемента.
Доказать, что если --- частичный порядок, то --- частичный порядок.
Показать, что если --- система частичных порядков на множестве , то --- частичный порядок на множестве .
Доказать, что отношение на множестве есть предпорядок тогда и только тогда, когда .
Пусть --- отношение предпорядка на . Положим
Доказать, что:
есть отношение эквивалентности на ;
если , , , то ;
есть отношение частичного порядка на , где
Доказать, что если --- частичный (линейный, полный) порядок на и , то есть частичный (линейный, полный) порядок на .
Пусть --- частичный порядок на . Доказать, что иррефлексивно и транзитивно.
Доказать, что если некоторое отношение на иррефлексивно и транзитивно, то отношение
есть частичный порядок на .
Показать, что если и --- частично упорядоченные множества и --- монотонная функция, осуществляющая взаимно однозначное соответствие между и , то может не быть монотонной.
Рассмотреть случай, когда --- линейно упорядоченное множество.
Доказать, что любое частично упорядоченное множество изоморфно некоторой системе подмножеств множества , упорядоченной включением .
Пусть и --- линейные порядки на множестве . Когда --- линейный порядок?
Доказать, что любое непустое конечное частично упорядоченное множество содержит минимальный и максимальный элементы.
Пусть частично упорядоченное множество конечно. Доказать, что для любого элемента существуют элементы и из такие, что и есть максимальный элемент в , и есть минимальный элемент в .
Построить линейный порядок на множестве:
;
;
комплексных чисел.
Доказать, что любое конечное множество можно линейно упорядочить.
Доказать, что всякий частичный порядок на конечном множестве может быть продолжен до линейного порядка на множестве (см. также задачу I.5.69).
Пусть --- частично упорядоченное множество, в котором каждая цепь имеет не более элементов, а любое подмножество попарно несравнимых элементов состоит не более чем из элементов. Показать, что имеет не более элементов.
Пусть есть частичный порядок на множестве , --- частичный порядок на множестве . Назовем прямым произведением частично упорядоченных множеств и множество с заданным на нем отношением :
Доказать, что есть частичный порядок на .
Пусть --- частично упорядоченное множество, и . Назовем сегментом множество . Показать, что множество всех сегментов множества , частично упорядоченное по включению, изоморфно некоторому подмножеству прямого произведения и двойственного к нему частично упорядоченного множества.
Назовем частично упорядоченное множество самодвойственным, если оно изоморфно двойственному к нему частично упорядоченному множеству. Доказать, что:
имеются в точности два неизоморфных частично упорядоченных двухэлементных множества, каждое из которых самодвойственно;
имеется пять попарно неизоморфных частично упорядоченных множеств, имеющих три элемента, и три из них самодвойственны.
Будем говорить, что частично упорядоченное множество удовлетворяет:
-
условию минимальности, если всякое непустое подмножество множества обладает по крайней мере одним минимальным элементом;
-
условию обрыва убывающих цепей, если всякая строго убывающая цепь в конечна;
-
условию индуктивности, если для любого свойства выполнено следующее:
пусть для любого элемента из справедливости свойства для всех элементов, строго меньших , вытекает справедливость для , тогда свойством обладают все элементы множества . Доказать эквивалентность всех этих условий.
Доказать, что частично упорядоченное множество удовлетворяет условию минимальности тогда и только тогда, когда все его цепи вполне упорядочены.
Описать все линейно упорядоченные множества , обладающие таким свойством, что для любых существует только конечное число таких, что .
Найти все множества такие, что существует полный порядок такой, что также является полным порядком на .
Пусть и для всех
Определим . Доказать, что:
есть частичный порядок на ;
есть точная нижняя грань относительно порядка .
Доказать, что любое подмножество множества , частично упорядоченное по включению, имеет точную верхнюю грань и точную нижнюю грань.
Доказать, что:
любое линейно упорядоченное множество есть решетка;
семейство всех эквивалентностей на множестве есть решетка.
Доказать, что в решетке любой максимальный элемент является наибольшим, а любой минимальный элемент является наименьшим.
Доказать, что в любой конечной решетке существуют наибольший и наименьший элементы.
Привести примеры решеток:
без наибольшего элемента, но с наименьшим элементом;
без наименьшего элемента, но с наибольшим элементом;
без наибольшего и без наименьшего элементов.
Доказать, что в любой решетке выполнены тождества:
Пусть на множестве заданы двуместные функции и , удовлетворяющие тождествам -- из предыдущей задачи.
Доказать, что для любых тогда и только тогда, когда .
Определим . Доказать, что есть решетка относительно , причем точная нижняя и точная верхняя грани элементов и совпадают с и соответственно.
Доказать, что во всякой булевой алгебре :
существует наименьший элемент и наибольший элемент ;
для всякого дополнение единственно;
и ;
;
;
.
Доказать, что алгебра подмножеств, упорядоченная включением, есть булева алгебра.
Доказать, что и для любого фильтра .
Пусть --- булева алгебра, . Доказать, что если для любого и любых элементов , то множество
есть фильтр на .
Пусть --- фильтр на булевой алгебре и . Доказать, что существует фильтр такой, что или .
Доказать, что для любого фильтра следующие условия эквивалентны:
есть максимальный фильтр;
есть простой фильтр;
есть ультрафильтр.
Доказать, что любой фильтр на булевой алгебре содержится в некотором максимальном фильтре на .
Доказать, что для любых элементов булевой алгебры , если неверно, что , то существует простой фильтр такой, что и .
Пусть --- булева алгебра, --- множество всех простых фильтров на . Положим для
Доказать, что множество
есть алгебра подмножеств множества .
Доказать, что любая булева алгебра изоморфна некоторой алгебре подмножеств подходящего множества (теорема Стоуна).
Доказать, что любой фильтр на конечной булевой алгебре имеет наименьший элемент.
Доказать, что любая конечная булева алгебра изоморфна алгебре всех подмножеств некоторого множества.
Доказать, что:
(рефлексивность);
если , то (симметричность);
если и , то (транзитивность).
Доказать, что:
;
, и ;
если существует функция из на , то .
Пусть и . Доказать, что .
Доказать, что если и , то (теорема Кантора–Бернштейна).
Доказать, что:
всякое подмножество конечного множества конечно;
объединение конечного числа конечных множеств конечно;
прямое произведение конечного числа конечных множеств конечно.
Доказать, что конечное множество не эквивалентно никакому своему собственному подмножеству и никакому собственному надмножеству.
Доказать, что два конечных множества эквивалентны тогда и только тогда, когда они содержат одинаковое число элементов.
Доказать, что кардинальных чисел бесконечно много.
Доказать, что из всякого бесконечного множества можно выделить счетное подмножество.
Доказать, что множество тогда и только тогда бесконечно, когда оно эквивалентно некоторому собственному подмножеству.
Показать, что всякое подмножество счетного множества счетно или конечно.
Пусть область определения функции счетна. Доказать, что область значений этой функции конечна или счетна.
Доказать, что непустое множество является счетным или конечным тогда и только тогда, когда оно есть множество значений некоторой функции из в .
Доказать, что если из счетного множества удалить конечное подмножество, то оставшееся множество будет счетным.
Доказать, что:
если и счетны, то счетно;
если все конечны, непусты и попарно не пересекаются, то счетно;
если все счетны, то счетно.
Доказать, что:
если бесконечно и --- конечное или счетное множество, то ;
если бесконечно и несчетно, конечно или счетно, то .
Доказать, что если счетны, то счетно множество .
Доказать, что:
множество целых чисел счетно;
множество рациональных чисел счетно;
множество рациональных чисел сегмента счетно при ;
множество пар , где и --- рациональные числа, счетно.
Доказать, что множество всех конечных последовательностей, составленных из элементов некоторого счетного множества, есть счетное множество.
Доказать, что множество всех конечных подмножеств счетного множества счетно.
Доказать, что множество многочленов от одной переменной с целыми коэффициентами счетно.
Доказать счетность множества алгебраических чисел, т.е. чисел, являющихся корнями многочленов от одной переменной с целыми коэффициентами.
Доказать, что любое множество попарно непересекающихся открытых интервалов на действительной прямой не более чем счетно.
Доказать, что мощность любого множества попарно непересекающихся букв Т на плоскости не более чем счетна.
Доказать, что если и существует такое, что для всех различных элементов из справедливо , то конечно или счетно.
Доказать, что множество точек разрыва монотонной функции на действительной оси не более чем счетно.
Доказать, что:
;
, где , ;
.
Доказать, что множества точек квадрата и отрезка эквивалентны.
Доказать, что множества точек двух окружностей эквивалентны.
Доказать, что .
Установить взаимно однозначное соответствие между точками квадрата и плоскости.
Доказать, что множество точек сегмента несчетно.
Какова мощность множества иррациональных чисел?
Доказать существование трансцендентных (неалгебраических) чисел.
Доказать, что объединение конечного или счетного числа множеств мощности имеет мощность .
Доказать, что множество всех счетных последовательностей натуральных чисел имеет мощность .
Доказать, что:
множество всех счетных последовательностей, составленных из и , имеет мощность ;
.
Доказать, что:
если для всех , то ;
если для всех и , то .
Какова мощность множества:
всех счетных последовательностей действительных чисел;
всех непрерывных функций на действительной прямой;
всех монотонных функций на действительной прямой?
Пусть --- счетное множество точек на действительной прямой. Можно ли выбрать так, чтобы
Доказать, что множество действительных функций, заданных на сегменте , имеет мощность, большую .
Доказать, что мощность множества всех функций, определенных на сегменте при и разрывных хотя бы в одной точке, больше .
Доказать, что множество всех подмножеств множества имеет мощность, большую .
Пусть --- семейство множеств такое, что для каждого множества из существует множество из , не эквивалентное никакому подмножеству множества . Доказать, что объединение всех множеств из не эквивалентно никакому подмножеству множества из .
Доказать, что не существует множества, содержащего все множества.
Будем говорить, что последовательность натуральных чисел растет быстрее, чем последовательность , если . Доказать, что:
для каждой последовательности натуральных чисел существует последовательность, растущая быстрее ее;
если множество последовательностей обладает свойством, что для каждой последовательности существует последовательность из , растущая быстрее, чем , то множество несчетно.
Доказать, что если линейно упорядоченные множества подобны, то они и эквивалентны.
Доказать, что любое множество , эквивалентное линейно упорядоченному множеству , можно линейно упорядочить так, что станет подобным .
Пусть , , --- линейно упорядоченные множества. Доказать, что:
(рефлексивность);
если , то (симметричность);
если и , то (транзитивность).
Пусть и --- линейно упорядоченные множества. Доказать, что если , то , но обратное неверно.
Доказать, что множество из элементов можно линейно упорядочить способами.
Доказать, что все конечные линейно упорядоченные множества одинаковой мощности подобны между собой.
Доказать, что для бесконечных множеств утверждение предыдущей задачи неверно.
Доказать, что линейно упорядоченные множества подобны тогда и только тогда, когда между ними существует взаимно однозначное соответствие, являющееся монотонным отображением.
Доказать, что для любого линейно упорядоченного множества и любых :
;
если --- наименьший элемент , то ;
--- линейно упорядоченное множество;
если , то .
Доказать, что множество всех отрезков линейно упорядоченного множества , упорядоченное отношением включения, подобно .
Доказать, что бесконечное линейно упорядоченное множество имеет порядковый тип тогда и только тогда, когда оно удовлетворяет следующим условиям:
в имеется наименьший элемент ,
для любого существует точная нижняя грань в множестве ( называется непосредственно следующим за );
для любого подмножества множества из того, что и содержит вместе с каждым своим элементом непосредственно следующий за ним элемент, следует, что .
Доказать, что бесконечное линейно упорядоченное множество имеет порядковый тип тогда и только тогда, когда все его начальные отрезки конечны.
Доказать, что любое счетное линейно упорядоченное множество имеет порядковый тип тогда и только тогда, когда удовлетворяет следующим условиям:
в нет наименьшего и наибольшего элементов;
для любых таких, что , существует такой, что (такой порядок называется плотным).
Доказать, что всякое счетное линейно упорядоченное множество подобно некоторому подмножеству множества рациональных чисел.
Пусть --- линейно упорядоченное множество, содержащее не менее двух элементов, Положим для любых
Доказать, что:
есть линейный порядок на ;
любое счетное линейно упорядоченное множество подобно некоторому подмножеству множества .
Доказать, что порядковый тип любого интервала (не сегмента) действительных чисел есть .
Подмножество линейно упорядоченного множества с порядком называется плотным в , если для любых существует такое, что или . Доказать, что если содержит счетное плотное в подмножество, то подобно некоторому подмножеству множества действительных чисел с естественным порядком.
Показать, что для любого порядкового типа .
Показать, что , , , .
Доказать, что:
для любых порядковых типов и существуют и однозначно определены порядковые типы и ;
для любого линейно упорядоченного множества и любого семейства порядковых типов существует и однозначно определен порядковый тип .
Привести пример порядковых типов и таких, что
Доказать, что:
;
;
;
, но ;
;
;
;
;
есть порядковый тип сегмента при .
Привести пример порядковых типов и таких, что
Доказать, что:
;
;
;
;
;
.
Построить множества порядковых типов
Доказать, что для любых порядковых типов , и
Привести пример порядковых типов , и таких, что
Пусть и --- линейно упорядоченные множества, --- семейство попарно непересекающихся подмножеств множества такое, что . Доказать, что если , то для любого семейства порядковых чисел имеем .
Доказать, что , где для всех и .
Доказать, что:
;
;
, где --- линейно упорядоченное множество, а есть множество с двойственным порядком.
Доказать, что:
всякое конечное линейно упорядоченное множество вполне упорядочено;
множество , где , вполне упорядочено;
множество , где , вполне упорядочено;
множество , где , не является вполне упорядоченным.
Являются ли вполне упорядоченными следующие множества:
множество целых чисел с их естественным порядком;
множество рациональных чисел с обычным порядком ;
множество действительных чисел с обычным порядком ;
множество чисел вида , где --- положительное целое число, с обычным порядком ?
Доказать, что:
всякое непустое вполне упорядоченное множество имеет наименьший элемент;
каждое подмножество вполне упорядоченного множества вполне упорядочено.
Доказать, что если и вполне упорядочено, то можно вполне упорядочить так, чтобы было .
Показать, что если --- вполне упорядоченное множество, то у каждого элемента множества , кроме наибольшего, имеется непосредственно следующий за ним элемент (см. задачу I.5.11).
Можно ли во вполне упорядоченном множестве выделить бесконечную убывающую цепь элементов ?
Доказать, что линейно упорядоченное множество вполне упорядочено тогда и только тогда, когда оно не содержит подмножества типа .
Пусть --- вполне упорядоченное множество. Доказать, что не существует такого монотонного взаимно однозначного соответствия , чтобы для некоторого элемента было .
Доказать, что вполне упорядоченное множество не может быть подобным своему отрезку или части своего отрезка.
Доказать, что два различных отрезка вполне упорядоченного множества не могут быть подобными.
Доказать, что существует не более одного изоморфизма двух вполне упорядоченных множеств.
Доказать, что из двух вполне упорядоченных множеств одно подобно другому или его отрезку.
Доказать, что линейно упорядоченное множество конечно тогда и только тогда, когда оно вполне упорядочено как относительно заданного, так и относительно двойственного порядка.
Пусть --- вполне упорядоченное множество, и для любого элемента множество удовлетворяет условию: если , то . Доказать, что (принцип трансфинитной индукции).
Пусть , --- произвольные порядковые числа. Доказать, что:
или или ;
из указанных выше условий выполняется для и лишь одно.
Пусть , где и --- порядковые числа. Показать, что .
Доказать, что всякое множество порядковых чисел вполне упорядочено.
Доказать, что для любого множества порядковых чисел :
существует порядковое число, большее всех чисел из ;
среди порядковых чисел, не принадлежащих множеству , существует наименьшее.
Доказать, что не существует множества, содержащего все порядковые числа.
Доказать, что есть порядковое число, непосредственно следующее за (см. задачу I.5.11).
Доказать, что для любого порядкового числа имеет место одно и только одно из утверждений:
-
;
-
множество имеет максимальный элемент;
-
— предельное порядковое число.
Доказать, что любое порядковое число представимо в виде , где есть предельное порядковое число или , --- натуральное число.
Доказать, что:
сумма двух порядковых чисел есть порядковое число;
произведение двух порядковых чисел есть порядковое число;
упорядоченная сумма порядковых чисел, где множество индексов вполне упорядочено, есть порядковое число.
Пусть и линейно упорядочены. Доказать, что если и есть порядковое число, то и все вполне упорядочены.
Доказать, что:
если и вполне упорядочены и , то ;
, ;
;
;
;
.
Привести пример порядковых чисел , и таких, что
Доказать, что:
;
, если ;
;
, если ;
.
Пусть . Порядковое число называется разностью и и обозначается через , если .
Доказать, что:
существует и единственно;
;
;
.
Доказать, что:
если и , то ;
если , то существуют и единственны такие и , что , и ;
если , то для любого существуют и единственны такие и , что и (теорема о делении с остатком).
Доказать, что для любых порядковых чисел и , если и , то существуют натуральное число и порядковые числа такие, что и , , (алгоритм Евклида).
Пусть свойство таково, что для любого ординального числа из того, что все ординальные числа обладают свойством , следует, что обладает свойством . Доказать, что все ординальные числа обладают свойством (принцип трансфинитной индукции для ординальных чисел).
Доказать, что для любых порядковых чисел и существует и единственно .
Построить множество порядкового типа .
Доказать, что:
если и , то ;
;
.
Доказать, что:
если и , то ;
если и , то ;
если и , то существуют и однозначно определены и такие, что
если и , то существуют натуральное число и такие последовательности порядковых чисел и , что
Множество называется транзитивным, если отношение
вполне упорядочивает , и если из , следует . Доказать, что для любого порядкового числа существует и единственно транзитивное множество, упорядоченное по типу .
Следующее утверждение называется аксиомой выбора.
-
Аксиома выбора. Пусть — непустое множество для любого . Тогда существует функция выбора такая, что для любого . Доказать, что каждое из следующих утверждений эквивалентно аксиоме выбора.
-
Лемма Цорна. Частично упорядоченное множество, каждое из линейно упорядоченных подмножеств которого имеет верхнюю грань, содержит максимальный элемент.
-
Принцип максимальности Куратовского–Хаусдорфа. Каждая цепь частично упорядоченного множества содержится в некоторой максимальной цепи.
-
Аксиома Цермело. Для любого семейства непустых попарно непересекающихся множеств существует такое множество , что для каждого состоит ровно из одной точки.
-
Теорема Цермело. Каждое множество можно вполне упорядочить.
-
Лемма Тейхмюллера–Тьюки. Каждое семейство множеств, имеющее конечный характер, обладает максимальным элементом. (Семейство множеств имеет конечный характер, если оно удовлетворяет условию: каждое конечное подмножество множества принадлежит .)
Пусть --- частично упорядоченное множество, в котором каждая цепь имеет верхнюю грань, и . Доказать, что существует максимальный элемент такой, что .
Пусть --- множество подмножеств множества такое, что для каждой цепи (порядок по включению) объединение множеств из принадлежит . Доказать, что тогда имеет максимальный элемент.
Доказать, что для всякого частичного порядка на множестве существует линейный порядок на множестве такой, что .
Доказать, что для произвольных мощностей и выполняется одно и только одно из условий , или (трихотомия).
Доказать, что кардинальные числа линейно упорядочены отношением .
Доказать, что среди кардинальных чисел нет наибольшего.
Доказать, что:
;
, где конечное;
;
;
.
Доказать, что:
для любых множеств существуют множества такие, что , и ;
сумма двух кардинальных чисел всегда существует.
Доказать для произвольных кардинальных чисел:
;
;
.
Пусть , , , --- конечные множества. Доказать, что:
;
;
Доказать, что .
Привести пример таких кардинальных чисел и , что , но .
Доказать, что тогда и только тогда, когда существует такое, что . Показать, что такое определяется не однозначно.
Доказать, что:
;
;
;
.
Доказать, что:
если и , то ;
произведение двух кардинальных чисел всегда существует.
Доказать для произвольных кардинальных чисел:
;
;
;
;
;
, если --- конечное, а --- бесконечное кардинальное число;
, если --- бесконечное кардинальное число.
Доказать, что , если --- бесконечное кардинальное число.
Доказать, что если и --- кардинальные числа и одно из них бесконечно, то , если и .
Доказать, что:
;
;
.
Доказать, что для двух кардинальных чисел и всегда существует .
Доказать для произвольных кардинальных чисел , и :
;
;
;
;
.
Доказать, что .
Доказать для произвольных кардинальных чисел:
если и , то ;
если , то ;
если , то ;
если , то ;
если , то ;
если , то ;
тогда и только тогда, когда ;
если и , то ;
тогда и только тогда, когда ;
тогда и только тогда, когда ;
.
Доказать для произвольных кардинальных чисел:
если , то ;
если , то , а --- конечное.
Доказать для произвольных кардинальных чисел:
если , то ;
если , , то .
Доказать для произвольных кардинальных чисел:
если , для всех , то ;
если и конечно, то ;
если , то .
Доказать, что
Пусть --- семейство кардинальных чисел, причем для . Доказать, что
Пусть --- семейство кардинальных чисел, причем для . Доказать, что
Доказать, что тогда и только тогда, когда существует такое, что .
Доказать, что если --- подстановка на множестве , то:
;
.
Пусть есть разбиение множества на непустые попарно непересекающиеся множества. Доказать, что:
;
.
Доказать, что:
;
, где .
Доказать, что если для всех , то:
;
.
Пусть . Доказать, что:
;
, где для .
Пусть и --- два семейства кардинальных чисел и для всех . Доказать, что:
если для всех , то ;
если для всех , то .
Пусть Доказать, что .
Пусть , --- семейство кардинальных чисел, не превосходящих , . Доказать, что .
Пусть и --- кардинальные числа, и для каждого . Доказать, что .
Доказать, что:
;
.
Доказать, что для любого кардинального числа нельзя представить в виде , где .