теория множеств (математика)

[avva]

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

Набор множеств 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, и мы можем повторить эту процедуру несчетное число раз и построить несчетный попарно непересекающийся поднабор.

Comments

[krolik-ja.livejournal.com]

"Выбираем любой член набора {x_1...x_n}, и выбрасываем из рассмотрения все члены, в которых есть любые из элементов x_1...x_n. " -- это как?

[avva.livejournal.com]

Строим два набора A и B, на каждом шагу добавляем в A какой-нибудь произвольный член X\B, а в B - все члены X\B, в которых есть хоть один общий элемент с тем членом, что мы добавили в A. Из этого построения следует, что каждый добавленный в A член будет не пересекаться со всеми уже имеющимися в A.

Из нашего предположения следует, что на каждом шагу мы добавлем в B максимум счетное число членов X, и поэтому после любого счетного числа шагов B будет счетным, а X\B поэтому непустым и даже несчетным, так что мы сможем сделать следующий шаг. Из этого следует, что мы сможем сделать несчетное число шагов (собственно, |X| шагов) и построить несчетный набор A (собственно, размером |X|).

(P.S. если совсем строго, то нужно расписать построение A и B по трансфинитной индукции: мы на самом деле строим A_delta и B_delta по индукции delta ≤ |X|).

(P.P.S. если совсем совсем строго, то я немного неправ выше: не факт, что мы сделаем |X| шагов и получим набор размером |X|. Нам это гарантировано, только если |X| - регулярный кардинал. Если это не так, то может случиться, что у нас кончатся элементы для добавления в A через какое-то меньшее, чем |X|, число шагов, но оно все равно будет несчетным, и у нас все равно получится несчетный набор, хоть и меньше по размеру, чем |X|).

[kaathewise.livejournal.com]

Я думаю, лучше переформулировать это так: т.к. каждый элемент встречается счетное число раз, то каждое множество пересекается не более чем со счетным числом других; поэтому поступим так: возьмем первое множество, и выкинем те, которые с ним пересекаются, потом возьмем одно из оставшихся и т.д.

Но тут нужная трансфинитная индукция, а я не могу сразу ее представить.

вредности ради :)

[grizzlyv.livejournal.com]

В случае n=1 доказывать действительно ничего не надо, но X_n не обязан быть попарно непересекающимся. Или все множества предполагаются различными?

Re: вредности ради :)

[avva.livejournal.com]

Да, мы работаем с X_n в рамках теории множеств, т.е. X_n - множество (хоть я его для ясности называю набором), и его члены "не повторяются". Если n=2, например, то легко могут быть два разных члена X_n с нетривиальным пересечением, типа {0,1} и {0,2}. Но при n=1 это невозможно.

Re: вредности ради :)

[grizzlyv.livejournal.com]

Да, конечно.

[onanymous.myopenid.com (from livejournal.com)]

AC, значит, нужна.

[avva.livejournal.com]

В моем док-ве, понятно, нужна, потому что без AC нет причины считать мощность X кардиналом, нет возможности применить к ней трансфинитную индукцию итд.

Сама формулировка леммы не требует AC, но когда есть утверждение о существовании чего-то несчетного, что нужно как-то выбрать из чего-то большего, то понятно, что автоматически подозреваешь необходимость AC. Так что полагаю, что нужна, но поручиться не берусь.

[migmit.livejournal.com]

Строго говоря, нам тут нужна (да и возможна) только индукция до первого несчётного ординала.

[avva.livejournal.com]

Да, вы правы, но все равно без AC как без рук: даже нельзя пользоваться тем, что счетное объединение счетных множеств счетно. Поэтому док-во рушится в нескольких местах: и в начале при переходе от X к X_n, и при индукции даже до первого несчетного ординала не получается обеспечить выбор нового члена для A на каждом шаге.

Может, Axiom of Countable Choice хватит для док-ва? Я недостаточно уверенно себя тут чувствую.

[grizzlyv.livejournal.com]

Мы ведь можем предположить от противного, что выбран некоторый (один из возможных) счётный набор Z_n попарно непересекающихся множеств, в который уже нельзя добавить множество из X_n. Такое предположение разве выходит за рамки Axiom of Countable Choice?

А дальше так же приходим к нужному противоречию с другой стороны: ведь во всём X_n не более счётного количества множеств содержат элементы из множеств Z_n. Значит, есть чего добавить.

Здесь в явном виде трансфинитная индукция не предполагается. Или опять путаю?

[avva.livejournal.com]

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

Я недостаточно хорошо помню формальный аппарат ZF, чтобы хорошо представлять себе, можно ли в ZF+ACC формализовать "возьмем какой-то элемент несчетного множества X\B, про которое мы знаем, что оно непустое, и добавим в A". Возможно, все работает, а у меня просто путаница в голове, но не уверен.

[grizzlyv.livejournal.com]

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

Нам ведь не нужно строить решение -- только доказать его существование.

UPD. Хотя AC может потребоваться в утверждении о невозможности выбора ("набор, в который нельзя ничего добавить"), как ни странно это звучит. Здесь у меня не хватает понимания.

UPD2. В любом случае взять (выбрать) элемент из непустого множества -- это всё же элементарная операция над множеством. Она не требует никакой из AC. AC нужна, чтобы делать выбор по элементу из (бесконечных) наборов множеств.

[avva.livejournal.com]

Кажется, эта статья отвечает на все наши вопросы:

The Strength of the Δ-system Lemma
PAUL HOWARD and JEFFREY SOLSKI

http://projecteuclid.org/download/pdf_1/euclid.ndjfl/1093634567

Согласно этой статье, требуется больше, чем ACC: а именно, существование, для любого несчетного множества, несчетного подмножества с функцией выбора на нем. Это слабее, чем AC, потому что подмножество может быть намного меньше исходного множества. Подробности в Theorem 2.4.

[grizzlyv.livejournal.com]

Спасибо, очень интересно!
Да, снимает все вопросы. И написано на редкость понятно, как для мат.статьи.