Maximale und minimale Elemente

In der Mathematik , insbesondere in der Ordnungstheorie , ist ein maximales Element einer Teilmenge einer vorgeordneten Menge ein Element, das nicht kleiner als jedes andere Element in ist . Ein minimales Element einer Teilmenge einer vorgeordneten Menge ist dual definiert als ein Element, das nicht größer als jedes andere Element in ist . ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

Die Begriffe des maximalen und minimalen Elements sind schwächer als die des größten und kleinsten Elements , die auch als Maximum bzw. Minimum bekannt sind. Das Maximum einer Teilmenge einer vorgeordneten Menge ist ein Element, das größer oder gleich jedem anderen Element ist, und das Minimum wird analog definiert. Im Spezialfall einer partiell geordneten Menge kann es zwar höchstens ein Maximum und höchstens ein Minimum geben, aber auch mehrere maximale oder minimale Elemente. ^{[ 1 ] [ 2 ]} Bei total geordneten Mengen stimmen die Begriffe des maximalen Elements und des Maximums sowie die Begriffe des minimalen Elements und des Minimums überein. ${\displaystyle S}$${\displaystyle S}$${\displaystyle S,}$${\displaystyle S}$

Beispielsweise ist in der nach Enthaltensein geordneten Menge das Element { d , o } minimal, da es keine Menge der Menge enthält; das Element { g , o , a , d } ist maximal, da es keine Menge der Menge gibt, die es enthält; das Element { d , o , g } ist weder minimal noch maximal; und das Element { o , a , f } ist sowohl minimal als auch maximal. Im Gegensatz dazu existiert für weder ein Maximum noch ein Minimum.$${\displaystyle S:=\left\{\{d,o\},\{d,o,g\},\{g,o,a,d\},\{o,a,f\}\right\}}$$${\displaystyle S.}$

Das Lemma von Zorn besagt, dass jede partiell geordnete Menge, für die jede total geordnete Teilmenge eine obere Schranke besitzt , mindestens ein maximales Element enthält. Dieses Lemma ist äquivalent zum Wohlordnungssatz und zum Auswahlaxiom ^{[ 3 ]} und impliziert wichtige Ergebnisse in anderen mathematischen Gebieten, wie den Satz von Hahn-Banach , den Satz von Kirszbraun , den Satz von Tychonoff , die Existenz einer Hamelbasis für jeden Vektorraum und die Existenz eines algebraischen Abschlusses für jeden Körper .

Sei eine vorgeordnete Menge und sei ein maximales Element von bezüglich ein Element , sodass ${\displaystyle (P,\leq )}$${\displaystyle S\subseteq P.}$${\displaystyle S}$${\displaystyle \,\leq \,}$${\displaystyle m\in S}$

Wenn die Bedingung erfüllt ist , dann notwendigerweise${\displaystyle s\in S}$${\displaystyle m\leq s,}$${\displaystyle s\leq m.}$

Ebenso, einDas kleinste Element vonbezüglich${\displaystyle S}$${\displaystyle \,\leq \,}$ist ein Element, so dass ${\displaystyle m\in S}$

Wenn die Bedingung erfüllt ist , dann notwendigerweise${\displaystyle s\in S}$${\displaystyle s\leq m,}$${\displaystyle m\leq s.}$

Äquivalent dazu ist ein minimales Element von bezüglich genau dann, wenn ein maximales Element von bezüglich ist, wobei nach Definition genau dann gilt, wenn (für alle ). ${\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}$

Wenn die Teilmenge nicht angegeben ist, sollte davon ausgegangen werden, dass explizit eine${\displaystyle S}$${\displaystyle S:=P.}$Das maximale Element (bzw.minimale Element)von${\displaystyle (P,\leq )}$ist ein maximales (bzw. minimales) Element vonbezüglich${\displaystyle S:=P}$${\displaystyle \,\leq .}$

