Ein Ausdruck oder eine Liste kann mehrere Komponenten haben. Zum Beispiel kann ein Ausdruck sowohl rationale als auch emotionale Komponenten haben: Peter mag Uta weil sie schön und reich ist.
Eine Liste besteht aus Komponenten. Zum Beispiel enthält die Liste [ a, b, c, d ] vier Komponenten, nämlich a, b, c und d.
Eine Menge ist eine Gesamtheit von Elementen. In der Mengenlehre werden Paare von Mengen auf folgende Weise gebildet. Zwei Mengen x und y werden mit Mengenklammern umgeben: { x } und { y }. { x } und { y } sind ebenfalls Mengen, sie enthalten jeweils nur ein einziges Element. Diese ein-elementigen Mengen werden nun noch einmal mit Mengenklammern in der folgenden Weise umgeben:
{ x, { y } }.
Dieser Ausdruck enthält neben Mengenklammern und Symbolen für Mengen zusätzlich das Komma «,», welches eine zentrale Funktion hat.
Das Komma trennt die zwei Mengen x und { y }, welche als Elemente in der Gesamtmenge { x, { y } } vorhanden sind.
Dieses Gebilde { x, { y } } wird in der Mengenlehre als
das Paar der Mengen x und y bezeichnet
und es wird so abgekürzt: 〈 x, y 〉 oder [ x, y ].
Diese Konstruktion lässt sich beliebig oft wiederholen.
a) Bilden Sie aus drei Mengen x, y, z erst das Paar 〈 x, y 〉 und dann das Paar 〈 〈 x, y 〉, 〈 z 〉 〉.
Auf diese Weise werden Listen konstruktiv erzeugt. Dieses Verfahren wird auch in der Programmierung von Computern als Standard verwendet.
Für Menschen ist es zweckmäßig, so viele Klammern wie möglich zu entfernen. Der Sinn muss dabei aber noch eindeutig erhalten bleiben.
Aus n Mengen x1, …, xn wird induktiv («vom Speziellen auf das Allgemeine schließend») eine Liste 〈 x1, …, xn 〉 durch folgende Regeln erzeugt:
| 〈 x1 〉 ist eine Liste. | (R1) |
| Wenn 〈 x1, …, xm 〉 eine Liste von x1, …, xm Mengen ist und m < n ist, dann ist auch 〈 x1, …, xm, xm+1 〉 eine Liste von x1, …, xm+1 Mengen. | (R2) |
b) Vervollständigen Sie diese induktive Definition, in dem Sie eingesparte Klammern an den richtigen Stellen einfügen.
Spitze Klammern «〈 〉» werden meist in logischen und mengentheoretischen Texten verwendet: 〈 x1, …, xn 〉, während in der Informatik und in vielen mathematischen Texten die «normale» Listenschreibweise verwendet wird: [ x1, …, xn ].
Wenn aus dem Kontext ersichtlich ist, dass eine Menge x die Form einer Liste hat, d.h. x = 〈 x1, …, xn 〉, wird oft gesagt, dass x – also eine Menge – «Komponenten hat» oder «n Komponenten hat» oder «xi eine Komponente von x ist» oder «xi die i-te Komponente von x ist».
Der Zwischenschritt, in dem die Menge zunächst mit einer Liste gleichgesetzt wird, fehlt in solchen Formulierungen, weil die Leser diese Identität sofort erkennen.
Zwei Listen 〈 x1, …, xm 〉 und 〈 y1, …, yn 〉 lassen sich zusammenfügen (konkatenieren):
〈 x1, …, xm 〉 
〈 y1, …, yn 〉 = 〈 x1, …, xm, y1, …, yn 〉
Die Beziehung des Zusammenfügens werden wir in weiteren Übungen noch genauer kennenlernen.
c) Definieren Sie die Konkatenation von zwei Listen. Hilfestellung: Beginnen Sie induktiv mit 〈 y1 〉 und fügen Sie y1 zur Liste 〈 x1, …, xm 〉 hinzu.