K02 Mengen und Abbildungen

Dateiinhalt

Eine Menge ist eine ungeordnete Zusammenfassung bestimmter mathematischer Objekte.

Notationen für Mengen:
-----------------------

Aufzählungsnotation:  A = {1,3,5,7,9}

Vordefinierte Mengen: ℕ, ℝ, ℚ, ℤ, ℤₙ = {0,1,2,...,n-1}, [n]={1,...,n}

Durch Angabe einer Eigenschaft (Separation, Komprehension):

            B = { x | x∈ℕ ∧ x ist ungerade }

/* Georg Cantor, dt. Mathematiker, 1845-1918: Begründer der Mengenlehre, 
Mächtigkeiten unendlicher Mengen, Menge aller Mengen */


Elementschaft, Inklusion und Gleichheit
---------------------------------------

Man schreibt x∈A um zu sagen, dass x ein Element von A ist, also
zur Menge A gehört.

Man schreibt A ⊆ B um zu sagen, dass A eine Teilmenge von B ist.

Merke: A ⊆ B ist gleichbedeutend mit ∀x.x∈A ⇒ x∈B

Um zu zeigen, dass A ⊆ B, zeigt man also ∀x.x∈A => x∈B. 
Nach unseren Beweisregeln bedeutet dass, dass man für ein f.a.b. x, 
welches in A ist (Annahme x∈A), zeigen muss, 
dass es auch in B ist (Zeige x∈B).

Merke A=B ist gleichbedeutend mit A⊆B ∧ B⊆A. Um zu zeigen, dass
zwei Mengen A und B gleich sind, muss man also zuerst A⊆B zeigen und
dann auch noch B⊆A.


Operationen auf Mengen:
-----------------------

Vereinigung: A ∪ B = { x | x∈A ∨ x∈B} 
Intuitiv: "Menge aller x mit x aus A _oder_ x aus B"

Schnitt: A ∩ B = { x | x∈A ∧ x∈B} 
Intuitiv: "Menge aller x mit x aus A _und_ x aus B"

Differenz: A \ B = { x | x∈A ∧ ¬x∈B}

Symmetrische Differenz: A Δ B = A\B ∪ B\A

Hinweis: Man veranschaulicht sich diese Operationen 
am besten anhand eines Venn-Diagramms.

Kartesisches Produkt: A x B = { (x,y) | x∈A ∧ y∈B }

Das kartesische Produkt A x B umfasst also alle (geordneten!) 
Paare der Form (x,y) mit x∈A und y∈B.


Schnitt- und Vereinigungsmenge sind kommutativ, es gelten auch die 
beiden Distributivgesetze. Wir zeigen exemplarisch das eine der beiden:




 
 
 
 