Wenn die vorgeordnete Menge zufällig auch eine partiell geordnete Menge ist (oder allgemeiner, wenn die Einschränkung eine partiell geordnete Menge ist), dann ist ein maximales Element von genau dann, wenn es kein Element enthält, das strikt größer als ist . Dies bedeutet, dass es kein Element gibt, sodass und . Die Charakterisierung minimaler Elemente erhält man, indem man anstelle von verwendet.${\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 .}$

Maximale Elemente müssen nicht existieren.

• Beispiel 1: Sei , wobei die reellen Zahlen bezeichnet . Für alle außer (d. h., aber nicht ).${\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}$
• Beispiel 2: Sei , wobei die rationalen Zahlen bezeichnet und irrational ist.${\displaystyle S=\{s\in \mathbb {Q} ~:~1\leq s^{2}\leq 2\},}$${\displaystyle \mathbb {Q} }$${\displaystyle {\sqrt {2}}}$

Im Allgemeinen ist nur eine partielle Ordnung auf . Wenn ein maximales Element ist, dann bleibt es möglich, dass weder noch . Dies lässt die Möglichkeit offen, dass es mehr als ein maximales Element gibt. ${\displaystyle \,\leq \,}$${\displaystyle S.}$${\displaystyle m}$${\displaystyle s\in S,}$${\displaystyle s\leq m}$${\displaystyle m\leq s.}$

• Beispiel 3: Im Zaun sind alle Werte minimal und alle Werte maximal, wie in der Abbildung gezeigt.${\displaystyle a_{1}<b_{1}>a_{2}<b_{2}>a_{3}<b_{3}>\ldots ,}$${\displaystyle a_{i}}$${\displaystyle b_{i}}$
• Beispiel 4: Sei A eine Menge mit mindestens zwei Elementen und sei die Teilmenge der Potenzmenge, die aus einelementigen Teilmengen besteht , partiell geordnet durch . Dies ist die diskrete partiell geordnete Menge, in der keine zwei Elemente vergleichbar sind und somit jedes Element maximal (und minimal) ist; außerdem gilt für jedes verschiedene Element weder noch .${\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\}.}$

Für eine partiell geordnete Menge wird der irreflexive Kern mit bezeichnet und ist definiert durch , falls und . Für beliebige Elemente trifft genau einer der folgenden Fälle zu: ${\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}$und sind unvergleichbar.${\displaystyle y}$

Gegeben sei eine Teilmenge und einige${\displaystyle S\subseteq P}$${\displaystyle x\in S,}$

• Wenn Fall 1 für kein Element zutrifft, dann ist ein maximales Element von wie oben definiert;${\displaystyle y\in S,}$${\displaystyle x}$${\displaystyle S,}$
• Wenn Fall 1 und 4 niemals auf irgendeinen Fall zutreffen, dann wird dieser als größtes Element von bezeichnet.${\displaystyle y\in S,}$${\displaystyle x}$${\displaystyle S.}$

Die Definition eines größten Elements ist somit strenger als die eines maximalen Elements.

Äquivalent dazu kann das größte Element einer Teilmenge als ein Element definiert werden, das größer ist als jedes andere Element der Teilmenge. Eine Teilmenge kann höchstens ein größtes Element haben. ^{[ Beweis 1 ]}${\displaystyle S}$${\displaystyle S}$${\displaystyle S.}$

Das größte Element von , falls es existiert, ist auch ein maximales Element von ^{[ Beweis 2 ]} und das einzige. ^{[ Beweis 3 ]} Nach der Kontraposition kann , falls mehrere maximale Elemente besitzt, kein größtes Element haben; siehe Beispiel 3. Falls die Bedingung der aufsteigenden Kette erfüllt ist , besitzt eine Teilmenge von genau dann ein größtes Element , wenn sie ein maximales Element besitzt. ^{[ Beweis 4 ]}${\displaystyle S,}$${\displaystyle S,}$${\displaystyle S}$${\displaystyle P}$${\displaystyle S}$${\displaystyle P}$

