Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Теоремы о частично упорядоченных множествах






К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа [P2] и лемма Куратовского-Цорна [P3]. Эти утверждения эквивалентны между собой и существенно опираются на так называемую аксиому выбора[P4] (в действительности, эквивалентны аксиоме выбора).

Типовая задача:

 

Является ли отношение, заданное на вершинах единичного куба в Rn как aRb, если в координатах вершины a не больше единиц, чем в координатах вершины b, отношением частичного порядка? Решение: Отношение R является отношением частичного порядка, если оно: - рефлексивно, т.е. aRa; - антисиметрично, т.е. ; - транзитивно, т.е. . Для иллюстрации возьмём трёхмерный единичный куб с проставленными координатами вершин. Тогда, очевидно, для куба в пространстве Rn вершину определяются набором из n символов . В n-мерном кубе всего К=2n вершин. На множестве вершин введём функцию , равную числу единиц в её n-наборе. Очевидно, что 0 ≤ N(Aj) ≤ n. Тогда отношение R можно определить как . Проверяем свойства: - рефлексивность: AiRAj достаточно очевидно, что этим свойством R обладает, т.к. ; - антисимметричность: Однако соотношение возможно не только при Ai = Aj (рисунок); - транзитивность: ? Действительно, если Таким образом, отношение не является отношением частичного порядка, так как оно не является антисимметричным.

 

 

Список использованных Интернет-ресурсов:

1. https://ru.wikipedia.org/wiki/Частично_упорядоченное_множество

2. https://bankzadach.ru/teoriya-mnozhestv-/otnoshenie-chastichnogo-poryadka-000136.html

 

[P1]

В математике бинарным отношением называется подмножество декартова произведения двух множеств. В частности, бинарным отношением на множестве называется множество упорядоченныхпар элементов этого множества

 

Примечания:

1. Прямое или декартово произведение множеств — множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств.

2. Мно́ жество — одно из ключевых понятий математики, в частности, теории множеств и логики. Понятие множества обычно принимается за одно из исходных (аксиоматических) понятий, то есть не сводимое к другим понятиям, а значит и не имеющее определения.

3. Тео́ рия мно́ жеств — раздел математики, в котором изучаются общие свойства множеств. Теория множеств лежит в основе большинства математических дисциплин; она оказала глубокое влияние на понимание предмета самой математики.

 

 

[P2] Принцип максимума Хаусдорфа, также называемый теоремой Хаусдорфа о максимуме, утверждает:

В любом частично упорядоченном множестве существует максимальное линейно упорядоченное подмножество.

 

[P3] Лемма Цорна, также известная как лемма Куратовского — Цорна, утверждает:

Частично упорядоченное множество, в котором любая цепь имеет верхнюю грань, содержит максимальный элемент.

 

[P4] Аксиомой выбора называется следующее высказывание теории множеств: «Для каждого семейства непустых непересекающихся множеств существует (по меньшей мере одно) множество d, которое имеет только один общий элемент c c каждым из множеств b данного семейства»






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.