В математике , особенно в теории порядка , величайший элемент подмножестваиз частично упорядоченного множества (посета) является элементом это больше, чем любой другой элемент . Термин наименьший элемент определяется двояко , то есть это элемент это меньше, чем любой другой элемент
Определения
Позволять быть предварительно заказанным набором и пусть Элемент называется наибольший элемент если и если он также удовлетворяет:
- для всех
Используя вместо в приведенном выше определении определение наименьшего элемента получается. Явно элементназывается наименьший элемент если и если он также удовлетворяет:
- для всех
Если является частично упорядоченным множеством, томожет иметь не более одного наибольшего элемента и не более одного наименьшего элемента. Всякий раз, когда величайший элементсуществует и единственно , то этот элемент называется наибольшим элементом. Терминология - наименьший элемент определяется аналогично.
Если имеет наибольший элемент (соотв. наименьший элемент) , то этот элемент также называют верхней (соответственно. снизу ) из
Отношение к верхней / нижней границам
Наибольшие элементы тесно связаны с верхними границами .
Позволять быть предварительно заказанным набором и пустьВерхняя граница из в это элемент такой, что а также для всех Важно отметить, что верхняя граница в это не требуется , чтобы быть элементом
Если тогда это величайший элемент если и только если является верхней границей в а также В частности, любой величайший элемент также является верхней границей (в ), но верхняя граница в это величайший элемент если и только если оно принадлежит к В частном случае, когда определение " является верхней границей в "становится: такой элемент, что а также для всех что полностью идентично определению величайшего элемента, данному ранее. Таким образом это величайший элемент если и только если является верхней границей в .
Если является верхней границей в это не верхняя граница в (что может произойти тогда и только тогда, когда ) тогда не может быть величайшим элементом(однако возможно, что какой-то другой элемент является величайшим элементом). В частности, это возможно длячтобы одновременно не было наибольшего элемента и чтобы существовала некоторая верхняя граница в .
Даже если у набора есть некоторые верхние границы, у него не обязательно должен быть наибольший элемент, как показано на примере отрицательных действительных чисел . Этот пример также демонстрирует, что существование наименьшей верхней границы (в данном случае числа 0) также не означает существования наибольшего элемента.
Контраст максимальным элементам и локальным / абсолютным максимумам
Наибольший элемент подмножества предварительно упорядоченного набора не следует путать с максимальным элементом набора, то есть элементами, которые строго не меньше любого другого элемента в наборе.
Позволять быть предварительно заказанным набором и пусть Элемент Говорят , чтобы быть максимальный элемент из если выполняется следующее условие:
- в любое время удовлетворяет тогда обязательно
Если является частично упорядоченным множеством, то является максимальным элементом тогда и только тогда, когда не существует такой, что а также Максимальный элемент определяется как максимальный элемент подмножества
Набор может состоять из нескольких максимальных элементов, но не иметь самого большого элемента. Подобно верхним границам и максимальным элементам, самые большие элементы могут не существовать.
В полностью упорядоченном множестве максимальный элемент и самый большой элемент совпадают; и его еще называют максимальным ; в случае значений функции он также называется абсолютным максимумом , чтобы избежать путаницы с локальным максимумом . [1] Двойные условия являются минимальным и абсолютным минимумом . Вместе они называются абсолютными экстремумами . Аналогичные выводы справедливы для наименьшего количества элементов.
- Роль (не) сопоставимости в различении наибольших и максимальных элементов
Одно из самых важных различий между величайшим элементом и максимальный элемент предварительно заказанного набора имеет отношение к тому, с какими элементами они сопоставимы. Два элементасчитаются сопоставимыми, если или же ; их называют несравнимыми, если они не сопоставимы. Поскольку предварительные заказы являются рефлексивными (что означает, что верно для всех элементов ), каждый элемент всегда сравнимо с собой. Следовательно, единственные пары элементов, которые могут быть несравнимыми, - это разные пары. В общем, однако, предварительно упорядоченные множества (и даже направленные частично упорядоченные множества) могут иметь несравнимые элементы.
По определению элемент это величайший элемент если для каждого ; так что по самому своему определению, величайший элементдолжны, в частности, быть сопоставимы с каждым элементом вОт максимальных элементов этого не требуется. Максимальные элементыкоторые не должны быть сопоставимы с каждым элементом вЭто потому, что в отличие от определения «наибольший элемент», определение «максимальный элемент» включает в себя важный оператор if . Определяющее условие для быть максимальным элементом можно перефразировать как:
- Для всех ЕСЛИ (поэтому элементы, несравнимые с игнорируются) тогда
- Пример, когда все элементы максимальны, но ни один не является наибольшим
Предположим, что - это набор, содержащий не менее двух (различных) элементов и определяющий частичный порядок на заявив, что если и только если Если принадлежит тогда ни ни выполняется, что показывает, что все пары различных (т. е. неравных) элементов в находятся в сопоставимых. Вследствие этого, не может иметь наибольшего элемента (потому что наибольший элемент в частности, должны быть сопоставимы с каждым элементом но не имеет такого элемента). Однако каждый элемент является максимальным элементом потому что в это сравнимо с а также этот элемент сам (что, конечно, ). [примечание 1]
Напротив, если предварительно заказанный набор действительно есть величайший элемент тогда обязательно будет максимальным элементом и более того, как следствие величайшего элемента быть сопоставимым с каждым элементом если также частично упорядочен, то можно сделать вывод, что это единственный максимальный элемент Однако вывод об уникальности больше не гарантируется, если предварительно упорядоченный набор это не также частично упорядоченное. Например, предположим, что является непустым набором и определяет предварительный заказ на заявив, что всегда справедливо для всехНаправлено предупорядоченное множество частично заказан тогда и только тогда, когда имеет ровно один элемент. Все пары элементов изсопоставимы, и каждый элемент является наибольшим элементом (а значит, и максимальным элементом) Так, в частности, если имеет как минимум два элемента, тогда имеет несколько отличных величайших элементов.
Характеристики
На всем протяжении пусть - частично упорядоченное множество, и пусть
- Множество может иметь не более одного наибольшего элемента. [примечание 2] Таким образом, если набор имеет наибольший элемент, он обязательно уникален.
- Если он существует, то наибольший элемент приведен верхняя граница из что также содержится в
- Если это величайший элемент тогда также является максимальным элементом [примечание 3] и, кроме того, любой другой максимальный элемент обязательно будет равно [примечание 4]
- Таким образом, если набор имеет несколько максимальных элементов, тогда у него не может быть самого большого элемента.
- Если удовлетворяет условию возрастающей цепочки , подмножество из имеет наибольший элемент тогда и только тогда , когда он имеет один максимальный элемент. [примечание 5]
- Когда ограничение к это общий заказ (на самом верхнем рисунке пример), то понятия максимального элемента и наибольшего элемента совпадают. [примечание 6]
- Однако это не является обязательным условием всякий раз, когда имеет наибольший элемент, понятия совпадают, как было сказано выше.
- Если понятия максимального элемента и наибольшего элемента совпадают на каждом двухэлементном подмножестве из тогда это полный заказ на [примечание 7]
Достаточные условия
- У конечной цепи всегда есть наибольший и наименьший элемент.
Верх и низ
Наименьший и наибольший элементы всего частично упорядоченного множества играют особую роль и также называются нижним (⊥) и верхним () или нулевым (0) и единичным (1) соответственно. Если оба существуют, то называется ограниченным множеством . Обозначение 0 и 1 используется предпочтительно, когда poset представляет собой решетку с дополнениями и когда нет вероятности путаницы, то есть когда речь не идет о частичных порядках чисел, которые уже содержат элементы 0 и 1, отличные от нижнего и верхнего. Существование наименьшего и наибольшего элементов - это особое свойство полноты частичного порядка.
Дополнительную вводную информацию можно найти в статье о теории порядка .
Примеры
- Подмножество целых чисел не имеет верхней границы в набореиз действительных чисел .
- Пусть отношение на быть предоставленным Набор имеет верхнюю границу а также но нет никакой наименьшей верхней границы и никакого наибольшего элемента (см. рисунок).
- В рациональных числах набор чисел с квадратом меньше 2 имеет верхнюю границу, но не имеет наибольшего элемента и наименьшей верхней границы.
- В набор чисел меньше 1 имеет наименьшую верхнюю границу, а именно. 1, но не самый большой элемент.
- В набор чисел, меньших или равных 1, имеет наибольший элемент, а именно. 1, что также является его точной верхней границей.
- В при заказе товара набор пар с участием не имеет верхней границы.
- В в лексикографическом порядке это множество имеет верхние границы, например У него нет минимальной верхней границы.
Смотрите также
- Essential supremum и Essential infimum
- Начальные и конечные объекты
- Максимальные и минимальные элементы
- Ограничить верхний и нижний предел (нижний предел)
- Верхняя и нижняя границы
Заметки
- ^ Конечно, в этом конкретном примере существует только один элемент в это сравнимо с что обязательно сам, поэтому второе условие "и "было лишним.
- ^ Если а также оба величайшие, тогда а также и поэтому по антисимметрии .
- ^ Если это величайший элемент а также тогда По антисимметрии это дает ( а также ) невозможно.
- ^ Если - максимальный элемент, то поскольку самый большой, следовательно поскольку максимально.
- ^ Только если: см. Выше. - Если: Допустим от противного, что имеет только один максимальный элемент, но не величайший элемент. С не самый лучший, некоторые должно существовать то, что несравнимо с Следовательно не может быть максимальным, то есть должен держаться за некоторые Последнее должно быть несравнимо с тоже, так как противоречит максимальность в то время как противоречит несравнимости а также Повторяя этот аргумент, бесконечная восходящая цепочка можно найти (так что каждый несравнимо с и не максимальный). Это противоречит условию возрастающей цепи.
- ^ Пусть быть максимальным элементом для любого либо или же Во втором случае определение максимального элемента требует, чтобы из этого следует, что Другими словами, это величайший элемент.
- ^ Если были несравненными, тогда будет иметь два максимальных, но не наибольших элемента, что противоречит совпадению.
Рекомендации
- ^ Понятие локальности требует, чтобы область определения функции была по крайней мере топологическим пространством .
- Дэйви, BA; Пристли, HA (2002). Введение в решетки и порядок (2-е изд.). Издательство Кембриджского университета . ISBN 978-0-521-78451-1.