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

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

Диаграмма Хассе множества делителей числа 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.}$

Если то является наибольшим элементом из тогда и только тогда, когда является верхней границей из в и В частности, любой наибольший элемент из также является верхней границей (в ), но верхняя граница из в является наибольшим элементом из тогда и только тогда, когда он принадлежит В частном случае, когда определение " является верхней границей из в " становится: является элементом таким, что и для всех , что полностью идентично определению наибольшего элемента, данному ранее. Таким образом, является наибольшим элементом из тогда и только тогда, когда является верхней границей из в . ${\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}$

Если является верхней границей в , которая не является верхней границей в (что может произойти, если и только если ), то не может быть наибольшим элементом (однако может быть возможно, что какой-то другой элемент является наибольшим элементом ). В частности, возможно, что одновременно не будет наибольшего элемента и будет существовать некоторая верхняя граница в . ${\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 . Определяющее условие для того, чтобы быть максимальным элементом , можно переформулировать следующим образом: ${\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.}$

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

Предположим, что — множество, содержащее не менее двух (различных) элементов, и определяем частичный порядок на , объявляя, что если и только если Если принадлежат к , то ни то, ни выполняется, что показывает, что все пары различных (т.е. неравных) элементов в являются в сравнимыми. Следовательно, не может иметь наибольший элемент (потому что наибольший элемент из , в частности, должен был бы быть сравним с каждым элементом из , но не имеет такого элемента). Однако каждый элемент является максимальным элементом из , поскольку существует ровно один элемент из , который и сравним с , и этот элемент является самим собой (что, конечно, и есть ). ^{[примечание 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}$

Напротив, если предупорядоченное множество имеет наибольший элемент , то обязательно будет максимальным элементом и, более того, как следствие того, что наибольший элемент сравним с каждым элементом из , если также частично упорядочено, то можно заключить, что является единственным максимальным элементом из Однако вывод об уникальности больше не гарантируется, если предупорядоченное множество также не является частично упорядоченным. Например, предположим, что является непустым множеством, и определим предварительный порядок на , объявив, что всегда выполняется для всех Направленное предупорядоченное множество является частично упорядоченным тогда и только тогда, когда имеет ровно один элемент. Все пары элементов из сравнимы, и каждый элемент из является наибольшим элементом (и, следовательно, также максимальным элементом) из Так, в частности, если имеет по крайней мере два элемента, то имеет несколько различных наибольших элементов. ${\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}$
• Когда ограничение на является полным порядком ( на самом верхнем рисунке это пример), то понятия максимального элемента и наибольшего элемента совпадают. ^{[примечание 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} }$
• Пусть отношение задано как Множество имеет верхние границы и, однако, не имеет наименьшей верхней границы и наибольшего элемента (см. рисунок). ${\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. Понятие локальности требует, чтобы область определения функции была по крайней мере топологическим пространством .

• Дэви, BA; Пристли, HA (2002). Введение в решетки и порядок (2-е изд.). Cambridge University Press . ISBN 978-0-521-78451-1.