Benutzer:Schojoha/Spielwiese/Ordnungstheorie

Porezkisches Gesetz

In der booleschen Algebra, einem der Teilgebiete der Mathematik, ist das porezkische Gesetz (englisch Poretzky's law) ein Satz, der eine charakteristische Eigenschaft des Nullelements einer booleschen Algebra wiedergibt und nach dem russischen Mathematiker Platon Sergejewitsch Porezki benannt ist.

Darstellung des Gesetzes

Porezkis Gesetz lässt sich folgendermaßen formulieren:

Gegeben seien eine boolesche Algebra $(B,\land ,\lor ,{'},1,0)$ und darin ein festes Element $a\in B$.

Dann ist $a=0$ dann und nur dann, wenn für alle $b\in B$ die Gleichung

$b=(a\land b^{'})\lor (a^{'}\land b)$

erfüllt ist.

Erläuterung und Beweisskizze

• Dass das Nullelement $a=0$ einerseits die Gleichung $b=(a\land b^{'})\lor (a^{'}\land b)$ für alle $b\in B$ stets erfüllt, ergibt sich daraus, dass der zugehörige Verband $(B,\land ,\lor )$ auf natürliche Weise eine beschränkte halbgeordnete Menge darstellt mit $0=\min B$ und $1=0{'}=\max B$. Setzt man in der Gleichung andererseits $b=a$, so folgt wegen $a\land a^{'}=0$ unmittelbar $a=0$.
• Auf anderem Wege kann man auch in Rechnung stellen, dass die boolesche Algebra $(B,\land ,\lor ,{'},1,0)$ stets und in bekannter Weise als boolescher Ring $(B,{+},{-},{\cdot },1,0)$ aufgefasst werden kann. Unter dieser Sichtweise besagt das porezkische Gesetz, dass das Nullelement $a=0$ dadurch gekennzeichnet ist, dass für $b\in B$ stets die Gleichung $b=a+b$ gilt.

Literatur

• Joseph Gallian: Contemporary Abstract Algebra. D. C. Heath and Company, Lexington (Mass.), Toronto 1986, ISBN 0-669-09325-4. 
• Hans Hermes: Einführung in die Verbandstheorie (= Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete. Band 73). Zweite erweiterte Auflage. Springer Verlag, Berlin, Heidelberg, New York 1967 (MR0220634). 

Anmerkungen

rrreferences group="A" />

Einzelnachweise

rrreferences />

KKKategorie:Boolesche Algebra]] KKKategorie:Satz (Mathematik)]]

Lemma von Iwamura

Das Lemma von Iwamura ist ein Lehrsatz des mathematischen Gebiets der Ordnungstheorie und geht auf eine wissenschaftliche Publikation des Mathematikers Tsurane Iwamura aus dem Jahre 1944 zurück. Das Lemma behandelt eine Frage zur Überdeckungsdarstellbarkeit von gerichteten Mengen und gab Anlass zu einer Reihe von weitergehenden Untersuchungen.

Formulierung des Lemmas

An die Monographie Einführung in die Ordnungstheorie von Marcel Erné anschließend lässt sich das Lemma folgendermaßen darstellen:

Für jede unendliche teilweise geordnete Menge $(M,\leq )$, die durch die zugrunde liegende Ordnungsrelation $\leq$ nach oben gerichtet ist, gibt es ein Teilmengensystem ${\mathcal {K}}\subset 2^{M}$ mit folgenden Eigenschaften:

(I) ${\mathcal {K}}$ ist eine durch die Inklusionsrelation wohlgeordnete Kette von Mengen.

(II) Die Teilmengen $K\in {\mathcal {K}}$ überdecken die Grundmenge $M$; es gilt also $\bigcup {\mathcal {K}}=M$.

(III) Für jede Teilmenge $K\in {\mathcal {K}}$ gilt hinsichtlich ihrer Mächtigkeit die Ungleichung $|K|<|M|$.

(IV) Für jede Teilmenge $K\in {\mathcal {K}}$ ist die mit der induzierten Ordnungsrelation versehene teilweise geordnete Menge $(K,{\leq }|_{K})$ ebenfalls nach oben gerichtet.

Erläuterungen und Anmerkungen

• Das Lemma lässt sich zurückführen auf die Tatsache, dass jede unendliche Menge $M$ darstellbar ist als Vereinigung eines durch die Inklusionsrelation wohlgeordneten Teilmengensystems von $M$, in dem jede der darin liegenden Teilmengen eine echt kleinere Mächtigkeit hat als die Menge $M$ selbst.
• Das Lemma beruht weiterhin darauf, dass für eine unendliche Menge $M$ das Teilmengensystem der endlichen Teilmengen und die Menge $M$ selbst stets gleichmächtig sind.
• Als Anwendung kann man mittels des Lemmas von Iwamura zeigen, dass eine partiell geordnete Menge bereits dann vollständig ist (d. h. jede nach oben gerichtete Teilmenge hat eine kleinste obere Schranke), wenn jede nach oben gerichtete Kette eine kleinste obere Schranke hat.

Literatur

• Marcel Erné: Einführung in die Ordnungstheorie. Bibliographisches Institut, Mannheim 1982, ISBN 3-411-01638-8 (MR0689891). 
• T. Iwamura: Ein Hilfssatz über gerichtete Mengen (Japanisch). In: Zenkoku Shijo Sugaku Danwakai. Band 262, 1944, S. 107–111. 
• George Grätzer: General Lattice Theory (= Lehrbücher und Monographien aus dem Gebiete der Exakten Wissenschaften, Mathematische Reihe. Band 52). Birkhäuser Verlag, Basel, Stuttgart 1978, ISBN 3-7643-0813-3 (MR0504338). 
• George Markowsky: Chain-complete posets and directed sets with applications. In: Algebra Universalis. Band 6, 1976, S. 53–68, doi:10.1007/BF02485815 (MR0398913). 
• J. Mayer-Kalkschmidt, E. Steiner: Some theorems in set theory and applications in the ideal theory of partially ordered sets. In: Duke Mathematical Journal. Band 31, 1964, S. 287–289 (MR0160729). 

Einzelnachweise

rreferences />

KKKategorie:Ordnungstheorie|Iwamura, Lemma von]] KKKategorie:Satz (Mathematik)|Iwamura, Lemma von]]

