Mathematische Grundlagen

Abbildung

 aufwärts

Abbildungen sind spezielle zweistellige Relationen. Während eine Relation eine völlig beliebige Teilmenge eines kartesischen Produktes ist, werden an eine Abbildung zwei bestimmte Bedingungen gestellt. Dies kommt in der folgenden Definition zum Ausdruck.

Definition

Definition:  Seien A und B Mengen. Eine Abbildung ist eine Relation f enthalten in A × B mit den folgenden Eigen­schaften (1) und (2). Wegen der Gültigkeit dieser Eigen­schaften ist bei Abbildungen folgende Schreibweise üblich:

f : A Pfeil nach rechts B statt f enthalten in A × B und
f(a) = b statt (a, bElement f. 

Die Menge A wird in die Menge B abgebildet. Jedes Element a Element A wird auf irgendein Element b Element B abgebildet, dabei heißt b das Bild von a unter der Abbildung f.

 

Die folgende Eigenschaft (1) besagt, dass wenn zwei Elemente gleich sind, auch die ent­sprechenden Bilder gleich sind. Kein Element wird also gleichzeitig auf zwei verschiedene Bilder abgebildet, das Bild ist immer eindeutig.

(1) eindeutig  für alle a, a' Element A :   a = a'    folgt  f(a) = f(a')

 

eindeutig
(von jedem Punkt geht höchstens ein Pfeil aus)

 

Eigenschaft (2) besagt, dass jedes Element a Element A ein Bild hat.

(2) total definiert  für alle a Element A   es existiert b Element B :   f(a) = b

 

total definiert
(von jedem Punkt geht mindestens ein Pfeil aus)

 

(1) und (2) zusammen ergeben: von jedem Punkt geht genau ein Pfeil aus (die Abbildung ist wohl­definiert). Eine Relation, die nur (1) erfüllt, wird als partielle Abbildung bezeichnet.

 

(1) + (2) Abbildung

 

Abbildung
(von jedem Punkt geht genau ein Pfeil aus)

Genau wie eine Relation ist also eine Abbildung nichts anderes als eine Menge von Paaren, die allerdings die genannten Bedingungen (1) und (2) erfüllen muss. Ein anderes Wort für Abbildung ist Funktion. Gelegentlich trifft man auf Formulierungen wie "die Funktion y = 3x2 ". Gemeint ist hierbei "die Funktion mit der Funktions­gleichung y = 3x2 ", und dies ist die Menge { (x, y)  |  y = 3x2}, also die Menge aller Paare (x, y), die der Funktions­gleichung genügen.

Injektitiv, surjektiv, bijektiv

Definition:  Sei f : A Pfeil nach rechts B eine Abbildung, d.h. f erfüllt (1) und (2). Die Abbildung f heißt injektiv, wenn f die folgende Eigenschaft (3) hat; f heißt surjektiv, wenn f die folgende Eigenschaft (4) hat; f heißt bijektiv, wenn f beide Bedingungen (3) und (4) erfüllt.

 

Die folgende Eigenschaft (3) besagt, dass wenn zwei Elemente verschieden sind, auch die ent­sprechenden Bilder verschieden sind.

(3) injektiv  für alle a, a' Element A :   a ≠ a'  folgt  f(a) ≠ f(a')

 

injektiv
(bei jedem Punkt kommt höchstens ein Pfeil an)

 

Eigenschaft (4) besagt, dass jedes Element b Element B ein Bild ist (d.h. ein Urbild hat).

(4) surjektiv  für alle b Element B   es existiert a Element Af(a) = b

 

surjektiv
(bei jedem Punkt kommt mindestens ein Pfeil an)

 

(3) und (4) zusammen ergeben: bei jedem Punkt kommt genau ein Pfeil an (die Abbildung ist bijektiv). Dies bedeutet, dass die inverse Relation f -1 der Abbildung f auch eine Abbildung ist (sogar ebenfalls eine bijektive Abbildung).

 

(3) + (4) bijektiv

 

bijektiv
(bei jedem Punkt kommt genau ein Pfeil an)

 

Tatsächlich wissen schon kleine Kinder, was eine bijektive Abbildung ist. Beim Zählen nämlich kommt es darauf an, eine bijektive Abbildung herzustellen zwischen der Menge der Gegenstände, die gezählt werden sollen, und der Menge {1, ..., n} (vergl. nächster Abschnitt: Mächtigkeit einer Menge). Sollen beispiels­weise Stofftiere gezählt werden, so stellt das Kind die Abbildung her, indem es unter Beachtung der Bedingungen (1) bis (4) jeweils auf ein Stofftier zeigt und dabei eine Zahl sagt.

Ganz kleine Kinder, die noch nicht richtig zählen können, verletzen regelmäßig mindestens eine der Bedingungen (1) bis (4). So zeigt das Kind etwa mehrfach auf ein Stofftier oder vergisst eines. Oder es zeigt zwar auf alle Stofftiere, sagt dabei aber die Zahlen "1, 2, 2, 3, 4". Oder es sagt die Zahlen "1, 2, 5, 6, 8".

Mächtigkeit

Definition:  Die Mächtigkeit |A| einer Menge A ist wie folgt definiert:

|A|  =   geschweifte Klammer
0    falls A =  leere Menge ,
n Element natürliche Zahlen      falls es eine bijektive Abbildung  f : {1, ..., nDoppelpfeil A  gibt,
0    falls es eine bijektive Abbildung  f : natürliche Zahlen Doppelpfeil A  gibt,
Mächtigkeit des Kontinuums    falls es eine bijektive Abbildung  f : reelle Zahlen Doppelpfeil A  gibt.

Eine Menge mit der Mächtigkeit n Element natürliche Zahlen0 heißt endliche Menge. Bei endlichen Mengen ist die Mächtigkeit gleich der Anzahl der Elemente. Eine Menge, die nicht endlich ist, heißt unendliche Menge.

Bei unendlichen Mengen kann man den Begriff der Mächtigkeit nicht mehr anschaulich mit der Anzahl der Elemente verbinden. So sind etwa die Mengen natürliche Zahlen und ganze Zahlen gleich mächtig, obwohl natürliche Zahlen anschaulich "weniger" Elemente enthält als ganze Zahlen. Andererseits sind auch wieder nicht alle unendlichen Mengen gleich mächtig.

Definition:  Zwei Mengen A und B sind gleich mächtig, wenn es eine bijektive Abbildung zwischen ihnen gibt:

|A| = |B|  genau dann wenn   es existiert  bijektive Abbildung  f : A Doppelpfeil B

 

Offenbar gibt es eine bijektive Abbildung zwischen natürliche Zahlen und ganze Zahlen, etwa gemäß folgender Wertetabelle:

1234567...
01-12-23-3...

 

Andererseits gibt es keine bijektive Abbildung zwischen den unendlichen Mengen natürliche Zahlen und reelle Zahlen, daher sind diese beiden Mengen nicht gleich mächtig. Es gibt also offenbar verschiedene Grade des Unendlichen.

Die Mächtigkeit ℵ0 wird als abzählbar unendlich bezeichnet. Eine Menge ist abzählbar unendlich, wenn sie gleich mächtig zu den natürlichen Zahlen ist. Die Bezeichnung ℵ0 geht auf Cantor zurück. Das Zeichen ℵ (aleph) ist der erste Buchstabe des hebräischen Alphabets. Die Mächtigkeit ℵ0 ist die kleinste Mächtigkeit, die eine unendliche Menge haben kann.

Eine Menge, die entweder endlich oder abzählbar unendlich ist, wird als abzählbar bezeichnet. Offenbar ist eine Menge M abzählbar, wenn es eine surjektive Abbildung von natürliche Zahlen auf M gibt.

 

Eine unendliche Menge, die nicht abzählbar unendlich ist, wird als über­abzählbar unendlich bezeichnet. So ist beispiels­weise reelle Zahlen über­abzählbar unendlich. Das Zeichen Mächtigkeit des Kontinuums bedeutet "Mächtigkeit des Kontinuums".

Beispiel:  Einige Beispiele für die Mächtigkeit von Mengen:

| {1, 2, 5, 7} |  =  4

| {2, 4, 6, 8, ... } |  =  ℵ0

|ganze Zahlen|  =  ℵ0

|rationale Zahlen|  =  ℵ0

| [0,1] |  =  Mächtigkeit des Kontinuums

|komplexe Zahlen|  =  Mächtigkeit des Kontinuums

|reelle Zahlenn|  =  Mächtigkeit des Kontinuums

|Potenzmenge(natürliche Zahlen)|  =  Mächtigkeit des Kontinuums

Folge

Definition:  Sei A eine Menge. Unter einer Folge versteht man eine Abbildung

anatürliche Zahlen0 Pfeil nach rechts A.

Eine endliche Folge ist eine Abbildung

a :  {0, ..., n-1} Pfeil nach rechts A,   n Element natürliche Zahlen0.

Hierbei ist n die Länge der endlichen Folge.

Wir schreiben endliche Folgen so: a = a0, ..., an-1. Endliche Folgen lassen sich auch als n-Tupel (a0, ..., an-1) auf­fassen, d.h. als Elemente des kartesischen Produktes An.

Permutation

Definition:  Eine Permutation ist eine bijektive Abbildung

p :  {0, ..., n-1} Pfeil nach rechts {0, ..., n-1},   n Element natürliche Zahlen.

Beispiel:  Die endliche Folge  p = 4, 1, 2, 0, 3  ist eine Permutation.

Literatur

Bücher

 

Weiter mit:   [Graph]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 15.04.2014   Updated: 21.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik