Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Bijektion nachweisen

Bijektion nachweisen

Universität / Fachhochschule

Funktionen

Tags: Funktion Bijektion

Verstehnix aktiv_icon

15:57 Uhr, 20.01.2012

Halli Hallo,
ich habe eine Aufgabe bekommen bei der man die Bijektion nachweisen soll folgende Funktion musste von mir gebildet werden

f:MxN->

{

0...,mn-1}

(x, y) \to f (x) n + g (y)

wobei

m, n

in den natürlichen Zahlen liegen und

M

und

N

endliche Mengen sind

wie zeige ich jetzt das die Funktion injektiv bzw surjektiv ist ?

vielen dank im Vorraus

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Sina86

17:13 Uhr, 20.01.2012

Hallo,

gar nicht, die Funktion

f

ist nicht wohldefiniert und die Funktion

g

ist überhaupt nicht definiert. Da kannst du auch nichts zeigen.

Lieben Gruß
Sina

Verstehnix aktiv_icon

17:26 Uhr, 20.01.2012

oh da hab ich was vergessen zu schreiben ;-)
f(x)und

g (y)

ist definiert als

f (x) \to {0, ..., n - 1}

und

g (y) \to {0, ..., m - 1}

ich weiß wie injektivität und surjektivität definiert sind

surjektivität: wenn für alle b∈B : ein a∈A

: F (a) = b

gilt

injektivität: wenn für alle

a

,a´∈A

: a

≠a´dann f(a)≠f(a´)

aber leider nicht wie ich die Funktion da einbauen kann :$

Sina86

17:33 Uhr, 20.01.2012

???

Also das passt immer noch nicht. Zunächst einmal kannst du die Funktion in deinem ersten Beitrag

f : M \times N \to {0, . . ., m n - 1}

nicht

f

nennen, wenn ein offensichtlich anderes

f

in der Funktionsvorschrift vorkommt. Dann sind die Definitionen

f (x) \to {0, . . ., n - 1}

(und analog für

g

) keine Definitionen. Ich nehme mal an, das soll etwas sein wie

f : N \to {0, . . ., n - 1}

und

g : M \to {0, . . ., m - 1}

.

Aber auch das bringt dich nicht weiter. Sind nämlich z.B.

f, g

jeweils die Nullabbildung, dann ist auch

f (x) n + g (y) = 0

für alle

x

und

y

und damit ist deine Funktion nicht bijektiv.

Verstehnix aktiv_icon

14:41 Uhr, 21.01.2012

Dann versteh ich aber nicht wie ich die Aufgabe lösen soll ich schreib am besten nochmal alles was ich vorher gemacht hab auf ;

geg:

M

und

N

seien Mengen mit den Mächtigkeiten IMI=m∈ℕ und INI=n∈ℕ zzg. das IMxN=mn indem man eine Bijektion zwischen MxN und

{

0,...,mn-1} angibt

1.Zuordnungsvorschrift gebildet über lexicographische Ordnung

x 0 y 0 \to 0

x 0 y 1 \to 1

x0yn-1->n-1
.
.
.
xm-1y0->(m-1)*n
.
.
.
xm-1yn-1->((m-1)+1)*n =mn-1 (bis hier alles Richtig ? )

2.allgemein würde Sie dann lauten: xiyj->in+j
und daraus hab ich dann die funktiontherme gebildet
f(x)→

{

0,...,m-1} und g(y)→{0,...,n-1}

3.und die Funktion
f:IMxNI->

{

0...,mn-1} (x,y)→f(x)n+g(y)

bitte helft mir ich seh den Fehler nicht