Ergänzung zum Fixpunktsatz von Tarski und Knaster: Der Satz von Davis

Der Fixpunktsatz von Tarski und Knaster, benannt nach Bronisław Knaster und Alfred Tarski, ist ein mathematischer Satz aus dem Gebiet der Verbandstheorie.

Aussage

Sei ${\mathcal {A}}:=\langle A,\leq \rangle$ ein vollständiger Verband, $f\colon A\to A$ monoton, und $P:=\{x\in A\mid f(x)=x\}$ die Menge der Fixpunkte von $f$ in $A$. Unter diesen Voraussetzungen ist $P\neq \emptyset$ und ${\mathcal {P}}:=\langle P,\leq \rangle$ ebenfalls ein vollständiger Verband.

Beweisidee

$\textstyle \bigcup _{\mathcal {A}}$ sei die Supremum-Operation von ${\mathcal {A}}$, und $\textstyle \bigcap _{\mathcal {A}}$ die Infimum-Operation von ${\mathcal {A}}$.

Die folgenden Schritte zeigen, dass ${\mathcal {P}}$ für beliebige Teilmengen von $P$ ein Infimum und ein Supremum in $P$ liefert.

1. $\textstyle \bigcup _{\mathcal {A}}\{x\in A\mid x\leq f(x)\}$ ist Fixpunkt von $f$, und zwar der größte in $A$. Somit ist dies das ${\mathcal {P}}$-Supremum von $P$.
2. Dual zu Schritt 1: $\textstyle \bigcap _{\mathcal {A}}\{x\in A\mid f(x)\leq x\}$ ist Fixpunkt von $f$, und zwar der kleinste in $A$.
3. Für beliebige Teilmengen $Y\subseteq P$, soll es ein ${\mathcal {P}}$-Supremum geben. Die Fälle $Y=P$ und $Y=\emptyset$ sind bereits in den Schritten 1 und 2 gezeigt. Betrachtet werden nun die anderen Fälle. Dazu wird ausgenutzt, dass $\langle U,\leq \rangle$ mit $\textstyle U:=\{x\in A\mid \bigcup _{\mathcal {A}}Y\leq x\}$ wieder ein vollständiger Verband ist, und $f|_{U}$ eine monotone Funktion $U\to U$ ist, die nach Schritt 2 einen kleinsten Fixpunkt in $U$ hat. Dieser ist das ${\mathcal {P}}$-Supremum von $Y$. In Formeln: $\textstyle \bigcup _{\mathcal {P}}Y:=\bigcap _{\mathcal {A}}\{x\in A\mid \bigcup _{\mathcal {A}}Y\cup f(x)\ \leq \ x\}$.
4. Dual zu Schritt 3 wird gezeigt, dass beliebige Teilmengen von $P$ ein ${\mathcal {P}}$-Infimum haben.

Konsequenzen

Eine oft verwendete Konsequenz ist die der Existenz von kleinsten und größten Fixpunkten von bezüglich $\subseteq$ monotonen Funktionen.

Umkehrung

Der Fixpunktsatz besitzt eine gewisse Umkehrung in einem Satz, den Anne C. Davis im Jahre 1955 vorgelegt hat:

Besitzt in einem Verband ${\mathcal {A}}$ jede monotone Abbildung $f\colon {\mathcal {A}}\to {\mathcal {A}}$ einen Fixpunkt, so ist ${\mathcal {A}}$ ein vollständiger Verband.

Literatur

• Garrett Birkhoff: Lattice Theory. 3. Auflage. American Mathematical Society, Providence, Rhode Island 1979. 
• George Grätzer: General Lattice Theory. 2. Auflage. Birkhäuser Verlag, Basel, Boston, Berlin 1998, ISBN 3-7643-5239-6 (MR1670580). 
• L. A. Skornjakow: Elemente der Verbandstheorie (= Wissenschaftliche Taschenbücher, Reihe Mathematik/Physik. Band 130). Akademie Verlag, Berlin 1973, ISBN 3-7643-5239-6. 
• Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications. In: Pacific Journal of Mathematics. 5:2. Jahrgang, 1955, S. 285–309 (projecteuclid.org). 

Einzelnachweise

rreferences />

KKKategorie:Verbandstheorie]] KKKategorie:Satz (Mathematik)|Tarski und Knaster, Fixpunktsatz von]]

Satz von Birkhoff (unfertig!!!)

Der Satz von Birkhoff (englisch Birkhoff's theorem) ist einer der klassischen Sätze des mathematischen Gebiets der Verbandstheorie. Der Satz behandelt und beantwortet die Frage der Darstellung distributiver Verbände als Mengenverbände und ist eng verwandt mit Marshall Harvey Stones Darstellungssatz für Boolesche Algebren.

Formulierung des Satzes

Der Satz lässt sich zusammengefasst angeben wie folgt:

In einem modularen Verband besitzt jede unverkürzbare aus irreduzibelen Komponenten bestehende Darstellung eines Elements (soweit überhaupt vorhanden) stets dieselbe Anzahl von Komponenten.

Im Einzelnen gilt:

Sind ein modularer Verband $(V,\vee ,\wedge )$ sowie zwei natürliche Zahlen $n\geq 1$ und $m\geq 1$ und Elemente $v,x_{0},\,\dots ,x_{n-1},y_{0},\,\dots ,y_{m-1}\in V$ gegeben und hat $v$ die beiden Darstellungen

$v=x_{0}\vee \,\dots \vee x_{n-1}=y_{0}\vee \,\dots \vee y_{m-1}$,

wobei die beteiligeten Elemente $x_{i}$ und $y_{j}$ sämtlich $\vee$-irreduzibel und beide Darstellungen $\vee$-irredundant sind ,

so ist $n=m$

und dabei gibt es zu jedem Index $i\in \{0,\,\dots ,n-1\}$ einen Index $j(i)\in \{0,\,\dots ,m-1\}$ mit

$v=x_{0}\vee \,\dots \vee x_{i-1}\vee y_{j(i)}\vee x_{i+1}\vee \,\dots \vee x_{n-1}$.

In gleicher Weise gilt der zugehörige duale Satz.

Verwandte Sätze

I

Erläuterungen und Anmerkungen

• In einem Verband $(V,\vee ,\wedge )$

Literatur

• Garrett Birkhoff: Lattice Theory (= American Mathematical Society Colloquium Publications. Band XXV). 3. Auflage. American Mathematical Society, Providence, R.I. 1967 (MR0227053). 
• Hans Hermes: Einführung in die Verbandstheorie (= Die Grundlehren der mathematischen Wissenschaften. Band 73). Zweite erweiterte Auflage. Springer Verlag, Berlin, Heidelberg, New York 1967 (MR0220634). 
• Helmuth Gericke: Theorie der Verbände (= Hochschultaschenbücher. 38/38a). 2. Auflage. Bibliographisches Institut, Mannheim 1967 (MR0219453). 
• M. H. Stone: The theory of representations for Boolean algebras. In: Transactions of the American Mathematical Society. Band 40, 1936, S. 37–111, doi:10.1090/S0002-9947-1936-1501865-8 (MR1501865). 
• Egon Pracht: Algebra der Verbände (= Uni-Taschenbücher. Band 958). Ferdinand Schöningh, Paderborn, München, Wien, Zürich 1980, ISBN 3-506-99236-8 (MR0637885). 
• L. A. Skornjakow: Elemente der Verbandstheorie (= Wissenschaftliche Taschenbücher, Reihe Mathematik/Physik. Band 130). Akademie Verlag, Berlin 1973, ISBN 3-7643-5239-6. 
• Gábor Szász: Einführung in die Verbandstheorie. Akadémiai Kiadó, Budapest 1962 (MR0138567). 

Einzelnachweise

rreferences />

KKKategorie:Verbandstheorie]] KKKategorie:Satz (Mathematik)|Birkhoff]]

