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

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

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

Приклади

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

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

Див. також

Джерела


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.