Максимальные и минимальные элементы

Элемент, который не является ≤ (или ≥) каким-либо другим элементом

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

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

Понятия максимального и минимального элементов слабее, чем понятия наибольшего элемента и наименьшего элемента , которые также известны соответственно как максимум и минимум. Максимум подмножества предварительно упорядоченного набора — это элемент, который больше или равен любому другому элементу, а минимум снова определяется двойственно. В частном случае частично упорядоченного множества , хотя может быть не более одного максимума и не более одного минимума, может быть несколько максимальных или минимальных элементов. ^{[1] [2]} При дальнейшей специализации на полностью упорядоченных множествах понятия максимального элемента и максимума совпадают, а понятия минимального элемента и минимума совпадают. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S,}$ ${\displaystyle S}$

Например, в сборнике

$${\displaystyle S:=\left\{\{d,o\},\{d,o,g\},\{g,o,a,d\},\{o,a,f\}\right\}}$$

содержаниюdogoaddogoaf ${\displaystyle S.}$

Лемма Цорна утверждает, что каждое частично упорядоченное множество, для которого каждое полностью упорядоченное подмножество имеет верхнюю границу , содержит хотя бы один максимальный элемент. Эта лемма эквивалентна теореме о хорошем порядке и аксиоме выбора ^[3] и подразумевает важные результаты в других математических областях, таких как теорема Хана-Банаха , теорема Киршбрауна , теорема Тихонова , существование базиса Гамеля для каждого векторного пространства. и существование алгебраического замыкания для каждого поля .

Определение

Пусть — предупорядоченное множество , и пусть максимальный элемент по отношению к — это такой элемент, что ${\displaystyle (P,\leq )}$ ${\displaystyle S\subseteq P.}$ ${\displaystyle S}$ ${\displaystyle \,\leq \,}$ ${\displaystyle m\in S}$

если удовлетворяет , то обязательно ${\displaystyle s\in S}$ ${\displaystyle m\leq s,}$ ${\displaystyle s\leq m.}$

Аналогично ,минимальным элементом поотношению к ${\displaystyle S}$ ${\displaystyle \,\leq \,}$такой элемент, ${\displaystyle m\in S}$

если удовлетворяет , то обязательно ${\displaystyle s\in S}$ ${\displaystyle s\leq m,}$ ${\displaystyle m\leq s.}$

Эквивалентно, является минимальным элементом относительно того и только тогда, когда является максимальным элементом относительно где по определению, тогда и только тогда, когда (для всех ). ${\displaystyle m\in S}$ ${\displaystyle S}$ ${\displaystyle \,\leq \,}$ ${\displaystyle m}$ ${\displaystyle S}$ ${\displaystyle \,\geq ,\,}$ ${\displaystyle q\geq p}$ ${\displaystyle p\leq q}$ ${\displaystyle p,q\in P}$

Если подмножество не указано, то следует предположить, что явно ${\displaystyle S}$ ${\displaystyle S:=P.}$максимальный элемент (соответственноминимальный элемент)является ${\displaystyle (P,\leq )}$максимальным (соответственно минимальным) элементомотносительно ${\displaystyle S:=P}$ ${\displaystyle \,\leq .}$

Если предварительно упорядоченный набор также является частично упорядоченным набором (или, в более общем смысле, если ограничение является частично упорядоченным набором), то он является максимальным элементом тогда и только тогда, когда не содержит ни одного элемента, строго большего, чем явно, это означает, что не существует существует любой элемент такой, что и Характеристика минимальных элементов получается путем использования вместо ${\displaystyle (P,\leq )}$ ${\displaystyle (S,\leq )}$ ${\displaystyle m\in S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle m;}$ ${\displaystyle s\in S}$ ${\displaystyle m\leq s}$ ${\displaystyle m\neq s.}$ ${\displaystyle \,\geq \,}$ ${\displaystyle \,\leq .}$

Существование и уникальность

Забор состоит только из минимальных и максимальных элементов (пример 3).

Максимальные элементы не обязательно должны существовать.

• Пример 1: Пусть где обозначает действительные числа . Для всех кроме (то есть, но не ). ${\displaystyle S=[1,\infty )\subseteq \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle m\in S,}$ ${\displaystyle s=m+1\in S}$ ${\displaystyle m<s}$ ${\displaystyle m\leq s}$ ${\displaystyle m=s}$
• Пример 2: Пусть где обозначает рациональные числа , а где иррационально. ${\displaystyle S=\{s\in \mathbb {Q} ~:~1\leq s^{2}\leq 2\},}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle {\sqrt {2}}}$