Satz von Kurosch-Ore

Der Satz von Kurosch-Ore (englisch Kurosh-Ore theorem oder Kuroš-Ore theorem) ist einer der klassischen Sätze des mathematischen Gebiets der Verbandstheorie. Der Satz behandelt eine Fragestellung zu irreduziblen Darstellungen von Elementen modularer Verbände und geht auf zwei Publikationen zurück, die von dem sowjetischen Mathematiker Alexander Gennadjewitsch Kurosch (im Jahre 1935) und von dem norwegischen Mathematiker Øystein Ore (im Jahre 1936) vorgelegt wurden. Er ist verwandt mit dem aus der Linearen Algebra bekannten Austauschsatz von Steinitz und eng verbunden mit dem Isomorphiesatz für modulare Verbände, auf dem der Beweis des Kurosch-Ore'schen Satzes im Wesentlichen beruht.

Formulierung des Satzes

Der Satz lässt sich zusammengefasst angeben wie folgt:

In einem modularen Verband besitzt jede unverkürzbare aus irreduzibelen Komponenten bestehende Darstellung eines Elements (soweit überhaupt vorhanden) stets dieselbe Anzahl von Komponenten.

Im Einzelnen gilt:

Sind ein modularer Verband $(V,\vee ,\wedge )$ sowie zwei natürliche Zahlen $n\geq 1$ und $m\geq 1$ und Elemente $v,x_{0},\,\dots ,x_{n-1},y_{0},\,\dots ,y_{m-1}\in V$ gegeben und hat $v$ die beiden Darstellungen

$v=x_{0}\vee \,\dots \vee x_{n-1}=y_{0}\vee \,\dots \vee y_{m-1}$,

wobei die beteiligten Elemente $x_{i}$ und $y_{j}$ sämtlich $\vee$-irreduzibel und beide Darstellungen $\vee$-irredundant sind ,

so ist $n=m$

und dabei gibt es zu jedem Index $i\in \{0,\,\dots ,n-1\}$ einen Index $j(i)\in \{0,\,\dots ,m-1\}$ mit

$v=x_{0}\vee \,\dots \vee x_{i-1}\vee y_{j(i)}\vee x_{i+1}\vee \,\dots \vee x_{n-1}$.

In gleicher Weise gilt der zugehörige duale Satz.

Verwandte Sätze

I

Zum Satz von Kurosch-Ore gibt es noch weitere Versionen. So wird etwa in der Monographie Lattices and Ordered Algebraic Structures von Thomas Scott Blyth der Satz in einer anderen, der obigen im Wesentlichen gleichwertigen Formulierung angeboten, die folgendes besagt:

In einem modularen Verband, der die absteigende Kettenbedingung erfüllt, haben alle irredundanten aus $\vee$-irreduzibelen Komponenten bestehenden $\vee$-Darstellungen eines Elements dieselbe Anzahl von Komponenten.

Wie Blyth zeigt, lässt sich in dieser Version der Satz von Kurosch-Ore weiter verschärfen, wenn statt eines modularen sogar ein distributiver Verband zugrundeliegt:

In einem distributiven Verband mit absteigender Kettenbedingung besitzt jedes vom Nullelement verschiedene Verbandselement eine und nur eine irredundante aus $\vee$-irreduzibelen Komponenten bestehenden $\vee$-Darstellung.

Der letzte Satz tritt ebenfalls in der Monographie Einführung in die Verbandstheorie von Hans Hermes auf und wird dort vom Autor als Zerlegungssatz bezeichnet.

II

In seiner Monographie erwähnt Hermes den Satz von Kurosch-Ore zwar nicht, er formuliert jedoch dort im Zusammenhang mit dem Isomorphiesatz für modulare Verbände einen anderen Satz, der dem Kurosch-Ore'schen Satz ähnelt und den Hermes als Kettensatz bezeichnet. Dieser Kettensatz lässt sich folgendermaßen darstellen:

Sind in dem modularen Verband $(V,\vee ,\wedge )$ zwei Elemente $v$ und $w$ durch eine endliche Kette $K_{0}\subseteq (V,\leq )$ verbunden und ist $K_{0}$ zugleich maximal in dem durch Inklusion geordneten Mengensystem aller $v$ und $w$ verbindenden Ketten, so ist auch jede andere $v$ und $w$ verbindende Kette $K$ endlich und erfüllt dabei hinsichtlich ihrer Mächtigkeit die Ungleichung $|K|\leq |K_{0}|$.

Der Kettensatz wird – nach Richard Dedekind – auch als dedekindscher Kettensatz bezeichnet und gilt in gleicher Weise noch in jedem (nach oben oder nach unten) semimodularen Verband.

