Введение
Это глоссарий некоторых терминов, используемых в различных областях математики, связанных с теорией порядка, решеток и областей определения. Обратите внимание, что также имеется структурированный список тем по теории порядка. Другими полезными ресурсами могут служить следующие обзорные статьи: свойства полноты частично упорядоченных множеств, законы дистрибутивности в теории порядка, свойства сохранения функций между частично упорядоченными множествами. В дальнейшем частично упорядоченные множества обычно будут обозначаться только их несущими множествами. Если смысл ясен из контекста, для обозначения соответствующего реляционного символа будет достаточно использовать , даже без предварительного определения. Кроме того, < будет обозначать строгое упорядочение, индуцированное .
This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:
completeness properties of partial orders
distributivity laws of order theory
preservation properties of functions between posets. In the following, partial orders will usually just be denoted by their carrier sets. As long as the intended meaning is clear from the context, will suffice to denote the corresponding relational symbol, even without prior introduction. Furthermore, < will denote the strict order induced by
NOTOC
А. В
Ациклический. Бинарное отношение ациклично, если оно не содержит "циклов": эквивалентно, его транзитивное замыкание антисимметрично. Обратное. Смотрите обратное отношение. Нерефлексивный. Отношение R на множестве X является нерефлексивным, если не существует элемента x в X такого, что x R x.
Изотонный. Смотрите монотонный.
Isotone. See monotone.
Я
Присоединяйтесь. См. супремум.
Л.
Решетка. Решетка – это частично упорядоченное множество, в котором существуют все непустые конечные объединения (suprema) и пересечения (infima). Наименьший элемент. Для подмножества X частично упорядоченного множества P, элемент a из X называется наименьшим элементом X, если a ≤ x для каждого элемента x из X. Двойственным понятием является наибольший элемент. Длина цепи – это число элементов минус один. Цепь с 1 элементом имеет длину 0, цепь с 2 элементами имеет длину 1 и так далее. Линейный. См. полный порядок. Линейное расширение. Линейное расширение частичного порядка – это расширение, являющееся линейным порядком или полным порядком. Локус. Локус – это полная алгебра Хейтинга. Локусы также называются фреймами и встречаются в двойственности Стоуна и бесструктурной топологии. Локально конечный частично упорядоченный набор. Частично упорядоченное множество P является локально конечным, если каждый интервал [a, b] = {x ∈ P | a ≤ x ≤ b} является конечным множеством. Нижняя граница. Нижняя граница подмножества X частично упорядоченного множества P – это элемент b из P, такой что b ≤ x для всех x из X. Двойственным понятием является верхняя граница. Нижнее множество. Подмножество X частично упорядоченного множества P называется нижним множеством, если для всех элементов x из X и p из P, p ≤ x влечет за собой, что p содержится в X. Двойственным понятием является верхнее множество.
М.
Максимальная цепь. Цепь в частично упорядоченном множестве, к которой нельзя добавить ни одного элемента, не нарушив свойства полного порядка. Это понятие сильнее, чем насыщенная цепь, поскольку оно также исключает существование элементов, меньших всех элементов цепи, или больших всех её элементов. Конечная насыщенная цепь является максимальной тогда и только тогда, когда она содержит как минимальный, так и максимальный элемент частично упорядоченного множества. Максимальный элемент. Максимальный элемент подмножества X частично упорядоченного множества P – это элемент m из X, такой что m ≤ x влечет m = x для всех x из X. Двойственным понятием является минимальный элемент. Максимальный элемент. Синоним наибольшего элемента. Для подмножества X частично упорядоченного множества P элемент a из X называется максимальным элементом X, если x ≤ a для каждого элемента x из X. Максимальный элемент обязательно является максимальным, но обратное неверно. Встреча. См. инфимум. Минимальный элемент. Минимальный элемент подмножества X частично упорядоченного множества P – это элемент m из X, такой что x ≤ m влечет m = x для всех x из X. Двойственным понятием является максимальный элемент. Минимальный элемент. Синоним наименьшего элемента. Для подмножества X частично упорядоченного множества P элемент a из X называется минимальным элементом X, если x ≥ a для каждого элемента x из X. Минимальный элемент обязательно является минимальным, но обратное неверно. Монотонный. Функция f между частично упорядоченными множествами P и Q называется монотонной, если для всех элементов x, y из P, x ≤ y (в P) влечет f(x) ≤ f(y) (в Q). Другими названиями этого свойства являются изотония и сохранение порядка. В анализе, при наличии линейных порядков, такие функции часто называют монотонно возрастающими, но это не очень удобное описание при работе с нелинейными порядками. Двойственным понятием является антимонотонность или обращение порядка.
О
Двойственный порядок. Двойственный порядок частично упорядоченного множества — это то же множество с отношением частичного порядка, замененным на обратное. Вложение порядка. Функция f между частично упорядоченными множествами P и Q является вложением порядка, если для всех элементов x, y из P, x ≤ y (в P) эквивалентно f(x) ≤ f(y) (в Q). Изоморфизм порядка. Отображение f: P → Q между двумя частично упорядоченными множествами P и Q называется изоморфизмом порядка, если оно биективно и как f, так и f−1 являются монотонными функциями. Эквивалентно, изоморфизм порядка является сюръективным вложением порядка. Сохраняющий порядок. Смотрите монотонный. Обращающий порядок. Смотрите антимонотонный.
П.
Частичный порядок. Частичный порядок — это бинарное отношение, которое является рефлексивным, антисимметричным и транзитивным. В некотором злоупотреблении терминологией, этот термин иногда используется для обозначения не только самого отношения, но и соответствующего частично упорядоченного множества. Частично упорядоченное множество. Частично упорядоченное множество, или, сокращенно, посет, — это множество вместе с частичным порядком на нём. Посет. Частично упорядоченное множество. Предварительный порядок. Предварительный порядок — это бинарное отношение, которое является рефлексивным и транзитивным. Такие порядки также могут называться квазипорядками или нестрогими предварительными порядками. Термин «предварительный порядок» также используется для обозначения ациклического бинарного отношения (также называемого ациклическим графом). Предварительно упорядоченное множество. Сохраняющая. Функция f между посетами P и Q называется сохраняющей супремумы (соединения), если для всех подмножеств X множества P, имеющих супремум sup X в P, существует sup{f(x) : x ∈ X}, равный f(sup X). Такая функция также называется сохраняющей соединения. Аналогично, говорят, что f сохраняет конечные, ненулевые, направленные или произвольные соединения (или пересечения). Обратное свойство называется отражающим соединения. Простой. Идеал I в решетке L называется простым, если для всех элементов x и y в L, x ∧ y ∈ I влечет x ∈ I или y ∈ I. Двойственное понятие называется простым фильтром. Эквивалентно, множество является простым фильтром тогда и только тогда, когда его дополнение является простым идеалом. Принципиальный. Фильтр называется принципиальным фильтром, если он имеет наименьший элемент. Двойственно, принципиальный идеал — это идеал с наибольшим элементом. Наименьшие или наибольшие элементы в этих случаях также могут называться принципиальными элементами. Проекция (оператор). Самоотображение частично упорядоченного множества, которое является монотонным и идемпотентным при композиции функций. Проекции играют важную роль в теории доменов. Псевдодополнение. В алгебре Хейтинга элемент x ⇒ 0 называется псевдодополнением x. Оно также задается как sup{y : y ∧ x = 0}, то есть как наименьшая верхняя граница всех элементов y, для которых y ∧ x = 0.
Poset. A partially ordered set. Preorder. A preorder is a binary relation that is reflexive and transitive. Such orders may also be called quasiorders or non strict preorder. The term preorder is also used to denote an acyclic binary relation (also called an acyclic digraph). Preordered set. A preordered set is a set together with a preorder on
Preserving. A function f between posets P and Q is said to preserve suprema (joins), if, for all subsets X of P that have a supremum sup X in P, we find that sup{f(x): x in X} exists and is equal to f(sup X). Such a function is also called join preserving. Analogously, one says that f preserves finite, non empty, directed, or arbitrary joins (or meets). The converse property is called join reflecting. Prime. An ideal I in a lattice L is said to be prime, if, for all elements x and y in L, x ∧ y in I implies x in I or y in I. The dual notion is called a prime filter. Equivalently, a set is a prime filter if and only if its complement is a prime ideal. Principal. A filter is called principal filter if it has a least element. Dually, a principal ideal is an ideal with a greatest element. The least or greatest elements may also be called principal elements in these situations. Projection (operator). A self map on a partially ordered set that is monotone and idempotent under function composition. Projections play an important role in domain theory. Pseudo complement. In a Heyting algebra, the element x ⇒; 0 is called the pseudo complement of x. It is also given by sup{y : y ∧ x = 0}, i. e. as the least upper bound of all elements y with y ∧ x = 0.
Q. В
Квазипорядок. См. предзаказ. Квазитранзитивное. Отношение является квазитранзитивным, если оно транзитивно для различных элементов. Транзитивность влечёт квазитранзитивность, а квазитранзитивность влечёт ацикличность.
R. В
Отражающее. Функция f между частично упорядоченными множествами P и Q называется отражающей супремумы (соединения), если для любого подмножества X множества P, для которого супремум sup{f(x): x ∈ X} существует и имеет вид f(s) для некоторого s ∈ P, выполняется, что sup X существует и sup X = s. Аналогично, говорят, что f отражает конечные, непустые, направленные или произвольные соединения (или пересечения). Обратное свойство называется сохраняющим соединения. Рефлексивное. Бинарное отношение R на множестве X является рефлексивным, если x R x выполняется для каждого элемента x ∈ X. Резидуальное. Двойственное отображение, связанное с резидуальным отображением. Резидуальное отображение. Монотонное отображение, для которого прообраз основного вниз-множества снова является основным. Эквивалентно, это один из компонентов связи Галуа.
Т
Верхняя граница. См. пункт. Полный порядок. Полный порядок T – это частичный порядок, в котором для любых x и y из T выполняется либо x ≤ y, либо y ≤ x. Полные порядки также называются линейными порядками или цепями. Полное отношение. Синоним для связанного отношения. Транзитивное отношение. Отношение R на множестве X называется транзитивным, если для всех элементов x, y, z из X из x R y и y R z следует x R z.
Транзитивное замыкание. Транзитивное замыкание R* отношения R состоит из всех пар (x, y), для которых существует конечная цепочка вида x R a, a R b, …, z R y.
Transitive closure. The transitive closure R∗ of a relation R consists of all pairs x,y for which there cists a finite chain x R a, a R b, , z R y.
У
Единица. Наибольший элемент полурешётки P может называться единицей или просто 1 (если он существует). Другой распространенный термин для этого элемента – верхняя грань. Он является инфимумом пустого множества и супремумом P. Двойственным понятием является ноль. Верхнее множество. См. верхняя полурешётка. Верхняя граница. Верхняя граница подмножества X полурешётки P – это элемент b из P, такой что x ≤ b для всех x из X. Двойственным понятием является нижняя граница. Верхняя полурешётка. Подмножество X полурешётки P называется верхней полурешёткой, если для всех элементов x из X и p из P, x ≤ p влечет за собой, что p содержится в X. Двойственным понятием является нижняя полурешётка.
V. В
Оценка. Для данной решетки, оценка называется строгой (то есть, ), монотонной, модулярной (то есть, ) и положительной. Непрерывные оценки являются обобщением мер.
В
Далеко ниже отношения. В частично упорядоченном множестве P, элемент x находится значительно ниже y, что записывается как x<<y, если для любого направленного подмножества D множества P, имеющего супремум, из y ≤ sup D следует x ≤ d для некоторого d из D. Также говорят, что x аппроксимирует y. См. также теория доменов. Слабый порядок. Частичный порядок ≤ на множестве X называется слабым порядком, если частично упорядоченное множество (X, ≤) изоморфно счетному семейству множеств, упорядоченных по сравнению кардинальности.
Z. В
Ноль. Наименьший элемент частично упорядоченного множества P может называться нулем или просто 0 (если он существует). Другой распространенный термин для этого элемента — нижняя граница. Нуль является супремумом пустого множества и инфимумом P. Двойственное понятие называется единицей.