Additive Ersetzungen
Mit Hilfe der Kardinalitätsfunktion können wir nun additive Ersetzungen definieren. Wir fassen diese Ersetzungen auch als Summen auf und führen deswegen zwei parallel verwendete Notationen ein.
Definition (additive Ersetzung, Summen, F″x, Σa ∈ x F(a : c(a, x)), xFb)
Sei F : V : Kard → V : Kard eine Sprachfunktion, und sei x ein Aggregat.
Ein Aggregat y heißt die F-Summe über x, oder die additive F-Ersetzung von x, in Zeichen
y = F″x oder y = Σa ∈ x F(a : c(a, x)),
falls gilt:
y = { b : c(xFb) | es gibt ein a ∈ x mit F(a, c(a, x))(0) = b }, wobei für alle b:
xFb = { a : F(a, c(a, x))(1) | a ∈ x, F(a, c(a, x))(0) = b }.
Die Idee ist: Gilt a ∈ κ x, und ist F(a : κ) = b : μ, so ersetzen wir die κ-vielen a in x additiv durch μ-viele b. Additiv heißt, dass jede Konstellation
F(a, c(a, x)) = b : μ(a), a ∈ x
μ(a)-viele b zu y = Σa ∈ x F(a : c(a, x)) beiträgt.
Satz (Existenz der additiven Ersetzung)
Sei F : V : Kard → V : Kard eine Sprachfunktion, und sei x ein Aggregat.
Dann existiert y = Σa ∈ x F(a : c(a, x)).
Beweis
Ist a ∈ x, so schreiben wir kurz b(a) für F(a, c(a, x))(0).
Sei nun G : V : Kard → V : Kard eine Sprachfunktion mit
G(a, c(a, x)) = b(a) : c(xFb(a)) für alle a ∈ x.
(xFb existiert nach dem Satz über das Einstellen der Häufigkeiten auf x.)
Dann ist y = G″supx wie gewünscht.
Für V-injektive Ersetzungen gilt:
Satz
Ist F : V : Kard → V : Kard V-injektiv, so gilt für alle x:
F″x = F″supx = { F(a, c(a, x)) | a ∈ x }.
Weiter notieren wir:
Satz
Ist F : V → V : Kard, so gilt für alle x, y mit set(x) = set(y), dass F″x = F″y.
Nach Definition laufen Summen immer über Ausdrücke der Form a : κ. Wir vereinbaren aber:
Konvention
Wird über Aggregate der Form x = { a : κ } summiert,
so lesen wir x als „a : κ“.
Wegen κ = { 0 : κ } können wir speziell Kardinalzahlen κ in einem funktionalen Kontext als Ausdrücke 0 : κ lesen. Damit gilt etwa:
Σa ∈ x κa = Σa ∈ x 0 : κa.
Formal verläuft die Definition von Σa ∈ x κa wie folgt. Die κa stehen wie üblich für eine Funktion G : V → Kard, d. h. κa ist eine andere Schreibweise für G(a). Es sei dann F : V : Kard → V : Kard die Funktion mit F(a : κ) = 0 : G(a) für alle a, κ. Dann setzen wir:
Σa ∈ x κa = Σa ∈ x F(a : c(a, x)).
De facto hängt diese Summe nicht von den Werten c(a, x) ab, und damit gilt für alle y mit set(y) = set(x), dass Σa ∈ x κa = Σa ∈ y κa.
Ist schließlich x eine Menge von Kardinalzahlen, so sei
Σ x = Σκ ∈ x κ.
Summen über allgemeine Aggregate definieren wir erst später. Summen über Mengen von Kardinalzahlen entsprechen dem Vorgang „ersetze für alle κ ∈ x das eindeutige κ in x durch 0 : κ“. Die allgemeine Form „ersetze für alle κ ∈ x jedes κ in x durch 0 : κ“ ist naturgemäß wesentlich komplexer; wir brauchen hierzu Multiplikationen.
Weiter definieren wir für Kardinalzahlen κ0, …, κν :
κ0 + … + κν = Σi ∈ { 0, …, ν } κi .
Damit ist z. B. κ + μ das Ergebnis der folgenden additiven Ersetzung: Ersetze im Aggregat { 0, 1 } additiv 0 durch κ-viele Nullen und 1 durch μ-viele Nullen. Nach Definition der hinter κ + μ stehenden Summe gilt κ + μ = c({ 0 : κ, 1 : μ }). Es ist an dieser Stelle nicht klar, dass κ + μ = μ + κ gilt.
Eigenschaften der additiven Ersetzung
Wir stellen einige Regeln zusammen.
Satz (Eigenschaften der Summenbildung)
Universell gilt:
(i) | x = Σa ∈ x a : c(a, x). |
(ii) | c(x) = Σa ∈ x c(a, x) (= Σa ∈ x 0 : c(a, x)). |
(iii) | Σa ∈ x b : κa = { b : Σa ∈ x κa }, und mit obiger Konvention dann also Σb ∈ y b : (Σa ∈ x κa) = Σb ∈ y Σa ∈ x b : κa. |
Beweis
zu (i):
Sei F(x : κ) = x : κ für alle x, κ. Dann ist F V-injektiv, und für alle x gilt
Σa ∈ x a : c(a, x) = Σa ∈ x F(a : c(a, x)) = { a : c(a, x) | a = a } = x.
zu (ii):
Die Summe Σa ∈ x 0 : c(a, x) ist gegeben durch die Funktion F mit F(a : κ) = 0 : κ für alle a, κ. Dann gilt nach Definition der Summe:
Σa ∈ x c(a, x) = { 0 : c(xF0) } = c(xF0) mit
xF0 = { a : F(a, c(a, x))(1) | a ∈ x, F(a, c(a, x))(0) = 0 } = { a : c(a, x) | a ∈ x } = x.
Dies zeigt die Behauptung.
zu (iii):
Nach Definition der Summe gilt (mit einer Funktion F mit F(a : c(a, x)) = b : κa für alle a ∈ x):
Σa ∈ x b : κa = { b : c(xFb) } mit xFb = { a : κa | a ∈ x }.
Nach (ii) ist aber c(xFb) = Σa ∈ x κa, was die Behauptung zeigt.
Wir notieren diese Ergebnisse noch in der F″x-Schreibweise. Hierzu führen wir spezielle Funktionen ein:
Definition (Id, N)
Wir definieren Id, N : V : Kard → V : Kard durch:
| Id(a : κ) | = a : κ, |
| N(a : κ) | = 0 : κ für alle a, κ. |
Nach den obigen Konventionen können wir Id, N auch als Funktionen von V nach V auffassen mit Id(a) = a und N(a) = 0.
Damit lesen sich die Aussagen (i), (ii) und (iii) des Satzes dann als:
| (i) | x | = Id″x, |
| (ii) | c(x) | = N″x, |
| (iii) | F″x | = { b : G″x }, falls F(a : κ) = b : κa, G(a : κ) = 0 : κa für alle a, κ. |
Ob die Bild- oder die Summenschreibweise besser lesbar ist, ist von Fall zu Fall unterschiedlich. Die Aussage (iii) etwa ist in der Summenschreibweise sicher suggestiver, während die Gleichung c(x) = N″x die Cantorsche Kardinalzahldefinition knapper zum Ausdruck bringt.
Wir führen noch eine nützliche Variante der Summennotation ein.
Definition (Formeln im Index einer Summe)
Sei φ(x) eine Formel. Dann schreiben wir
Σa ∈ x, φ(x) F(a, c(a, x)) für die Summe Σa ∈ xφ F(a, c(a, xφ)) (= F″xφ),
mit xφ = { a : c(a, x) | a ∈ x, φ(x) }.
Sei y = F″x = Σa ∈ x F(a : c(a, x)) für eine Funktion F : V : Kard → V : Kard und ein Aggregat x. Wir versuchen, c(y) zu bestimmen. Nach (i) des Satzes und Definition der Summe gilt:
c(y) = Σb ∈ y c(b, y) = Σb ∈ y c(xFb).
Weiter ist nach (i) und Definition von xFb:
c(xFb) = Σa ∈ x, F(a : c(a, x))(0) = b F(a : c(a, x))(1).
Also insgesamt:
(A) c(y) = Σb ∈ y Σa ∈ x, F(a : c(a, x)(0) = b F(a : c(a, x))(1).
Intuitiv durchläuft die Doppelsumme einfach alle a ∈ x, und damit sollte gelten:
(B) c(y) = Σa ∈ x F(a : c(a, x))(1).
Wir können die Aussage (B) nicht zeigen. Wir brauchen zusätzliche Axiome für die c-Funktion. Hierzu ist es suggestiv, die Überlegungen in der Bildschreibweise zu notieren. Hier lauten die beweisbare Aussage (A) und die erwünschte Aussage (B):
| (A) c(y) | = N″ F″x, |
| (B) c(y) | = (N ∘ F)″x. |
[ zu (A): y = F″x, also nach (i) c(y) = N″ F″x = Σb ∈ y N(b : c(b, y)) = Σb ∈ y c(b, y)).
zu (B): für alle a ∈ x gilt (N ∘ F)(a : c(a, x)) = 0 : F(a : c(a, x))(1), also
(N ∘ F)″x = Σa ∈ x F(a : c(a, x))(1). ]
Wir formulieren als Axiom:
(Kom) Kommutativitätsschema
Für alle Sprachfunktionen F : V : Kard → V : Kard gilt:
∀x. (N ∘ F)″x = N″ F″x.
In der Summenschreibweise haben wir also:
Summenregel für Funktionen F : V : Kard → V : Kard
Σa ∈ x F(a : c(a, x))(1) = Σb ∈ F″x Σa ∈ xFb F(a : c(a, x))(1).
Wir halten einige Folgerungen des Axioms fest. Ist F anzahltreu, d. h. von der Form F : V : Kard → V, so gilt:
Satz (Streichungsregel für anzahltreue Funktionen)
Sei F : V : Kard → V, und sei y = F″x für ein Aggregat x. Dann gilt:
c(x) = c(y).
Mit anderen Worten: N″ = N″ F″.
Beweis
Es gilt:
c(x) = Σa ∈ x c(a, x) = Σb ∈ y Σa ∈ xFb c(a, x) = Σb ∈ y c(xFb) = Σb ∈ y c(b, y) = c(y).
Das Kommutativitätsaxiom wird hier am zweiten Gleichheitszeichen verwendet, die Anzahltreue von F am dritten.
Allgemeiner haben wir:
Satz
Seien F, G : V : Kard → V : Kard Sprachfunktionen mit F(a : κ)(1) = G(a : κ)(1) für alle a, κ. Dann gilt c(F″x) = c(G″x) für alle x.
Mit anderen Worten: N″ F″ = N″ G″.
Beweis
c(F″x) = N″ F″x =(Kom) (N ∘ F)″x = Σa ∈ x F(a, c(a, x))(1) =Voraussetzung
Σa ∈ x G(a, c(a, x))(1) =analog c(G″x).
Der Spezialfall „F anzahltreu und G = Id“ liefert obige Streichungsregel.
Korollar (zweite Streichungsregel)
Sei F : V : Kard → V : Kard, und sei G : V : Kard → V.
Dann gilt:
N″ G″ F ″ = N″ F″ = (N ∘ F)″ = (N ∘ G ∘ F)″.
Beweis
Die erste Gleichung folgt aus der Streichungsregel oben.
Die zweite Gleichung ist eine Anwendung von (Kom).
Weiter erfüllen die Funktionen F und G′ = G ∘ F die Voraussetzung des obigen Satzes, und damit gilt N″ F″ = N″ (G ∘ F)″.
Nach (Kom) ist aber wieder N″ (G ∘ F)″ = (N ∘ G ∘ F)″.
Dagegen ist (G ∘ F)″x = G″ F″x im Allgemeinen nicht einmal für anzahltreue G und F = N richtig. Sei nämlich G die Sprachfunktion mit G(0 : 1) = 1 : 1 und G(a : κ) = a : κ sonst. Sei x = { ν : 1 | ν < ℵ0 }. Wir werden später (mit Hilfe zusätzlicher Axiome) zeigen, dass, wie es sein soll, c(x) = ℵ0 gilt. Damit haben wir dann:
N″x = c(x) = ℵ0 = { 0 : ℵ0 }, also G″ N″x = ℵ0, während
(G ∘ N)″x = { 1 : ℵ0 }.
Auch ohne c(x) = ℵ0 kann man sehen, dass 1 ∈ (G ∘ N)″ x und 1 ∉ G″ N″x.
Obige Sprachfunktion G ist anzahltreu, d. h. von der Form G : V : Kard → V, aber nicht von der Form G : V → V. Für diese speziellen anzahltreuen Funktionen gilt nun Kommutativität:
Satz (verallgemeinertes Kommutativitätsschema)
Für alle Sprachfunktionen F : V : Kard → V : Kard und G : V → V gilt:
∀x. (G ∘ F)″x = G″ F″x.
Das Axiom (Kom) ist der Spezialfall dieses Satzes mit der Sprachfunktion N : V → V an der Stelle von G.
Beweis
Wir betrachten zunächst (G ∘ F)″x.
Sei c ∈ κ (G ∘ F)″x. Dann existiert ein a ∈ x mit
(+) c = G(F(a : c(a, x)(0))).
Wir nennen jedes a ∈ x mit (+) ein Urbild von c.
G ist insbesondere anzahltreu und damit gilt dann:
(++) κ = Σa ∈ x, a Urbild von c F(a : c(a, x))(1).
Wir betrachten nun G″y mit y = F″x. Die Elemente von y sind von der Form F(a : c(a, x))(0), a ∈ x, und damit sind die Elemente c von G″y wieder von der Form (+).
Sei also a ∈ x, und seien c und κ durch (+) und (++) definiert.
Sei weiter μ = c(c, G″y). Wir zeigen, dass μ = κ.
Es gilt:
(+++) yGc = F″ { a : c(a, x) | a ∈ x, a Urbild von c }.
Damit rechnen wir dann:
μ =G anzahltreu Σb ∈ yGc c(b, y) =
Σb ∈ yGc Σa ∈ xFb, a Urbild von c F(a : c(a, x))(1) = (Kom), (+++)
Σa ∈ x, a Urbild von c F(a : c(a, x))(1) =(++) κ.
Relationen und Kardinalität
Wir zeigen, dass die Kardinalitätsfunktion äußere Bijektionen respektiert:
Satz (c ist konstant auf den Äquivalenzklassen von ≡ )
Sei R : A ≡ B. Dann gilt c(A) = c(B) = c(R).
Beweis
Seien P1, P2 anzahltreue Sprachfunktionen mit
P1((a, b) : κ) = a : κ,
P2((a, b) : κ) = b : κ für alle (a, b), κ.
Wir zeigen, dass A = P1″ R gilt. Damit gilt dann:
c(A) = N″ P1″ R = N″ R = c(R).
Analog gilt B = P2″ R und c(B) = c(R).
Es gilt A = dom(R), also A = { a : c1(a, R) | a = a }.
Aber für alle a gilt
{ (a, b) : κ | (a, b) ∈ κ R } = RP1a, also
c1(a, R) =Def. c({ (a, b) : κ | (a, b) ∈ κ R }) = c(RP1a).
Dies zeigt A = P1″ R.
Speziell erhalten wir:
Korollar
Ist f : A → B eine mengentheoretische Bijektion, so gilt c(A) = c(B).
Beweis
Es gilt f : A ≡ B.
Weiter erhalten wir die folgende Vertauschungsregel für Doppelsummen:
Korollar (Doppelsummen über dom(R) und rng(R))
Für alle Relationen R : A ≡ B gilt:
Σa ∈ A Σb ∈ B c((a, b), R) = Σb ∈ B Σa ∈ A c((a, b), R).
Beweis
Sei a ∈ A beliebig. Dann gilt:
(+) Σb ∈ B c((a, b), R) = Σz ∈ R, P1(z) = a c(z, R).
Beweis von (+)
Wir schreiben kurz ca, b für c((a, b), R). Damit gilt dann:
Σz ∈ R, P1(z) = a c(z, R) = c({ (a, b) : ca, b | (a, b) ∈ R }) =
c({ (a, b) : ca, b | b ∈ B }) = c({ a } × { b : ca, b | b ∈ B }) =(E3)
c({ b : ca, b | b ∈ B }) = Σb ∈ B c((a, b), R).
Damit gilt dann mit A = P1″R (vgl. den Beweis oben):
Σa ∈ A Σb ∈ B c((a, b), R) = Σa ∈ A Σz ∈ R, P1(z) = a c(z, R) = Σa ∈ A c(RP1a) = c(A).
Analog ist die zweite Doppelsumme gleich c(B).
Aus c(A) = c(B) folgt die Behauptung.
Wir zeigen noch, dass die Aussage des obigen Satzes de facto äquivalent zum Kommutativitätsschema ist:
Satz
Über den restlichen Axiomen sind äquivalent:
(i) | (Kom). |
(ii) | Für alle Relationen R : A ≡ B gilt c(A) = c(B). |
Beweis
(i) ↷ (ii): haben wir oben gezeigt.
(ii) ↷ (i):
Sei F : V : Kard → V : Kard, und sei A ein beliebiges Aggregat.
Wir zeigen, dass (N ∘ F)″ A = N″ F″ A.
Wir definieren hierzu eine Relation R durch:
R = { (a, F(a, c(a, A))(0)) : F(a, c(a, A))(1) | a ∈ A }.
Sei AF = { a : F(a, c(a, A))(1) | a ∈ A }.
Dann gilt AF = dom(R).
Weiter sei B = { F(a, c(a, A))(0) : 1 | a ∈ A }.
Für b ∈ B gilt c2(b, R) = c(xFb) (mit Verwendung von (E2)).
Damit dann rng(R) = { b : c(xFb) | b ∈ B } = F″ A.
Also R : AF ≡ F″ A. Nach Voraussetzung (ii) gilt also
N″ AF = c(dom(R)) = c(rng(R)) = N″ F″ A.
Aber N″ AF = Σa ∈ A F(a, c(a, A))(1) = (N ∘ F)″ A.
Dies zeigt die Behauptung.
Ein weiteres Korollar des Satzes über Relationen ist:
Korollar (Kommutativität der Addition)
Für alle κ, μ gilt κ + μ = μ + κ.
Beweis
Sei R = { (0, 1) : κ, (1, 0) : μ }.
Dann ist dom(R) = { 0 : κ, 1 : μ } und rng(R) = { 0 : μ, 1 : κ }.
Wegen R : dom(R) ≡ rng(R) gilt also:
κ + μ = c({ 0 : κ, 1 : μ }) = c(dom(R)) = c(rng(R)) = c({ 0 : μ, 1 : κ }) = μ + κ.
Schließlich definieren wir:
Definition (Summe zweier Aggregate, x + y)
Seien x, y, z Aggregate. z heißt die Summe von x und y, in Zeichen z = x + y, falls für alle a gilt:
(+) c(a, z) = c(a, x) + c(a, y).
Die Summe existiert für alle x, y: Sie ist die Einstellung der Häufigkeiten von set(x ∪ y) gemäß (+). Gilt x ∩ y = 0, so ist x + y = x ∪ y.
Es gilt x + y = y + x, da die Kommutativität c(a, x) + c(a, y) = c(a, y) + c(a, x) für alle a gilt.
Allgemeine Summen diskutieren wir später.