Die Mathe-Redaktion - 14.12.2017 09:01 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 588 Gäste und 18 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Mengenlehre » Abzählbarkeit, Surjektion, Injektion
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Abzählbarkeit, Surjektion, Injektion
tehtacolord
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.11.2016
Mitteilungen: 85
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-11-18 22:32


Hallo zusammen,

gezeigt werden sollen folgende Aussagen:

a) Es sein X eine abzählbare Menge und f: X->Y eine surjektive Abbildung.
Zeigen Sie, dass dann auch Y abzählbar ist.

b) |N x |N ist abzählbar
(Kreuzprodukt der natürlichen Zahlen mit sich selbst)

c) Seien x1 und x2 abzählbare Mengen. Dann ist auch x1 X x2 abzählbar.

d) Q ist abzählbar. (Die Menge der rationalen Zahlen)


Meine Ansätze dabei:

d) Ist mittels cantorschem Diagonalverfahren recht simpel zu zeigen,um die Surjektion von |N -> Q zu zeigen. daher ist meine Überlegung, dass das mit b) möglicherweise ebenfalls so geht. Kann das einer bestätigen?

Zu a) und c) habe ich keine Ahnung, wäre einer so freundlich mir hilfreiche Hinweise in die richtige Richtung zu geben?


Vielen Dank schonmal vorab!



  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 3158
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-11-18 22:38


Eine Menge <math>X</math> heißt abzählbar (manche Autoren sagen: höchstens abzählbar), wenn es eine surjektive Abbildung <math>\mathds{N} \to X</math> gibt. Damit ist a) klar, man verkettet einfach die beiden surjektiven Abbildungen. Bei b) verwendet man das Diagonalverfahren. Bei c) wähle zwei surjektive Abbildungen <math>\mathds{N} \to X_1</math>, <math>\mathds{N} \to X_2</math>. Daraus ergibt sich eine surjektive Abbildung <math>\mathds{N} \times \mathds{N} \to X_1 \times X_2</math>. Nun verwendet man b) und a). Schließlich folgt d) aus c) und a): Verwende dafür eine surjektive Abbildung <math>\mathds{Z} \times \mathds{N}^+ \to \mathds{Q}</math>. Fazit: Es baut alles schön aufeinander auf.



  Profil  Quote  Link auf diesen Beitrag Link
tehtacolord
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.11.2016
Mitteilungen: 85
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2017-11-18 22:48


Besten Dank, ist ja doch noch einfacher als ich gedacht habe :^)




  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2017-11-18 22:54


2017-11-18 22:32 - tehtacolord im Themenstart schreibt:
Hallo zusammen,

gezeigt werden sollen folgende Aussagen:

a) Es sein X eine abzählbare Menge und f: X->Y eine surjektive Abbildung.
Zeigen Sie, dass dann auch Y abzählbar ist.


b) |N x |N ist abzählbar (Kreuzprodukt der natürlichen Zahlen mit sich selbst)

Vielen Dank schonmal vorab!


Wenn X abzählbar ist, und man bildet alle oder ein Teil von X nach Y ab, dann muss ja jedes Element y in Y mindestens 1 mal getroffen werden, also Bild eines x sein. Dann ist Y gleich gross oder kleiner als X, da ja jedes Element in Y getroffen wird. Es gibt kein y in Y das nicht ein Bild von eines x aus X ist, wg. Surjektivität. Damit ist Y abzählbar.

b) |N| x |N| ist Q sehr ähnlich, aber kleiner als Q. Alle positiven ungekürzten Brüche lassen sich bijektiv auf |N| x |N| abbilden, meine ich.
c) is dann mit geklärt.


[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 1017
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2017-11-18 23:04



b) |N| x |N| ist Q sehr ähnlich, aber kleiner als Q. Alle positiven ungekürzten Brüche lassen sich bijektiv auf |N| x |N| abbilden, meine ich.

Wenn es eine Bijektion <math>\mathbb{N}\times\mathbb{N}\to\mathbb{Q}</math> gibt, dann sind die Mengen gleichmächtig. (Oder in einem gewissen Sinne gleich groß)