Hermes greift beim Beweis des Kettensatzes wiederum auf ein anderes Resultat zurück, welches er als Folgerung aus dem erwähnten Isomorphiesatz gewinnt und das er als Nachbarsatz bezeichnet. Dieser Satz macht inhaltlich die Aussage, dass in einem modularen Verband $(V,\vee ,\wedge )$ und ebenso in dem zugehörigen dualen Verband $(V,\wedge ,\vee )$ für je zwei verschiedene Elemente $v,w\in V$ stets das semimodulare Gesetz erfüllt ist.

Erläuterungen und Anmerkungen

• In einem Verband $(V,\vee ,\wedge )$ ist für ein Element $v\in V$ eine Darstellung (englisch representation) eine Gleichung der Form $v=v_{0}\vee \,\dots \vee v_{n-1}$ oder der Form $v=v_{0}\wedge \,\dots \wedge v_{n-1}$ mit einer natürlichen Zahl $n\geq 0$. Die $v_{i}$ nennt man dabei die Komponenten der Darstellung. Die Zahl $n+1$ ist die Anzahl der Komponenten. Falls notwendig spricht man genauer von einer $\vee$-Darstellung bzw. einer $\wedge$-Darstellung.
• Man bezeichnet eine Darstellung $v=v_{0}\vee \,\dots \vee v_{n-1}$ bzw. $v=v_{0}\wedge \,\dots \wedge v_{n-1}$ als $\vee$-redundant (englisch join-redundant) bzw. als $\wedge$-redundant (englisch meet-redundant) genau dann, wenn es einen Index $i\in \{0,\,\dots ,n-1\}$ gibt mit $v=v_{0}\vee \,\dots \vee v_{i-1}\vee v_{i+1}\vee \,\dots \vee v_{n-1}$ bzw. mit $v=v_{0}\wedge \,\dots \wedge v_{i-1}\wedge v_{i+1}\wedge \,\dots \wedge v_{n-1}$. Andernfalls bezeichnet man eine solche Darstellung als $\vee$-irredundant (englisch join-irredundant) bzw. als $\wedge$-irredundant (englisch meet-irredundant). Ist der Kontext klar, so sagt man einfach redundant bzw. irredundant. Eine redundante Darstellung ist also in diesem Sinne verkürzbar, während eine irredundante Darstellung unverkürzbar ist.
• Ein Element $v\in V$ ist $\vee$-irreduzibel bzw. vereinigungsirreduzibel (englisch join-irreducible) genau dann, wenn für $v_{1},v_{2}\in V$ aus $v=v_{1}\vee v_{2}$ stets $v=v_{1}$ oder $v=v_{2}$ folgt. Entsprechend ist ein Element $v\in V$ $\wedge$-irreduzibel bzw. durchschnittsirreduzibel (englisch meet-irreducible) genau dann, wenn für $v_{1},v_{2}\in V$ aus $v=v_{1}\wedge v_{2}$ stets $v=v_{1}$ oder $v=v_{2}$ folgt. Ist der Kontext klar, so sagt man einfach irreduzibel. Der obige verbandstheoretische Irreduzibilitätsbegriff entspricht dem Irreduzibilitätsbegriff der Ringtheorie.
• Jeder Verband $(V,\vee ,\wedge )$ ist zugleich eine teilweise geordnete Menge $(V,\leq )$, deren Ordnungsrelation man aus den beiden Verknüpfungen $\vee$ und $\wedge$ erhält, wobei man diese ihrerseits zurückgewinnt durch die paarweise Bildung von Infimum und Supremum. Damit lassen sich in Verbänden alle Begriffe verwenden, die man aus der Ordnungstheorie kennt, und nicht zuletzt auch der Begriff der Kette. Hier sagt man dann, es seien zwei verschiedene Elemente $v$ und $w$ durch eine Kette $K$ verbunden, wenn $K$ bezüglich der induzierten Ordnungsrelation ${\leq }|_{K}$ ein kleinstes und ein größtes Element besitzt und diese beiden mit $v$ und $w$ übereinstimmen.
• Eine teilweise geordnete Menge $(V,\leq )$ erfüllt die absteigende Kettenbedingung (englisch descending chain condition), wenn jede Kette der Form $v_{1}\geq v_{2}\geq \dots \geq v_{n}\geq \dots$ nach endlich vielen Schritten stationär wird. Eine aus unendlich vielen verschiedenen Elementen bestehende Kette der Form $v_{1}>v_{2}>\dots >v_{n}>\dots$ ist dann also unmöglich. Der dazu duale Begriff ist der der aufsteigenden Kettenbedingung (englisch ascending chain condition).
• Laut Lew Anatoljewitsch Skornjakow ist der Verband der Unterräume eines linearen Raums (mit der Inklusion als Ordnungsrelation) das wichtigste Beispiel für einen modularen Verband, während (im Allgemeinen) der Verband aller Untergruppen eine Gruppe ... kein modularer Verband sei.
• Helmuth Gericke stellt in seiner Theorie der Verbände den Normalteilerverband einer Gruppe (mit der Inklusion als Ordnungsrelation) als wichtiges Beispiel eines modularen Verbandes heraus. Den Satz von Kurosch-Ore gibt er – ohne Kurosch und Ore zu erwähnen – unter der Überschrift Der Austauschsatz in modularen Verbänden wieder.

Literatur

