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

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

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

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

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

упорядоченный по содержанию , элемент { d , o } является минимальным, поскольку он не содержит наборов в коллекции, элемент { g , o , a , d } является максимальным, поскольку в коллекции нет наборов, которые его содержат, элемент { d , o , g } не является ни тем, ни другим, а элемент { o , a , f } является одновременно минимальным и максимальным. Напротив, ни максимума, ни минимума не существует для

S.

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

Определение [ править ]

Позволять $(P,\leq )$ быть заранее заказанным набором и пусть $S\subseteq P.$ элемент Максимальный $S$ относительно $\,\leq \,$ это элемент $m\in S$ такой, что

если

s\in S

удовлетворяет

m\leq s,

тогда обязательно

s\leq m.

, Аналогично минимальный элемент $S$ относительно $\,\leq \,$ это элемент $m\in S$ такой, что

если

s\in S

удовлетворяет

s\leq m,

тогда обязательно

m\leq s.

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

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

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

Существование и уникальность [ править ]

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

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

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

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

Наибольший и наименьший элементы [ править ]

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

$x<y$ ;
$x=y$ ;
$y<x$ ;
$x$ и $y$ несравнимы.

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

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

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

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

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

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

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

Направленные наборы [ править ]

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

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

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

Свойства [ править ]

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

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

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

Теория потребителя [ править ]

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

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

y\in B

подразумевает

y\preceq x

где он интерпретируется как потребительский набор, в котором не доминирует какой-либо другой набор в том смысле, что

x\prec y,

то есть

x\preceq y

и не

y\preceq x.

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

y\in B

подразумевает

y\prec x.

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

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

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

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

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

Связанные понятия [ править ]

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

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

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

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

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

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

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