Edit: Ich sehe gerade, dass ich zu erst falsch gelesen habe.
Du sagst ja, dass sich alle positiven ungekürzten Brüche sich bijektiv auf <math>\mathbb{N}\times\mathbb{N}</math> abbilden lassen.
So allgemein muss es aber gar nicht gemacht werden.
Man kann ganz <math>\mathbb{Q}</math> bijektiv auf <math>\mathbb{N}\times\mathbb{N}</math> abbilden und nicht nur die positiven ungekürzten Brüche.



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2017-11-18 23:57


2017-11-18 23:04 - PrinzessinEinhorn in Beitrag No. 4 schreibt:

b) |N| x |N| ist Q sehr ähnlich, aber kleiner als Q. Alle positiven ungekürzten Brüche lassen sich bijektiv auf |N| x |N| abbilden, meine ich.

Wenn es eine Bijektion <math>\mathbb{N}\times\mathbb{N}\to\mathbb{Q}</math> gibt, dann sind die Mengen gleichmächtig. (Oder in einem gewissen Sinne gleich groß)

Edit: Ich sehe gerade, dass ich zu erst falsch gelesen habe.
Du sagst ja, dass sich alle positiven ungekürzten Brüche sich bijektiv auf <math>\mathbb{N}\times\mathbb{N}</math> abbilden lassen.
So allgemein muss es aber gar nicht gemacht werden.
Man kann ganz <math>\mathbb{Q}</math> bijektiv auf <math>\mathbb{N}\times\mathbb{N}</math> abbilden und nicht nur die positiven ungekürzten Brüche.

Hmm sehr gut !
<math>\mathbb{Z}\times\mathbb{Z}</math> kann man mit Digonalverfahren Kantor auf ganz Q abbilden.
Ein surjektive Abbildung nach <math>\mathbb{N}\times\mathbb{N}</math> ist durch ignorieren des minus zu bilden, aber das wär nicht injektiv.
Aber wie negative r aus Q nach <math>\mathbb{N}\times\mathbb{N}</math> eineindeutig abbilden ? Du meinst, es gibt auch für negative <math>q \in Q</math> ein <math>f:q \mapsto (n,m) \in \mathbb{N}\times\mathbb{N}</math> ?
und kein anderes positives <math>r \in Q \mapsto (n,m) \in \mathbb{N}\times\mathbb{N}</math>.
Es müsste f derart sein, dass aus <math>f(q)=f(r) \Rightarrow q =r</math>.



  Profil  Quote  Link auf diesen Beitrag Link
tehtacolord
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.11.2016
Mitteilungen: 85
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2017-11-22 12:53


Eine erneute Frage hätte ich:

Wie weit geht der Beweis mittels Diagonalisierung i.d.R.?
Genügt es für formale Korrektheit das "Abzählschema" der diagonal notierten Paare (n,m) aus NxN zu zeigen oder sollte zusätzlich eine surjektive Abbildung N-> NxN gefunden werden?

Im Prinzip sollte es doch genügen zu argumentieren, dass entlang des "Abzählpfades" jedes Element aus NxN EXAKT ein mal gezählt wird und dadurch eine Bijektion entsteht.

2017-11-18 22:38 - Triceratops in Beitrag No. 1 schreibt:
E Bei c) wähle zwei surjektive Abbildungen <math>\mathds{N} \to X_1</math>, <math>\mathds{N} \to X_2</math>. Daraus ergibt sich eine surjektive Abbildung <math>\mathds{N} \times \mathds{N} \to X_1 \times X_2</math>. Nun verwendet man b) und a). </math>.

Mir ist nicht ganz klar weshalb aus der Surjektivität von N->X und N->Y die Surjektivität von NxN->XxY ergibt. Könntest du dazu ausführen?



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2017-11-22 16:28

\(\begingroup\)
2017-11-22 12:53 - tehtacolord in Beitrag No. 6 schreibt:
Eine erneute Frage hätte ich:

Wie weit geht der Beweis mittels Diagonalisierung i.d.R.?
Genügt es für formale Korrektheit das "Abzählschema" der diagonal notierten Paare (n,m) aus NxN zu zeigen oder sollte zusätzlich eine surjektive Abbildung N-> NxN gefunden werden?