• Garrett Birkhoff: Lattice Theory (= American Mathematical Society Colloquium Publications. Band XXV). 3. Auflage. American Mathematical Society, Providence, R.I. 1967 (MR0227053). 
• T. S. Blyth: Lattices and Ordered Algebraic Structures (= Universitext). Springer-Verlag London, Ltd., London 2005 (MR2126425). 
• Hans Hermes: Einführung in die Verbandstheorie (= Die Grundlehren der mathematischen Wissenschaften. Band 73). Zweite erweiterte Auflage. Springer Verlag, Berlin, Heidelberg, New York 1967 (MR0220634). 
• Helmuth Gericke: Theorie der Verbände (= Hochschultaschenbücher. 38/38a). 2. Auflage. Bibliographisches Institut, Mannheim 1967 (MR0219453). 
• George Grätzer: General Lattice Theory. New appendices by the author with B. A. Davey, R. Freese, B. Ganter, M. Greferath, P. Jipsen, H. A. Priestley, H. Rose, E. T. Schmidt, S. E. Schmidt, F. Wehrung and R. Wille. 2. Auflage. Birkhäuser Verlag, Basel, Boston, Berlin 1998, ISBN 3-7643-5239-6 (MR1670580). 
• A. G. Kuroš: Durchschnittsdarstellungen mit irreduziblen Komponenten in Ringen und sogenannten Dualgruppen. In: Mat. Sb. Band 42, 1935, S. 613–616. 
• Ralph N. McKenzie, George F. McNulty, Walter F. Taylor: Algebras, Lattices, Varieties. Volume I (= The Wadsworth & Brooks/Cole Mathematics Series). Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, California 1987, ISBN 0-534-07651-3 (MR0883644). 
• O. Ore: On the foundation of abstract algebra. II. In: Ann. of Math. (2). Band 37, 1936, S. 265–292 (MR1503277). 
• Egon Pracht: Algebra der Verbände (= Uni-Taschenbücher. Band 958). Ferdinand Schöningh, Paderborn, München, Wien, Zürich 1980, ISBN 3-506-99236-8 (MR0637885). 
• L. A. Skornjakow: Elemente der Verbandstheorie (= Wissenschaftliche Taschenbücher, Reihe Mathematik/Physik. Band 130). Akademie Verlag, Berlin 1973, ISBN 3-7643-5239-6. 
• Gábor Szász: Einführung in die Verbandstheorie. Akadémiai Kiadó, Budapest 1962 (MR0138567). 

Einzelnachweise

rreferences />

KKKategorie:Verbandstheorie]] KKKategorie:Satz (Mathematik)|Kurosch-Ore]]

Ordnungsdimension

In der Ordnungstheorie, einem der Teilgebiete der Mathematik, versteht man unter der Ordnungsdimension eine bestimmte Kardinalzahl, die jeder teilweise geordneten Menge zugeordnet ist. Grundlage dieser Zuordnung ist ein auf die beiden Mathematiker Ben Dushnik und Edwin W. Miller zurückgehender Lehrsatz, der als Satz von Dushnik-Miller bekannt ist.

Der Satz von Dushnik-Miller

Er besagt folgendes:

Jede teilweise Ordnung ist der Durchschnitt von linearen Ordnungen.

Das heißt:

Ist $(X,\leq )$ eine teilweise geordnete Menge, so existiert auf der Trägermenge $X$ ein System ${\mathfrak {L}}$ von linearen Ordnungsrelationen mit

$\leq \;=\,\bigcap _{L\in {\mathfrak {L}}}\,L$.

Definition

Für eine teilweise geordnete Menge $(X,\leq )$ ist deren Ordnungsdimension, formal: $\operatorname {odim} (X,\leq )$ oder $\dim(X,\leq )$, definiert wie folgt:

Die Ordnungsdimension von $(X,\leq )$ ist gleich der kleinsten Mächtigkeit von allen Systemen linearer Ordnungsrelationen auf $X$, durch die $\leq$ als Durchschnitt gemäß dem Satz von Dushnik-Miller dargestellt werden kann.

Anmerkungen, Beispiele, Resultate

• Statt von der Ordnungsdimension sprechen manche Autoren auch von der Dushnik–Miller-Dimension.
• Der Satz von Dushnik-Miller ist eng mit dem Lemma von Szpilrajn verwandt.
• Die Potenzmenge ${\mathcal {P}}(X)$ einer nichtleeren Menge $X$, versehen mit der Teilmengenrelation, hat die Ordnungsdimension $\operatorname {odim} ({\mathcal {P}}(X),\subseteq )=|X|$.
• Ist $N$ eine natürliche Zahl, in deren Primfaktorzerlegung genau $\omega (N)$ Primfaktoren vorkommen, und ist $(X,\leq )=(T_{N},\mid )$ deren Teilermenge, versehen mit der Teilerrelation, so gilt $\operatorname {odim} (T_{N},\mid )=\omega (N)$. Für $N=360=2^{3}\cdot 3^{2}\cdot 5$ etwa ist $\operatorname {odim} (T_{360},\mid )=\omega (360)=3$ und für $N=26411=7^{4}\cdot 11$ ist $\operatorname {odim} (T_{26411},\mid )=\omega (26411)=2$.
• Es liegen – neben vielen anderen – die folgenden Resultate vor:
  • Über die Beziehung zwischen Ordnungsdimension und Spernerzahl : Die Ordnungsdimension einer teilweise geordneten Menge $(X,\leq )$ ist höchstens so groß wie deren Spernerzahl $\operatorname {w} (X,\leq )$, sofern die Spernerzahl endlich ist.
  • Die (nach dem japanischen Mathematiker Toshio Hiraguchi benannte) Ungleichung von Hiraguchi: Für eine natürliche Zahl $n\geq 4$ und eine endliche teilweise geordnete Menge $(X,\leq )$ mit $|X|=n$ Elementen beträgt die Ordnungsdimension $\operatorname {odim} (X,\leq )$ höchstens ${\frac {n}{2}}$.
  • Der (nach dem norwegischen Mathematiker Øystein Ore und Toshio Hiraguchi benannte) Satz von Hiraguchi-Ore, welcher einen alternativen Zugang zum Begriff der Ordnungsdimension bietet: Die Ordnungsdimension einer teilweise geordneten Menge $(X,\leq )$ ist gleich der kleinsten Anzahl von linear geordneten Mengen, in deren direktes Produkt $(X,\leq )$ eingebettet werden kann.
  • Der (nach dem deutschen Mathematiker Egbert Harzheim benannte) Satz von Harzheim: Ist $N$ eine natürliche Zahl und ist für jede endliche Teilmenge $E$ einer gegebenen teilweise geordneten Menge $(X,\leq )$ die Ordnungsdimension $\operatorname {odim} (E,{{E\times E}\;\cap \leq })$ der auf $E$ eingeschränkten Ordnungsrelation höchstens $N$, so ist auch $\operatorname {odim} (X,\leq )$ höchstens $N$.

Literatur

• Ben Dushnik, E. W. Miller: Partially ordered sets. In: American Journal of Mathematics. Band 63, 1941, S. 600–610, doi:10.2307/2371374, JSTOR:2371374 (ams.org). 
• Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen (= Springer-Lehrbuch). Springer Spektrum, Berlin, Heidelberg 2013, ISBN 978-3-642-37499-9, S. 47 ff., doi:10.1007/978-3-642-37500-2. 
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York 2005, ISBN 0-387-24219-8, S. 206 ff. (MR2127991). 
• Wacław Sierpiński: Cardinal and Ordinal Numbers. Panstwowe Wydawnictwo Naukowe, Warschau 1958, S. 188 (MR0095787). 

