Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2016 / Logik und Diskrete Strukturen / Material / Mengen (Vorlesungsnotizen)


Inhaltsbereich

Mengen (Vorlesungsnotizen)

Unsere Notizen zur 3. Vorlesung; über das Thema Mengen, Relationen und Abbildungen.

Plain Text icon mengen.txt — Plain Text, 7 KB (8021 bytes)

Dateiinhalt

Eine Menge ist eine ungeordnete Zusammenfassung bestimmter mathematischer Objekte.

Notationen fuer Mengen:
-----------------------

Aufzaehlung: A = {1,3,5,7,9}

Vordefinierte Mengen: N, R, Q, Z, Z_n = {0,1,2,...,n-1}, [n]={1,...,n}

Durch Angabe einer Eigenschaft (Separation, Komprehension):

            B = {x:N | x ist ungerade}


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

Man schreibt x:A (eigentlich statt : das Element-zeichen, eine Art
griechisches Epsilon) um zu sagen, dass x ein Element von A ist, also
zur Menge A gehoert.


Man schreibt A <= B (eigentlich statt <= das gerundete Teilmengenzeichen) um zu sagen, dass A eine Teilmenge von B ist.

Merke: A <= B ist gleichbedeutend mit All x.x:A => x:B

Um zu zeigen, dass A <= B, zeigt man also All x.x:A => x:B. Nach den
obigen Beweisregeln bedeutet dass, dass man fuer 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 zeigen A<=B und
dann auch noch B<=A.


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

Vereinigung: A u B = {x | x:A \/ x:B}

Schnitt: A & B = {x | x:A /\ x:B} (hier in Wirklichkeit die bekannten Zeichen fuer Vereinigungs- und Schnittmenge)

Differenz: A \ B = {x | x:A /\ ~ x:B}

Symmetrische Differenz: A Dreieck B = A \ B u B \ A

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 u C) = (A & B) u (A & C) .
Wir zeigen zunaechst A & (B u C) <= (A & B) u (A & C) .
  Sei also x : A&(B u C) (H)  /* Wir haben also x:A (H.1) und x:B u C (H.2*/
  Wir machen eine Fallunterscheidung ueber x:B u C (H.2).
  1. Fall x:B (H1)
    Es ist dann x:A & B (H.1 und H1)
    Also x : (A & B) u (A & C).
  2. Fall x:C (H1)
    Es ist dann x:A & C (H.1 und H1)
    Also x : (A & B) u (A & C).
Jetzt zeigen wir die umgekehrte Richtung (A & B) u (A & C) <= A & (B u C) 
  Sei also x : A&B u A&C (H)  
  Wir machen eine Fallunterscheidung ueber H.
  1. Fall x:A&B (H1)
    Es ist dann x:B u C  (H2)
    Also x : A & (B u C) (H1.1 und H2)
  2. Fall x:A&C (H1)
    Es ist dann x:B u C  (H2)
    Also x : A & (B u C) (H1.1 und H2)
QED

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

Zwei Mengen A, B mit A & B = 0 (leere Menge) heissen *disjunkt*.
In diesem Fall wird die Vereinigung A u B auch A+B notiert.

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(0) = {0}, P({0}) = {0,{0}}. 


Kardinalitaet
-------------

Die Anzahl der Elemente einer Menge A heisst Kardinalitaet von A und
wird |A| notiert. Manchmal sieht man auch #A oder card(A).

Ist |A| eine natuerliche Zahl so ist A eine endliche Menge. Nicht alle
Mengen sind endlich, z.B. N, R, etc sind es nicht.

Fuer endliche Mengen A,B gilt:

|A u B| <= |A| + |B|
|A + B| = |A| + |B|
|P(A)| = 2^|A|


Relationen
==========