; (

hagman aktiv_icon

15:07 Uhr, 21.01.2012

Aha. Also formulieren wir deine Angaben von oben mal etwas ausführlicher (und dadurch richtiger).
Nach Voraussetzung gibt es bijektive(!) Abbildungen

f : M \to {0, ..., m - 1}

und

g : N \to {0, ..., n - 1}

.
Wir definieren

h : M \times N \to {0, ..., m n - 1}, (x, y) \mapsto n \cdot f (x) + g (y)

. (Wie oben angemahnt, verwende für ein neues Objekt auch einen neuen Bezeichner!)

Zunächst ist zu zeigen, dass dies tatsächlich eine Abbildung nach

{0, ..., m n - 1}

ist!!
Wegen

f (x), g (y), n \in ℕ_{0}

ist zunächst stets auch

n \cdot f (x) + g (y) \in ℕ_{0}

. Ferner ist wegen

f (x) \leq m - 1

und

g (x) \leq n - 1

stets

h (x, y) \leq n \cdot (m - 1) + (n - 1) = n \cdot m - 1

. Somit ist dieser Punkt schon einmal erledigt.

Ist diese Abbildung

h

injektiv?
Es sei

h (x_{1}, y_{1}) = h (x_{2}, y_{2}),

also

n \cdot f (x_{1}) + g (y_{1}) = n \cdot f (x_{2}) \cdot g (y_{2})

. Darf die gesamte Arithmetik aus

ℤ

verwendet werden oder müsst ihr euch noch sehr nah an den Peanoaxiomen auf

ℕ

hindurchhangeln? Im erstgenannten Fall ergibt sich jedenfalls

n \cdot (f (x_{1}) - f (x_{2})) = g (y_{2}) - g (y_{1})

. Die linke Seite ist ein Vielfaches von

n,

also auch die rechte. Andererseits liegt die rechte Seite zwischen

- (n - 1)

und

n - 1

einschließlich. Es folgt, dass

g (y_{2}) - g (y_{1}) = 0,

also wegen der Injektivität von

g

schon einmal

y_{1} = y_{2}

ist. Dann ist weiter

n \cdot (f (x_{1}) - f (x_{2})) = 0,

also

f (x_{1}) - f (x_{2}) = 0

oder

n = 0

. Im ersten Fall ergibt sich

x_{1} = x_{2}

per Injektivität von

f

und wir sind fertig, denn wir haben

(x_{1}, y_{1}) = (x_{2}, y_{2})

gezeigt.
Den Fall

n = 0

behandeln wir lienber insgesamt gesondert weiter unten.

Ist die Abbildung

h

surjektiv?
Sei

z \in {0, . ., n m - 1}

. Betrachte zunächst wiederum den Fall

n \neq 0

. Dann gibt es per Division mit Rest eine Zahl

q \in ℤ

und

r \in {0, ..., n - 1}

mit

z = q \cdot n + r

. Hierbei ist

q \geq 0,

denn

q < 0

bedeutet

q \leq - 1,

also

z = q \cdot n + r \leq - n + (n - 1) < 0

im Widerspruch zu

z \geq 0

. Andererseits ist

q \leq m - 1,

denn

q > m - 1

bedeutet

q \geq m,

also

z = q \cdot n + r \geq n \cdot m + 0

im Widerspruch zu

z \leq n m - 1

. Mithin ist

q \in {0, ..., m - 1}

. Nach Voraussetzung gibt es

x \in M, y \in N

mit

f (x) = q

und

f (y) = r

. Es folgt

h (x, y) = n \cdot f (x) + g (y) = n \cdot q + r = z

.
Auch hier mussten wir zunächst den Fall

n = 0

ausklammern.

Was ergibt sich denn im Fall

n = 0

?
Der Fall bedeutet

N = \emptyset

und es ist zu zeigen, dass

| M \times \emptyset | = 0,

mit anderen Worten

M \times \emptyset = \emptyset

.
Das ist aber direkt klar, denn ein Element

z \in M \times \emptyset

hat ja per Definition die Form

z = (x, y)

mit

x \in M

und

y \in \emptyset

. Da es aber gar kein

y \in \emptyset

gibt, kann es auch kein

z \in M \times \emptyset

geben,

d . h

M \times \emptyset

ist die leere Menge

Verstehnix aktiv_icon

15:31 Uhr, 21.01.2012

zuerst vielen Dank hagman für deine schnelle und sehr ausführliche antwort

zitat(hagman):
Darf die gesamte Arithmetik aus ℤ verwendet werden oder müsst ihr euch noch sehr nah an den Peanoaxiomen auf ℕ hindurchhangeln?

Ja wir dürfen leider bisher nur mit den Peanoaxiomen arbeiten ,was bedeutet das für meine Beweisführung?

hagman aktiv_icon

19:43 Uhr, 21.01.2012

Oooookay.
Das bedeutet, dass man nicht so einfach mit

f (x_{1}) - f (x_{2})

usw. arbeiten darf, denn (möglicherweise) negative Zahlen gibt es für euch sozusagen noch nicht.
Aber oBdA ist

f (x_{1}) \geq f (x_{2}),

also

f (x_{1}) = f (x_{2}) + d

mit

d \in ℕ_{0}

.
Dann

n \cdot f (x_{1}) + g (y_{1}) = n \cdot f (x_{2}) + g (y_{2})

\Rightarrow n \cdot (f (x_{2}) + d) + g (y_{1}) = n \cdot f (x_{2}) + g (y_{2})

\Rightarrow n \cdot d + g (y_{1}) = g (y_{2})

Wenn

d \geq 1

ist links

\geq n,

aber rechts

\leq n - 1

. Also folgt

d = 0, d . h

. zunächst direkt

f (x_{1}) = f (x_{2})

und somit

x_{1} = x_{2}

.
Ferner

n \cdot 0 + g (y_{1}) = g (y_{2}),

also

g (y_{1}) = g (y_{2})

und somit

y_{1} = y_{2}

Verstehnix aktiv_icon

19:19 Uhr, 22.01.2012

ich glaub ich verstehs langsam, ich danke dir hagman .

Verstehnix aktiv_icon

19:19 Uhr, 22.01.2012

ich glaub ich verstehs langsam, ich danke dir hagman .

966032

965134

	Status: nicht eingeloggt	Noch nicht registriert?