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}

    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
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: ∈, ∉, ≡, ∀, ∃, ∅, ⋂, ⋃, ⋀, ⋁, ¬, →, ↔, ↓,  ⇒, ⇔, ⟼, ☇, √, ∤, |, ≥, ≤, ∑, ⊕, ≠, ∪, ⊂, ⊃, ⊆, ⊇, ○, Ā, Ē, Ū, Ō, ⚡, Ω,  ɸ, ω, τ, Σ, ℕ, ℤ, π, ✓, ∞, ρ