В общем случае это только частичный порядок в If является максимальным элементом, и тогда остается возможным, что ни и Это не оставляет открытой возможности существования более одного максимальных элементов. ${\displaystyle \,\leq \,}$ ${\displaystyle S.}$ ${\displaystyle m}$ ${\displaystyle s\in S,}$ ${\displaystyle s\leq m}$ ${\displaystyle m\leq s.}$

• Пример 3: В заборе все минимальны и все максимальны, как показано на рисунке. ${\displaystyle a_{1}<b_{1}>a_{2}<b_{2}>a_{3}<b_{3}>\ldots ,}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$
• Пример 4. Пусть A — множество, состоящее как минимум из двух элементов, и пусть — подмножество степенного множества , состоящее из одноэлементных подмножеств , частично упорядоченных по формуле. Это дискретное частично упорядоченное множество, в котором никакие два элемента не сравнимы, и, следовательно, каждый элемент является максимальным (и минимальным). ); более того, для любого отчетливого ни или ${\displaystyle S=\{\{a\}~:~a\in A\}}$ ${\displaystyle \wp (A)}$ ${\displaystyle \,\subseteq .}$ ${\displaystyle \{a\}\in S}$ ${\displaystyle a,b\in A,}$ ${\displaystyle \{a\}\subseteq \{b\}}$ ${\displaystyle \{b\}\subseteq \{a\}.}$

Величайшие элементы

Для частично упорядоченного множества иррефлексивное ядро ​​обозначается и определяется как if и Для произвольных членов применяется ровно один из следующих случаев: ${\displaystyle (P,\leq ),}$ ${\displaystyle \,\leq \,}$ ${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle x\leq y}$ ${\displaystyle x\neq y.}$ ${\displaystyle x,y\in P,}$

1. ${\displaystyle x<y}$;
2. ${\displaystyle x=y}$;
3. ${\displaystyle y<x}$;
4. ${\displaystyle x}$и несравнимы. ${\displaystyle y}$

Учитывая подмножество и некоторые ${\displaystyle S\subseteq P}$ ${\displaystyle x\in S,}$

• если случай 1 никогда не применяется ни к одному из них, то это максимальный элемент, определенный выше; ${\displaystyle y\in S,}$ ${\displaystyle x}$ ${\displaystyle S,}$
• если случай 1 и 4 никогда не применим ни к одному из них, то он называется наибольшим элементом ${\displaystyle y\in S,}$ ${\displaystyle x}$ ${\displaystyle S.}$

Таким образом, определение наибольшего элемента сильнее, чем определение максимального элемента.

Эквивалентно, наибольший элемент подмножества может быть определен как элемент, который больше, чем любой другой элемент подмножества. Подмножество может иметь не более одного наибольшего элемента. ^{[доказательство 1]} ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S.}$

Наибольший элемент if он существует, также является максимальным элементом ^{[доказательства 2]} и единственным. ^{[доказательство 3]} В противоположность этому , если он имеет несколько максимальных элементов, он не может иметь наибольший элемент; см . пример 3. Если удовлетворяет условию возрастающей цепи , подмножество имеет наибольший элемент тогда и только тогда , когда оно имеет один максимальный элемент. ^{[доказательство 4]} ${\displaystyle S,}$ ${\displaystyle S,}$ ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle P}$

Когда ограничение to представляет собой полный порядок ( на самой верхней картинке приведен пример), тогда понятия максимального элемента и наибольшего элемента совпадают. ^{[доказательство 5]} Это не обязательное условие: всякий раз, когда имеется наибольший элемент, понятия тоже совпадают, как сказано выше. Если понятия максимального элемента и наибольшего элемента совпадают на каждом двухэлементном подмножестве, то это полный порядок на ^{[доказательство 6]} ${\displaystyle \,\leq \,}$ ${\displaystyle S}$ ${\displaystyle S=\{1,2,4\}}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle P.}$ ${\displaystyle \,\leq \,}$ ${\displaystyle P.}$

Режиссерские наборы

В полностью упорядоченном множестве термины «максимальный элемент» и «наибольший элемент» совпадают, поэтому оба термина используются как взаимозаменяемые в таких областях, как анализ , где рассматриваются только полные порядки. Это наблюдение применимо не только к полностью упорядоченным подмножествам любого частично упорядоченного множества, но также и к их теоретико-порядковому обобщению через направленные множества . В ориентированном множестве каждая пара элементов (особенно пары несравнимых элементов) имеет общую верхнюю границу внутри множества. Если направленное множество имеет максимальный элемент, то это также его наибольший элемент ^{(доказательство 7)} и, следовательно, его единственный максимальный элемент. Ориентированное множество без максимальных или наибольших элементов см. в примерах 1 и 2 выше.

Аналогичные выводы справедливы и для минимальных элементов.

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

Характеристики