Im Prinzip sollte es doch genügen zu argumentieren, dass entlang des "Abzählpfades" jedes Element aus NxN EXAKT ein mal gezählt wird und dadurch eine Bijektion entsteht.

2017-11-18 22:38 - Triceratops in Beitrag No. 1 schreibt:
E Bei c) wähle zwei surjektive Abbildungen <math>\mathds{N} \to X_1</math>, <math>\mathds{N} \to X_2</math>. Daraus ergibt sich eine surjektive Abbildung <math>\mathds{N} \times \mathds{N} \to X_1 \times X_2</math>. Nun verwendet man b) und a). </math>.

Das Cantorverfahren ist hier
de.wikipedia.org/wiki/Cantors_erstes_Diagonalargument
sehr gut erklärt.

Das ist ja in sich die Definition einer surjektiven Abbildung ohne explizite Formel. Die liefert  \(N X N \mapsto Q^+ \)

Man kann sicher eine passende Formel finden.

Weiter heisst es :
"Um die Gleichmächtigkeit aller rationalen Zahlen und der natürlichen Zahlen zu zeigen, erweitert man diese Abzählung."

Man erhält dann: \(N X N \mapsto Q \)


Mir ist nicht ganz klar weshalb aus der Surjektivität von N->X und N->Y die Surjektivität von NxN->XxY ergibt. Könntest du dazu ausführen?

Wenn die beiden Abbildungen N->X , N ->Y surjektiv sind also alle x in X bzw. alle y in Y getroffen werden also Bilder sind, dann auch alle Paare (x,y) aus (X,Y) mein ich. Das ist aber kein astreiner Beweis. sag ich mal selbstkritisch. wink
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 3158
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2017-11-22 16:41

\(\begingroup\)
@tehtacolord:

b) Das Diagonalverfahren ist eine bijektive Abbildung $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$. Sie lässt sich auch explizit hinschreiben als $(x,y) \mapsto x+\frac{(x+y)(x+y+1)}{2}$.

c) Seien $f_1 : X_1 \to Y_1$ und $f_2 : X_2 \to Y_2$ surjektiv. Dann ist auch $f_1 \times f_2 : X_1 \times X_2 \to Y_1 \times Y_2$, also die Abbildung $(x_1,x_2) \mapsto (f_1(x_1),f_2(x_2))$ surjektiv. Der Beweis dafür ergibt sich automatisch. Was ich mit "automatisch" meine, steht z.B. hier: article.php?sid=1805

Probiere es einmal und zeige uns deine Fortschritte.

Ein gut gemeinter Rat: Die Beiträge von juergen007 besser nicht lesen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2017-11-22 17:04

\(\begingroup\)
2017-11-22 16:41 - Triceratops in Beitrag No. 8 schreibt:
b) Das Diagonalverfahren ist eine bijektive Abbildung $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$.
Du meintest $\mathbb{N} \times \mathbb{N} \to \mathbb{Q^+}$. ?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
BerndLiefert
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 21.10.2014
Mitteilungen: 261
Aus: Lehramtplanet
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2017-11-22 17:21

\(\begingroup\)
2017-11-22 17:04 - juergen007 in Beitrag No. 9 schreibt:
2017-11-22 16:41 - Triceratops in Beitrag No. 8 schreibt:
b) Das Diagonalverfahren ist eine bijektive Abbildung $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$.
Du meintest $\mathbb{N} \times \mathbb{N} \to \mathbb{Q^+}$. ?
Nein. Schau dir die Abbildung an...
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2017-11-22 17:52

\(\begingroup\)
2017-11-22 17:21 - BerndLiefert in Beitrag No. 10 schreibt:
2017-11-22 17:04 - juergen007 in Beitrag No. 9 schreibt:
2017-11-22 16:41 - Triceratops in Beitrag No. 8 schreibt:
b) Das Diagonalverfahren ist eine bijektive Abbildung $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$.
Du meintest $\mathbb{N} \times \mathbb{N} \to \mathbb{Q^+}$. ?
Nein. Schau dir die Abbildung an...
Ja hmm es gibt beide...
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2017-11-23 00:11

