Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 4.12.2000

§7 Endliche Mengen

\underline{(7.1) DEF:} M und N seien nichtleere Mengen.

a) M heißt gleichmächtig zu N (in Zeichen: M ∼ N), wenn es eine bijektive Abbildung M ⟶ N gibt.

b) M heißt endlich, wenn es ein n ∈ IN gibt mit M ∼ {1, 2, 3, …, n} ⊆ IN. n wird dann die Anzahl der Elemente von M genannt. Bezeichnung: n =: |M| .

c) Die leere Menge ist endlich mit | ∅ | = 0 .

d) Ist M nicht endlich, so heißt M unendlich (|M| = ∞).

\underline{(7.2) BEM:} a) IN ist eine unendliche Menge. Die Annahme, daß IN endlich ist, führt auf einen Widerspruch.

b) Eine Menge M heißt abzählbar unendlich, wenn es eine bijektive Abbildung M ⟶ IN gibt, wenn also M ∼ IN gilt. Die Mengen IN, IN_{0}, ZZ, Q sind alle abzählbar unendlich. Bei einer unendlichen Menge spricht man von der Kardinalzahl oder Mächtigkeit als Maß für die Größe dieser Menge. Die Kardinalzahl von IN wird mit ℵ_{0} bezeichnet (ℵ ist der erste Buchstabe des hebräischen Alphabets). Gleichmächtige Menge haben dieselbe Kardinalzahl. Es gilt | IN | = | IN_{0} | = | ZZ | = | Q| = ℵ_{0}. Es ist sicher überraschend, daß IN und ZZ dieselbe Mächtigkeit haben (der Beweis wurde in der Vorlesung angedeutet), obwohl IN eine echte Teilmenge von ZZ ist. Dagegen kann eine endliche Menge nie zu einer echten Teilmenge gleichmächtig sein. Daß IN und Q gleichmächtig sind, beweist man mit dem 2. Cantor’schen Diagonalverfahren.

c) Die Menge IR ist unendlich, es gibt aber keine Bijektion IR ⟶ IN. (Das läßt sich mit dem 1. Cantor’sches Diagonalverfahren beweisen.) Man sagt: IR hat eine größere Mächtigkeit als IN , oder IR ist überabzählbar. | IR | = ℵ_{1}. Die Kontinuumshypothese besagt, daß es zwischen ℵ_{0} und ℵ_{1} keine weitere Kardinalzahl gibt.

Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 8.12.2000

\underline{(7.3) SATZ:} a) M und N seien nichtleere Mengen, und f : M ⟶ N sei eine bijektive Abbildung. Dann gilt: M ist genau dann endlich, wenn N endlich ist. In beiden Fällen ist dann | M | = | N | .

b) Ist M endlich, so ist auch jede Teilmenge T ⊆ M endlich, und es gilt | T | ≤ | M | .

\underline{(7.4) SATZ:} Für endliche Mengen M und N gilt:

a) M ∪ N ist endlich und | M ∪ N | = | M | + | N | − | M ∩ N |

b) Im Falle M ∩ N = ∅ ist | M ∪ N | = | M | + | N | .

c) M ∩ N ist endlich und 0 ≤ | M ∩ N | ≤ min(| M |, | N |) .

d) Im Falle M ⊆ N ist N \ M endlich und | N \ M | = | N | − | M | .

e) M × N ist endlich und | M × N | = | M | × | N | .