Zeige A∩(B∪C) = (A∩B)∪(A∩C).
Wir zeigen zunächst A∩(B∪C) ⊆ (A∩B)∪(A∩C) .
  Sei also x ∈ A∩(B∪C) (H1)  
  /* Wir haben also x∈A (H1.1) und x∈B∪C (H1.2) */
  Wir machen eine Fallunterscheidung über x∈B∪C (H1.2).
  1. Fall x∈B (H2)
    Es ist dann x∈A∩B (H1.1 und H2) /* x∈A∧x∈B⇒x∈A∩B nach Def.*
    Also x ∈ (A∩B)∪(A∩C).
  2. Fall x∈C (H3)
    Es ist dann x∈A∩C (H1.1 und H3)
    Also x ∈ (A∩B)∪(A∩C).
Jetzt zeigen wir die umgekehrte Richtung (A∩B)∪(A∩C) ⊆ A∩(B∪C) 
  Sei also x ∈ A∩B∪A∩C (H4)  
  Wir machen eine Fallunterscheidung über H4.
  1. Fall x∈A∩B (H5)
    Aus H5 folgt x∈A ∧ x∈B (H6)
    Aus H6.2 folgt x∈B∪C  (H7)
    Also x ∈ A∩(B∪C) aus H6.1 und H7
  2. Fall x∈A∩C (H8)
    Aus H8.2 folgt x∈B∪C  (H9)
    Also x ∈ A∩(B∪C) (H8.1 und H9)
□

Die leere Menge schreibt man {} oder Ø. Sie hat keine Elemente. 

Zwei Mengen A,B mit A∩B = Ø (leere Menge) heißen *disjunkt*.
In diesem Fall wird die Vereinigung A∪B auch A+B notiert 
(eigentliches Symbol: ∪ mit einem + darüber oder drin, 
manchmal auch ∪ mit einem Pünktchen drüber oder drin).

Die *Potenzmenge* P(A) einer Menge A umfasst alle Teilmengen von A.
Das P wird meist in Fraktur oder kalligraphisch gesetzt.

Es ist also X∈P(A) <=> X⊆A.

Zum Beispiel ist P({1,3,5}) = {{},{1},{3},{5},{1,3},{3,5},{1,5},{1,3,5}}.
P(Ø) = {Ø}, P({Ø}) = {Ø,{Ø}}, P({Ø,{Ø}}) = {Ø,{Ø},{{Ø}},{Ø,{Ø}}},…


Kardinalität
-------------

Die Anzahl der Elemente einer Menge A heißt Kardinalität von A und
wird |A| notiert. Manchmal sieht man auch #A oder card(A).

Ist |A| eine natürliche Zahl so ist A eine endliche Menge. 
Nicht alle Mengen sind endlich, z.B. ℕ, ℝ, etc. sind es nicht.

Für endliche Mengen A,B gilt:

|A ∪ B| ⊆ |A| + |B|
|A + B| = |A| + |B|
|P(A)|  = 2^|A|


Relationen
==========

Eine (binäre) Relation zwischen zwei Mengen A und B ist eine
Teilmenge R ⊆ AxB. Man schreibt für (a,b)∈R auch aRb. 
Ist A=B, so spricht man von einer Relation R auf der Menge A.

Eine Relation auf A heisst 

* reflexiv,        wenn ∀x∈A.xRx
* symmetrisch,     wenn ∀x,y∈A.xRy ⇒ yRx
* antisymmetrisch, wenn ∀x,y∈A.xRy ⇒ yRx ⇒ x=y
* transitiv,       wenn ∀x,y,z∈A.xRy ⇒ yRz ⇒ xRz

Besondere Bezeichnungen:
Quasiordnung:       refl., trans.
partielle Ordnung:  refl., trans., antisymm.
Äquivalenzrelation: refl., trans., symm.

Beispiel einer partiellen Ordnung: 
Teilbarkeit auf der Menge der natürlichen Zahlen

Beispiele für Äquivalenzrelationen: Selber Rest bei Division durch 7, 
oder eine andere Zahl. Selber Musikgeschmack, selbe Zahl von Freunden, ... 


Abbildungen
===========
Eine Relation R ⊆ AxB bei der jedem Element aus A genau ein Element aus B
zugeordnet wird, heißt Abbildung oder Funktion von A nach B. 
Eine Funktion f von A nach B ist also eine Menge von Paaren f, derart, 
dass zu jedem a∈A genau ein b∈B mit (a,b)∈f existiert. 
Man schreibt in diesem Fall b=f(a).

Man sagt auch: 
R ist links-total:    ∀a∈A.∃b∈B.aRb
und rechts-eindeutig: ∀a∈A.∀b,c∈B.aRb ∧ aRc ⇒ b=c 

(NB: Es gibt auch analoge Begriffe für Relationen
  rechts-total:    ∀b∈B.∃a∈A.aRb
  links-eindeutig: ∀b∈B.∀a,c∈A.aRb ∧ cRb ⇒ a=c 
)


Eine Funktion von AxB nach C heißt zweistellige Funktion. Sie
ordnet jedem Paar (a,b) genau ein Element f(a,b)∈C zu. Beispiele für
zweistellige Funktionen sind die Addition + : RxR → R und andere
Rechenoperationen.

Allein aus der Tatsache, dass Funktionen genau ein Ergebnis liefern, 
ergeben sich bereits nicht ganz triviale Konsequenzen:

Sei f:A→B eine Funktion.

Zeige ∀x∈A. f(f(f(f(f(x)))))=x ∧ f(f(f(x)))=x => f(x)=x.
Wir nehmen an x∈A.
  f(f(f(f(f(x)))))=x (H1)
  f(f(f(x)))=x (H2)
  Aus H1 und H2 (durch Ersetzen von f(f(f(x))) durch x)
  erhalten wir f(f(x))=x (H3) 
  Aus H2 und H3 ergibt sich f(x)=x.
QED.


Bild und inverses Bild
----------------------
Ist f:A→B und U⊆A so ist das Bild f(U) von U unter f definiert durch
  f(U) = { b∈B | ∃a∈A. a∈U ∧ f(a)=b }

Ist V⊆B so ist das Urbild f⁻¹(V) von V unter f definiert durch
 f⁻¹(V) = { a∈A | ∃b∈B. b∈V ∧ f(a)=b }

Beispiel: 
Sei f(x)=x²+1. 
Das Bild   von [0,∞] ist [1,∞]. 
Das Urbild von [2,∞] ist (-∞,-1]∪[1,∞).

Beispiel:
Zeige U₁⊆U₂ ∧ U₂⊆A => f(U₁)⊆f(U₂).
Wir nehmen an
U₁⊆U₂ (H1)
U₂⊆A  (H2)
Sei b∈B f.a.b. und  b∈f(U₁) (H3).
  Zeige b∈f(U₂).
  Wir verwenden H3   /* hat die Form ∃a∈A.a∈U₁∧f(a)=b*/.
  Sei also c∈A f.a.b. und
  c∈U₁ (H4)
  f(c)=b (H5). 
    Aus H1 und H4 erhalten wir
    c∈U₂ (H6).
      Aus H5 und H6 ergibt sich
      ∃a∈A.a∈U₂∧f(a)=b  /* mit a:=c */
      das aber ist b∈f(U₂)
