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

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

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

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

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

Лемма Цорна утверждает, что каждое частично упорядоченное множество, для которого каждое полностью упорядоченное подмножество имеет верхнюю границу, содержит по крайней мере один максимальный элемент. Эта лемма эквивалентна теореме хорошо упорядочения и аксиомы выбора и предполагает значительные результаты в других математических областях , как теорема Хана-Банаха , то теорема 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, \,}$${\ displaystyle q \ geq p}$${\ displaystyle p \ leq q}$${\ displaystyle p, q \ in P}$

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

множества мощности , состоящее из одноэлементных подмножеств , частично упорядочено Это является дискретным ч.у.м. , где никаких два элемента не сравним , и , таким образом , каждый элемент является максимальным (и минимальными ); более того, для каких-либо отличных ни, ни${\ Displaystyle S = \ {\ {а \} ~: ~ а \ в А \}}$ ${\ Displaystyle \ WP (А)}$${\ displaystyle \, \ substeq.}$${\ displaystyle \ {a \} \ in S}$${\ displaystyle a, b \ in A,}$${\ Displaystyle \ {а \} \ substeq \ {Ь \}}$${\ displaystyle \ {b \} \ substeq \ {a \}.}$

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

Для частично упорядоченного множества

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

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

Учитывая подмножество и некоторые${\ Displaystyle S \ substeq P}$${\ Displaystyle х \ в S,}$

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

наибольший элемент из${\ displaystyle y \ in S,}$${\ displaystyle x}$${\ displaystyle S.}$

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

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

Наибольший элемент, если он существует, также является максимальным элементом и единственным. По

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

Когда ограничение до является

полным порядком ( пример на верхнем рисунке), тогда понятия максимального элемента и наибольшего элемента совпадают. Это не является обязательным условием: всякий раз, когда есть наибольший элемент, понятия также совпадают, как указано выше. Если понятия максимального элемента и наибольшего элемент совпадает на каждом из двух элементов подмножества из , то есть общего порядка на${\ Displaystyle \, \ Leq \,}$${\ displaystyle S}$${\ Displaystyle S = \ {1,2,4 \}}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle P.}$${\ Displaystyle \, \ Leq \,}$${\ displaystyle P.}$

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

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

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

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

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

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

целые числа в обычном порядке.${\ displaystyle S}$ ${\ Displaystyle \ mathbb {Z}}$

Множество максимальных элементов подмножества всегда является

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

Примеры

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

эффективной границей .

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

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

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

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

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

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

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

Следует отметить, что формальное определение очень похоже на определение наибольшего элемента упорядоченного множества. Однако, когда это только предварительный заказ, элемент с указанным выше свойством ведет себя очень похоже на максимальный элемент в упорядочивании. Например, максимальный элемент не является уникальным, поскольку не исключает возможности того, что (while и не подразумевают, а просто безразличие ). Понятие наибольшего элемента для предварительного заказа предпочтения будет понятием наиболее предпочтительного выбора. То есть некоторые с ${\ 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 у \ пре х.}$

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

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

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

Примечания

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

использованная литература