Самый большой элемент и наименьший элемент

Диаграмма Хассе набора $P$ делителей числа 60, частично упорядоченных соотношением " $x$ делит $y$". Красное подмножество $S=\{1,2,3,5,6,10,15,30\}$ имеет один величайший элемент, а именно. 30 и один наименьший элемент, а именно. 1. Эти элементы также являются максимальными и минимальными элементами красного подмножества соответственно.

В математике , особенно в теории порядка , наибольший элемент подмножества. $S$ ( частично упорядоченного множества poset) является элементом $S$ это больше, чем любой другой элемент $S$. Термин «наименьший элемент» определяется двояко , то есть это элемент $S$ который меньше любого другого элемента $S.$

Определения

Позволять $(P,\leq )$ быть заранее заказанным набором и пусть $S\subseteq P.$ Элемент $g\in P$ считается величайшим элементом $S$ если $g\in S$ и если это также удовлетворяет:

$s\leq g$ для всех $s\in S.$

Переключив сторону отношения, которое $s$ включено в приведенное выше определение, определение наименьшего элемента $S$ получается. Явно элемент $l\in P$ называется элементом наименьшим $S$ если $l\in S$ и если это также удовлетворяет:

$l\leq s$ для всех $s\in S.$

Если $(P,\leq )$ также является частично упорядоченным множеством, тогда $S$ может иметь не более одного наибольшего элемента и не более одного наименьшего элемента. Всякий раз, когда величайший элемент $S$ существует и единственен, то этот элемент называется наибольшим элементом множества. $S$. Терминология наименьший элемент $S$ определяется аналогично.

Если $(P,\leq )$ имеет наибольший элемент (соответственно наименьший элемент), то этот элемент также называется верхним элемента (соответственно нижним . ) $(P,\leq ).$

Связь с верхними/нижними границами

Наибольшие элементы тесно связаны с верхними границами .

Позволять $(P,\leq )$ быть заранее заказанным набором и пусть $S\subseteq P.$ граница Верхняя ​ $S$ в $(P,\leq )$ это элемент $u$ такой, что $u\in P$ и $s\leq u$ для всех $s\in S.$ Важно отметить, что верхняя граница $S$ в $P$ не обязательно должен быть элементом $S.$

Если $g\in P$ затем $g$ является величайшим элементом $S$ тогда и только тогда, когда $g$ является верхней границей $S$ в $(P,\leq )$ и $g\in S.$ В частности, любой величайший элемент $S$ также является верхней границей $S$ (в $P$), но верхняя граница $S$ в $P$ является величайшим элементом $S$ тогда и только тогда, когда принадлежит оно $S.$ В частном случае, когда $P=S,$ определение " $u$ является верхней границей $S$ в $S$" становится: $u$ такой элемент, что $u\in S$ и $s\leq u$ для всех $s\in S,$ что полностью идентично данному ранее определению наибольшего элемента. Таким образом $g$ является величайшим элементом $S$ тогда и только тогда, когда $g$ является верхней границей $S$ в $S$.

Если $u$ является верхней границей $S$ в $P$ это не верхняя граница $S$ в $S$ (что может произойти тогда и только тогда, когда $u\not \in S$) затем $u$ может не быть величайшим элементом $S$ (однако возможно, что какой-то другой элемент является величайшим элементом $S$). В частности, это возможно для $S$ одновременно не иметь наибольшего элемента и существовать некоторая верхняя граница $S$ в $P$.

Даже если набор имеет некоторые верхние границы, он не обязательно должен иметь наибольший элемент, как показано на примере отрицательных действительных чисел . Этот пример также демонстрирует, что существование наименьшей верхней границы (в данном случае числа 0) также не подразумевает существование наибольшего элемента.

Контраст с максимальными элементами и локальными/абсолютными максимумами

В приведенном выше порядке делимости красное подмножество $S=\{1,2,3,4\}$ имеет два максимальных элемента, а именно. 3 и 4, ни один из которых не является лучшим. Он имеет один минимальный элемент, а именно. 1, что также является его наименьшим элементом.

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

Позволять $(P,\leq )$ быть заранее заказанным набором и пусть $S\subseteq P.$ Элемент $m\in S$ называется максимальным элементом $S$ если выполнено следующее условие:

в любое время $s\in S$ удовлетворяет $m\leq s,$ тогда обязательно $s\leq m.$

