Бесконе́чное мно́жество — множество, не являющееся конечным. Можно дать ещё несколько эквивалентных определений бесконечного множества:
- Множество, в котором для любого натурального числа
найдётся конечное подмножество из элементов. - Множество, в котором найдётся счётное подмножество.
- Множество, в котором найдётся подмножество, равномощное некоторому (ненулевому) предельному ординалу.
- Множество, для которого существует биекция с некоторым его собственным подмножеством.
Аксио́мой вы́бора, англ. аббр. AC называется следующее высказывание теории множеств:
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Выпуклое множество в аффинном или векторном пространстве — множество, в котором все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству.
Решётка — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани. Отсюда вытекает существование этих граней для любых непустых конечных подмножеств.
Части́чно упоря́доченное мно́жество — математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определённой последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими. В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».
Принцип максимума Хаусдорфа, также называемый теоремой Хаусдорфа о максимуме, утверждает:
Лемма Цорна — одно из утверждений, эквивалентных аксиоме выбора, наряду с теоремой Цермело и принципом максимума Хаусдорфа.
В данной статье рассматриваются различные формулировки и доказывается эквивалентность следующих предложений:
- Аксиома выбора
- Теорема Цермело
- Принцип максимума Хаусдорфа
- Лемма Цорна
Теорема Алекса́ндера о предбазе — теорема общей топологии, устанавливающая критерий компактности топологического пространства.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины.
В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы в некотором частичном порядке. Графы сравнимости также называют транзитивно-ориентируемыми графами, частично упорядочиваемыми графами и графами вложенности.Граф несравнимости — это неориентированный граф, в котором пары элементов соединяются ребром, если элементы несравнимы в некотором частичном порядке.
Теорема Робертсона — Сеймура утверждает, что любое семейство графов, замкнутое относительно операций удаления и стягивания рёбер, может быть определено конечным набором запрещённых графов.
Градуированное частично упорядоченное множество — частично упорядоченное множество P, снабжённое функцией ранга ρ из P в N, удовлетворяющей следующим двум свойствам:
- функция ранга совместима с упорядочиванием, в смысле, что для любых x и y с порядком x < y должно выполняться ρ(x) < ρ(y);
- функция ранга совместима с отношением подчинения упорядочения, в смысле, что для любого x подчинённого y должно выполняться ρ(y) = ρ(x) + 1.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Теорема де Брёйна — Эрдёша — теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Теорема Мирского — теорема, двойственная теореме Дилуорса. Была доказана в 1971 году.
