В математике , особенно в теории порядка , наибольшим элементом подмножества частично упорядоченного множества ( ЧУМ) является элемент, который больше, чем любой другой элемент . Термин «наименьший элемент» определяется двояко , то есть это элемент , который меньше любого другого элемента.
Переключив сторону отношения, которое включено в приведенное выше определение, получается определение наименьшего элемента . Явно говорят , что элемент является наименьшим элементом, если и если он также удовлетворяет:
для всех
Если это также частично упорядоченное множество , то оно может иметь не более одного наибольшего элемента и не более одного наименьшего элемента. Всякий раз, когда наибольший элемент существует и уникален, этот элемент называется наибольшим элементом . Аналогично определяется терминология наименьшего элемента .
Если у него есть наибольший элемент (соответственно наименьший элемент), то этот элемент также называется верхним (соответственно нижним ) элемента .
Пусть это предупорядоченный набор и
верхняя граница in — это такой элемент , что и для всех . Важно отметить, что верхняя граница in не обязательно должна быть элементом
If then является наибольшим элементом тогда и только тогда, когда является верхней границей in и В частности, любой наибольший элемент также является верхней границей (in ), но верхняя граница in является наибольшим элементом тогда и только тогда, когда он принадлежит В
частном случае, когда определение « является верхней границей в » становится: является элементом таким, что и для всех который полностью идентично определению наибольшего элемента, данному ранее. Таким образом , это наибольший элемент тогда и только тогда, когда является верхней границей in .
Если верхняя граница in не является верхней границей in (что может произойти тогда и только тогда ), то не может быть наибольшим элементом (однако возможно, что какой-то другой элемент является наибольшим элементом ). В частности, возможно одновременное отсутствие наибольшего элемента и существование некоторой верхней границы in .
Даже если набор имеет некоторые верхние границы, он не обязательно должен иметь наибольший элемент, как показано на примере отрицательных действительных чисел . Этот пример также демонстрирует, что существование наименьшей верхней границы (в данном случае числа 0) также не подразумевает существование наибольшего элемента.
Контраст максимальным элементам и локальным/абсолютным максимумам.
Наибольший элемент подмножества предварительно упорядоченного набора не следует путать с максимальным элементом набора, который представляет собой элементы, которые не строго меньше любого другого элемента в наборе.
всякий раз, когда удовлетворяет, тогда обязательно
Если - частично упорядоченное множество, то оно является максимальным элементом тогда и только тогда, когда не существует такого , что и
Максимальный элемент определяется как максимальный элемент подмножества.
Множество может иметь несколько максимальных элементов, но при этом не иметь наибольшего элемента. Подобно верхним границам и максимальным элементам, наибольшие элементы могут не существовать.
В полностью упорядоченном множестве максимальный и наибольший элементы совпадают; и его еще называют максимальным ; в случае значений функции его также называют абсолютным максимумом , чтобы избежать путаницы с локальным максимумом . [1]
Двойственные термины — это минимум и абсолютный минимум . Вместе они называются абсолютными экстремумами . Аналогичные выводы справедливы и для наименьшего количества элементов.
Роль (не)сравнимости в различении наибольших и максимальных элементов
Одно из наиболее важных различий между наибольшим элементом и максимальным элементом предупорядоченного множества связано с тем, с какими элементами они сравнимы. Два элемента называются сравнимыми , если или ; их называют несравнимыми, если они несравнимы. Поскольку предварительные заказы рефлексивны (это означает, что это верно для всех элементов ), каждый элемент всегда сравним сам с собой. Следовательно, единственные пары элементов, которые могут быть несравнимыми, — это различные пары. Однако в целом предупорядоченные множества (и даже направленные частично упорядоченные множества) могут содержать несравнимые элементы.
По определению, элемент является наибольшим элементом if для каждого ; поэтому по самому своему определению наибольший элемент должен , в частности, быть сравним с каждым элементом в.
Это не требуется от максимальных элементов. Максимальные элементы не обязательно должны быть сопоставимы с каждым элементом в.
Это потому, что в отличие от определения «наибольшего элемента», определение «максимального элемента» включает важный оператор if . Определяющее условие для того, чтобы быть максимальным элементом, можно переформулировать как:
Для всех ЕСЛИ (поэтому несравнимые элементы игнорируются ) тогда
Пример, когда все элементы максимальны, но ни один из них не является наибольшим
Предположим, что это набор, содержащий по крайней мере два (различных) элемента, и определите частичный порядок , заявив, что тогда и только тогда, когда
If принадлежит then, ни то , ни другое не выполняется, что показывает, что все пары различных (т. е. неравных) элементов в являются в сопоставимом. Следовательно, не может иметь наибольшего элемента (поскольку наибольший элемент , в частности, должен быть сопоставим с каждым элементом , но не имеет такого элемента). Однако каждый элемент является максимальным элементом, поскольку в нем есть ровно один элемент, который одновременно сравним и этот элемент сам по себе (это, конечно, ). [примечание 1]
Напротив, если предварительно упорядоченный набор действительно имеет наибольший элемент , то он обязательно будет максимальным элементом и, более того, как следствие того, что наибольший элемент сравним с каждым элементом, если также частично упорядочен, тогда можно заключить, что является единственным максимальным элементом
. Однако вывод о единственности больше не гарантируется, если предварительно упорядоченный набор также не является частично упорядоченным. Например, предположим, что это непустой набор, и определите предварительный порядок, объявив , что он всегда выполняется для всех. Направленный предварительно упорядоченный набор является частично упорядоченным тогда и только тогда, когда он содержит ровно один элемент. Все пары элементов из сопоставимы, и каждый элемент из является наибольшим элементом (и, следовательно, также максимальным элементом) So, в частности, если он имеет хотя бы два элемента, то имеет несколько различных наибольших элементов.
Множество может иметь не более одного наибольшего элемента. [примечание 2] Таким образом, если в наборе есть наибольший элемент, то он обязательно уникален.
Если он существует, то наибольший элемент является верхней границей , которая также содержится в
Если это наибольший элемент, то он также является максимальным элементом [примечание 3] и, более того, любой другой максимальный элемент обязательно будет равен [примечание 4]
Таким образом, если множество имеет несколько максимальных элементов, то оно не может иметь наибольший элемент.
Когда ограничение to представляет собой полный порядок ( на самой верхней картинке приведен пример), тогда понятия максимального элемента и наибольшего элемента совпадают. [примечание 6]
Однако это не является необходимым условием, ибо всякий раз, когда имеется наибольший элемент, понятия тоже совпадают, как сказано выше.
Если понятия максимального элемента и наибольшего элемента совпадают на каждом двухэлементном подмножестве, то это полный порядок на [примечание 7]
Достаточные условия
Конечная цепь всегда имеет наибольший и наименьший элемент.
Верх и низ
Наименьший и наибольший элементы всего частично упорядоченного множества играют особую роль и называются также нижним (⊥) и верхним (⊤) или нулем (0) и единицей (1) соответственно. Если оба существуют, ЧУУ называется ограниченным ЧУУ . Обозначение 0 и 1 используется предпочтительно, когда ЧУМ представляет собой дополняемую решетку и когда путаница невозможна, т. е. когда речь не идет о частичных порядках чисел, которые уже содержат элементы 0 и 1, отличные от нижнего и верхнего. Существование наименьшего и наибольшего элементов является особым свойством полноты частичного порядка.
Дополнительную вводную информацию можно найти в статье по теории порядка .
Примеры
Подмножество целых чисел не имеет верхней границы в множестве действительных чисел .
Пусть отношение on задается формулой: Множество имеет верхние границы , но не имеет ни малейшей верхней границы, ни наибольшего элемента (см. рисунок).
В рациональных числах набор чисел с квадратом меньше 2 имеет верхние границы, но не имеет ни наибольшего элемента, ни наименьшего верхнего предела.
В наборе чисел меньше 1 имеется наименьшая верхняя граница, а именно. 1, но нет величайшего элемента.
В множестве чисел, меньших или равных 1, есть наибольший элемент, а именно. 1, что также является его наименьшей верхней границей.
^ Конечно, в данном конкретном примере существует только один элемент, сравнимый с которым обязательно является он сам, поэтому второе условие «и » было избыточным.
^ Если и оба величайшие, то и, следовательно, по антисимметрии .
^ Если — наибольший элемент и тогда По антисимметрии , это делает ( и ) невозможным.
^ Если это максимальный элемент, то поскольку он наибольший, следовательно, поскольку он максимальный.
^ Только если: см. выше. — Если: Предположим, что противоречие имеет только один максимальный элемент, но не имеет наибольшего элемента. Поскольку не является наибольшим, должно существовать некоторое несравнимое с . Следовательно, не может быть максимальным, то есть должно выполняться для некоторых. Последнее также должно быть несравнимо с, поскольку противоречит максимальности ' и в то же время противоречит несравнимости и Повторяя этот аргумент, бесконечное возрастание можно найти цепочку (такую, что каждая из них несравнима и не максимальна). Это противоречит условию восходящей цепочки.
^ Пусть будет максимальным элементом для любого или Во втором случае определение максимального элемента требует этого, поэтому следует, что Другими словами, это наибольший элемент.
^ Если бы были несравнимы, то имели бы два максимальных, но не наибольший элемент, что противоречит совпадению.
Рекомендации
^ Понятие локальности требует, чтобы область определения функции была как минимум топологическим пространством .