Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen

Mengen, Teilmengen, Mengenoperationen, kartesisches Produkt, Relationen, Äquivalenz und Ordnungen — mit Venn-Diagrammen, einer Relationsmatrix und dem, wozu das alles in der künstlichen Intelligenz gut ist.

13 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 5 von 52

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Was du mitnimmst

Was eine Menge, eine Teilmenge und das kartesische Produkt sind — und warum die Zahl der Teilmengen exponentiell wächst.
Was eine Relation ist, welche Eigenschaften sie hat und wie man sie als Matrix und als Graph zeichnet.
Warum Klassifikation eine Zerlegung in Äquivalenzklassen ist und ein Modell eine Funktion — eine besondere Relation.

Vorher gut zu wissen: Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren

Mengen und Relationen sind der Baukasten, aus dem fast jede Definition in der KI besteht. Ein Zustandsraum ist eine Menge von Zuständen, die Übergänge zwischen ihnen sind Relationen, Trainingsdaten sind eine Menge von Paaren, und die Klassifikation teilt Eingaben in Klassen ein. Wer diese beiden Begriffe versteht, liest die Definitionen in den weiteren Teilen wie normalen Text.

Wie man die Symbole (∈, ⊆, ∪, ×) schreibt, haben wir im vorigen Teil besprochen. Hier gehen wir unter die Oberfläche: was sie genau bedeuten, welche Eigenschaften sie haben und wozu sie in der künstlichen Intelligenz gut sind.

1. Was eine Menge ist

Definition — Menge und Element

Eine Menge ist eine Zusammenfassung voneinander verschiedener Objekte. Diese Objekte nennen wir die Elemente der Menge.

Die Schreibweise x ∈ A bedeutet „x ist ein Element der Menge A“, die Schreibweise x ∉ A „x ist kein Element von A“.

Einfach gesagt

Eine Menge ist ein Sack, in den du etwas hineinlegst. Uns interessiert nur, was im Sack ist — nicht, in welcher Reihenfolge du es hineingelegt hast, und auch nicht, wie oft. Zwei Murmeln derselben Farbe sind für die Menge eine Farbe.

Eine Menge schreiben wir entweder durch Aufzählung ihrer Elemente in geschweiften Klammern — A = {1, 2, 3} oder {↑, →, ↓, ←} — oder durch eine Eigenschaft, die die Elemente erfüllen: {x ∈ ℕ : x ist gerade}. Für A = {1, 2, 3} gilt 2 ∈ A und 5 ∉ A. Die Schreibweise über eine Eigenschaft kann auch unendliche Mengen beschreiben und wird in der KI fast immer verwendet: „die Menge aller Zustände, von denen aus man das Ziel erreichen kann“.

Definition — Gleichheit von Mengen

Die Mengen A und B sind gleich, A = B, wenn sie genau dieselben Elemente haben: ∀x : (x ∈ A ⇔ x ∈ B).

Einfach gesagt

Zwei Säcke sind gleich, wenn in ihnen dasselbe ist. Deshalb gilt {1, 2, 2} = {2, 1} = {1, 2}: Weder Reihenfolge noch Wiederholung spielen eine Rolle.

Definition — Mächtigkeit und leere Menge

Die Mächtigkeit (Kardinalität) |A| einer endlichen Menge A ist die Anzahl ihrer Elemente.

Die leere Menge ∅ ist die Menge, die kein Element hat; |∅| = 0.

Einfach gesagt

Die Mächtigkeit ist die Antwort auf die Frage „Wie viel ist im Sack?“: |{1, 2, 3}| = 3. Die leere Menge ist ein leerer Sack — sie ist immer noch eine Menge, es ist nur nichts darin.

2. Teilmengen und Potenzmenge

Aus einer Menge können wir kleinere auswählen. Dafür brauchen wir drei Begriffe, die aufeinander aufbauen: Teilmenge, echte Teilmenge und Potenzmenge.

Definition — Teilmenge

Die Menge A ist eine Teilmenge der Menge B, geschrieben A ⊆ B, wenn jedes Element von A auch ein Element von B ist: ∀x : x ∈ A ⇒ x ∈ B.

Einfach gesagt

Eine Teilmenge ist eine Auswahl aus dem Sack: Du nimmst einige Dinge aus B und legst sie in einen kleineren Sack A. Nichts, was nicht in B ist, darfst du zu A hinzufügen. So gilt {1, 3} ⊆ {1, 2, 3}, aber {1, 4} ⊄ {1, 2, 3}, weil 4 in der ursprünglichen Menge nicht vorkommt. Jede Menge ist Teilmenge von sich selbst, und die leere Menge ist Teilmenge jeder Menge.