Wenn die Einschränkung von eine Totalordnung ist ( im obersten Bild ist ein Beispiel dargestellt), dann stimmen die Begriffe des maximalen Elements und des größten Elements überein. ^{[ Beweis 5 ]} Dies ist keine notwendige Bedingung: Immer wenn ein größtes Element besitzt, stimmen die Begriffe ebenfalls überein, wie oben erwähnt. Stimmen die Begriffe des maximalen Elements und des größten Elements auf jeder zweielementigen Teilmenge von überein, dann ist eine Totalordnung auf ^{[ Beweis 6 ].}${\displaystyle \,\leq \,}$${\displaystyle S}$${\displaystyle S=\{1,2,4\}}$${\displaystyle S}$${\displaystyle S}$${\displaystyle P.}$${\displaystyle \,\leq \,}$${\displaystyle P.}$

Das Dual zum Größten ist der Begriff des kleinsten Elements , der sich zum Minimalen in der gleichen Weise verhält wie das Größte zum Maximalen .

In einer total geordneten Menge fallen die Begriffe maximales Element und größtes Element zusammen. Daher werden beide Begriffe in Gebieten wie der Analysis , in denen nur totale Ordnungen betrachtet werden, synonym verwendet. Diese Beobachtung gilt nicht nur für total geordnete Teilmengen beliebiger partiell geordneter Mengen, sondern auch für deren ordnungstheoretische Verallgemeinerung mittels gerichteter Mengen . In einer gerichteten Menge besitzt jedes Paar von Elementen (insbesondere Paare unvergleichbarer Elemente) eine gemeinsame obere Schranke innerhalb der Menge. Besitzt eine gerichtete Menge ein maximales Element, so ist dieses auch ihr größtes Element ^{[ Beweis 7 ]} und somit ihr einziges maximales Element. Beispiele 1 und 2 oben zeigen gerichtete Mengen ohne maximales oder größtes Element .

Ähnliche Schlussfolgerungen gelten auch für minimale Elemente.

Weiterführende Informationen finden sich im Artikel über Ordnungstheorie .

• Jede endliche, nichtleere Teilmenge besitzt sowohl maximale als auch minimale Elemente. Eine unendliche Teilmenge muss keines dieser Elemente enthalten, beispielsweise die ganzen Zahlen in der üblichen Reihenfolge.${\displaystyle S}$${\displaystyle \mathbb {Z} }$
• Die Menge der maximalen Elemente einer Teilmenge ist stets eine Antikette , das heißt, keine zwei verschiedenen maximalen Elemente sind vergleichbar. Dasselbe gilt für minimale Elemente.${\displaystyle S}$${\displaystyle S}$

• Bei der Pareto-Effizienz ist ein Pareto-Optimum ein maximales Element in Bezug auf die partielle Ordnung der Pareto-Verbesserung, und die Menge der maximalen Elemente wird als Pareto-Front bezeichnet.
• In der Entscheidungstheorie ist eine zulässige Entscheidungsregel ein maximales Element in Bezug auf die partielle Ordnung der dominierenden Entscheidungsregel .
• In der modernen Portfoliotheorie wird die Menge der maximalen Elemente in Bezug auf die Produktordnung nach Risiko und Rendite als Effizienzgrenze bezeichnet .
• In der Mengenlehre heißt eine Menge endlich , wenn jede nichtleere Familie von Teilmengen ein minimales Element besitzt, wenn sie nach der Inklusionsrelation geordnet wird .
• In der abstrakten Algebra ist das Konzept des maximalen gemeinsamen Teilers erforderlich, um den größten gemeinsamen Teiler auf Zahlensysteme zu verallgemeinern, in denen die gemeinsamen Teiler einer Menge von Elementen mehr als ein maximales Element haben können.
• In der algorithmischen Geometrie sind die Maxima einer Punktmenge maximal in Bezug auf die partielle Ordnung der koordinatenweisen Dominanz.

