Vorlesung vom 13.11.2012
Relationen
Def: Eine Teilmenge R ⊆ AxB wird (binäre) Relation zwischen dem Mengen A und B genannt.
Für (a,b)∈R kannn äquivalent auch a R b geschrieben werden. (a steht in Relation R zu b).
Eine Teilmenge R ⊆ A x A wird Relation über (oder auf) A genannt.
Beispiele:
1) A x B ist die Allrelation
∅ ist die leere Relation
Id_A={(a,a)|a∈A} ist die identische Relation über A
2) Die Teilbarkeitsrelation | über ℕ+
k|n ⇔ ∃ m∈ℕ n=k*m
andere Schreibweise (2, 10)∈|
aber (3, 13)∉|
3) Vergleichsrelationen: ≤ < ≥ > über ℕ, ℤ, Q, R
4) Jede Abildung f: A->B kann als Relation interpretiert werden
f={(a,b) AxB|b=f(a)}
5)S= Menge der Studenten an der FU
M= Menge der angebotenen Module
R ⊆ SxM={(s,m)| s hat Modul m abgeschlossen}
Darstellung von Relationen
1) Auflistung der Mengen (wenn R endlich)
Beispiel: Teilbarkeit über {2,3,4,5,6}
R={(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}
2) Tabellenform Spalten für Elemente aus A
Zeilen für Elemente aus B
6 1 0 0 0 1
5 0 0 0 1 0
B 4 1 0 1 0 0
3 0 1 0 0 0
2 1 0 0 0 0
2 3 4 5 6
A
3. bipartik Graphen R ⊆ A x B
Ein Graph:
a1, a2, an übereinandergeschrieben daneben b1, b2, bn übereinander geschrieben eine linie a1 -> b2 -> an -> bn -> a1 -> b2 -> a2 -> b1
4) gerichtete Graphen für Relationen über A
--(die Zahlen sind im Kreis angeordnet. Es gehen Pfeile vom Teiler zum Vielfachen)
5) Diagramme als Verallgemeinerung von Tabellen
Operationen auf Relationen
Vereinigung R⋃S={(a,b)∈AxB|a R b ⋁ a S b}
Durchschnitt R⋂S={(a,b)∈AxB| aRb⋀aSb}
Komplement R = AxB\R={a,b)∈AxB|(a,b)∉ R}
inverse Relation R^(-1) ⊆ BxA R^(-1)∈BxA|aRb}
- Relationsverkettung: R ⊆ AxB, S ⊆ BxC R°S ⊆ AxC
R○S={(a,c)∈AxC|∃b∈B aRb^bSc}
Beispiele: | und < über ℕ
Vereinigung | ∪ < ={(a,b)∈ ℕxℕ| a|b v a<b} = ≤
Durchschnitt | ⋂ < = 'Echte Teilbarkeit'
={(a,b)| a|b ^a<b}
Komplement < = {(a,b)|¬a<b} =≥
<^(-1) ={(b,c)| a<b}={(b,c)|b>a}=>
-----------------------------------------------
≤○≤ über ℕ
= {(a,c) | ∃ b∈ℕ a<b<c} = {(a,c)|a ≤ c}
<○< über ℕ
= {(a,c) | ∃ b∈ℕ a < b⋀b < c} = {(a,c)|a+1<c}
bzw. {(a,c)|a<c-1}
M Menge aller Menschen
R⊆ MxM aRb <=> a ist Kind von b
R^(-1) a R^(-1) b <=> a ist Vater oder Mutter von b
R○R a R○R c <=> a ist Enkelkind von c
R○R^(-1) a R○R^(-1) b <=> ∃b a R b ⋀c R b
<=> a und c haben einen gemeinsamen Elternteil oder a=c
R^(-1)○R a R^(-1)○R c <=> ∃b b R a ⋀b R c
<=> a und c haben gemeinsames Kind oder a=c und c hat ein Kind (b)
Eigenschaften von Relationen über einer Menge (siehe Script S. 28)
Def: Sei R AxA, dann ist
- Reflexiv, wenn für alle a∈A gilt aRa, d.h. Id_A ∈ R
- Symmetrisch, wenn aus aRb immer bRa folgt, d.h. R=R^(-1)
- Transitiv, wenn aus aRb und bRc folgt, dass aRc, d.h. R○R⊆R
- Antisymmetrisch, wenn aus aRb und bRa folgt, dass a=b, d.h R⋂R^(-1)⊆Id_A
- Asymmetrisch, wenn aus a Rb folgt, dass (b,a)∉R, d.h. R⋂R^(-1)=∅
Beispiele: | ist reflexiv, transitiv, antisymmetrisch(für A∈ℕ)
≤ ist reflexiv, transitiv, antisymmetrsich
< ist transitiv, asymmetrisch, antisymmetrisch
15.11.2012
Äquivalenzrelationen
Def: Eine Relaion R über A ist eine Äquivalenzrelation, wenn sie reflexiv, symmetrisch und transitiv ist.
1) R ist Reflexiv: ∀a∈A aRa
2) R ist Symmetrisch: ∀a,b∈A aRb->bRa
3)R ist transitiv: ∀a,b,c∈A aRb⋀bRc->aRc
Beispiele:
1) Für jede Menge A sind AxA und Id_A Äquivalenzrelation
2) F = Menge aller Boolschen Formeln ≡ die semantische (logische) Äquivalen von Formeln => Äquivalenzrelation
3) M Menge aller Menschen
m_1Rm_2 <=> m_1 und m_2 haben gleichen Vater und gleiche Mutter
4) A=ℕ (oder A =ℤ)
Fixieren Teiler d>0 hier d=5
a R_5 b <=> a mod 5=b mod 5
neues Symbol: a ≡ b mod 5 (gesprochen: a ist kongruent zu b modulo 5)
alternative Definition
a≡b mod 5 <=> 5|b-a
Def: Ist R⊆AxA eine Äquivalenzrelation und a∈A, dann nennt man die Menge [a]_R={x∈A|xRa} die Äquivalenzklasse von a unter der Relation R (alternative Bezeichnung:a/R)
Beispiel 4
≡ mod 5 über N R_5
[14]_(R_5)={4,9,14,19...}
[23]_(R_5)={3,8,13,18...}
insgesamt 5 Äquivalenzklassen: [0]_(R_5), [1]_(R_5), [2]_(R_5), [3]_(R_5), [4]_(R_5)
Satz: Ist R⊆AxA Äquivalenzrelation und [a]_R, [b]_R zwei Äquivalenzklassen, dann sind [a]_R=[b]_R oder [a]_R ⋂ [b]_R=∅
Beweis:
[a]_R ⋂ [b]_R≠∅ (1)=> aRb (2)=> [a]_R=[b]_R
(1)[a]_R ⋂ [b]_R≠∅ =>3c€A [a]_R ⋂ [b]_R => cRa^cRb |Definition der Äquivalenzklassen
R a
/ |
c |Transitivität
\ v
R b
=> aRc^cRb |Symmetrie
=> aRb |Transitivität
(2) aRb zu zeigen [a]_R=[b]_R <=> (i) [a]_R⊆[b]_R
und (ii) [a]_R⊆[b]_R
(i) Sei c ein beliebiges Element aus [a]_R
=>cRa⋀aRb |Skizze (wer will kann die machen)
=>cRb |Transitivität
=>c∈[b]_R |Def
(ii) aRb=> bRa
und (i) anwenden: [b]_R⊆[a]_R =>Gleichheit
Folgerung: Die Menge der Äquivalenzklassen einer Äquivalenzrelation R⊆AxA bildet eine Partition von A
Beispiel: ≡ mod 5
{{0,5,10,15,...},{1,6,11,16,...},{2,7,12,17,...},{3,8,13,18,...},{4,9,14,19,...}}
Ein Element von [a]_R wird Reprsentant der Klasse genannt (insbesondere ist a Repräsentant von [a]_R)
Eine Auswahl von jeweils einem Repräsentanten aus jeder Äquivalenzklasse bildet ein Repräsentantensystem
Unser Bsp: {0,1,2,3,4} Standardrepräsentantensystem
alternativ: {15,6,27,38,109}
Beobachtung: Sind R und S Äquivalenzrelationen über A, dann ist R⋂S eine Äquivalenzrelation
Begründung: reflexiv (a,a)∈R und (a,a)∈S=> (a,a)∈R⋂S
symmetrisch: (a,b)∈R⋂S=>(a,b)∈R ^(a,b)∈S
=>(b,a)∈R ^(b,a)∈S |R,S Äquivalezrelaionen
=>(b,a)∈R⋂S
transitiv: (a,b)€R⋂S^(b,c)∈R⋂S=>(a,b)∈R^(b,c)∈R^(a,b)∈S^(a,b)∈S
=>(a,c)R^(a,c)∈S
=>(a,c)€R⋂S
Achtung: Gilt im Allgemeinen nicht für R⋃S
Gegenbeispiel: A=ℕ R ist ≡ mod 2; S ist ≡ mod 3
a=2 c=3 (2,3)∉R⋃S weil (2,3)∉R und (2,3)∉S
Finde b (a,b)€R und (b,c)€S
b=6 2=b mod 2
b=3 mod 3
=> nicht transitiv
Für jede RelationR⊆AxA ist der nachfolgend definierte, reflexiv-symmetrische-transitive Abschuss von R die kleinste Äquivalenzrelation, die R als Unterrelation enhält.
(1) R_r =R ⋃ Id_A
(2) R_rs =R_r⋃ (R_r)^(-1)
(3) R_rst= R_rs⋃R_rs○R_rs⋃ R_rs○R_rs○R_rs⋃...
<unendlich>
= U
(R_rs)^i wobei(R_rs)^i=R_rs○.....○R_rs
i=1
20.11.2012
Ordnungsrelationen
Def: Eine Relation R über einer Menge A, die reflexiv, transitiv und antisymmetrisch ist, wird Halbordnungsrelation (alternativ: partielle Ordnungsrelation) genannt.
Man nennt dann (A,R) eine Halbordnung oder kurz Poset.
Bsp:
(1) Für jede Menge M ist (P(M),≤) eine Halbordnung
(2) (ℕ+,|) ist Halbordnung
(3) (ℕ,≤),(ℤ,≤)... sind Halbordnungen
(4) S die Wörter einer Sprache mit der lexikographischen Ordnung ist eine Halbordnungsrelation
Darstellung von endlichen Posets durch Hasse-Diagramme
(A,<) Poset: Das Hasse-Diagramm stellt die kleinste Teilrelation von < dar, deren reflexiv-transitiver Abschluss die Relation < erzeugt.
Beispiel1:
Hasse-Diagramm von (P({a,b,c},≤)
{a} {b} {c}
\ | /
∅
(jede Ebene enthält die Mengen mit einem, zwei...Elementen; von jeder Menge der Ebene mit Mengen mit n Elementen wird ein Pfeil zu den Mengen der Ebene mit Mengen mit n+1 Elementen gezogen, die die jew Menge enthält und ein Weiteres Element)
Beispiel 2: ({1,...,12})
1: 2,3,5,7,11
2: 4,6,10
3: 6,9
5: 10
7:
11:
4: 8
6: 12
10:
9:
Def: Eine Halbordnungsrelation (A,R) ist total oder linear, wenn für alle a,b€A gilt, dass aRb oder bRa (keine Verzweigungen)
Def: Eine Relation R über A, die transitiv und asymmetrisch ist, nennt man eine strikte (strenge) (Halb-)Ordnungsrelation
R ist antisymmetrisch: aRb ⋀ bRa => a=b
R ist asymmetrsich: aRb => ¬(bRa)
Asymmetrie =>Antisymmetrie
Halbordnungsrelaion über A|strikte Ordnungsrelation
R ⟼ R\Id_A
R'⋃Id_A (zurück) R'
BSP: ≤ ⟼ <
⊆ ⟼ ⊂
Def: Sei (A,<) ein Poset, B⊆A, a,b€A
a ist maximales(minimales) Element von B, wenn a∈B und es gibt kein b≠a aus B mit a<b (b<a)
a ist obere (untere) Schranke von B, wenn für alle b∈B gilt b<a (a<b)
a ist größtes (kleinstest) Element von N, wenn a∈B und a ist obere(untere) Schranke von B
a ist obere (untere) Grenze von B, wenn a das kleinste (größte) Element der Menge der oberen(unteren) Schranken von B ist
Bemerkungen:
(1) Wenn ein größtes (kleinstes) Element von B existiert, dann ist es eindeutig. Man nennt es das Maximum (Minimum) von B
(2) Wenn eine obere (untere) Grenze von B existiert, dann ist sie eindeutig. Man nennt sie das Supremum (Infimum) von B
(3) Wenn Maximum existiert, dann ist es das einzige maximale Element.
(4) Wenn das Maximum (Minimum) existiert, dann ist es gleichzeitig Supremum (Infimum)
zu den Bemerkungen
ad 1) Angenommen a und a' erfüllen Def für größtes Element von B (zu zeigen: a=a')
Nach Def: a∈B und a obere Schranke von B
a'∈B und a' obere Schranke von B
a obere Schranke von B a'<a
a' obere Schranke von B a<a'
=> a=a' Antisymmetrie
ad 2) folgt aus 1) weil Supremum ein Minimum (der Menge der Oberen Schranken) ist.
ad 3) Sei a das Maximum von B
=> (i)a€B und (ii)∀b€B b<a
zu zeigen: a ist Supremum von B, d.h.
(iii)a ist obere Schranke von B und (iv)für jede obere Schranke c von B gilt a<c
(iii)=(ii)
(iv)=(i) weil a€B liegt es unter c
22.11.2012
Funktionen
Def: Eine Funktion f von einer Menge A in Menge B ist eine Zuordnung, die jedes Element a∈A zu einem eindeutig bestmmten Element b∈B in Beziehung setzt. Dieses b bezeichnen wir mit f(a)
D.h. Eine Funktion f:A→B ist eine Relation zwischen A und B, bei der für jedes a∈A genau ein b∈B existiert, so dass (a,b)∈f
Relation Funktion
f⊆AxB f:A→B
(a,b)∈f f(a)=b
<=>a f b
Definitionsbereich: A
Wertebereich (W-Vorrat):B
f:A→B Funktion
M⊆A, N⊂B
Bild von M unter f :f(M)={b∈B|∃a∈M f(a)=b}
Urbild von N unter f:f^(-1)(N)={a∈A|f(a)∈N}
Insbesondere ist f(A)=Im(f) das Bild von f
Beispiel: f:|R->|R
f(x)=x^2
M=[-1,2]⊆|R
f(M)=[0,4]
N=[1,4]⊆|R(≥0)
f^(-1)(N)=[-2,-1]⋃[1,2]
Def: Eine Funktion f:A->B nennt man:
injektiv, wenn verschiedene Elemente aus A auf verschiedene Elemente aus B abgebildet werden,
d.h. ∀a,a'∈A f(a)=f(a') => a=a'
surjektiv, wenn das Bild der Funktion den gesamten Wertevorrat umfasst, d.h. ∀b∈B f(a)=b
bijektiv, wenn f injektiv und surjektiv ist.
Beispiel:
f(x)=x^2 als Funktion f:|R->|R
ist nicht injektiv, denn f(-2)=f(2) und nicht surjektiv, weil -1 ∉ f(|R)
f:|R->|R(≥0) ist surjekti v, weil für jedes y∈R(≥0) gilt f(√y)=(√y)^2=y
f:|R(≥0)->R(≥0) ist bijektiv, weil surjektiv mit f(√y)=(√y)^2=y und injektiv, weil für 0 ≤ x< x' => x^2 < x'^2
Beobachtung: Ist f:A->B bijektiv, dann ist die innere Relation f^(-1) auch eine Funktion f^(-1):B→A
Bsp (wo das nicht funktioniert): 2 Mengen A{a,b} und B{1,2,3};
als Funktion f = {(a,2),(b,3)}
inverse Relation: f^(-1) = {(2,a),(3,b)} (ist keine Funktion von B nach A, da es für die 1 in B kein zugeordnetes Element aus A gibt.)
2. Beispiel: 2 Mengen A{a, b, c} und B{1,2,3}
f^-1 = {(1,b),(2,a),(3,c)} ist Funktion B→A (für jedes B gibt es ein A)
Def: Sind f: A→B und g:B→C Funktionen, dann ist die Relationsverkettung f*g eine Funktion von A nach C, die wir (als Funktion) mit gf:A→C bezeichnen
(gf)(x)=g(f(x))
Beispiel:
f(x)=sin x g(x)=x^2
gf(x)=(sin x)^2 = sin^2 x (zweiteres ist die übliche Schreibweise)
fg(x)=sin (x^2) = sin x^2
Satz: Seien f:A→B und g:B→C Funktionen
Dann gilt:
(1) ist f bijektiv, dann ist f^(-1)f = Id_A (Identische Relation auf A) und ff^(-1) = Id_B
(2) Sind f und g injektiv, dann ist auch gf injektiv
(3) Sind f und g surjektiv, dann ist auch gf surjektiv
(4) Sind f und g bijektiv, dann ist auch gf bijektiv und es gilt (gf)^(-1) = f^(-1)g^(-1)
(5) ist f injektiv, dann gibt es eine Funktion h: B→A, so dass hf=Id_A
(6) ist f surjektiv, dann gibt es eine Funktion h: B→A, so dass fh=Id_B
zu (4): Bild mit 3 Mengen (und vielen Pfeilen^^): damit sie bijektiv ist, müssen in jeder Menge gleich viel Elemente vorhanden sein. es gibt 3 Mengen (A, B, C) und 2 Funktionen: g und f. f:A→B g:B→C fg: A→C
zu (5): die "linke Menge" darf nicht größer als die "rechte Menge" sein. z.b. A hat 4 Elemente, B hat 6
allen Elementen aus B, die keinem Element von A zugewiesen wurden, wird bei h ein beliebiges Element aus A zugeordnet
zu (6): die "rechte Menge" darf nicht größer sein als die "linke Menge"
Beispiel (5): sin:[0,π)/2]→|R ist injektiv (beschreibt die Sinusfunktion von seinem Wendepunkt (0,0) bis zu seinem max (π)/2)
h:R→[0,π)/2]
h(x)= arcsin falls x€[0,1], sonst 0
(6) f(x)=x^2 als funktion f:R-->R(>=0) surjektiv h(y)=√y
Beobachtung: ist f:A→B eine Funktion, dann ist die Relation f <= AxA mit a ~_fa' <-def-> f(a)=f(a') eine Äquivalenzrelation (Faserung von A unter f) (Faserung müssen wir aber angeblich nicht wissen)
Natürliche Zahlen
Peano-Axione der natürlichen Zahlen ℕ
(1) 0∈ℕ
(2) Für jedes n∈ℕ gibt es einen eindeutigen Nachfolger S(n)∈ℕ
(3) verschiedene natürliche Zahlen haben verschiedene Nachfolger
(4) 0 ist kein Nachfolger einer natürlichen Zahl
(5) N ist die keinste Menge mit den Eigenschaft (1) bis (4)
27.11.2012
2 Konsequenzen
1. Rekursive Definition von Funktionen auf ℕ durch Verankerung mit Definition von f(0) und Rekursionsschritt in dem f(S(n)) auf f(n) zurückgeführt wird.
Addition: Wie kann man eine beliebige Zahl n zu m addieren?
m+0=m (1)
m+S(n)=S(m+n) (2)
Multiplikation
m*0=0 (3)
m*S(n)= m*n+m (4)
2. Beweise für Aussagen, die für alle n∈ℕ gelten mit vollständiger Induktion:
Durch Induktionsanfang: Zeige, dass die Aussage für n=0 gilt
und Induktionsschritt: Wenn Aussage wahr ist für n, dann auch für S(n)
Beispiel 1
1) Die Addition von natürlichen Zahlen ist assoziativ, d.h. für beliebige k,m∈ℕ und für alle n∈ℕ gilt
(k+m)+n=k+(m+n)
Beweis mit Indukton nach n:
Induktionsanfang: n=0
(k+m)+0=k+m=k+(m+0) | (1)
Induktonsvoraussetzung: (k+m)+n=k+(m+n)
Induktionsbehauptung: (k+m)+S(n)=k+(m+S(n))
Induktionsschritt: (k+m)+S(n)=S((k+m)+n) | (2)
=S(k+(m+n)) | IV (Induktionsvoraussetzung)
=k+S(m+n) | (2)
=k+(m+S(n)) []| (2)
Verkürzte Darstellung
IA für Induktionsanfang
IV für Induktionsvoraussetzng
IB für Induktionsbehauptung
IS für Induktionsschritt
Beispiel 2: Die Summe der ersten n undgeraden Zhlen ist gleich n^2
IA: n=1 1=1^2
n n+1
IV: Σ (2i-1)=n^2 (IB: Σ(2i-1)= (n+1)^2
i=1 i=1
IS: n->n+1
n+1 n
Σ(2i-1) = Σ(2-1)+2(n+1)-1
i=1 i=1
=n^2+2n+1=(n+1)^2 |(IV)
bisheriges Prinzip
P(n) ist wahr für alle n∈N, wenn
(1) P(0) wahr ist
(2) P(n)→P(n+1) für alle n∈N
Variante 1 P(n) ist wahr für alle n∈ℕ mit n≥n_0, wenn
(1) P(n_0) wahr
(2) P(n)→P(n+1) für alle n≥n_0
Variante 2 (verallgemeinerte Induktion)
P(n) ist wahr für alle n∈ℕ wenn
(1) P(0)
(2) P(0)⋀P(1)⋀..⋀P(n)->P(n+1)
oder Kombinationen von Variante 1 und 2
Beispiel 3: Jeder Betrag n≥8 kann durch Briefmarken mit 3 und 5 Cent zusammengesetzt werden.
Für alle n≥8 gibt es a,b∈ℕ, so dass n=3a+5b
IA: n=8 a=1 b=1
IS: n→n+1
nach IV: n=3a+5b
Fall 1: b≥1
a'=a+2 b'=b-1∈ℕ
3a'+5b'=3(a+2)+5(b-1)=3a+5b+6-5
Fall 2: b (mod 2)=0 => a≥ 3 weil n≥8
b'=b+2 a'=a-3 €N
3a'+5b'=..=n+1
Beispiel 4: Jede natürliche Zahl n >= 2 kann man als Produkt von Primzahlen darstellen (ev. mit nur einem Faktor)
IA: n=2 2=2 [✓]
IS: <n → n
Fall 1: n ist Primzahl n = n [✓]
Fall 2: n ist keine Primzahl, dann gibt es k,l∈ℕ n=k*l wobei k≠1,l≠1
=> k<n und l < n
IV: für k: k = p_1*...*p_i (p_i = primzahlen)
IV: für l: l = q_1*...*q_j (q_j = primzahlen)
n=k*l=p_1*...*p_i*q_1*...*q_j
falscher induktionsbeweis:
Herde mit n+1 tieren. wir nehmen a raus
c hat nach IV gleiche farbe wie b und gleiche Farbe
blabla... siehe http://www.numerik.uni-hd.de/~mrheinla/lehre/konstanz/analysis1_ws05/ZurInduktion.pdf
Endlichkeit, Abzählbarkeit
Natürliche zahlen im Sinne von J von Neumann
0 = ∅
1 = {∅}
2 = {∅, {∅}}
3 = {∅, {∅}, {∅, {∅}}}
S(n) = n ⋃ {n} = {0,1,...n}
=> natürliche Zahl n ist eine n-elementige Menge
Def.: Zwei Mengen A und B sind gleichmächtig, wenn eine bijektive Funktion f: A->B existiert.
Eine Menge A ist endlich, wenn es eine von Neumann-Zahl n∈N gilt, die gleichmächtig zu A ist. Notation |A| = n bzw. #A
Für unendliche Mengen schreibt man |A| = ∞
Eine Menge A ist abzählbar, wenn sie endlich ist oder A ist gleichmächtig zu ℕ (abzählbar unendlich)
29.11.2012
A ist endlich <=> 3 von Neumann-Zahl n, so dass eine Bijektion f:A->n
|A|=n
A ist abzählbar <=> A ist endlich oder es gibt eine Bijektion f:A→N
Eigenschaften von endlichen Mengen
1)|A\B|=|A|-|A⋂B|
2)|A⋃B|=|A|+|B|-|A⋂B| |Inklusion-Exklusion-Prinzip //Formel siehe Skript Seite 39 mittig (2.)
3)|AxB|=|A|*|B|
4)|ρ(A)|=2^|A| |Potenzmenge von A
zu 4) П(A)={B|B⊆A}
Bijektion f:ρ(A)-> {Funktionen von A nach {0,1}}
B|-> (Phi)_B:A→{0,1}
(Phi)_B(x)={1 falls x€B, 0 sonst
B=h^(-1)(1) <-| h:A->{0,1}
Allgemein:Anzahl der Funktionen von A nach B ist |B|^(|A|)
hier B={0,1}
=> Anzhal der Charakteristischen Funktionen=|{0,1}|^|A|=2^|A|
Welche unendlichen Mengen sind Abzählbar?
1)ℕ ist abzählbar: Id_N:N->N ist bijektiv
2)ℕ+ ist abzählbar: gesucht Bijektion N->N+
n |-> n+1
n'-1 <-| n'
3)ℤ ist abzählbar: Idee
N: 0 1 2 3 4 ...
Z:...-3 -2 -1 0 1 2 3 4 ...
0->0, 1->-1 2->1 3->-2...
formal: f:N -> Z
n|-> {n/2 falls n gerade, -(n+1)/2 falls n ungerade
-2z-1 falls z<0, 2z falls z≥0} <-| z
4) |R ist abzählbar
hier Idee für Q+ ist abzählbar
Q+ besteht aus Brüchen der Formel m/n, m,n€N+
//Graph: siehe Skript Seite 40 mittig
5) |R ist NICHT abzählbar
Wir zeigen: Die Menge der reellen Zahlen im Intervall [0,1] ist nicht abzählbar.
Jede Zahl aus [0,1] is darstellbar als 0,b_0 b_1 b_2 b_3...
einige Darstellungen sind nicht eindeutig, nämlich alle, die mit 0-Periode oder 9-Periode enden
es gilt: 0,b_0 b_1 b_2 9 = 0, b_0 b_1 (b_2+1) 0
Grund: 0,9=1
1=3*1/3=3*0,3 =0,9
Beweis durch Widerspruch
angenommen f:N->[0,1] ist bijektiv
f(0)=0,a_00 a_01 a_02...
f(1)=0,a_10 a_11 a_12...
f(2)=0,a_20 a_21 a_22...
f(3)=...
Konstruktion von r€[0,1]
r=b_0 b_1 b_2 b_3 ...
mit b_i={7 falls a_ii≠7, 6 falls a_ii=7
r∉lm(f)
->Widerspruch, f ist nicht surjektiv, also auch nicht bijektiv
Satz: Für jede Menge M gilt: M und ρ(M) sind nicht gleichmächtig
Beweis mit Widerspruch:
angenommen f: M->ρ(M) ist bijektiv
Konstruktion einer Menge B€ρ(M), die nicht im Bild von f liegen kann, führt zum Widerspruch.
B={x€M|x∉f(x)} m={a,b,c} f(a)={a,b} f(b)={a,c} f(c)={b,c}
B={b}0>b∉lm(f)
Allgemein b€lm(f)
=>3a€A f(a)=B
a€B?
a€B<=>a∉f(a)<=>a∉B //da f(a)=B
Sonderzeichen: ∈, ∉, ≡, ∀, ∃, ∅, ⋂, ⋃, ⋀, ⋁, ¬, →, ↔, ↓, ⇒, ⇔, ⟼, ☇, √, ∤, |, ≥, ≤, ∑, ⊕, ≠, ∪, ⊂, ⊃, ⊆, ⊇, ○, Ā, Ē, Ū, Ō, ⚡, Ω, ɸ, ω, τ, Σ, ℕ, ℤ, π, ✓, ∞, ρ