Цілком впорядкована множина

Цілком впорядкована множина — лінійно впорядкована множина, в якій для кожної непорожньої підмножини існує найменший елемент відповідно до заданого порядку (див. Фундована множина).

Для цілком впорядкованих множин можна застосовувати трансфінітну індукцію для доведення тверджень для всіх елементів множини.

• Теорема Цермело: твердження, що довільну множину можна цілком впорядкувати — рівносильне аксіомі вибору чи лемі Цорна.^[1]
• Якщо X та Y — дві цілком впорядковані множини, то існує вкладення однієї множини в іншу зі збереженням порядку в обох множинах.^[2]
• Довільна цілком впорядкована множина ізоморфна зі збереженням порядку деякому порядковому числу, яке називається тип порядку цієї множини.
• Позиція елемента в цілком впорядкованій множині теж задається порядковим числом.

• Натуральні числа
• Незліченні цілком впорядковані множини можуть бути побудовані тільки з використанням аксіоми вибору.

На відміну від стандартного впорядкування для ≤ натуральних чисел, стандартне впорядкування ≤ цілих це не цілковите впорядкування, бо, наприклад, множина від'ємних чисел не містить найменшого елемента.

Наступне відношення R це приклад цілковитого впорядкування цілих: x R y тоді і тільки тоді, коли виконується одна з наступних умов:

1. x = 0
2. x додатне і y від'ємне
3. x і y обидва додані і x ≤ y
4. x і y обидва від'ємні і |x| ≤ |y|

Це відношення R можна візуалізувати так:

0 1 2 3 4 … −1 −2 −3 …

R ізоморфне порядковому числу ω + ω.

Іншим відношенням для цілковитого впорядкування цілих є: x ≤_z y тоді і тільки тоді, коли (|x| < |y| або (|x| = |y| і x ≤ y)). Цей цілковитий порядок можна візуалізувати так:

0 −1 1 −2 2 −3 3 −4 4 …

Тут тип порядку (позиція останнього елемента, якщо такий існує) ω.

• Лема Цорна

• Андрійчук В.І., Комарницький М.Я., Іщук Ю.Б. (2003). Вступ до дискретної математики. Львів: Видавничий центр ЛНУ ім. І.Франка. с. 254.
• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ(інші мови), 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)