Фундована множина
Фундована множина (фундований порядок) — частково впорядкована множина, в якій для кожної непорожньої підмножини існує мінімальний елемент. Мінімальних елементів може бути декілька і навіть нескінченна кількість. Формально, якщо на множині (або класі) задане бінарне відношення і для кожної існує мінімальний щодо елемент для якого не існує елемента такого, що виконується Тобто,
Інакше можна сказати, що множина фундована тоді і тільки тоді, коли в ній не існує нескінченної спадної послідовності елементів.
Приклади
Фундовані, але не лінійно впорядковані множини:
- додатні цілі числа {1, 2, 3, ...}, з порядком визначеним як a < b тоді і тільки тоді, коли a ділить b і a ≠ b.
- множина всіх скінченних рядків над фіксованою абеткою з порядком визначеним як s < t тоді і тільки тоді, якщо s це власний підрядок t.
- множина N × N двійок натуральних чисел, впорядкованих так: (n1, n2) < (m1, m2) тоді і тільки тоді, якщо n1 < m1 і n2 < m2.
- множина всіх регулярних виразів над фіксованою абеткою з порядком визначеним як s < t тоді і тільки тоді, якщо s це власний (правильний) підвираз t.
- будь-який клас чиї елементи це множини з відношенням ("елемент з"). Це аксіома регулярності.
- вузли будь-якого скінченного скінченного ациклічного графу, з відношенням R визначеним так: a R b тоді і тільки тоді, якщо існує ребро від a до b.
Приклади нефундованих відношень включають:
- від'ємні цілі числа {−1, −2, −3, …}, зі стандартним порядком, бо будь-яка необмежена множина не має найменшого елемента.
- Множина рядків над скінченною абеткою з більш ніж одним елементом, зі звичайним (лексикографічним) порядком, бо послідовність "B" > "AB" > "AAB" > "AAAB" > … це нескінченний спадний ланцюг. Це відношення не фундоване навіть незважаючи на те, що вся множина має мінімільний елемент, а саме порожній рядок.
- раціональні числа (або дійсні) зі стандартним порядком, бо, наприклад, множина додатних раціональних (або дійсних) не має мінімуму.
Див. також
Джерела
- Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ, 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)
- Куратовский К., Мостовский А. Теория множеств. — Москва : Мир, 1970. — 416 с.(рос.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.