\(\begingroup\)
2017-11-22 17:52 - juergen007 in Beitrag No. 11 schreibt:
2017-11-22 17:21 - BerndLiefert in Beitrag No. 10 schreibt:
2017-11-22 17:04 - juergen007 in Beitrag No. 9 schreibt:
2017-11-22 16:41 - Triceratops in Beitrag No. 8 schreibt:
b) Das Diagonalverfahren ist eine bijektive Abbildung $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$.
Du meintest $\mathbb{N} \times \mathbb{N} \to \mathbb{Q^+}$. ?
Nein. Schau dir die Abbildung an...
Ja hmm es gibt beide...


ich will meine Sichtweise erklären, obwohl ich es nicht muss.
Wir bilden Paare natürlicher Zahlen (n,m), m <>0, kanonisch auf \(\frac{n}{m}\) ab. Diese Abbildung ist nicht injektiv aber surjektiv. Es werden auch mehrfach kürzbare Brüche, aber alle möglichen erzielt: Surjektiv nicht injektiv.
Dann werden diese Brüche in gewisser Weise nummeriert, wobei kürzbare übersprungen werden.
Dann haben wir $NxN \mapsto \mathbb{Q^+} \mapsto N$. Zusammen genommen haben wir dann $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$, Bijektiv. Ich diskutiere das gerne hier, mit dere Möglichkeit des Irrtums allerseitens. Aber bitte von Pöbel- PMs abzusehen. Denn das ist Feigheit.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
BerndLiefert
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 21.10.2014
Mitteilungen: 261
Aus: Lehramtplanet
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2017-11-23 00:30

\(\begingroup\)
2017-11-23 00:11 - juergen007 in Beitrag No. 12 schreibt:
2017-11-22 17:52 - juergen007 in Beitrag No. 11 schreibt:
2017-11-22 17:21 - BerndLiefert in Beitrag No. 10 schreibt:
2017-11-22 17:04 - juergen007 in Beitrag No. 9 schreibt:
2017-11-22 16:41 - Triceratops in Beitrag No. 8 schreibt:
b) Das Diagonalverfahren ist eine bijektive Abbildung $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$.
Du meintest $\mathbb{N} \times \mathbb{N} \to \mathbb{Q^+}$. ?
Nein. Schau dir die Abbildung an...
Ja hmm es gibt beide...


ich will meine Sichtweise erklären, obwohl ich es nicht muss.
Wir bilden Paare natürlicher Zahlen (n,m), m <>0, kanonisch auf \(\frac{n}{m}\) ab. Diese Abbildung ist nicht injektiv aber surjektiv. Es werden auch mehrfach kürzbare Brüche, aber alle möglichen erzielt: Surjektiv nicht injektiv.
Dann werden diese Brüche in gewisser Weise nummeriert, wobei kürzbare übersprungen werden.
Dann haben wir $NxN \mapsto \mathbb{Q^+} \mapsto N$. Zusammen genommen haben wir dann $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$, Bijektiv. Ich diskutiere das gerne hier, mit dere Möglichkeit des Irrtums allerseitens. Aber bitte von Pöbel- PMs abzusehen. Denn das ist Feigheit.

Danke, dass du deine Sichtweise erklärt hast, obwohl du das nicht musstest.
Auch ich bitte von Pöbel-PMs abzusehen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2017-11-25 03:57

\(\begingroup\)
2017-11-22 16:41 - Triceratops in Beitrag No. 8 schreibt:
@tehtacolord:

b) Das Diagonalverfahren ist eine bijektive Abbildung $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$. Sie lässt sich auch explizit hinschreiben als $(x,y) \mapsto x+\frac{(x+y)(x+y+1)}{2}$.

Nicht ganz.
www.mathepedia.de/Bijektion.aspx

"Eine Abbildung f:A→B heißt Bijektion oder bijektive Abbildung genau dann, wenn f injektiv und surjektiv ist. Damit ist f eine eineindeutige Auf-Abbildung. Jedem Element aus A wird genau ein Element aus B zugeordnet und alle Elemente aus B kommen als Bilder vor."

