Сравнимость

Property of elements related by inequalities

Диаграмма Хассе натуральных чисел , частично упорядоченная по принципу " x ≤ y, если x делит y ". Числа 4 и 6 несравнимы, поскольку ни одно из них не делит другое.

В математике два элемента x и y множества P называются сравнимыми относительно бинарного отношения ≤, если хотя бы одно из x ≤ y или y ≤ x является истинным. Они называются несравнимыми , если они несравнимы.

Строгое определение

Бинарное отношение на множестве по определению является любым подмножеством Данного тогда и только тогда, когда , и в этом случае говорят, что он связан с по Элемент называется -сравнимым , или сравнимым ( относительно ), с элементом, если или Часто вместо , используется символ, обозначающий сравнение, такой как (или и многие другие), и в этом случае вместо пишется , поэтому используется термин «сравнимый». ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle P\times P.}$ ${\displaystyle x,y\in P,}$ ${\displaystyle xRy}$ ${\displaystyle (x,y)\in R,}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle R.}$ ${\displaystyle x\in P}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle y\in P}$ ${\displaystyle xRy}$ ${\displaystyle yRx.}$ ${\displaystyle \,<\,}$ ${\displaystyle \,\leq \,,}$ ${\displaystyle \,>,\,}$ ${\displaystyle \geq ,}$ ${\displaystyle R,}$ ${\displaystyle x<y}$ ${\displaystyle xRy,}$

Сравнимость относительно индуцирует каноническое бинарное отношение на ; в частности, отношение сравнимости , индуцируемое , определяется как множество всех пар, таких что сравнимо с ; то есть, таких, что хотя бы одно из и является истинным. Аналогично, отношение несравнимости на , индуцируемое , определяется как множество всех пар, таких что несравнимо с , то есть, таких, что ни одно из , ни не является истинным. ${\displaystyle R}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle (x,y)\in P\times P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle (x,y)\in P\times P}$ ${\displaystyle x}$ ${\displaystyle y;}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$

Если вместо используется символ , то сравнимость относительно иногда обозначается символом , а несравнимость — символом . ^[1] Таким образом, для любых двух элементов и частично упорядоченного множества верно ровно одно из и . ${\displaystyle \,<\,}$ ${\displaystyle \,\leq \,}$ ${\displaystyle \,<\,}$ ${\displaystyle {\overset {<}{\underset {>}{=}}}}$ ${\displaystyle {\cancel {\overset {<}{\underset {>}{=}}}}\!}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}$ ${\displaystyle x{\cancel {\overset {<}{\underset {>}{=}}}}y}$

Пример

Полностью упорядоченный набор — это частично упорядоченный набор , в котором любые два элемента сравнимы. Теорема о расширении Шпильрайна утверждает, что каждый частичный порядок содержится в полном порядке. Интуитивно теорема гласит, что любой метод сравнения элементов, который оставляет некоторые пары несравнимыми, может быть расширен таким образом, что каждая пара станет сравнимой.

Характеристики

Оба отношения сравнимости и несравнимости симметричны , то есть сравнимо с тогда и только тогда, когда сравнимо с и то же самое для несравнимости. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x,}$

Графики сопоставимости

Граф сравнимости частично упорядоченного множества имеет в качестве вершин элементы и имеет в качестве ребер именно те пары элементов, для которых . ^[2] ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \{x,y\}}$ ${\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}$

Классификация

При классификации математических объектов (например, топологических пространств ) два критерия считаются сравнимыми, когда объекты, подчиняющиеся одному критерию, составляют подмножество объектов, подчиняющихся другому, то есть когда они сравнимы по частичному порядку ⊂. Например, критерии T 1 и T 2 сравнимы, а критерии T ₁ и трезвости — нет.

Смотрите также

• Строгое слабое упорядочение  – математическое ранжирование множества Pages displaying short descriptions of redirect targets, частичное упорядочение, в котором несравнимость является транзитивным отношением.

Ссылки

1. Троттер, Уильям Т. (1992), Комбинаторика и частично упорядоченные множества: теория размерности , Johns Hopkins Univ. Press, стр. 3
2. Гилмор, ПК; Хоффман, А.Дж. (1964), «Характеристика графов сравнимости и графов интервалов», Канадский журнал математики , 16 : 539–548, doi : 10.4153/CJM-1964-055-5.

Внешние ссылки

• "PlanetMath: partial order". Архивировано из оригинала 11 июля 2012 г. Получено 6 апреля 2010 г.