Antikette

Antikette ist ein mathematischer Begriff aus dem Teilgebiet der Mengenlehre und gehört in das Begriffsfeld der Ordnungsrelation. In der englischsprachigen Literatur entspricht ihm der Begriff antichain, manchmal auch als Sperner family oder Sperner system bezeichnet.

Der Begriff Antikette gehört ebenso wie der Begriff der Kette zum Kernbestand desjenigen Teils der Mathematik, der sich mit Fragestellungen zu Ordnungsrelationen befasst. Hier ist neben der Mengenlehre insbesondere die Kombinatorik der endlichen halbgeordneten Mengen (englisch combinatorial order theory) zu erwähnen. Zu den zentralen Ergebnissen zählen Sätze wie der Satz von Sperner, der Satz von Dilworth, der Heiratssatz und viele weitere.

Klärung des Begriffs

Definition

Eine Teilmenge $A\subseteq P$ einer Halbordnung $(P,\leq )$ heißt Antikette, falls für zwei verschiedene Elemente $a,b\in A$ weder $a\leq b$ noch $b\leq a$ gilt.

Veranschaulichung

Betrachtet man die Ordnungsrelation $\leq$ nur innerhalb der Teilmenge $A$, so findet man dort keine zwei miteinander in Relation stehenden Elemente. Innerhalb der Antikette $A$ ist also die Situation entgegengesetzt der Situation, welche in einer Kette der Halbordnung gegeben ist.

Vom Begriff der Antikette erhält man eine gute Anschauung bei Betrachtung des Hasse-Diagramms der halbgeordneten Menge $(P,\leq )$. Antiketten erkennt man im Hasse-Diagramm als solche Teilmengen, für die keine zwei Elemente durch einen Kantenzug verbunden sind.

Die Schnittmenge einer Antikette mit einer Kette hat stets die Mächtigkeit $\leq 1$, besteht also stets aus höchstens einem Element. So lässt sich der Begriff demnach auch fassen: Eine Teilmenge $A\subseteq P$ einer halbgeordneten Menge $(P,\leq )$ ist genau dann eine Antikette, wenn es keine Kette von $(P,\leq )$ in zwei oder mehr Elementen schneidet.

Beispiele

Die reellen Zahlen

Die reellen Zahlen $\mathbb {R}$ bilden mit der gewöhnlichen strengen Ordnung $\leq$ eine Kette. Die einzigen Antiketten sind die trivialen: Die leere Menge $\varnothing$ und die einelementigen Teilmengen.

Die Primzahlen

Man betrachte die natürlichen Zahlen $\mathbb {N} =\{1,2,3,\ldots \}$ als Trägermenge und als Ordnungsrelation $\leq$ die bekannte Teilerrelation. Für zwei natürliche Zahlen $k$ und $l$ ist also $k\leq l$ gleichbedeutend damit, dass $k$ Teiler von $l$ ist, also dass es eine natürliche Zahl $n$ gibt, sodass $k\cdot n=l$ gilt.

Nach dieser Maßgabe ist in dieser halbgeordneten Menge $(\mathbb {N} ,\leq )$ zum Beispiel die Menge aller Primzahlen eine Antikette.

Die Teiler von 60

Als Trägermenge $P$ wähle man die Menge der Teiler von 60 und als Ordnungsrelation $\leq$ wieder die Teilerrelation. Dann ist $\{4,6,10,15\}$ eine Antikette von $(P,\leq )$.

Mengen von endlichen Mengen derselben Mächtigkeit

Man betrachte eine beliebiges Mengensystem ${\mathcal {X}}$ als Trägermenge. Als Ordnungsrelation $\leq$ wähle man die Inklusionsrelation $\subseteq$.

Für $n\in \mathbb {N}$ setze ${\mathcal {X}}_{n}=\{\,A\in {\mathcal {X}}\;:\;\left|A\right|=n\,\}$, also ist ${\mathcal {X}}_{n}$ das System der $n$-elementigen Teilmengen von ${\mathcal {X}}$. Dann ist jedes ${\mathcal {X}}_{n}$ Antikette von $({\mathcal {X}},\subseteq )$.

Orbits

Die Automorphismengruppe $\operatorname {Aut} (P,\leq )$ der halbgeordneten Menge $(P,\leq )$ operiert als Untergruppe der symmetrischen Gruppe $S_{P}$ in natürlicher Weise auf $P$, indem als Verknüpfung $\phi \cdot x=\phi (x)$ für $x\in P$ und $\phi \in \operatorname {Aut} (P,\leq )$ genommen wird.

Die dadurch gegebenen Orbits $\operatorname {Aut} (P,\leq )\cdot x=\{\,\phi (x)\;:\;\phi \in \operatorname {Aut} (P,\leq )\,\}$ mit $x\in P$ sind im Falle, dass $P$ endlich ist, stets Antiketten von $(P,\leq )$.

Die Spernerzahl

Definition

Die Spernerzahl (englisch Sperner number) der geordneten Menge $(P,\leq )$ ist definiert als das Supremum der Mächtigkeiten aller in $(P,\leq )$ vorkommenden Antiketten. Die Spernerzahl wird heute üblicherweise mit dem Buchstaben $w$ bezeichnet, entsprechend der Gepflogenheit in der englischsprachigen Literatur.

In der deutschsprachigen Literatur wird die Spernerzahl von $(P,\leq )$ (entsprechend dem dafür in der englischsprachigen Literatur auch geläufigen Terminus width) manchmal auch die Breite von $(P,\leq )$ genannt.

Formale Darstellung

$w(P,\leq )=\sup\{\,|A|\;:\;A{\text{ Antikette in }}(P,\leq )\,\}$

Wenn aus dem Kontext klar ist, um welche geordnete Menge $(P,\leq )$ es sich handelt, schreibt man kurz und einfach $w$.

Erläuterung

Die Spernerzahl $w$ ist stets höchstens so groß wie die Mächtigkeit $|P|$ der Trägermenge von $(P,\leq )$. Im Falle, dass $P$ eine endliche Menge ist, ist auch die Spernerzahl endlich und damit eine natürliche Zahl. Dann wird das Supremum angenommen und es gilt:

