открытая запись
В комментах к этой Открытой Записи приветствуются любые темы, любые комменты, любые вопросы, любые ответы, любые дискуссии.
Давайте поговорим о чем-нибудь.
Давайте поговорим о чем-нибудь.
June 5th, 2014
теория множеств (математика)
Читаю книгу Кунена по теории множеств (для себя, просто чтобы вспомнить кое-какие вещи). Некоторые теоремы и леммы пытаюсь доказывать сам, не заглядывая в текст. Заржавевшие мозги страшно скрипят. Над следующей задачкой вчера думал три часа, но все-таки придумал. Может, кому-то еще будет интересно подумать над элементарной леммой из теории множеств:
Набор множеств S называется дельта-системой, если есть такое фиксированное множество r, что пересечение любых двух разных множеств из S равно в точности r (в частном случае r = Ø S является попарно непересекающимся). Доказать, что у любого несчетного (uncountable) набора конечных множеств X есть опять-таки несчетный поднабор S, являющийся дельта-системой.
Мое доказательство под катом.
[спойлер]
Мое доказательство: пусть дан несчетный набор X конечных множеств. Сгруппируем все множества размером n в нем в поднабор X_n. Хотя бы один X_n должен быть несчетным, и достаточно доказать утверждение леммы для него, т.е. зная, что все множества одного размера n. Доказывать будем индукцией по n. В случае n=1 X_n является попарно непересекающимся и доказывать ничего не надо.
В общем случае зададимся вопросом, есть ли элемент y, который входит в несчетное количество членов X_n? Если да, то рассмотрим только поднабор Y, состоящий из множеств, содержащих y, и удалим из всех этих множеств y. Получим несчетный набор с множествами размером n-1, по индуктивному предположению в нем найдется дельта-система над фиксированным множеством r, и добавив обратно y к множествам этой дельта-системы и к r, получим искомое.
Если же каждый элемент, который встречается в множествах X_n, входит в них максимум счетное число раз, то построим несчетный попарно непересекающийся поднабор следующим образом. Выбираем любой член набора {x_1...x_n}, и выбрасываем из рассмотрения все члены, в которых есть любые из элементов x_1...x_n. Таковых не более чем счетное число, поэтому у нас все еще остается несчетное число кандидатов X_n, и мы можем повторить эту процедуру несчетное число раз и построить несчетный попарно непересекающийся поднабор.
Набор множеств S называется дельта-системой, если есть такое фиксированное множество r, что пересечение любых двух разных множеств из S равно в точности r (в частном случае r = Ø S является попарно непересекающимся). Доказать, что у любого несчетного (uncountable) набора конечных множеств X есть опять-таки несчетный поднабор S, являющийся дельта-системой.
Мое доказательство под катом.
[спойлер]
Мое доказательство: пусть дан несчетный набор X конечных множеств. Сгруппируем все множества размером n в нем в поднабор X_n. Хотя бы один X_n должен быть несчетным, и достаточно доказать утверждение леммы для него, т.е. зная, что все множества одного размера n. Доказывать будем индукцией по n. В случае n=1 X_n является попарно непересекающимся и доказывать ничего не надо.
В общем случае зададимся вопросом, есть ли элемент y, который входит в несчетное количество членов X_n? Если да, то рассмотрим только поднабор Y, состоящий из множеств, содержащих y, и удалим из всех этих множеств y. Получим несчетный набор с множествами размером n-1, по индуктивному предположению в нем найдется дельта-система над фиксированным множеством r, и добавив обратно y к множествам этой дельта-системы и к r, получим искомое.
Если же каждый элемент, который встречается в множествах X_n, входит в них максимум счетное число раз, то построим несчетный попарно непересекающийся поднабор следующим образом. Выбираем любой член набора {x_1...x_n}, и выбрасываем из рассмотрения все члены, в которых есть любые из элементов x_1...x_n. Таковых не более чем счетное число, поэтому у нас все еще остается несчетное число кандидатов X_n, и мы можем повторить эту процедуру несчетное число раз и построить несчетный попарно непересекающийся поднабор.
