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

Элемент ≥ (или ≤) друг друга

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

всякий раз, когда удовлетворяет, тогда обязательно ${\displaystyle s\in S}$ ${\displaystyle m\leq s,}$ ${\displaystyle s\leq m.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Верх и низ

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

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

Примеры

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

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

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

• Эссенциальный супремум и эссенциальный инфимум
• Начальные и конечные объекты
• Максимальные и минимальные элементы
• Предел верхний и нижний предел (нижний предел)
• Верхняя и нижняя границы

Примечания

1. Конечно, в данном конкретном примере существует только один элемент, сравнимый с которым обязательно является он сам, поэтому второе условие «и » было избыточным. ${\displaystyle S}$ ${\displaystyle m,}$ ${\displaystyle m}$ ${\displaystyle \geq m,}$
2. Если и оба величайшие, то и, следовательно, по антисимметрии . ${\displaystyle g_{1}}$ ${\displaystyle g_{2}}$ ${\displaystyle g_{1}\leq g_{2}}$ ${\displaystyle g_{2}\leq g_{1},}$ ${\displaystyle g_{1}=g_{2}}$
3. Если — наибольший элемент и тогда По антисимметрии , это делает ( и ) невозможным. ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle s\in S,}$ ${\displaystyle s\leq g.}$ ${\displaystyle g\leq s}$ ${\displaystyle g\neq s}$
4. Если это максимальный элемент, то поскольку он наибольший, следовательно, поскольку он максимальный. ${\displaystyle M}$ ${\displaystyle M\leq g}$ ${\displaystyle g}$ ${\displaystyle M=g}$ ${\displaystyle M}$
5. Только если: см. выше. — Если: Предположим, что противоречие имеет только один максимальный элемент, но не имеет наибольшего элемента. Поскольку не является наибольшим, должно существовать некоторое несравнимое с . Следовательно, не может быть максимальным, то есть должно выполняться для некоторых. Последнее также должно быть несравнимо с, поскольку противоречит максимальности и в то же время противоречит несравнимости и Повторяя этот аргумент, бесконечное возрастание можно найти цепочку (такую, что каждая из них несравнима и не максимальна). Это противоречит условию восходящей цепочки. ${\displaystyle S}$ ${\displaystyle m,}$ ${\displaystyle m}$ ${\displaystyle s_{1}\in S}$ ${\displaystyle m.}$ ${\displaystyle s_{1}\in S}$ ${\displaystyle s_{1}<s_{2}}$ ${\displaystyle s_{2}\in S.}$ ${\displaystyle m,}$ ${\displaystyle m<s_{2}}$ ${\displaystyle m}$ ${\displaystyle s_{2}\leq m}$ ${\displaystyle m}$ ${\displaystyle s_{1}.}$ ${\displaystyle s_{1}<s_{2}<\cdots <s_{n}<\cdots }$ ${\displaystyle s_{i}}$ ${\displaystyle m}$
6. Пусть будет максимальным элементом для любого или Во втором случае определение максимального элемента требует этого, поэтому следует, что Другими словами, это наибольший элемент. ${\displaystyle m\in S}$ ${\displaystyle s\in S}$ ${\displaystyle s\leq m}$ ${\displaystyle m\leq s.}$ ${\displaystyle m=s,}$ ${\displaystyle s\leq m.}$ ${\displaystyle m}$
7. Если бы были несравнимы, то имели бы два максимальных, но не наибольший элемент, что противоречит совпадению. ${\displaystyle a,b\in P}$ ${\displaystyle S=\{a,b\}}$

Рекомендации

1. Понятие локальности требует, чтобы область определения функции была как минимум топологическим пространством .

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