• Каждое конечное непустое подмножество имеет как максимальные, так и минимальные элементы. Бесконечное подмножество не обязательно должно содержать ни один из них, например целые числа обычного порядка. ${\displaystyle S}$ ${\displaystyle \mathbb {Z} }$
• Множество максимальных элементов подмножества всегда является антицепью , то есть никакие два различных максимальных элемента не сравнимы. То же самое касается и минимальных элементов. ${\displaystyle S}$ ${\displaystyle S}$

Примеры

• В эффективности Парето оптимум Парето является максимальным элементом относительно частичного порядка улучшения Парето, а набор максимальных элементов называется границей Парето.
• В теории принятия решений допустимое решающее правило является максимальным элементом относительно частичного порядка доминирующего решающего правила .
• В современной портфельной теории набор максимальных элементов относительно порядка продуктов по риску и доходности называется эффективной границей .
• В теории множеств множество конечно тогда и только тогда, когда каждое непустое семейство подмножеств имеет минимальный элемент при упорядочении по отношению включения .
• В абстрактной алгебре понятие максимального общего делителя необходимо для обобщения наибольших общих делителей на системы счисления, в которых общие делители набора элементов могут иметь более одного максимального элемента.
• В вычислительной геометрии максимумы множества точек максимальны относительно частичного порядка покоординатного доминирования.

Теория потребителя

В экономике можно ослабить аксиому антисимметрии, используя предварительные заказы (обычно полные предварительные заказы ) вместо частичных заказов; понятие, аналогичное максимальному элементу, очень похоже, но используется другая терминология, как подробно описано ниже.

В теории потребления пространство потребления — это некоторое множество , обычно положительное ортанта некоторого векторного пространства, так что каждое из них представляет количество потребления, определенное для каждого существующего товара в экономике. Предпочтения потребителя обычно выражаются общим предварительным заказом , поэтому и читается: не более чем так же предпочтительно, как . Когда и интерпретируется, что потребитель безразличен между и, но это не является основанием для вывода о том, что отношения предпочтений никогда не считаются антисимметричными. В этом контексте любой элемент называется максимальным , если ${\displaystyle X}$ ${\displaystyle x\in X}$ ${\displaystyle \preceq }$ ${\displaystyle x,y\in X}$ ${\displaystyle x\preceq y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\preceq y}$ ${\displaystyle y\preceq x}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x=y.}$ ${\displaystyle B\subseteq X,}$ ${\displaystyle x\in B}$

$${\displaystyle y\in B}$$

${\displaystyle y\preceq x}$ ${\displaystyle x\prec y,}$ ${\displaystyle x\preceq y}$ ${\displaystyle y\preceq x.}$

Следует отметить, что формальное определение очень похоже на определение наибольшего элемента упорядоченного множества. Однако, когда это только предварительный порядок, элемент с указанным выше свойством ведет себя очень похоже на максимальный элемент в упорядочении. Например, максимальный элемент не уникален, поскольку не исключает возможности того, что (хотя и не подразумевают , а просто безразличие ). Понятием наибольшего элемента предзаказа предпочтений будет понятие наиболее предпочтительного выбора. То есть некоторые с ${\displaystyle \preceq }$ ${\displaystyle x}$ ${\displaystyle x\in B}$ ${\displaystyle y\preceq x}$ ${\displaystyle x\preceq y}$ ${\displaystyle y\preceq x}$ ${\displaystyle x\preceq y}$ ${\displaystyle x=y}$ ${\displaystyle x\sim y}$ ${\displaystyle x\in B}$

$${\displaystyle y\in B}$$

${\displaystyle y\prec x.}$

Очевидным применением является определение соответствия спроса. Пусть – класс функционалов от . Элемент называется ценовым функционалом или ценовой системой и отображает каждый потребительский набор в его рыночную стоимость . Бюджетное соответствие — это соответствие , отображающее любую систему цен и любой уровень доходов в подмножество ${\displaystyle P}$ ${\displaystyle X}$ ${\displaystyle p\in P}$ ${\displaystyle x\in X}$ ${\displaystyle p(x)\in \mathbb {R} _{+}}$ ${\displaystyle \Gamma \colon P\times \mathbb {R} _{+}\rightarrow X}$

$${\displaystyle \Gamma (p,m)=\{x\in X~:~p(x)\leq m\}.}$$

Соответствие спроса отображает любую цену и любой уровень дохода в набор -максимальных элементов . ${\displaystyle p}$ ${\displaystyle m}$ ${\displaystyle \preceq }$ ${\displaystyle \Gamma (p,m)}$

$${\displaystyle D(p,m)=\left\{x\in X~:~x{\text{ is a maximal element of }}\Gamma (p,m)\right\}.}$$

Это называется соответствием спроса, потому что теория предсказывает, что при данных условиях рациональный выбор потребителя будет неким элементом ${\displaystyle p}$ ${\displaystyle m}$ ${\displaystyle x^{*}}$ ${\displaystyle x^{*}\in D(p,m).}$