Eine (binaere) Relation zwischen zwei Mengen A und B ist eine
Teilmenge R <= A x B. Man schreibt fuer (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 All x:A.xRx
* symmetrisch, wenn All x,y:A.xRy=>yRx
* antisymmetrisch, wenn All x,y:A.xRy=>yRx=>x=y
* transitiv, wenn All x,y,z:A.xRy=>yRz=>xRz

Besondere Bezeichnungen:

Quasiordnung: refl., trans.
partielle Ordnung: refl., trans., antisymm.
Aequivalenzrelation: refl., trans., symm.

Beispiele einer partiellen Ordnung: Teilbarkeit auf der Menge der natuerlichen Zahlen,

Beispiele fuer Aequivalenzrelationen: 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, heisst 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).

Eine Funktion von A x B nach C heisst zweistellige Funktion. Sie
ordnet jedem Paar (a,b) genau ein Element f(a,b):C zu. Beispiele fuer
zweistellige Funktionen sind die Addition + : R x R -> R und andere
Rechenoperationen.

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

Sei f:A->B eine Funktion.

Zeige All 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 (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 | Ex a:A. a:U /\ f(a)=b}

Ist V<=B so ist das Urbild f^(-1)(V) von V unter f definiert durch
 f^(-1)(V) = {a:A | f(a)=b}

Beispiel: f(x)=x^2+1. Das Bild von [0,oo] ist [1,oo]. Das Urbild von [2,oo] ist (-oo,-1] u [1,oo).

Zeige

U1<=U2 /\ U2<=A => f(U1)<=f(U2).
Wir nehmen an
U1<=U2 (H1)
U2<=A (H2)
Sei b:B f.a.b. und
b:f(U1) (H3).
Zeige b:f(U2).
Wir verwenden H3 /* hat die Form Ex a:A.a:U1/\f(a)=b*/.
Sei also c:A f.a.b. und
c:U1 (H4)
f(c)=b (H5). 
Aus H1 und H4 erhalten wir
c:U2 (H6).
aus H5 und H6 ergibt sich
Ex a:A.a:U2/\f(a)=b /* mit a:=c */
das aber ist b:f(U2)
QED

Surjektiv, Injektiv, Bijektiv
-----------------------------

Eine Funktion f:A->B heisst injektiv, wenn es zu jedem b:B hoechstens ein a:A mit f(a)=b gibt:

All a,a':A.f(a)=f(a') => a=a'

Eine Funktion f:A->B heisst surjektiv, wenn es zu jedem b:B mindestens ein a:A mit f(a)=b gibt:

All b:B.Ex a:A.f(a)=b

Eine Funktion f:A->B heisst 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 gleichviele. Man kann dann auch die Umkehrfunktion f^(-1):B->A definieren durch

f^(-1)(b) = "das eindeutig bestimmte a:A mit f(a)=b"

Dass es ueberhaupt immer ein Element mit f(a)=b gibt, ergibt sich aus
der Surjektivitaet; dass es eindeutig bestimmt ist, folgt aus der
Injektivitaet.


Isomorphie
----------

Seien R<=AxA und S<=BxB Relationen. Diese heissen *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)Sf(b).

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

In der Tat ist 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 Groesser-Gleich-Relation auf N
sind nicht isomorph: Sei R<=NxN definiert durch xRy <=> x<=y und sei S<=NxN definiert durch xSy <=> x>=y. 

Informeller Beweis durch Widerspruch: 

Es gibt ein Element a:N mit aRx fuer alle x (naemlich a=0). So ein Element gibt es aber nicht fuer S.

Formaler Beweis:

Zeige ~(Ex f:N->N."f bijektiv" /\ All x,y:N.xRy <=> f(x)Sf(y)).
Wir nehmen an Ex f:N->N."f bijektiv" /\ All x,y:N.xRy <=> f(x)Sf(y) (H)
Zeige Widerspruch.
Wir nehmen jetzt eine f.a.b. Funktion f:N->N an mit
f bijektiv (H1)
All x,y:N.xRy <=> f(x)Sf(y) (H2)
Wir verwenden H2 mit x=0, y=f^(-1)(f(0)+1) und erhalten
0 <= f^(-1)(f(0)+1) <=> f(0)>=f(0)+1. (H3)
Da aber 0<=f^(-1)(f(0)+1) folgt mit H3.1 auch f(0)>=f(0)+1, ein Widerspruch.
QED. 






Artikelaktionen


Funktionsleiste