$w(P,\leq )\ =\max\{\,|A|\;:\;A{\text{ Antikette in }}(P,\leq )\,\}.$

Beispiele

Die reellen Zahlen

$\mathbb {R}$ hat wie jede nichtleere Kette $w=1$.

Die Teiler von 60

Die oben angegebene Antikette $\{\,4,6,10,15\,\}$ (siehe Hasse-Diagramm) ist die größtmögliche. Also gilt hier $w=4$.

Die Potenzmengen

Für die Potenzmenge ${\mathcal {P}}(X)$ einer endlichen Menge $X$ mit $|X|=n$ Elementen gilt stets $w({\mathcal {P}}(X))={\binom {n}{\lfloor {\frac {n}{2}}\rfloor }}$. Denn genau dies besagt der Satz von Sperner.

Für unendliches $X$ der Mächtigkeit $|X|=\aleph _{\alpha }$ gilt $w({{\mathcal {P}}(X)})=2^{\aleph _{\alpha }}$.

Verbandseigenschaften

Erklärung

Das System ${\mathcal {D}}={\mathcal {D}}(P,\leq )$ der Antiketten von $(P,\leq )$ ist stets nichtleer und trägt die folgende Ordnungsrelation, welche die Ordnungsrelation von $(P,\leq )$ in natürlicher Weise auf ${\mathcal {D}}$ fortsetzt:

Für zwei Antiketten $A,B\in {\mathcal {D}}$ ist $A\leq B$ dann und nur dann, wenn zu jedem $b\in B$ ein $a\in A$ existiert mit $a\leq b$.

Die so definierte Ordnungsrelation, welche ebenfalls mit $\leq$ bezeichnet wird, gibt auf diesem Wege dem Antikettensystem ${\mathcal {D}}$ die Struktur eines distributiven Verbands.

Das Resultat von Dilworth

Bei endlichem $(P,\leq )$ liegt nun ein spezielles Augenmerk auf dem Teilsystem ${\mathcal {S}}={\mathcal {S}}(P,\leq )$ der Antiketten maximaler Größe:

${\mathcal {S}}=\{\,A\in {\mathcal {D}}\;:\;|A|=w(P,\leq )\,\}$

Hier gilt nämlich das folgende fundamentale Resultat von Robert Dilworth:

Bei endlichem $(P,\leq )$ ist $({\mathcal {S}},\leq )$ Unterverband von $({\mathcal {D}},\leq )$, wobei die zugehörigen Verbandsoperationen $\land$ und $\lor$ die folgende Darstellung haben:

(1) $A\land B=\operatorname {Min} ({A}\cup {B})$

(2) $A\lor B=\operatorname {Max} ({A}\cup {B})$

($A,B\in {\mathcal {S}}$ )

Dabei wird mit $\operatorname {Min} (X)$ bzw. mit $\operatorname {Max} (X)$ für $X\subseteq P$ die Teilmenge derjenigen Elemente von $X$ bezeichnet, welche bzgl. der induzierten Ordnungsrelation innerhalb $X$ minimal bzw. maximal sind.

Das Resultat von Kleitman, Edelberg, Lubell und Freese und der Satz von Sperner

Als Folgerung ergibt sich:

Eine endliche geordnete Menge $(P,\leq )$ enthält stets eine Antikette maximaler Größe, welche von allen Automorphismen $\phi \in \operatorname {Aut} (P,\leq )$ auf sich selbst abgebildet wird.

Oder anders ausgedrückt:

Eine endliche geordnete Menge $(P,\leq )$ enthält stets eine Antikette maximaler Größe, welche als Vereinigung gewisser Orbits $\operatorname {Aut} (P,\leq )\cdot x$ mit $x\in P$ darstellbar ist.

Hierdurch gelangt man auf direktem Wege zum Satz von Sperner. Denn im Falle, dass $(P,\leq )=(2^{M},\subseteq )$ mit endlicher Grundmenge $M$ ist, sind die Orbits identisch mit den Mächtigkeitsklassen ${M \choose k}$ $(k=0,\dots ,\left|{M}\right|)$.

Anzahl der Antiketten endlicher Potenzmengen

Auf Richard Dedekind geht das Problem zurück, für $n\in \mathbb {N} _{0}$ und $X=\{1,2,\ldots ,n\}$ die Anzahl $M(n)$ aller Antiketten der Potenzmenge ${\mathcal {P}}(X)$ zu bestimmen. Dieses Problem bezeichnet man daher als Dedekind-Problem (englisch Dedekind’s problem) und die Zahlen $M(n)$ als Dedekind-Zahlen (englisch Dedekind numbers).

Die Zahl $M(n)$ ist (im Wesentlichen) identisch mit der Anzahl der monoton wachsenden surjektiven Funktionen von ${\mathcal {P}}(\{1,2,\ldots ,n\})$ nach $2=\{0,1\}$ und genauso identisch mit der Anzahl der freien distributiven Verbände mit $n$ erzeugenden Elementen.

Da diese Zahlen ein erhebliches Wachstum aufweisen, ist die exakte Bestimmung von $M(n)$ bislang allein für $n=0,1,\ldots ,8$ gelungen:

${\begin{aligned}M(0)&=2\\M(1)&=3\\M(2)&=6\\M(3)&=20\\M(4)&=168\\M(5)&=7.581\\M(6)&=7.828.354\\M(7)&=2.414.682.040.998\\M(8)&=56.130.437.228.687.557.907.788\\\end{aligned}}$

Für eine Einschätzung der Größenordnung des Wachstums der $M(n)$ kennt man jedoch untere und obere Schranken, so zum Beispiel die folgenden, welche auf die Arbeit des Mathematikers Georges Hansel aus dem Jahre 1966 zurückgeht:

$2^{\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}\leq M(n)\leq 3^{\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}$

Wie Daniel J. Kleitman und George Markowsky in 1975 zeigten, lässt sich die genannte obere Schranke weiter verschärfen zu:

$M(n)\leq 2^{{\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}\cdot {\bigl (}1+{\mathcal {O}}{({\frac {\ln(n)}{n}})}{\bigr )}}$

und man kennt sogar noch bessere Schranken.

