Mengenlehre

Objekt X gehört zur Menge

Leere Menge

N := {0,1,2,3,4,5,…}

0 nur bei Informatik

Q := {p/q | p ∈ Z, q ∈ Z, q≠0}

Objekt X gehört nicht zur Menge M

P := {n ∈ N | n>=2, n ist nur durch 1 und n teilbar}

Für zwei Objekte x und y sei (x,y) das geordnete Paar, bestehend aus x und y.

Es zeichnet sich durch die Eigenschaft (x,y) = (x´,y´) genau dann, wenn (x = x´und y = y´) aus.

Kurtowsky definierte das geordnete Paar als (x,y) := {x,{x,y}}

Für Objekte x1, x2,...,xn (n>=3) definieren wir dann das n-Tupel (x1,x2,...,xn) := (x1,(x2,...,xn)) ← n-1 Einträge

• (1,2) = {1,{1,2}}

• (3,2,1) = (3,(2,1)) = {3,{3,(2,1)}} = {3,{3,{3,{1,2}}}}

{(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)}

A ist Teilmenge von B (⊆)

= {1,2}

A ist die “echte Teilmenge” von B

-> beide Mengen sind ungleich

= {1}

Potenzenge von A

-> Menge aller Teilmengen, die man mit den Elementen einer Menge bilden kann

Schnitt von A und B

-> Menge in A und zugleich in B enthalten sind

{2}

Vereinigung von A und B

-> Menge aller Elemente, die in A oder in B oder in beiden Mengen enthalten sind

{1,2,3,4,5,6}

Z := {…,-2,-1,0,1,2,…}

• ist die Menge aller Elemente, die zu A aber nicht zu B gehören

-> {1}

A u B = ø (Leere Menge)

-> Zwei Mengen sind disjunkt, wenn sie kein gemeinsames Element besitzen

Relation von A nach B

f ⊆ A x B, so dass für alle a ∈ A genau ein b ∈ B mit (a,b) ∈ f existiert. Wir schreiben f(a) = b

B^A ist die Menge aller Funktionen von A nach B

• ∀a, b ∈ A : a ≠ b → f (a) ≠ f (b)

• d.h. verschiedene Elemente werden auf verschiedene Elemente abgebildet

  
  

f^-1(x) = (x-2)/2

f(1)=4

f^-1(4)=1

f(x) = Bild

f^-1(x) = Urbild

• ∀b ∈ B ∃a ∈ A : f (a) = b

• d.h. jedes Element aus B wird durch f getroffen. Äquivalent: f(A) = B

• sie injektiv und surjektiv ist

• Wir sagen auch, dass f eine Bijektion ist

  • Bijektion f: A → B ist eine 1 zu 1 Zuordnung zwischen den Elementen A und B

eine Bijektion f: A -> A

eine Bijektion f: A-> B existiert

N und Z

N, N x N und Q

|A| = |B| genau dann, wenn (|A| ≤ |B| und |B| ≤ |A|)

Für jede Menge A sind A und 2^A nicht gleichmächtig

|A|=|N| gilt

A endlich oder abzählbar-unendlich ist

unendlich aber nicht abzählbar ist

Für jede unendliche Teilmenge von A ⊆ 2^N gilt |A| = |N| oder |A| = |2^N|.

a Relation b

Relation R ⊆ A × A und a, b ∈ A

aRa für alle a ∈ A gilt

kein a ∈ A mit aRa existiert

für alle a,b ∈ A gilt: aRb impliziert bRa

falls ∀ a,b ∈ A: aRb ∧ ba → a = b

falls ∀ a, b, c ∈ A : aRb ∧ bRc → aRc

R reflexiv, antisymmetrisch und transitiv ist

aRb oder bRa

R reflexiv, symmetrisch und transitiv ist.

• Für jede Menge A ist die Relation

  • IdA := {(a,a) | a ∈ A}

    • reflexiv, symmetrisch und transitiv. Insbesondere ist IdA eine Äquivalenzrelation

Für jede Menge A ist die Relation TA := A x A (die Klumpenrelation) reflexiv, symmetrisch und transitiv. Insbesondere ist sie eine Äquivalenzrelation.

Sei f: A → B eine Funktion. Dann ist Rf := {(a1,a2} ∈ A x A | f(a1) = f(a2)} eine Äquivalenzrelation, die sogenannte Bildgleichheitsäquivalenzrelation

Sei q ∈ Z eine ganze Zahl.

Auf der Menge Z definiert wir die binäre Relation auf Z

≡q := {(a,b) | a, b ∈ Z, q | (a−b)} ⊆ Z × Z

Sprechweise für a ≡q b: a und b sind kongruent modulo q.

Es gilt a ≡q b genau dann, wenn eine ganze Zahl x ∈ Z mit

a= x · q + b existiert.

Beachte: a ≡q b genau dann, wenn a ≡-q b

Für jede Zahl q ∈ Z ist ≡q eine Äquivalenzrelation auf Z

Sei R eine Äquivalenzrelation auf der Menge A und sei a ∈ A. Dann ist [a]R = {b ∈ A | aRb} die Äquivalenzklasse von a (bezüglich R)

• Beachte: Es gilt stehts a ∈ [a]R (denn eine Äquivalenzrelation ist reflexiv)

• Eine Äquivalenzklasse kann also nie leer sein, und jedes Element von A gehört zu einer Äquivalenzklasse

Sei R eine Äquivalenzrelation auf der Menge A und seien a, b ∈ A. Dann sind folgende drei Aussagen äquivalent:

1. aRb

2. [a]R = [b]R

3. [a]R ∩ [b]R ≠∅

R^-1 = {(b,a) ∈ B x A | (a,b) ∈ R}

R^-1 heißt die Umkehrfunktion von R

R ◦ S = {(a,c) ∈ A x C | ∃b ∈ B : (a,b) ∈ R und (b,c) ∈ S}

R ◦ S heißt die Komposition oder Verknüpfung von R und S