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

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

Диаграмма Хассе множества 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}$

Например, в коллекции, упорядоченной по включению , элемент { d , o } является минимальным, поскольку он не содержит множеств в коллекции, элемент { g , o , a , d } является максимальным, поскольку в коллекции нет множеств, которые его содержат, элемент { d , o , g } не является ни тем, ни другим, а элемент { o , a , f } является как минимальным, так и максимальным. Напротив, ни максимума, ни минимума не существует для $${\displaystyle S:=\left\{\{d,o\},\{d,o,g\},\{g,o,a,d\},\{o,a,f\}\right\}}$$ ${\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}}}$

В общем случае имеет место лишь частичный порядок на . Если — максимальный элемент, то остается возможность, что ни один из них не является , ни Это оставляет открытой возможность того, что существует более одного максимального элемента. ${\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\}.}$

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

Для частично упорядоченного множества иррефлексивное ядро ​​обозначается как и определяется как если и Для произвольных членов применим только один из следующих случаев: ${\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.}$

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

Когда ограничение на является полным порядком ( на самом верхнем рисунке это пример), то понятия максимального элемента и наибольшего элемента совпадают. ^{[доказательство 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.}$

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

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

Примечания

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

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. Jech, Thomas (2008) [первоначально опубликовано в 1973]. Аксиома выбора . Dover Publications . ISBN 978-0-486-46624-8.