Фундована множина

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Фундована множина (фундований порядок) — частково впорядкована множина, в якій для кожної непорожньої підмножини існує мінімальний елемент. Мінімальних елементів може бути декілька і навіть нескінченна кількість. Формально, якщо на множині (або класі) задане бінарне відношення і для кожної існує мінімальний щодо елемент для якого не існує елемента такого, що виконується Тобто,

Інакше можна сказати, що множина фундована тоді і тільки тоді, коли в ній не існує нескінченної спадної послідовності елементів.

Приклади

[ред. | ред. код]

Фундовані, але не лінійно впорядковані множини:

  • додатні цілі числа {1, 2, 3, ...}, з порядком визначеним як a < b тоді і тільки тоді, коли a ділить b і ab.
  • множина всіх скінченних рядків над фіксованою абеткою з порядком визначеним як 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" > … це нескінченний спадний ланцюг. Це відношення не фундоване навіть незважаючи на те, що вся множина має мінімільний елемент, а саме порожній рядок.
  • раціональні числа (або дійсні) зі стандартним порядком, бо, наприклад, множина додатних раціональних (або дійсних) не має мінімуму.

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]