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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Вполне упорядоченное множество — линейно упорядоченное множество M такое, что в любом его непустом подмножестве есть минимальный элемент, другими словами, это фундированное множество с линейным порядком.

Примеры[править | править код]

  • Пустое множество является вполне упорядоченным.
  • Простейший пример бесконечного вполне упорядоченного множества — множество натуральных чисел с естественным упорядочением.
  • Множество целых чисел не является вполне упорядоченным, так как, например, среди отрицательных чисел нет наименьшего. Однако его можно сделать вполне упорядоченным, если определить нестандартное отношение «меньше или равно»[1], которое обозначим и определим следующим образом:
если либо либо либо и
Тогда порядок целых чисел будет таким: В частности, будет наименьшим отрицательным числом.
  • Простейшим примером несчётного вполне упорядоченного множества является совокупность всех счётных порядковых чисел, упорядоченных отношением . В предположении континуум-гипотезы, его мощность равна мощности континуума.

Свойства[править | править код]

  • Утверждение о том, что каждое множество можно вполне упорядочить, равносильно аксиоме выбора. Если принять эту аксиому, то множество вещественных чисел можно вполне упорядочить, однако явное описание того, как это сделать, неизвестно.
  • Если X и Y — два вполне упорядоченных множества, то либо они изоморфны друг другу, либо ровно одно из них изоморфно начальному отрезку другого.

См. также[править | править код]

Литература[править | править код]

Примечания[править | править код]

  1. Дональд Кнут. Искусство программирования, том I. Основные алгоритмы. — М.: Мир, 1976. — С. 571 (15b). — 736 с.