Direkt zum Inhalt

Lexikon der Mathematik: Diagonalisierung (einer Menge von Objekten)

Methode zum Nachweis der Existenz eines (unendlichen) Objekts x, das nicht in einer vorgegebenen unendlichen Folge y1, y2, … von Objekten vorhanden ist.

Jedes einzelne Objekt yi besteht hierbei aus unendlich vielen Komponenten: \begin{eqnarray}{y}_{i}=({y}_{i,1,}{y}_{i,2},\ldots ).\end{eqnarray}

Die Konstruktion von x = (x1, x2, …) erfolgt so, daß sich die i-te Komponente von x von der i-ten Komponente von yi unterscheidet, also \begin{eqnarray}{x}_{i}\ne {y}_{i,i}\text{f}\ddot{u}\text{r}\ i=1,2,\ldots \text{}\ .\end{eqnarray}

Damit kann x in der Aufzählung der yi nicht vorkommen.

Die Methode der Diagonalisierung geht im Spezialfall auf G. Cantor zurück (Cantorsches Diagonalverfahren) und wird heute in vielen Bereichen der Mathematik und Informatik verwendet, von der Mengenlehre und Logik bis zur Komplexitätstheorie.

Mit dieser Methode zeigt man beispielsweise, daß es überabzählbar viele reelle Zahlen gibt, daß es nicht-berechenbare Funktionen gibt (berechen-bare Funktion), oder daß das Halteproblem nicht entscheidbar ist.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos