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

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

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

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

Позволять $(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.$

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

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

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

Одно из наиболее важных отличий между величайшим элементом $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$ ). ^{[примечание 1]}

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

Достаточные условия [ править ]

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

Верх и низ [ править ]

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

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

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

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

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

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

Примечания [ править ]

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