Das Dedekind-Problem ist noch ungelöst. Dem bedeutenden ungarischen Mathematiker Paul Erdős (1913–1996) wird die Bemerkung zugeschrieben, das Problem sei für dieses Jahrhundert zu schwer. Zwar legte der polnische Mathematiker Andrzej P. Kisielewicz im Jahre 1988 eine korrekte Formel vor. Diese gilt jedoch als nutzlos, da mit ihr selbst die Verifikation der schon bekannten Dedekind-Zahlen aus Gründen des Rechenaufwands nicht möglich ist.

Abgrenzung des Begriffs

In der Mengenlehre wird der Begriff der Antikette teilweise auch anders benutzt. Die Antiketteneigenschaft wird in gewissen Zusammenhängen an die Inkompatibilität zweier verschiedener Elemente geknüpft oder bei Booleschen Algebren an Disjunktheitsbedingungen. Über Einzelheiten gibt die Monographie von Thomas Jech Auskunft.

Literatur

Originalarbeiten

• Hans-Joachim Burscheid: Über die Breite des endlichen kardinalen Produktes von endlichen Ketten. In: Mathematische Nachrichten. Band 52, 1971, ISSN 0025-584X, S. 283–295, doi:10.1002/mana.19720520121.
• R. P. Dilworth: Some combinatorial problems on partially ordered sets. In: Richard Bellman, Marshall Hall, Jr. (Hrsg.): Combinatorial Analysis. Proceedings of the Tenth Symposium in Applied Mathematics of the American Mathematical Society, held at Columbia University, april 24–26, 1958 (= Proceedings of Symposia in Applied Mathematics. Band 10). American Mathematical Society, 1960, ISSN 0160-7634, S. 85–90. 
• Ralph Freese: An application of Dilworth's lattice of maximal antichains. In: Discrete Mathematics. Band 7, Nr. 1/2, 1974, ISSN 0012-365X, S. 107–109, doi:10.1016/S0012-365X(74)80022-1.
• Curtis Greene, Daniel J. Kleitman: The structure of Sperner k-Families. In: Journal of Combinatorial Theory. Series A, Band 20, Nr. 1, 1976, ISSN 0097-3165, S. 41–68, doi:10.1016/0097-3165(76)90077-7.
• Curtis Greene, Daniel J. Kleitman: Proof Techniques on the Theory of Finite Sets. In: Gian-Carlo Rota (Hrsg.): Studies in Combinatorics (= Studies in Mathematics. Band 17). Math. Assoc. America, Washington, D.C. 1978, ISBN 0-88385-117-2, S. 23–79 (MR0513002). 
• D. Kleitman, M. Edelberg, D. Lubell: Maximal sized antichains in partial orders. In: Discrete Mathematics. Band 1, Nr. 1, 1971, S. 47–53, doi:10.1016/0012-365X(71)90006-9.
• Hans-Josef Scholz: Über die Kombinatorik der endlichen Potenzmengen im Zusammenhang mit dem Satz von Sperner. Dissertation, Universität Düsseldorf 1987.
• Emanuel Sperner: Ein Satz über Untermengen einer endlichen Menge. In: Mathematische Zeitschrift. Band 27, Nr. 1, 1928, ISSN 0025-5874, S. 544–548, doi:10.1007/BF01171114.
• Georges Hansel: Sur le nombre des fonctions booléennes monotones de n variables. In: C. R. Acad. Sci. Paris Sér. A. Band 262, 1966, S. 1088–1090 (MR0224395). 
• Andrzej Kisielewicz: A solution of Dedekind’s problem on the number of isotone Boolean functions. In: J. Reine Angew. Math. Band 386. Washington, D.C. 1988, S. 139–144, doi:10.1515/crll.1988.386.139 (MR0936995). 
• D. Kleitman, G. Markowsky: On Dedekind’s problem: The number of Isotone Boolean functions. II. In: Trans. Amer. Math. Soc. Band 213, November 1975, S. 373–390, JSTOR:1998052 (MR0382107). 

Monographien

• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1, doi:10.1007/978-3-642-66235-5 (MR0460127). 
• Martin Aigner: Combinatorial Theory (= Grundlehren der Mathematischen Wissenschaften. Band 234). Springer Verlag, Berlin (u. a.) 1979, ISBN 3-540-90376-3 (MR0542445). 
• Martin Aigner: Diskrete Mathematik (= Dokumente zur Geschichte der Mathematik. Band 6). 6. Auflage. Vieweg Verlag, Wiesbaden 2006, ISBN 978-3-8348-0084-8 (MR1085963). 
• Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford 1987, ISBN 0-19-853367-5 (MR0892525). 
• Oliver Deiser: Grundbegriffe der wissenschaftlichen Mathematik. Sprache, Zahlen und erste Erkundungen. Springer Verlag, Heidelberg u. a. 2010, ISBN 978-3-642-11488-5 (Auszug in der Google-Buchsuche). 
• Konrad Engel: Sperner Theory (= Encyclopedia of Mathematics and its Applications. Band 65). Cambridge University Press, Cambridge u. a. 1997, ISBN 0-521-45206-6 (MR1429390). 
• Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen (= Springer-Lehrbuch). Springer Spektrum, Berlin / Heidelberg 2013, ISBN 978-3-642-37499-9. 
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York, NY 2005, ISBN 0-387-24219-8 (MR2127991). 
• Thomas Jech: Set Theory. The Third Millennium edition, revised and expanded (= Springer Monographs in Mathematics). Springer Verlag, Berlin u. a. 2003, ISBN 3-540-44085-2 (MR1940513). 
• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). Springer Verlag, Heidelberg (u. a.) 2011, ISBN 978-3-642-17363-9 (MR2865719). 
• Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way (= Cambridge Mathematical Library). Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4 (MR2483561). 

Weblinks

• Gy. Károlyi: Lectures on extremal set systems and two-colorings of hypergraphs. (PDF; 237 kB)
• Kombinatorische Methoden in der Informatik. (PDF; 1,36 MB; Skript einer Vorlesung von Prof. Dr. Peter Hauck, Uni Tübingen, SS 2008)

Einzelnachweise

rreferences />

KKKategorie:Mengenlehre]] KKKategorie:Ordnungstheorie]] KKKategorie:Diskrete Mathematik]]

Fußnoten

rreferences />

KKKategorie:Ordnungstheorie]]