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

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

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

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

Например, в коллекции

S = {{ d , o }, { d , o , g }, { g , o , a , d }, { o , a , f }}

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

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

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

Пусть быть предупорядоченное множество , и пусть A максимальный элемент в отношении является элементом таким образом, что ${\ displaystyle (P, \ leq)}$ ${\ Displaystyle S \ substeq 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.}

Эквивалентно, является минимальным элементом относительно тогда и только тогда, когда является максимальным элементом относительно where по определению, тогда и только тогда (для всех ). ${\ displaystyle m \ in S}$ ${\ displaystyle S}$ ${\ Displaystyle \, \ Leq \,}$ ${\ displaystyle m}$ ${\ displaystyle S}$ ${\ Displaystyle \, \ 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 .$

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

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

Максимальных элементов не должно быть.

Пример 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}

2 {\displaystyle {\sqrt {2}}}

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

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.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки [ править ]

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

[4] Еслииявляются наибольшим, тоииследовательнопо антисимметричности . $g_{1}$ $g_{2}$ $g_{1}\leq g_{2}$ $g_{2}\leq g_{1},$ $g_{1}=g_{2}$

[5] Еслиявляется наибольшим элементом,азатемПо антисимметрии , это делает (и) невозможным. $g$ $S$ $s\in S,$ $s\leq g.$ $g\leq s$ $g\neq s$

[6] Еслиявляется максимальным элементом, то(потому чтоон наибольший) и, следовательно,посколькуявляется максимальным. $n$ $n\leq h$ $g$ $n=g$ $n$

[7] Только если : см. Выше. - Если : Допустим для противоречия, чтоесть только один максимальный элемент,но нет наибольшего элемента. Посколькуне является наибольшим,должно существоватькакое-то, что несравнимо сСледовательно,не может быть максимальным, то естьдолжно выполняться для некоторых. Последнее также должно быть несравнимо с ним, посколькупротиворечитмаксимальности, в то время какпротиворечит несравнимостииповторению этого аргумента, бесконечному возрастанию.может быть найденацепочка(такая, что каждая изних несравнимаи не максимальна). Это противоречит условию возрастающей цепи. $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$

[8] Пустьмаксимальный элемент для любоголибоиливо втором случае, определение максимального элемента требует,поэтому следуетчтоДругими словами,наибольший элемент. $m\in S$ $s\in S$ $s\leq m$ $m\leq s.$ $s=m,$ $s\leq m.$ $m$

[9] Если быбыли несравнимы, тоимели бы два максимальных, но не величайших элемента, противоречащих совпадению. $a,b\in P$ $S=\{a,b\}$

[10] Позвольтебыть максимальным. Предположим для противоречия некоторой произвольнойнесравнима, то общая верхняя границаизисравнима сиследовательноне может быть равна, следовательно, вопреки максимальности. Отсюда- величайший элемент. $m\in D$ $x\in D$ $m$ $u$ $m$ $x$ $x$ $m$ $m<u$ $m$

[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.

[1]