Если $(P,\leq )$ является частично упорядоченным множеством, тогда $m\in S$ является максимальным элементом $S$ тогда и только тогда, когда не существует никакого $s\in S$ такой, что $m\leq s$ и $s\neq m.$ элемент Максимальный $(P,\leq )$ определяется как максимальный элемент подмножества $S:=P.$

Множество может иметь несколько максимальных элементов, но при этом не иметь наибольшего элемента. Подобно верхним границам и максимальным элементам, наибольшие элементы могут не существовать.

В полностью упорядоченном множестве максимальный и наибольший элементы совпадают; и его еще называют максимальным ; в случае значений функции его также называют абсолютным максимумом , чтобы избежать путаницы с локальным максимумом . Двойные термины — это минимум и абсолютный минимум . Вместе они называются абсолютными экстремумами . Аналогичные выводы справедливы и для наименьшего количества элементов.

Роль (не)сравнимости в различении наибольших и максимальных элементов

Одно из наиболее важных отличий между величайшим элементом $g$ и максимальный элемент $m$ из предзаказанного набора $(P,\leq )$ связано с тем, с какими элементами они сравнимы. Два элемента $x,y\in P$ называются сравнимыми, если $x\leq y$ или $y\leq x$; их называют несравнимыми, если они несравнимы. Поскольку предзаказы рефлексивны (это означает, что $x\leq x$ верно для всех элементов $x$), каждый элемент $x$ всегда сравнимо с самим собой. Следовательно, единственные пары элементов, которые могут быть несравнимыми, — это различные пары. Однако в целом предупорядоченные множества (и даже направленные частично упорядоченные множества) могут содержать несравнимые элементы.

По определению элемент $g\in P$ является величайшим элементом $(P,\leq )$ если $s\leq g,$ для каждого $s\in P$; так что по самому своему определению это величайший элемент $(P,\leq )$ должны, в частности, быть сопоставимы с каждым элементом в $P.$ Для максимальных элементов этого не требуется. Максимальные элементы $(P,\leq )$ не обязаны быть сопоставимыми с каждым элементом в $P.$ Это связано с тем, что в отличие от определения «наибольшего элемента», определение «максимального элемента» включает важный оператор if . Определяющее условие для $m\in P$ быть максимальным элементом $(P,\leq )$ можно перефразировать как:

Для всех $s\in P,$ ЕСЛИ $m\leq s$ (поэтому элементы, несравнимые с $m$ игнорируются) тогда $s\leq m.$

Пример, когда все элементы максимальны, но ни один из них не является наибольшим

Предположим, что $S$ представляет собой набор, содержащий как минимум два (различных) элемента и определяющий частичный порядок $\,\leq \,$ на $S$ заявив, что $i\leq j$ тогда и только тогда, когда $i=j.$ Если $i\neq j$ принадлежать $S$ тогда ни то, ни другое $i\leq j$ ни $j\leq i$ это показывает, что все пары различных (т.е. неравных) элементов в $S$ находятся в сопоставимом состоянии. Следовательно, $(S,\leq )$ не может иметь наибольшего элемента (поскольку наибольший элемент $S$ в частности, должно быть сопоставимо с каждым элементом $S$ но $S$ такого элемента нет). Однако каждый элемент $m\in S$ является максимальным элементом $(S,\leq )$ потому что в нем ровно один элемент $S$ это и то, и другое сравнимо с $m$ и $\geq m,$ этот элемент является $m$ сам по себе (что, конечно, $\leq m$).

Напротив, если предварительно заказанный набор $(P,\leq )$ действительно есть величайший элемент $g$ затем $g$ обязательно будет максимальным элементом $(P,\leq )$ и притом, как следствие величайшего элемента $g$ быть сопоставимым с каждым элементом $P,$ если $(P,\leq )$ также частично упорядочен, то можно заключить, что $g$ единственный элемент максимальный $(P,\leq ).$ Однако вывод о единственности больше не гарантируется, если предупорядоченный набор $(P,\leq )$ является также не частично упорядоченным. Например, предположим, что $R$ является непустым множеством и определяет предварительный порядок $\,\leq \,$ на $R$ заявив, что $i\leq j$ всегда справедлив для всех $i,j\in R.$ Направленный набор предзаказный $(R,\leq )$ частично упорядочен тогда и только тогда, когда $R$ имеет ровно один элемент. Все пары элементов из $R$ сопоставимы, и каждый элемент $R$ является наибольшим элементом (и, следовательно, также максимальным элементом) $(R,\leq ).$ Так, в частности, если $R$ имеет как минимум два элемента, то $(R,\leq )$ имеет несколько различных величайших элементов.

