Максимальные и минимальные элементы - Maximal and minimal elements

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

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

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

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

S = {{d, о}, {d, о, грамм}, {грамм, о, а, d}, {о, а, ж}}

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

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

Определение

Позволять ${ displaystyle (P, leq)}$ быть частично упорядоченным множеством и ${ Displaystyle S substeq P}$ . потом ${ displaystyle m in S}$ является максимальным элементом ${ displaystyle S}$ если ${ displaystyle S}$ не содержит элементов больше, чем ${ displaystyle m}$ , формально: если нет ${ displaystyle s in S}$ так что оба ${ displaystyle m leq s}$ и ${ displaystyle m neq s.}$

Определение минимальных элементов получается при использовании ≥ вместо ≤.

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

А изгородь состоит только из минимального и максимального элементов (Пример 3).

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

Пример 1: Позволять S = [1,∞) ⊂ ℝ, для всех м∈S у нас есть s=м+1∈S но м<s (то есть, м≤s но нет м=s).

Пример 2: Позволять S = {s∈ℚ: 1≤s²≤2} ⊂ ℚ и напомним, что

{ displaystyle { sqrt {2}}}

∉ℚ.

В общем, ≤ - это только частичный порядок на S. Если м является максимальным элементом и s∈S, остается возможность, что ни s≤м ни м≤s. Это оставляет открытой возможность того, что существует много максимальных элементов.

Пример 3: в изгородь а₁ < б₁ > а₂ < б₂ > а₃ < б₃ > ..., все а_я минимальны, и все б_я максимальные, см. рисунок.

Пример 4: Позволять А будет набором минимум из двух элементов и пусть S={{а}: а∈А} быть подмножеством набор мощности п(А) состоящий из синглтоны, частично упорядоченный ⊂. Это дискретный poset - никакие два элемента не сопоставимы - и, следовательно, каждый элемент {а}∈S максимальна (и минимальна) и для любых различных а′,а" ни один {а′} ⊂ {а"} ни {а″} ⊂ {а′}.

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

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

$Икс < у$ ,
$Икс = у$ ,
$у < Икс$ ,
$Икс$ и $у$ несравненные.

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

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

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

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

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

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

Направленные наборы

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

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

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

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

Каждое конечное непустое подмножество S имеет как максимальные, так и минимальные элементы. Бесконечная подстановка не обязательно должна иметь какие-либо из них, например ℤ в обычном порядке.
Множество максимальных элементов подмножества S всегда антицепь, то есть нет двух разных максимальных элементов S сопоставимы. То же самое и с минимальными элементами.

Примеры

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

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

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

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

{ displaystyle y in B}

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

{ Displaystyle у prevq х}

и он интерпретируется как потребительский набор, над которым не доминирует какой-либо другой набор в том смысле, что ${ Displaystyle х пре у}$ , то есть ${ Displaystyle х prevq y}$ и нет ${ Displaystyle у prevq х}$ .

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

{ displaystyle y in B}

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

{ Displaystyle у пре х.}

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

{ displaystyle Gamma (p, m) = {x in X mid p (x) leq m }.}

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

{ Displaystyle D (п, м) = { большой {} х в X середине х}

является максимальным элементом

{ Displaystyle Гамма (п, м) { большой }}}

.

Это называется соответствием спроса, потому что теория предсказывает, что для ${ displaystyle p}$ и ${ displaystyle m}$ Учитывая рациональный выбор потребителя ${ displaystyle x ^ {*}}$ будет какой-то элемент ${ Displaystyle х ^ {*} в 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$ и $грамм 2$ оба величайшие, тогда $грамм 1 \leq грамм 2$ и $грамм 2 \leq грамм 1$ , и поэтому $грамм 1 = грамм 2$ к антисимметрия.
^ Если $грамм$ это величайший элемент $S$ и $s \in S$ , тогда $s \leq грамм$ . К антисимметрия, это отображает ( $грамм \leq s$ и $грамм \neq s$ ) невозможно.
^ Если $м'$ - максимальный элемент, то $м' \leq грамм$ поскольку $грамм$ самый большой, следовательно $м' = грамм$ поскольку $м'$ максимально.
^ Только если: см. выше. - Если: Предположим от противного, что $S$ имеет только один максимальный элемент, $м$ , но не величайший элемент. С $м$ не самый лучший, некоторые $s 1 \in S$ должно существовать то, что несравнимо с $м$ . Следовательно $s 1 \in S$ не может быть максимальным, то есть $s 1 < s 2$ должен держаться за некоторые $s 2 \in S$ . Последнее должно быть несравнимо с $м$ тоже, так как $м < s 2$ противоречит $м$ максимальность в то время как $s 2 \leq м$ противоречит несравнимости $м$ и $s 1$ . Повторяя этот аргумент, бесконечная восходящая цепочка $s 1 < s 2 < \cdot\cdot\cdot < s п < \cdot\cdot\cdot$ можно найти (так что каждый $s я$ несравнимо с $м$ и не максимальный). Это противоречит условию возрастающей цепи.
^ Позволять $м \in S$ быть максимальным элементом для любого $s \in S$ либо $s \leq м$ или же $м \leq s$ . Во втором случае определение максимального элемента требует, чтобы $м = s$ , поэтому $s \leq м$ . Другими словами, $м$ это величайший элемент.
^ Если $а, б \in п$ были несравненными, тогда $S = {а, б$ } будет иметь два максимальных, но не самых больших элемента, что противоречит совпадению.
^ Позволять ${ displaystyle m in D}$ быть максимальным. Допустим от противного. ${ displaystyle x in D}$ несравнимо с ${ displaystyle m}$ , то общая верхняя оценка ${ displaystyle u}$ из ${ displaystyle m}$ и ${ displaystyle x}$ сравнимо с ${ displaystyle x}$ и поэтому не может равняться ${ displaystyle m}$ , следовательно ${ Displaystyle м <и}$ , что противоречит максимальности. Следовательно ${ displaystyle m}$ это величайший элемент.