QED


Surjektiv, Injektiv, Bijektiv
-----------------------------
Eine Funktion f:A→B heißt injektiv, wenn es zu jedem b∈B 
höchstens ein a∈A mit f(a)=b gibt:
∀a,a'∈A.f(a)=f(a') => a=a'
(NB: entspricht genau links-eindeutige Relation)

Eine Funktion f:A→B heißt surjektiv, wenn es zu jedem b∈B 
mindestens ein a∈A mit f(a)=b gibt:
∀b∈B.∃a∈A.f(a)=b  
(NB: entspricht genau recht-totale Relation)

Eine Funktion f:A→B heißt bijektiv, wenn sie sowohl injektiv, 
als auch surjektiv ist. 

Solch eine bijektive Funktion bildet eine 1-1 Beziehung zwischen den
Elementen von A und B. Insbesondere sind es gleich viele. Man kann 
dann auch die Umkehrfunktion f⁻¹:B→A definieren durch

f⁻¹(b) = "das eindeutig bestimmte a∈A mit f(a)=b"

Dass es überhaupt immer ein Element mit f(a)=b gibt, ergibt sich aus
der Surjektivität; dass es eindeutig bestimmt ist, folgt aus der
Injektivität.


Isomorphie
----------
Seien R⊆A×A und S⊆B×B Relationen. Diese heißen *isomorph*
zueinander (griechisch: gleiche Gestalt), wenn sie bis auf Umbenennung
dasselbe sind. Formal ist das der Fall, wenn es eine Bijektion f:A→B
gibt, sodass gilt aRb <=> f(a) S f(b).

Beispiel: die Kleiner-Relationen auf ℝ und auf ℝ⁺ sind isomorph. Wir
nehmen als Isomorphie die Bijektion f:ℝ→ℝ⁺ gegeben durch f(x)=e^x.

In der Tat gilt x<y <=> e^x < e^y

Isomorphe Relation haben dieselben Eigenschaften. Das kann man dazu 
benutzen um zu zeigen, dass zwei gegebene Relationen nicht isomorph sind: 
Man finde eine Eigenschaft, die die eine hat und die andere nicht. 

Beispiel: 
Die Kleiner-Gleich-Relation und die Grösser-Gleich-Relation auf ℕ
sind nicht isomorph: Sei R⊆ℕ×ℕ definiert durch xRy <=> x≤y und 
sei S⊆ℕ×ℕ definiert durch xSy <=> x≥y. 

Informeller Beweis durch Widerspruch: 
Es gibt ein Element a∈ℕ mit aRx für alle x (nämlich a=0). 
So ein Element gibt es aber nicht für S.

Formaler Beweis:

Zeige ¬(∃f∈ℕ→ℕ."f bijektiv" ∧ ∀x,y∈ℕ.xRy <=> f(x)Sf(y)).
Wir nehmen an ∃f∈ℕ→ℕ."f bijektiv" ∧ ∀x,y∈ℕ.xRy <=> f(x)Sf(y) (H)
  Zeige Widerspruch.
  Wir nehmen jetzt eine f.a.b. Funktion f∈ℕ→ℕ an mit
  f bijektiv (H1)
  ∀x,y∈ℕ.xRy <=> f(x)Sf(y) (H2)
    Wir verwenden H2 mit x=0, y=f⁻¹(f(0)+1) und erhalten
    0 ≤ f⁻¹(f(0)+1) <=> f(0) ≥ f(0)+1. (H3)
    Da aber 0≤f⁻¹(f(0)+1) folgt mit H3.1 auch f(0)≥f(0)+1, ein Widerspruch.
QED.