K02 Mengen und Abbildungen
Mengen: Elementschaft, Inklusion, Gleichheit, Mächtigkeit, Schnitt und Vereinigung; Abbildungen: Bilder, Injektivität, Surjektivität, Bijektivität, Isomorphie
K02_Mengen.txt
—
Plain Text,
9 KB (9217 bytes)
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.
Artikelaktionen