Связанные понятия

Подмножество частично упорядоченного множества называется конфинальным, если для каждого существует такое , что Каждое конфинальное подмножество частично упорядоченного множества с максимальными элементами должно содержать все максимальные элементы. ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle x\in P}$ ${\displaystyle y\in Q}$ ${\displaystyle x\leq y.}$

Подмножество частично упорядоченного множества называется нижним множеством , если оно замкнуто вниз: если и то Каждое нижнее множество конечного упорядоченного множества равно наименьшему нижнему множеству, содержащему все максимальные элементы ${\displaystyle L}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle y\in L}$ ${\displaystyle x\leq y}$ ${\displaystyle x\in L.}$ ${\displaystyle L}$ ${\displaystyle P}$ ${\displaystyle L.}$

Смотрите также

• Наибольший элемент и наименьший элемент  – элемент ≥ (или ≤) друг друга.
• Нижняя и верхняя границы  - наибольшая нижняя граница и наименьшая верхняя граница.
• Верхние и нижние границы  – мажоранта и миноранта в математике

Примечания

Доказательства

1. Если и оба величайшие, то и, следовательно, по антисимметрии . ${\displaystyle g_{1}}$ ${\displaystyle g_{2}}$ ${\displaystyle g_{1}\leq g_{2}}$ ${\displaystyle g_{2}\leq g_{1},}$ ${\displaystyle g_{1}=g_{2}}$ ${\displaystyle \blacksquare }$
2. Если — наибольший элемент и тогда По антисимметрии , это делает ( и ) невозможным. ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle s\in S,}$ ${\displaystyle s\leq g.}$ ${\displaystyle g\leq s}$ ${\displaystyle g\neq s}$ ${\displaystyle \blacksquare }$
3. Если это максимальный элемент, то (потому что он наибольший) и, следовательно, поскольку он максимален. ${\displaystyle m}$ ${\displaystyle m\leq g}$ ${\displaystyle g}$ ${\displaystyle m=g}$ ${\displaystyle m}$ ${\displaystyle \blacksquare }$
4. Только если : см. выше. — Если : Предположим, что противоречие имеет только один максимальный элемент, но не имеет наибольшего элемента. Поскольку не является наибольшим, должно существовать некоторое несравнимое с . Следовательно, не может быть максимальным, то есть должно выполняться для некоторых. Последнее также должно быть несравнимо с, поскольку противоречит максимальности и в то же время противоречит несравнимости и Повторяя этот аргумент, бесконечное возрастание можно найти цепочку (такую, что каждая из них несравнима и не максимальна). Это противоречит условию восходящей цепочки. ${\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}<\ldots <s_{n}<\cdots }$ ${\displaystyle s_{i}}$ ${\displaystyle m}$ ${\displaystyle \blacksquare }$
5. Пусть будет максимальным элементом для любого или Во втором случае определение максимального элемента требует этого, поэтому следует, что Другими словами, это наибольший элемент. ${\displaystyle m\in S}$ ${\displaystyle s\in S}$ ${\displaystyle s\leq m}$ ${\displaystyle m\leq s.}$ ${\displaystyle s=m,}$ ${\displaystyle s\leq m.}$ ${\displaystyle m}$ ${\displaystyle \blacksquare }$
6. Если бы были несравнимы, то имели бы два максимальных, но не наибольший элемент, что противоречит совпадению. ${\displaystyle a,b\in P}$ ${\displaystyle S=\{a,b\}}$ ${\displaystyle \blacksquare }$
7. Пусть будет максимальным. Пусть будет произвольным. Тогда общая верхняя граница и удовлетворяет , т. е. по максимальности. Поскольку выполняется по определению , имеем . Следовательно, это величайший элемент. ${\displaystyle m\in D}$ ${\displaystyle x\in D}$ ${\displaystyle u}$ ${\displaystyle m}$ ${\displaystyle x}$ ${\displaystyle u\geq m}$ ${\displaystyle u=m}$ ${\displaystyle x\leq u}$ ${\displaystyle u}$ ${\displaystyle x\leq m}$ ${\displaystyle m}$ ${\displaystyle \blacksquare }$

Рекомендации

• Математический портал

1. Ричмонд, Беттина ; Ричмонд, Томас (2009), Дискретный переход к высшей математике, Американское математическое общество, стр. 181, ISBN 978-0-8218-4789-3.
2. Скотт, Уильям Рэймонд (1987), Теория групп (2-е изд.), Дувр, стр. 22, ISBN 978-0-486-65377-8
3. Джех, Томас (2008) [первоначально опубликовано в 1973 году]. Аксиома выбора . Дуврские публикации . ISBN 978-0-486-46624-8.