Was hier nicht der Fall ist, da durch f nicht jedem Paar aus $\mathbb{N} \times \mathbb{N}$ ein Element aus N zugeordent wird, da wir kürzbare Paare überspringen. Dieses f ist nicht linkstotal also nicht injektiv.
r:$\mathbb{N} \times \mathbb{N} \to \mathbb{B}$, wobei ich mit B alle entstehenden Brüche meine, ist eine Bijektion.
$q:\mathbb{N} \times \mathbb{N} \to \mathbb{Q^+}$ ist auch keine Bijektion.
Man kann aber sagen, es gibt $g:\mathbb{N} \times \mathbb{N} \to \mathbb{A}$, mit A sind Äquivalenzklassen gleicher rationaler Zahlen gemeint, die sich nach N bijektiv abbilden lassen, meine ich:)

Die Mächtigkeit von Q und N ist jedoch gleich, nämlich $\aleph_0 = |\omega|$, die kleinste unendliche Ordinalzahl.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3533
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2017-11-25 08:27

\(\begingroup\)
2017-11-25 03:57 - juergen007 in Beitrag No. 14 schreibt:
Was hier nicht der Fall ist, da durch f nicht jedem Paar aus $\mathbb{N} \times \mathbb{N}$ ein Element aus N zugeordent wird, da wir kürzbare Paare überspringen. Dieses f ist nicht linkstotal also nicht injektiv.

Hm, versteh ich dich da richtig, dass du meinst die Abbildung $f:\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ mit

$(x,y) \mapsto x+\frac{(x+y)(x+y+1)}{2}$

wäre nicht bijektiv, also dann entweder nicht injektiv oder nicht surjektiv? Könntest du da statt einem theoretischen Exkurs einfach kleine Gegenbeispiele zur Injektivität bzw. Surjektivität nennen?   cool

PS: Aber bitte vorher die Definitionen von injektiv und surjektiv nachschlagen, denn z.B. sind "linkstotal" und "injektiv" zwei grundverschiedene Begriffe für Funktionen, die nichts miteinander zu tun haben.  eek
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 3158
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2017-11-25 09:10


@juergen007: Dein Fehler seit einigen Beiträgen ist u.a., dass du bei b) die rationalen Zahlen ins Spiel bringst. Darum geht es dort nicht, erst bei c) geht es um rationale Zahlen. Die Paare natürlicher Zahlen kann man in b) mit dem Diagonalverfahren abzählen, und zwar genau mit der bijektiven Abbildung, die ich angegeben habe.

Ich werde diesen Thread nun nicht mehr verfolgen.



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2017-11-25 17:19


aus


nawi.blogbasis.net/funktionen-bzw-abbildungen-26-04-2013

Eigenschaften Injektiv, Surjektiv und Bijektiv

Eine Abbildung kann weitere tolle Eigenschaften besitzen. Diese drei nennen sich „injektiv“, „surjektiv“ und „bijektiv“.
Injektiv

Als injektiv bezeichnet man eine Abbildung, welche linkstotal, rechtseindeutig und dazu noch linkseindeutig ist. Das bedeutet, wie oben schon erklärt, dass jedes Element aus dem Wertebereich maximal mit einem Element aus dem Definitionsbereich in Verbindung stehen darf. Formell:
∀x1,x2∈A.f(x1)=f(x2)⟹x1=x2



  Profil  Quote  Link auf diesen Beitrag Link
BerndLiefert
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 21.10.2014
Mitteilungen: 261
Aus: Lehramtplanet
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2017-11-25 18:34


Das wichtige Wort bei injektiven Abbildungen ist "linkseindeutig". Die anderen beiden Eigenschaften müssen erfüllt sein, damit es sich überhaupt um eine Abbildung handelt.

Bei der Abbildung die du konstruieren willst ist das ein Problem. Bei der Abbildung von Triceratops nicht.

Nochmal: Schau dir die Abbildung, die Triceratops angegeben hat, an. Definitionsbereich. Wertebereich. Abbildungsvorschrift.



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3533
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2017-11-25 20:32


2017-11-25 17:19 - juergen007 in Beitrag No. 17 schreibt:
Als injektiv bezeichnet man eine Abbildung, welche linkstotal, rechtseindeutig und dazu noch linkseindeutig ist. Das bedeutet, wie oben schon erklärt, dass jedes Element aus dem Wertebereich maximal mit einem Element aus dem Definitionsbereich in Verbindung stehen darf. Formell:
∀x1,x2∈A.f(x1)=f(x2)⟹x1=x2

