Математика · объяснение и практика
Теорема Шпернера: сколько подмножеств могут не содержать друг друга
Доказываем взвешенную оценку через полные цепи и перестановки, получаем центральный биномиальный предел и отличаем необходимое неравенство от критерия несравнимости.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
Семейство различных подмножеств n-элементного множества называется антицепью, если никакое из них не включено в другое. Его размер не превосходит C(n,⌊n/2⌋). Граница достигается всеми подмножествами одного среднего размера; доказательство использует то, что полная цепь содержит не больше одного элемента антицепи.
Несравнимость не означает непересечение
Множества {1,2} и {2,3} пересекаются, но ни одно не содержит другого. Они могут одновременно входить в антицепь. Пустое множество, наоборот, включено в каждое, поэтому антицепь с ним не может содержать другой объект. Аналогично полное исходное множество несовместимо в антицепи с любым другим его подмножеством.
Все разные подмножества одного размера образуют антицепь: строгое включение уменьшило бы число элементов. Выбрав средний размер, получаем C(n,⌊n/2⌋) объектов. Это доказывает достижимость предложенной границы, но ещё не её универсальность. Семейство может смешивать размеры, и простой подсчёт только одного слоя не запрещает ему оказаться больше. Для запрета нужна оценка, одновременно охватывающая все размеры.
Полная цепь соответствует порядку добавления элементов
Зафиксируем перестановку исходных n элементов. Последовательно добавляя их, получим цепь из пустого множества, одного элемента, двух и так далее до полного множества. Всего таких цепей n!, поскольку по цепи однозначно восстанавливается, какой элемент добавился на каждом шаге. В одной цепи все множества сравнимы, поэтому антицепь пересекает её не более чем в одном месте.
Посчитаем пары «множество A из семейства, полная цепь через A». Если |A|=k, первые k добавлений должны быть элементами A в любом порядке, а остальные — дополнением также в любом порядке. Поэтому через A проходят k!(n−k)! цепей. Суммирование по семейству не превосходит n!, так как ни одна цепь не может дать две пары. После деления получается сумма 1/C(n,|A|) по всем A не больше единицы.
Пример
Сколько максимум различных подмножеств шестичленного множества можно взять без включения одного в другое? Обоснуйте достижение, а не только оценку.
Центральный коэффициент C(6,3)=20. По теореме антицепь больше 20 невозможна. Все двадцать трёхэлементных подмножеств подходят: разные множества одной мощности не могут включаться друг в друга. Поэтому 20 — точный максимум. Число всех подмножеств 64 не подходит, поскольку в полном семействе есть многочисленные включения, в том числе через пустое множество.
Центральный коэффициент превращает взвешенный бюджет в обычный
Биномиальные коэффициенты максимальны в середине строки: отношение C(n,k+1)/C(n,k)=(n−k)/(k+1) показывает рост до середины и убывание после неё. Пусть M — центральный максимум. Тогда каждое слагаемое 1/C(n,|A|) не меньше 1/M. Если элементов семейства больше M, взвешенная сумма превысит единицу. Значит, размер антицепи не больше M, как и требовалось.
Обратное заключение из взвешенного неравенства неверно. Семейство {1} и {1,2} при n=4 имеет бюджет 1/4+1/6≤1, но первое множество включено во второе. Неравенство необходимо для антицепи, а не проверяет каждую пару. Также семейство, которое нельзя расширить без нарушения, не обязательно самое большое: одинокое пустое множество уже нерасширяемо, но при n≥2 средний слой больше. В задаче важно различать максимальность по включению и наибольшую численность.
От чтения к действию
А теперь — вы
Частые вопросы
Антицепь запрещает общие элементы?
Нет. Она запрещает включение одного множества в другое. Непустое пересечение само по себе не нарушает условие.
Бюджет не больше единицы доказывает антицепь?
Нет. Это необходимое следствие, а не обратный критерий. Нужно ещё проверить отсутствие включений между конкретными множествами.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему в частичном порядке не всякая пара сравнима
Как распознавать частичный порядок, различать несравнимые элементы, максимальный и наибольший объект и читать порядок по включению или делимости.
Открыть темуКак один набор пар даёт два способа подсчёта
Как доказать равенство двух сумм через один набор пар, выбрать учитываемую связь и проверить, что каждая сторона действительно считает те же объекты.
Открыть темуПочему множество всех подмножеств имеет два в степени n элементов
Почему все подмножества образуют новый набор из двух в степени n элементов, как кодировать выбор битами и что происходит при пустом исходном множестве.
Открыть тему