Knaster-Kuratowski-Mazurkiewicz-Lemma

Das Knaster-Kuratowski-Mazurkiewicz-Lemma ist im mathematischen Teilgebiet der Fixpunkttheorie, hier insbesondere verbunden mit Algebraischer Topologie und Kombinatorik, ein Resultat über bestimmte Überdeckungen von Simplizes durch abgeschlossene Mengen. Zuerst veröffentlicht und benannt wurde das Knaster-Kuratowski-Mazurkiewicz-Lemma von den polnischen Mathematikern Bronisław Knaster, Kazimierz Kuratowski und Stefan Mazurkiewicz im Jahr 1929. Es ist äquivalent zum Fixpunktsatz von Brouwer aus der Algebraischen Topologie und dem Lemma von Sperner aus der Kombinatorik. Das Knaster-Kuratowski-Mazurkiewicz-Lemma lässt sich aus dem Lusternik-Schnirelmann-Theorem herleiten.^[1]

Für den ${\displaystyle n}$-Standardsimplex ${\displaystyle \Delta ^{n}\subset \mathbb {R} ^{n+1}}$, definiert als konvexe Hülle der Einheitsvektoren ${\displaystyle e_{0},\ldots ,e_{n}\in \mathbb {R} ^{n+1}}$, wird eine Überdeckung durch ${\displaystyle n+1}$ abgeschlossene Teilmengen ${\displaystyle C_{0},\ldots ,C_{n}\subseteq \Delta ^{n}}$, sodass für jede Teilmenge ${\displaystyle I\subseteq \{0,\ldots ,n\}}$ die konvexe Hülle der Einheitsvektoren ${\displaystyle e_{i}\in \mathbb {R} ^{n+1}}$ in ${\displaystyle \bigcup _{i\in I}C_{i}\subseteq \Delta ^{n}}$ liegt, eine Knaster-Kuratowski-Mazurkiewicz-Überdeckung (oder kurz KKM-Überdeckung) genannt.

Das Knaster-Kuratowski-Mazurkiewicz-Lemma besagt, dass der Durchschnitt der Mengen einer Knaster-Kuratowski-Mazurkiewicz-Überdeckung nicht leer ist:

${\displaystyle \bigcap _{i=0}^{n}C_{i}\neq \emptyset .}$

In nebenstehender Skizze ist ${\displaystyle n=2}$ und ${\displaystyle \Delta ^{2}\subset \mathbb {R} ^{3}}$ ist als Dreieck dargestellt. Die drei farblich gekennzeichneten Flächen ${\displaystyle C_{0},C_{1},C_{2}}$ erfüllen offenbar die Voraussetzungen des Knaster-Kuratowski-Mazurkiewicz-Lemmas, das heißt sie bilden eine Knaster-Kuratowski-Mazurkiewicz-Überdeckung. Das Lemma besagt, dass der Durchschnitt ${\displaystyle C_{0}\cap C_{1}\cap C_{2}}$ dieser drei abgeschlossenen Mengen nicht leer ist, was hier offenbar der Fall ist, denn der im Inneren liegende Eckpunkt der drei Flächen gehört diesem Durchschnitt an. Gleichzeitig zeigt dieses Beispiel, dass der Durchschnitt tatsächlich aus nur einem Punkt bestehen kann.

Ausgehend vom schwachen Lemma von Sperner (1928) zeigten KKM das KKM-Lemma im Jahr 1929 und bewiesen zugleich mit Hilfe des Lemmas den Fixpunktsatz von Brouwer. 1974 bewies dann Mark Yoseloff, dass der brouwersche Fixpunktsatz das Lemma von Sperner impliziert.^[2]

Die Punkte ${\displaystyle x}$ des Simplex ${\displaystyle S}$ mit den Ecken ${\displaystyle e_{0},e_{1},\ldots ,e_{n}}$ sind von der Form

${\displaystyle x=c_{0}(x)e_{0}+c_{1}(x)e_{1}+\cdots +c_{n}(x)e_{n},\quad }$

mit stetig von ${\displaystyle x}$ abhängigen ${\displaystyle c_{t}(x)\in [0,1]}$, die ${\displaystyle c_{0}(x)+c_{1}(x)+\cdots +c_{n}(x)=1}$ erfüllen. Eine stetige Funktion ${\displaystyle f\colon S\to S}$ hat die Form

${\displaystyle f(x)=\sum \limits _{t=0}^{n}f_{t}(x)e_{t}}$

mit stetigen Abbildungen mit ${\displaystyle f_{t}\colon S\to [0,1]}$, die ${\displaystyle \textstyle \sum _{t=0}^{n}f_{t}(x)=1}$ erfüllen. Man betrachtet nun die Mengen

${\displaystyle C_{t}:=\{x\in S\mid f_{t}(x)\leq c_{t}(x)\},\quad t=0,1,\dots ,n}$

die wegen der Stetigkeit der ${\displaystyle f_{t}}$ und ${\displaystyle c_{t}}$ abgeschlossen sind. Diese Mengen erfüllen die KKM-Bedingung und deshalb

${\displaystyle \bigcap _{t=0}^{n}C_{t}\neq \emptyset }$

und somit existiert ein Punkt ${\displaystyle x_{0}\in S}$ mit ${\displaystyle f_{t}(x_{0})\leq c_{t}(x_{0})}$ für alle ${\displaystyle t}$.

Da außerdem ${\displaystyle \textstyle \sum _{t=0}^{n}f_{t}(x_{0})=\sum _{t=0}^{n}c_{t}(x_{0})=1}$ gilt, folgt daraus ${\displaystyle f_{t}(x_{0})=c_{t}(x_{0})}$ für alle ${\displaystyle t=0,1,\dots ,n}$ und daher

${\displaystyle f(x_{0})=\sum \limits _{t=0}^{n}f_{t}(x_{0})e_{t}=\sum \limits _{t=0}^{n}c_{t}(x_{0})e_{t}=x_{0}}$,

das heißt ${\displaystyle x_{0}}$ ist ein Fixpunkt.^[3]

1. ↑ Bronisław Knaster, Kazimierz Kuratowski und Stefan Mazurkiewicz: Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe. In: Fundamenta Mathematicae. Band 14, Nr. 1, 1929, S. 132–137, doi:10.4064/fm-14-1-132-137 (eudml.org). 
2. ↑ Mark Yoseloff: Topologic proofs of some combinatorial theorems. In: Journal of Combinatorial Theory, Series A. Band 17, Nr. 1, 1974, ISSN 0097-3165, S. 95–111, doi:10.1016/0097-3165(74)90031-4. 
3. ↑ Bronisław Knaster, Kazimierz Kuratowski und Stefan Mazurkiewicz: Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe. In: Fundamenta Mathematicae. Band 14, Nr. 1, 1929, S. 135–136, doi:10.4064/fm-14-1-132-137 (eudml.org).