Вполне упорядоченное множество: определение и примеры

Вполне упорядоченное множество - это множество с линейным порядком, в котором у каждого непустого подмножества есть наименьший элемент. Например, какое бы непустое множество натуральных чисел мы ни выбрали, в нём найдётся первое число. Требование относится ко всем подмножествам, а не только к самому исходному множеству. Чтобы увидеть разницу, ниже можно перебрать подмножества конечного примера и проследить, как меняется минимум.
Определение: порядок и наименьший элемент
Пусть на множестве задан линейный порядок : любые два элемента сравнимы, отношение рефлексивно, антисимметрично и транзитивно. Пара вполне упорядочена, если для каждого непустого существует , для которого при любом . Элемент называют наименьшим, или минимумом, .
Здесь важны два условия. Во-первых, минимум сам принадлежит выбранному подмножеству. Во-вторых, он не больше каждого его элемента. У пустого множества элемента нет, поэтому определение специально говорит о непустых подмножествах. Само пустое множество с пустым порядком считается вполне упорядоченным: подмножеств, нарушающих условие, у него нет.
В конечном примере выбранное подмножество может меняться, но его минимум всегда входит в выборку. На видео золотым отмечен именно он; элементы с тонкой окружностью в текущий выбор не входят.
Слово «упорядоченное» не означает, что элементы обязательно записаны по возрастанию на бумаге. Порядок - это отношение между ними. Например, записи и задают одно множество; при обычном порядке его минимум равен .
Как проверить конечный пример
Пусть с обычным порядком, а . Число принадлежит и не больше обоих его элементов, поэтому . Число меньше , но не подходит: оно находится в , а не в .