Свойства

Всюду пусть $(P,\leq )$ — частично упорядоченное множество и пусть $S\subseteq P.$

• Набор $S$ может иметь не более одного наибольшего элемента. Таким образом, если в наборе есть наибольший элемент, то оно обязательно уникально.
• Если он существует, то величайший элемент $S$ является верхней границей $S$ это также содержится в $S.$
• Если $g$ является величайшим элементом $S$ затем $g$ также является максимальным элементом $S$ и, более того, любой другой максимальный элемент из $S$ обязательно будет равен $g.$
  • Таким образом, если набор $S$ имеет несколько максимальных элементов, то у него не может быть наибольшего элемента.
• Если $P$ удовлетворяет условию восходящей цепи , подмножеству $S$ из $P$ имеет наибольший элемент тогда и только тогда , когда он имеет один максимальный элемент.
• Когда ограничение $\,\leq \,$ к $S$ это полный заказ ( $S=\{1,2,4\}$ на самой верхней картинке пример), то понятия максимального элемента и наибольшего элемента совпадают.
  • Однако это не является необходимым условием, когда $S$ имеет величайший элемент, понятия тоже совпадают, как сказано выше.
• Если понятия максимального элемента и наибольшего элемента совпадают на каждом двухэлементном подмножестве $S$ из $P,$ затем $\,\leq \,$ это полный порядок на $P.$

Достаточные условия

• Конечная цепь всегда имеет наибольший и наименьший элемент.

Верх и низ

Наименьший и наибольший элементы всего частично упорядоченного множества играют особую роль и называются также нижним (⊥) и верхним (⊤) или нулем (0) и единицей (1) соответственно.Если оба существуют, ЧУУ называется ограниченным ЧУУ .Обозначение 0 и 1 используется предпочтительно, когда ЧУ-множество представляет собой дополненную решетку и когда путаница невозможна, т. е. когда речь не идет о частичных порядках чисел, которые уже содержат элементы 0 и 1, отличные от нижнего и верхнего.Существование наименьшего и наибольшего элементов является особым свойством полноты частичного порядка.

Дополнительную вводную информацию можно найти в статье по теории порядка .

Примеры

Диаграмма Хассе примера 2

• Подмножество целых чисел не имеет верхней границы в множестве $\mathbb {R}$ действительных чисел .
• Пусть отношение $\,\leq \,$ на $\{a,b,c,d\}$ быть предоставлено $a\leq c,$ $a\leq d,$ $b\leq c,$ $b\leq d.$ Набор $\{a,b\}$ имеет верхние границы $c$ и $d,$ но нет ни малейшей верхней границы, ни самого большого элемента (см. рисунок).
• В рациональных числах набор чисел с квадратом меньше 2 имеет верхние границы, но не имеет ни наибольшего элемента, ни наименьшего верхнего предела.
• В $\mathbb {R} ,$ набор чисел меньше 1 имеет наименьшую верхнюю границу, а именно. 1, но нет величайшего элемента.
• В $\mathbb {R} ,$ набор чисел, меньших или равных 1, имеет наибольший элемент, а именно. 1, что также является его наименьшей верхней границей.
• В $\mathbb {R} ^{2}$ при заказе товара комплект пар $(x,y)$ с $0<x<1$ не имеет верхней границы.
• В $\mathbb {R} ^{2}$ с лексикографическим порядком это множество имеет верхние границы, например $(1,0).$ Он не имеет наименьшей верхней границы.

См. также

• Существенное высшее и существенное низшее
• Начальные и конечные объекты
• Максимальные и минимальные элементы
• Верхний предел и нижний предел (нижний предел)
• Верхняя и нижняя границы
• Ну-порядок - нестрогий порядок, такой, что в каждом непустом множестве есть наименьший элемент.

Ссылки

• Дэйви, бакалавр; Пристли, ХА (2002). Введение в решетки и порядок (2-е изд.). Издательство Кембриджского университета . ISBN  978-0-521-78451-1 .