In der Ökonomie kann man das Axiom der Antisymmetrie abschwächen, indem man Präordnungen (im Allgemeinen totale Präordnungen ) anstelle von partiellen Ordnungen verwendet; der Begriff ist dem maximalen Element sehr ähnlich, jedoch wird eine andere Terminologie verwendet, wie im Folgenden näher erläutert wird.

In der Konsumtheorie ist der Konsumraum eine Menge , üblicherweise der positive Orthant eines Vektorraums, sodass jedes Element eine für jedes Gut in der Volkswirtschaft festgelegte Konsummenge repräsentiert. Die Präferenzen eines Konsumenten werden üblicherweise durch eine totale Präordnung dargestellt, sodass gilt : ist höchstens so bevorzugt wie . Wenn und , wird dies so interpretiert, dass der Konsument zwischen und indifferent ist . Dies ist jedoch kein Grund zu der Annahme, dass Präferenzrelationen niemals als antisymmetrisch angenommen werden. In diesem Kontext heißt ein Element für jedes ein maximales Element , wenn impliziert, dass ein Konsumbündel ist, das von keinem anderen Bündel dominiert wird, d. h. ist und nicht .${\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.}$

Es sei angemerkt, dass die formale Definition der eines größten Elements einer geordneten Menge sehr ähnelt. Wenn es sich jedoch nur um eine Präordnung handelt, verhält sich ein Element mit der oben genannten Eigenschaft sehr ähnlich wie ein maximales Element in einer Ordnung. Beispielsweise ist ein maximales Element nicht eindeutig, und schließt nicht aus, dass (während und nicht implizieren, sondern lediglich Indifferenz ). Der Begriff des größten Elements für eine Präferenzpräordnung wäre der der am meisten bevorzugten Wahl. Das heißt, ein Element mit impliziert${\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.}$

Eine naheliegende Anwendung ist die Definition der Nachfragekorrespondenz. Sei die Klasse der Funktionale auf . Ein Element wird als Preisfunktional oder Preissystem bezeichnet und ordnet jedem Konsumbündel seinen Marktwert zu . Die Budgetkorrespondenz ist eine Korrespondenz, die jedes Preissystem und jedes Einkommensniveau auf eine Teilmenge abbildet. ${\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\}.}$$

Die Nachfragekorrespondenz ordnet jeden Preis und jedes Einkommensniveau der Menge der -maximalen Elemente von zu . ${\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\}.}$$

Man spricht von Nachfragekorrespondenz, weil die Theorie vorhersagt, dass bei gegebenen Bedingungen die rationale Wahl eines Konsumenten ein bestimmtes Element sein wird.${\displaystyle p}$${\displaystyle m}$${\displaystyle x^{*}}$${\displaystyle x^{*}\in D(p,m).}$

Eine Teilmenge einer partiell geordneten Menge heißt kofinal , wenn es zu jedem Element ein Element gibt , sodass gilt: Jede kofinale Teilmenge einer partiell geordneten Menge mit maximalen Elementen muss alle maximalen Elemente enthalten. ${\displaystyle Q}$${\displaystyle P}$${\displaystyle x\in P}$${\displaystyle y\in Q}$${\displaystyle x\leq y.}$

Eine Teilmenge einer partiell geordneten Menge heißt Untermenge , wenn sie nach unten abgeschlossen ist: Wenn und dann . Jede Untermenge einer endlichen geordneten Menge ist gleich der kleinsten Untermenge, die alle maximalen Elemente enthält.${\displaystyle L}$${\displaystyle P}$${\displaystyle P}$${\displaystyle y\in L}$${\displaystyle x\leq y}$${\displaystyle x\in L.}$${\displaystyle L}$${\displaystyle P}$${\displaystyle L.}$

• Größtes und kleinstes Element  – ​​ein mathematisches Konzept
• Infimum und Supremum  – Größte untere Grenze und kleinste obere Grenze
• Obere und untere Grenzen  – Majorant und Minor in der Mathematik

Beweise