У множества из четырёх элементов всего подмножеств, из них непустых. Ползунок позволяет перебрать эти вариантов: например, при номере 10 получаем . Номер здесь задаётся двоичной маской включения элементов, а не их суммой. Принцип подсчёта разобран в статье о числе подмножеств множества.
Для произвольного конечного линейно упорядоченного множества не обязательно выписывать все подмножества. Выберите любое непустое из них и последовательно сравните его конечное число элементов: после последнего сравнения останется наименьший. Значит, любой линейный порядок на конечном множестве является вполне упорядоченным. Но вычислительный перебор конечного набора не доказывает утверждение для бесконечного множества.
Натуральные числа и принцип наименьшего элемента
Возьмём с обычным порядком. Принцип вполне упорядоченности натуральных чисел утверждает: всякое непустое содержит наименьшее число. Если в конкретном курсе ноль относят к натуральным числам, утверждение остаётся верным для .
Например, множество чётных положительных чисел бесконечно, но его минимум равен . У множества натуральных чисел, больших миллиона, минимум равен . Бесконечность сама по себе не мешает существованию минимума: важно, как множество расположено в данном порядке.
Это свойство наследуется подмножеством. Если вполне упорядочено и получает тот же порядок, всякое непустое подмножество одновременно является непустым подмножеством . Поэтому его минимум существует. Вопрос о выборе подмножеств и операциях с ними удобно уточнять отдельно в материале об операциях над множествами.
Контрпримеры: когда минимума не хватает
Целые числа с обычным порядком не вполне упорядочены: у самого нет наименьшего элемента. Для любого целого число тоже целое и строго меньше. Достаточно одного такого непустого подмножества, чтобы опровергнуть полную упорядоченность.
Наличие минимума у всего множества тоже недостаточно. Возьмём с обычным порядком. У есть минимум . Однако у подмножества минимума нет: для любого число принадлежит и меньше. Ноль служит нижней гранью , но в не входит и потому не является его минимумом.
Аналогично имеет минимум , но его подмножество минимума не имеет: половина любого его элемента тоже лежит в и меньше. Это пример того, почему проверка только исходного множества пропускает существенную часть определения.
Один набор элементов, разные порядки
Свойство относится к паре «множество и порядок». На обычный порядок не подходит, зато можно задать другой: . Точнее, сначала сравниваем абсолютные значения, а при равных ненулевых модулях ставим положительное число раньше отрицательного. Любое непустое подмножество имеет элемент с наименьшим модулем; среди не более чем двух кандидатов одного модуля выбираем первый по этому правилу. Значит, новый порядок вполне упорядочивает .
В более общем виде теорема о вполне упорядочении утверждает, что любое множество допускает некоторый вполне упорядочивающий порядок. В стандартной теории множеств она эквивалентна аксиоме выбора. Утверждение о существовании такого порядка на действительных числах не говорит, что их обычный числовой порядок вполне упорядочен. Связь с другой эквивалентной формулировкой рассмотрена в статье о лемме Цорна.
Элемент после бесконечной последовательности
Не всякий вполне упорядоченный порядок похож на привычный ряд натуральных чисел. Добавим к натуральным числам новый элемент и поставим его после каждого натурального: . Для любого непустого подмножества, содержащего натуральное число, минимум находится среди его натуральных элементов. Если натуральных элементов нет, непустое подмножество состоит только из , и этот элемент сам является минимумом. Следовательно, полученный порядок вполне упорядочен.
При этом у нет непосредственного предшественника: какое бы натуральное число мы ни назвали, следующее натуральное тоже меньше . Этот пример показывает, почему шаг «от предыдущего к следующему» сам по себе не охватывает все вполне упорядоченные множества. Для доказательства свойства в точке нужно отдельно обосновать переход, используя информацию обо всех предшествующих элементах. В этом состоит роль предельного шага трансфинитной индукции. Бесконечное многоточие в записи обозначает порядок, а не процесс, который программа должна буквально закончить перед переходом к новому элементу.
Зачем это нужно для индукции и алгоритмов
Принцип наименьшего элемента объясняет доказательство математической индукцией. Пусть утверждение верно для , а из его верности для следует верность для . Если бы существовали натуральные контрпримеры, среди них был бы наименьший . Он не равен ; значит, - натуральное число, которое не является контрпримером. Шаг индукции тогда даёт верность утверждения для : противоречие.
Тот же приём работает шире: в трансфинитной индукции для каждого элемента доказывают утверждение, предполагая его верным для всех меньших элементов. Если бы остался контрпример, можно было бы взять наименьший и получить противоречие. Это не требует, чтобы каждый элемент имел непосредственного предшественника.
В информатике близкая идея помогает доказывать завершение рекурсии: каждой конфигурации сопоставляют значение в вполне упорядоченном множестве и показывают, что при каждом рекурсивном вызове оно строго уменьшается. Бесконечной последовательности таких уменьшений быть не может, иначе множество её значений имело бы минимум, после которого последовательность всё равно должна была бы уменьшиться. Например, если натуральная мера уменьшается на каждом шаге, бесконечная цепочка вызовов исключена. Это доказательство завершения, а не оценка времени работы.
Для составных состояний используют, например, пары натуральных чисел с лексикографическим порядком: сначала сравнивают первые координаты, при равенстве - вторые. Тогда сначала находят наименьшую первую координату среди элементов подмножества, а среди пар с ней - наименьшую вторую. О том, как устроено множество таких пар, см. статью о декартовом произведении.
Частые ошибки
- Проверять только минимум всего . Нужно проверить каждое непустое подмножество; пример с показывает разницу.
- Путать минимум с нижней гранью. Минимум обязательно принадлежит рассматриваемому подмножеству.
- Считать любой линейный порядок полным в этом смысле. Обычный порядок на линеен, но не вполне упорядочен.
- Игнорировать выбранное отношение. Одни и те же целые числа при разных порядках дают разные ответы.
- Считать отсутствие последнего элемента препятствием. У натуральных чисел нет наибольшего элемента, но они вполне упорядочены.
FAQ
Каждое ли бесконечное множество не вполне упорядочено?
Нет. Натуральные числа при обычном порядке бесконечны и вполне упорядочены. Нужно проверять существование минимумов подмножеств, а не число элементов.
Чем наименьший элемент отличается от минимального?
Наименьший сравним со всеми и не больше каждого элемента. В частичном порядке минимальный элемент означает лишь, что строго меньшего элемента нет; несколько минимальных элементов могут быть несравнимы. В линейном порядке эти понятия совпадают.
Может ли вполне упорядоченное множество не иметь наибольшего элемента?
Да. В каждое непустое подмножество имеет минимум, но к любому натуральному числу можно прибавить единицу. Определение не требует максимума.
Коротко
Вполне упорядоченное множество - линейно упорядоченное множество, у каждого непустого подмножества которого есть минимум. Для опровержения достаточно одного подмножества без минимума; для доказательства требуется общий аргумент. Это свойство лежит в основе рассуждений о наименьшем контрпримере, индукции и завершении рекурсивных процессов.
Читайте также

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

Декартово произведение множеств: примеры и формула
Декартово произведение множеств: что такое упорядоченная пара, как перечислить все элементы A x B, найти мощность и применить к координатной плоскости - с разбором типовых задач.

Принцип включения-исключения: формула и примеры
Принцип включения-исключения: формула для двух и трёх множеств, вывод через диаграмму Венна, задачи на делимость и вероятность, частые ошибки студентов.

Булев куб: вершины, рёбра и расстояние Хэмминга
Булев куб простыми словами: как двоичные наборы становятся вершинами, когда они соседствуют, сколько в кубе рёбер и как найти расстояние между вершинами.

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

Гиперграф: что это такое и как его построить
Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.