Definition — echte Teilmenge

A ist eine echte Teilmenge von B, geschrieben A ⊂ B, wenn A ⊆ B und zugleich A ≠ B.

Einfach gesagt

Eine echte Teilmenge ist eine Auswahl, in der mindestens etwas fehlt. {1, 3} ⊂ {1, 2, 3}, aber {1, 2, 3} ist keine echte Teilmenge von sich selbst — du hast wirklich alles genommen.

Definition — Potenzmenge

Die Potenzmenge 𝒫(A) ist die Menge, deren Elemente alle Teilmengen von A sind: 𝒫(A) = {S : S ⊆ A}.

Satz. Für eine endliche Menge A gilt |𝒫(A)| = 2^|A|.

Einfach gesagt

Die Potenzmenge ist die Liste aller Auswahlen, die man aus dem Sack treffen kann — einschließlich der leeren Auswahl und der Auswahl von allem. Warum es 2ⁿ davon gibt: Bei jedem Element entscheidest du, ob du es in die Auswahl legst oder nicht. Das sind zwei Möglichkeiten für jedes Element, bei drei Elementen 2 · 2 · 2 = 8, bei zehn Elementen schon 1024.

Für A = {a, b, c} ist 𝒫(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} — insgesamt 8 Teilmengen. Diesem exponentiellen Wachstum begegnest du in der KI auf Schritt und Tritt. Ein Modell, das auswählen soll, welche von 50 Merkmalen es verwendet, hat 2⁵⁰ Möglichkeiten — über eine Billiarde. Deshalb wird die Merkmalsauswahl nicht durch Ausprobieren aller Kombinationen gemacht.

3. Mengenoperationen

Definition — Vereinigung, Schnitt, Differenz, Komplement

A ∪ B = {x : x ∈ A ∨ x ∈ B} — Vereinigung,

A ∩ B = {x : x ∈ A ∧ x ∈ B} — Schnitt (Schnittmenge),

A ∖ B = {x : x ∈ A ∧ x ∉ B} — Differenz,

A^c = U ∖ A — Komplement bezüglich der Grundmenge U (des „Universums“).

De Morgansche Gesetze: (A ∪ B)^c = A^c ∩ B^c und (A ∩ B)^c = A^c ∪ B^c.

Einfach gesagt

Die Vereinigung ist „entweder, oder, oder beides“, der Schnitt „beides zugleich“, die Differenz „das hier, aber nicht das da“ und das Komplement „alles andere“. Das De Morgansche Gesetz sagt, dass „es stimmt nicht, dass es regnet oder schneit“ dasselbe ist wie „es regnet nicht und es schneit nicht“.

A ∪ B — Vereinigung

A ∩ B — Schnitt

A ∖ B — Differenz

A^c — Komplement

In der KI-Praxis rechnet man mit Schnittmengen zum Beispiel bei der Bewertung eines Modells. Wenn P die Menge der E-Mails ist, die das Modell als Spam markiert hat, und S die Menge der E-Mails, die wirklich Spam sind, dann ist die Präzision (precision) |P ∩ S| / |P| — wie viele der markierten wirklich Spam waren — und die Trefferquote (recall) |P ∩ S| / |S| — wie viel Spam das Modell erwischt hat.

4. Kartesisches Produkt und n-Tupel

Definition — geordnetes Paar und kartesisches Produkt

Ein geordnetes Paar (a, b) unterscheidet sich von der Menge {a, b} dadurch, dass die Reihenfolge zählt: (a, b) = (c, d) ⇔ a = c ∧ b = d.

Das kartesische Produkt A × B = {(a, b) : a ∈ A, b ∈ B}. Für endliche Mengen gilt |A × B| = |A| · |B|.

Allgemein ist A₁ × … × A_n die Menge der n-Tupel; Aⁿ = A × … × A (n-mal).

Einfach gesagt

Das kartesische Produkt ist eine Tabelle aller Kombinationen. Drei T-Shirts und zwei Hosen ergeben 3 · 2 = 6 Outfits. Die Koordinaten eines Punktes in der Ebene sind Paare aus ℝ × ℝ = ℝ².

