Соответствия, сравнения, количества

(a) Если все множества пересекаются, то достаточно и одного подсемейства. Итак пусть есть два непересекающихся множества, назовём элементы первого и второго — и Тогда если имеются множества и и то тройка и и и не удовлетворяет условию. Значит множества, содержащие по элементу и не содержащие и это либо множества только с (либо только с случаи симметричны), либо пара множеств и и То же можно сказать и про множества, содержащие по элементу из и Тогда глобально можем выделить три случая (остальные симметричны).

Первый случай: не существует множеств, содержащих элемент и второй не из и не существует множеств, содержащих элемент и второй не из Тогда искомые подсемейства можно предъявить так: в первом все множества, содержащие во втором все множества, не лежащие в первом подсемействе, содержащие элемент в третьем все оставшиеся множества.

Второй случай: не существует множеств, содержащих элемент и второй не из и не существует множеств, содержащих элементы и не содержащие и помимо и и Тогда искомые подсемейства можно предъявить так: в первом все множества, содержащие во втором множества и и и в третьем все оставшиеся.

Третий случай: не существует множеств, содержащих элементы и не содержащих элементы и помимо и и и не существует множеств, содержащих элементы и не содержащих и помимо и и и могут совпадать). Тогда искомые подсемейства можно предъявить так: в первом множества и и и во втором множества и и и в третьем все оставшиеся. Нетрудно убедиться, что действительно во всех случаях в каждоподсемействе любые два множества имеют общий элемент.

(b) Доказательство существования разбиения пунктом выше. Предъявим пример, при котором двух множеств не хватит. Пусть наше семейство — всевозможные пары различных элементов множества Всего таких множеств Если их можно разбить на два подсемейства указанным образом, хотя бы в одном подсемействе разбиения будет хотя бы множеств. Без ограничения общности скажем, что в нём есть множества и и Тогда если в нём есть ещё множество с двойкой, то это только и в таком случае других множеств в подсемействе быть не может, итого множеств. Если множеств с двойкой больше нет, то все содержат а таких множеств всего

(c) Для начала докажем существование разбиения. Если для любых множеств у каких-то двух из них найдётся общий элемент, можно осуществить спуск от к (для маленького утверждение доказано). Итак пусть есть непересекающихся множеств, назовём элементы первого и второго — и и Тогда если имеются множества и и то множеств и и и и в них никакие два не имеют общего элемента, противоречие с условием. Значит, множества, содержащие по элементу из и не содержащие элементов от это либо множества только с (либо только с случаи симметричны), либо пара множеств и и То же можно сказать и про множества, содержащие по элементу из и и

Тогда если среди элементов и есть элемент, скажем с которым нет множеств с элементами помимо то выберем в качестве подсемейств следующие множества: все множества, содержащие все ещё не лежащие ни в одном подсемействе множества, содержащие все ещё не лежащие ни в одном подсемействе множества, содержащие

Если же среди любой содержится в множестве с каким-то кроме то для пары элементов и существует не более одного элемента не из с которыми они в множествах, притом в каждой паре для обоих элементов существуют множества с таким элементом. Назовём такой элемент Выберем подсемейства следующим образом: множества и и и в первом, во втором все множества, содержащие третий элемент, в третьем все ещё не лежащие в подсемействах множества, содержащие четвёртый элемент, в все множества, ещё не лежащие в подсемействах, содержащие

Теперь приведём пример семейства множеств, удовлетворяющих условиям, которые не удастся разбить на подсемейства, чтобы в подсемействах любая пара множеств имела общий элемент. Пусть имеются элементы а множества — всевозможные пары двух различных. Условие на существование общего элемента в какой-то паре множеств из любых p множеств выполняется в силу количественных соображений (участий в множествах а возможных участников-элементов Множеств же всего Итак, любое подсемейство это либо всевозможные пары множеств на трёх элементах, либо какой-то набор множеств, содержащих общий элемент. Тогда если семейств первого вида а всего семейств менее то семейства второго вида содержат не более Всего получается множеств в семействе не более для величина максимальна при в таком случае она равна а это строго меньше суммы чисел от до а значит, и нашего числа множеств.