Identifizierungen

Ist F : A → B eine Bijektion, so können für jedes Element a der Menge A den Funktionswert F(a) als eine andere „Darstellung“ oder als „neuen Namen“ von a auffassen. In manchen Kontexten sagen wir auch, dass wir a mit F(a) identifizieren. Wir betrachten zwei Beispiele hierzu.

1. Endliche Funktionen als Tupel

Satz (Identifizierung von Funktionen auf endlichen Mengen und Tupeln)

Seien A, B endliche Mengen, und sei A = { a₁, …, a_k } mit |A| = k. Wir definieren G : ^AB → B^k durch

G(f) = (f (a₁), …, f (a_k)) für alle f : A → B.

Dann ist G : ^AB → B^k bijektiv.

Beweis

Sind f, g : A → B verschieden, so gibt es ein i mit f (a_i) ≠ g(a_i). Dann unterscheiden sich die Tupel G(f) und G(g) an der i-ten Stelle, sodass G(f) ≠ G(g). Dies zeigt, dass G injektiv ist. Ist nun (b₁, …, b_k)  ∈  B^k beliebig, so sei f : A → B die Funktion mit

f (a_i) = b_i für alle 1 ≤ i ≤ k.

Dann gilt G(f) = (b₁, …, b_k). Also ist G surjektiv.

Eine Funktion mit einem endlichen Definitionsbereich können wir also in natürlicher Weise mit einem Tupel identifizieren. Diese Identifizierung hängt von der Aufzählung a₁, …, a_k des Definitionsbereichs ab. Ist dieser gleich { 1, …, n }, so ist die Lesart von f : { 1, …, n } → B als Tupel (f (1), …, f (n)) so natürlich, dass sie oft stillschweigend durchgeführt wird. Ein wichtiges Beispiel ist die Tupelnotation für Permutationen f : { 1, …, n } → { 1, …, n }. Das Tripel (1, 3, 2) bezeichnet hier die Transposition π₂₃ auf { 1, 2, 3 }, die die Elemente 2 und 3 vertauscht.

Wir erläutern die Identifizierung noch an einem konkreten Beispiel:

Beispiel

Seien A = { 1, …, 5 } und B = { 1, 2, 3 }. Eine Funktion f : A → B ordnet jeder Zahl a in A eine Zahl f (a) in B zu. Es gilt

G(f) = (f (1), …, f (5)).

Mengentheoretisch ist f eine Menge von geordneten Paaren. Damit gilt etwa

G({ (1, 3), (2, 3), (3, 1), (4, 2), (5, 2) }) = (3, 3, 1, 2, 2).

G({ (1, 1), (2, 1), (3, 1), (4, 1), (5, 1) }) = (1, 1, 1, 1, 1).

2. Teilmengen als 0-1-Funktionen

Eine zweite wichtige Identifizierung betrifft Teilmengen einer Grundmenge und 0-1-wertige Funktionen auf dieser Grundmenge. Diese Identifizierung verwendet eine an vielen Stellen nützliche Begriffsbildung:

Definition (Indikatorfunktion)

Sei A eine beliebige Menge, und sei B ⊆ A. Dann definieren wir die Funktion ind^A_B : A → { 0, 1 } durch

${ind}_{B}^{A} (a) = { \begin{matrix} 1 & falls a \in B, \\ 0 & sonst. \end{matrix}$

Die Funktion ind^A_B : A → { 0, 1 } heißt die Indikatorfunktion oder charakteristische Funktion von B bzgl. der Grundmenge A.

Statt ind^A_B sind in der Analysis und Wahrscheinlichkeitstheorie auch die Bezeichnungen 1^A_B und χ^A_B gebräuchlich. Ist eine Grundmenge A festgelegt, lassen wir den oberen Index zur Vereinfachung der Notation oft weg.

Beispiel

Für die Grundmenge ℕ und die Mengen G, U der geraden bzw. ungeraden Zahlen gilt ind_G(2n) = ind_U(2n + 1) = 1, ind_G(2n + 1) = ind_U(2n) = 0 für alle n. Weiter gilt ind_G + ind_U = ind_ℕ bei punktweiser Addition. Dies entspricht der Tatsache, dass ℕ die disjunkte Vereinigung der Mengen U und G ist.

Der Übergang von einer Teilmenge zu ihrer Indikatorfunktion ist bijektiv. Genauer gilt:

Satz (Identifizierung von Teilmengen mit Indikatorfunktionen)

Sei A eine beliebige Menge. Wir definieren F : ℘(A) → ^A{ 0, 1 } durch

F(B) = ind^A_B für alle B ⊆ A.

Dann ist F : ℘(A) → ^A{ 0, 1 } bijektiv.

Der Beweis sei dem Leser zur Übung überlassen.

Beispiel

Sei A = { 1, …, 5 }. Mit der Identifizierung von Funktionen in ^A{ 0, 1 } mit 0-1-Tupeln gilt:

F({ 1, 3, 5 })	= (1, 0, 1, 0, 1) = 10101 (in Kurzform)
F({ 1, …, 5 })	= (1, 1, 1, 1, 1) = 11111
F({ 2 })	= (0, 1, 0, 0, 0) = 01000
F({ })	= (0, 0, 0, 0, 0) = 00000