Wie ich oben in #15 schon befürchtet hatte wieder nur die höchst umständliche Wiedergabe der Definition einer injektiven Funktion aus dem Internet, und zwar so, wie schon von BerndLiefert angemerkt, als ginge es hier noch um Relationen und nicht schon um Abbildungen - aber kein Wort dazu, wie es diesbezüglich um die Abbildung von Triceratops steht. Naja, warum erstaunt mich das eigentlich nicht?   razz




  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2094
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2017-11-26 07:42


Pardon ich hatte den wahrscheinlich falschen Gedanken das NxN irgendwie grösser ist als N.
die Formel hab ich nicht vollkommen nachgerechnet.







  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3533
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2017-11-27 08:18

\(\begingroup\)
2017-11-26 07:42 - juergen007 in Beitrag No. 20 schreibt:
Pardon ich hatte den wahrscheinlich falschen Gedanken das NxN irgendwie grösser ist als N.
die Formel hab ich nicht vollkommen nachgerechnet.

Ok, um das hier zu einem "guten Ende" zu bringen, nachfolgend dann auch noch die vollständige Rechnung dazu. Um zu zeigen, dass die Funktion $f:\mathbb N\times \mathbb N→\mathbb N$ mit

$(x,y)↦x+(x+y)(x+y+1)/2$

tatsächlich eine Bijektion ist, ist es glaube ich wohl am einfachsten, wenn ich die Umkehrabbildung $f^*$ zu $f$ angebe, welche es ja dann geben muss.

Eine entscheidende Rolle bei der Konstruktion von $f^*(n)$ für ein gegebenes $n \in \mathbb N$ spielen dabei die sog. "Dreieckszahlen"

$Δ_k:=k(k+1)/2,\quad k=0,1,2,3,...$

Du musst dir nämlich für $n$ die größte Dreieckszahl $Δ_{k_n}$ suchen, für welche gilt $Δ_{k_n}≤n$. Du kannst dafür auch einfach die eindeutig bestimmte nichtnegative Lösung der quadratische Gleichung

$k(k+1)/2=n$

im Bereich der reellen Zahlen bestimmen und diese dann auf die nächste ganze Zahl nach unten runden. Damit ergibt sich der gesuchte Index $k_n$ formelmäßig als

$k_n=\left\lfloor -\frac12+\sqrt{\frac14+2n}\,\right\rfloor$

Für $n=17$ würde sich so z.B. $k_{17}=5$ ergeben, wie man noch im Kopf nachrechnen kann. Damit ist dann auch die "Hauptarbeit" bei der ganzen Sache schon geleistet, denn die gesuchten Zahlen $x,y \in \mathbb N$, für welche gilt $f^*(n)=(x,y)$, berechnen sich dann ganz einfach mittels

$x=n−Δ_{k_n}, \ y=k_n−x$

Speziell für $n=17$ erhält man so $f^*(17)=(2,3)$ und tatsächlich ist ja $f(2,3)=17$.

Natürlich müsste man jetzt noch im Detail begründen, warum das so funktioniert. Eine entscheidende Rolle spielt dabei die Beobachtung, dass der "Abstand" zweier benachbarter Dreieckszahlen $\Delta_{k+1}$ und $\Delta_k$ genau $k+1$ beträgt, d.h., die Zahlen

$\Delta_k+\ell,\ \ell=0,1,2,..,k$

decken exakt alle natürlichen Zahlen in $[\Delta_k,\Delta_{k+1})$ ab. Die Menge der natürlichen Zahlen muss man sich also gewissermaßen als lückenlose und sich nicht überlappende Überdeckung durch die obigen Intervalle vorstellen.

Und ja, wie schon Triceratops oben sagte, hat das alles mit Brüchen, welche dir da offenbar dauernd in deinem Hinterkopf "herumspuken", noch gar nichts zu tun. Die kommen erst viel, viel später, nämlich im Aufgabenteil d) dann ins Spiel.   wink    
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
tehtacolord hat die Antworten auf ihre/seine Frage gesehen.
tehtacolord hatte hier bereits selbst das Ok-Häkchen gesetzt.
tehtacolord wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]