Das kartesische Produkt steckt in der KI überall. Trainingsdaten beim überwachten Lernen sind eine Teilmenge von X × Y — Paare (Eingabe, richtige Antwort). Ein Foto mit 28 × 28 Pixeln ist ein Punkt in ℝ⁷⁸⁴. Und bei einem Suchproblem ist die Übergangsfunktion auf S × A definiert — auf Paaren (Zustand, Aktion).

5. Relationen

Definition — Relation

Eine binäre Relation zwischen den Mengen A und B ist eine beliebige Teilmenge R ⊆ A × B. Statt (a, b) ∈ R schreibt man a R b und liest „a steht in Relation zu b“.

Ist A = B, sprechen wir von einer Relation auf der Menge A.

Einfach gesagt

Eine Relation ist eine Liste von Paaren, die „zusammengehören“. Wer wessen Elternteil ist, welche Stadt eine direkte Verbindung zu welcher hat, welcher Zustand zu welchem führt. Nicht mehr — nur eine Liste von Paaren.

Eine Relation auf einer kleinen Menge können wir auf zwei Arten zeichnen. Nehmen wir die Relation „a teilt b“ (b ist ein Vielfaches von a) auf der Menge {1, …, 6}. Als Matrix: In Zeile a und Spalte b steht ein Punkt, wenn a b teilt. Und als gerichteter Graph: ein Pfeil von a nach b.

Matrix: Zeile a, Spalte b

Graph: Pfeil a → b (ohne Schleifen a → a)

Die Relation „a teilt b“ auf der Menge {1, …, 6} Paare in der Relation: 14

Die Relation hat 14 Paare. In der KI begegnest du beiden Formen: Die Relationsmatrix ist das, womit der Computer rechnet (Adjazenzmatrix eines Graphen, Ähnlichkeitsmatrix), der Graph ist das, was ein Mensch zeichnet. Die Übergänge zwischen Zuständen bei der Suche sind eine Relation auf der Menge der Zustände, und der Graph der k nächsten Nachbarn aus der Label-Propagation ist die Relation „ist unter den nächsten“.

6. Eigenschaften von Relationen

Definition — Eigenschaften einer Relation auf einer Menge

Eine Relation R auf der Menge A ist

reflexiv, wenn ∀a ∈ A : a R a,
symmetrisch, wenn ∀a, b : a R b ⇒ b R a,
antisymmetrisch, wenn ∀a, b : (a R b ∧ b R a) ⇒ a = b,
transitiv, wenn ∀a, b, c : (a R b ∧ b R c) ⇒ a R c.

Einfach gesagt

Reflexiv: Jedes Element steht in Relation zu sich selbst. Symmetrisch: Es funktioniert in beide Richtungen. Antisymmetrisch: in beide Richtungen nur dann, wenn es um dasselbe geht. Transitiv: Wenn ein Weg von a nach b und von b nach c führt, führt auch ein direkter von a nach c.

Für Relationen auf der Menge {1, …, 6} sieht das so aus — und an der Kombination der Eigenschaften erkennst du, um welche Art von Relation es sich handelt:

Relation	Reflexiv	Symmetrisch	Antisymmetrisch	Transitiv
`a` ≤ `b`	ja	nein	ja	ja
`a` teilt `b`	ja	nein	ja	ja
gleicher Rest bei Division durch 3	ja	ja	nein	ja
\|`a` − `b`\| = 1 („Nachbarn“)	nein	ja	nein	nein

7. Äquivalenz und Zerlegung in Klassen

Definition — Äquivalenz und Zerlegung

Eine Relation, die reflexiv, symmetrisch und transitiv ist, ist eine Äquivalenzrelation. Die Äquivalenzklasse eines Elements a ist [a] = {x ∈ A : x R a}.

Eine Zerlegung (Partition) der Menge A ist eine Sammlung nichtleerer, paarweise disjunkter Teilmengen, deren Vereinigung A ist.

Satz. Die Klassen jeder Äquivalenzrelation bilden eine Zerlegung von A — und umgekehrt bestimmt jede Zerlegung die Äquivalenz „gehört zum selben Teil“.

Einfach gesagt

Eine Äquivalenz ist „ist in irgendeiner Hinsicht gleich wie“ — gleiche Farbe, gleicher Rest, gleiche Klasse. Eine solche Relation teilt die Menge immer in Fächer auf, die sich nicht überlappen und zusammen alles abdecken. Jedes Element liegt in genau einem Fach.

Klasse [0] {0, 3, 6}

Klasse [1] {1, 4, 7}

