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

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

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

Определения [ править ]

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

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

Используя вместо в приведенном выше определении, получается определение наименьшего элемента . Явно, элемент называется наименьший элемент , если и , если она также удовлетворяет: ${\ Displaystyle \, \ geq \,}$${\ Displaystyle \, \ Leq \,}$${\ 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).}$

Отношение к верхней / нижней границам [ править ]

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

Пусть быть предупорядоченное множество , и пусть Ап верхней границы из в элемент таким образом, что и для всех Важно отметить, что верхняя граница в это не требуется , чтобы быть элементом${\ displaystyle (P, \ leq)}$${\ Displaystyle S \ substeq 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.}$

Если then является наибольшим элементом тогда и только тогда, когда является верхней границей 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) также не означает существования наибольшего элемента.

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

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

Пусть быть предупорядоченное множество , и пусть Элемент называется быть максимальный элемент из , если выполняется следующее условие:${\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 )}$

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

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

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

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

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

Примеры [ править ]

• Подмножество целых чисел не имеет верхней границы в наборе из действительных чисел .${\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).}$

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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