Klasse [2] {2, 5, 8}

Zerlegung von {0, …, 8} nach dem Rest bei Division durch 3

Genau das macht die Klassifikation: Sie teilt die Menge aller möglichen Eingaben in Klassen auf — Spam und kein Spam, Hund, Katze und Papagei. Und das Clustering sucht eine Zerlegung der Daten, ohne dass ihm jemand sagt, welche Klassen es gibt. Das Ergebnis von k-means aus dem Teil über Arten des Lernens ist eine Zerlegung der Punkte in drei Klassen.

8. Ordnungen

Definition — Halbordnung und Totalordnung

Eine Relation, die reflexiv, antisymmetrisch und transitiv ist, ist eine Halbordnung (partielle Ordnung).

Ist zusätzlich jedes Paar von Elementen vergleichbar (∀a, b : a R b ∨ b R a), handelt es sich um eine Totalordnung (lineare Ordnung).

Einfach gesagt

Eine Ordnung sagt, was „vor“ was kommt. Bei Zahlen nach Größe kann man alles mit allem vergleichen. Bei einer Halbordnung nicht immer: 4 und 6 teilen sich gegenseitig nicht, also wissen wir nach der Teilbarkeit nicht, welche „kleiner“ ist.

Eine Halbordnung zeichnet man als Hasse-Diagramm: kleinere Elemente unten, größere oben und eine Linie nur zwischen unmittelbaren Nachbarn — der Rest ergibt sich aus der Transitivität. Hier die Teiler von 12, geordnet nach Teilbarkeit:

Teiler von 12, geordnet nach Teilbarkeit

Am Diagramm siehst du, dass 1 alles teilt und 12 durch alles teilbar ist — aber 4 und 6 oder 2 und 3 lassen sich nicht vergleichen. In der KI tauchen Ordnungen überall dort auf, wo etwas sortiert oder geplant wird: die Reihenfolge von Suchergebnissen, Prioritäten im Rand (frontier) des A*-Algorithmus oder Abhängigkeiten zwischen Schritten eines Plans („zuerst die Tür öffnen, dann hindurchgehen“). Der Graph der Voraussetzungen der Module im Lehrplan dieser Reihe ist übrigens ebenfalls eine Halbordnung.

9. Funktionen als besondere Relationen

Definition — Funktion

Eine Funktion von A nach B ist eine Relation f ⊆ A × B, in der jedes Element a ∈ A genau ein Element b ∈ B mit (a, b) ∈ f hat. Dieses wird mit f(a) bezeichnet.

Einfach gesagt

Eine Funktion ist eine Relation, die jede Frage mit genau einer Antwort beantwortet. „Ist Elternteil von“ ist keine Funktion — ein Mensch kann mehrere Kinder haben. „Hat als Mutter“ ist eine Funktion — jeder hat genau eine.

Damit schließt sich der Kreis: Ein Modell im maschinellen Lernen ist eine Funktion f : X → Y, also eine besondere Relation zwischen Eingaben und Ausgaben. Funktionen und ihren Eigenschaften widmet sich der nächste Teil des Lehrplans.

10. Zusammenfassung

Eine Menge ist eine Zusammenfassung von Elementen ohne Reihenfolge und ohne Wiederholung; eine n-elementige Menge hat 2ⁿ Teilmengen.
Vereinigung, Schnitt, Differenz und Komplement sind „oder“, „und“, „aber nicht“ und „alles andere“; auf Schnittmengen beruhen Präzision und Trefferquote eines Modells.
Das kartesische Produkt bildet Paare — aus ihnen bestehen Daten (Eingabe, Antwort) und Übergänge (Zustand, Aktion).
Eine Relation ist eine Menge von Paaren. Eine Äquivalenz zerlegt eine Menge in Klassen (Klassifikation, Clustering), eine Ordnung bestimmt, was vor was kommt.
Eine Funktion ist eine Relation mit genau einer Antwort — und ein Modell ist eine Funktion.

Siehst du das anders? Schreib an support@coden-app.com.

Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen

1. Was eine Menge ist

2. Teilmengen und Potenzmenge

3. Mengenoperationen

4. Kartesisches Produkt und n-Tupel

5. Relationen

6. Eigenschaften von Relationen

7. Äquivalenz und Zerlegung in Klassen

8. Ordnungen

9. Funktionen als besondere Relationen

10. Zusammenfassung

Ein Agent auf deinem Rechner, vom Telefon aus gesteuert