Bijektivität/Abzählbarkeit durch Identität nachweisen?
Hi, wir haben den Fall, bei einem Tut sagt der Tutor, dass er
durch eine FUnktion zeigen möchte, dass N^2 x N abzählbar ist, also das 3 fache kartesische Produkt von N.
Dafür sagt er, er bildet einfach die Identität so:
f: N^2 x N --> N^3
und jedes F((a,b),c)= (a,b,c)
also jedes Tupel von N^2 x N bekommt ein Tupel von N^3 zugeordnet.
Dadurch habe man eine Bijektion dargestellt und das beweise unter anderem, dass N^2 x N abzählbar ist....
Erst Mal, was genau meint man mit Identität? Weil ich von N^2 x N auf N^3, also eigentlich auf das gleiche abbilde?
Wenn ja warum beweist dass die Abzählbarkeit.
Z. B. R ist doch nicht abzählbar, wenn ich nun sage:
R --> R, also R bildet auf R ab, so habe ich doch auch eine bijektive Abbildung, trotzdem ist doch R nicht abzählbar? Bin ich jetzt einfach nur verwirrt oder hat sich der Tutor hat sich versprochen?
3 Antworten
Erst Mal, was genau meint man mit Identität? Weil ich von N^2 x N auf N^3, also eigentlich auf das gleiche abbilde?
Eine Identität ist eine Abbildung, die jedes Element wieder auf sich selbst abbildet. D.h. für eine Menge A ist
die Identität auf A.
Im konkreten Fall sind ℕ² × ℕ und ℕ³ genau genommen zwei verschiedene Mengen, weshalb
genau genommen keine Identität ist. Allerdings ist es nun so, dass die Mengen ℕ² × ℕ und ℕ³ so ähnlich zueinander sind, dass man das quasi wie die gleiche Menge ansehen kann. Jedes Element ((a, b), c) aus ℕ² × ℕ kann man quasi als das gleiche wie das entsprechende Element (a, b, c) aus ℕ³ ansehen (auch wenn es, wenn man es genau nimmt, verschiedene Elemente aus verschiedenen Mengen sind). Da also quasi ((a, b), c) das gleiche wie (a, b, c) ist, kann man hier quasi von einer Identität sprechen.
============
Wenn ja warum beweist dass die Abzählbarkeit.
Man kann zeigen, dass wenn A und B zwei abzählbare Mengen sind, dass dann auch A × B abzählbar ist. (Bei dem Beweis kann man sich an Cantors erstes Diagonalargument orientieren.)
Da ℕ abzählbar ist, ist damit auch ℕ × ℕ = ℕ² abzählbar.
Da ℕ² und ℕ abzählbar sind, ist damit auch ℕ² × ℕ abzählbar.
Wenn man nun eine bijektive Abbildung zwischen zwei Mengen hat, und die eine Menge abzählbar ist, ist auch die andere Menge abzählbar. Mit der gefundenen Bijektion f: ℕ² × ℕ → ℕ³, ((a, b), c) ↦ (a, b, c), und da ℕ² × ℕ abzählbar ist, folgt dann, dass auch ℕ³ abzählbar ist.
============
R --> R, also R bildet auf R ab, so habe ich doch auch eine bijektive Abbildung, trotzdem ist doch R nicht abzählbar?
Da hat man eine Bijektion. Aber zwischen zwei überabzählbaren Mengen. Dass man eine Bijektion zwischen den beiden Mengen gefunden hat, lässt ja folgern, dass beide endlich oder beide abzählbar oder beide überabzählbar sind (also das beispielsweise nicht die eine Menge abzählbar und die andere überzählbar sein kann). Das heißt nicht, dass beide Mengen abzählbar sein müssen, sondern nur, dass wenn die eine Menge abzählbar ist, die andere auch abzählbar ist.
Richtig. Ich vermute, dass der Tutor, oder wer dir das gezeigt hat, wahrscheinlich gedacht hat, du willst zeigen, dass ℕ³ abzählbar ist. Dass ℕ² × ℕ abzählbar ist, braucht man dann auf diesem Weg dafür als Voraussetzung, muss man also vorher anderweitig zeigen bzw. bereits gezeigt haben.
Oder derjenige hat nicht genauer nachgedacht, wie man üblicherweise zeigt, dass ℕ³ abzählbar ist (denn das zeigt man üblicherweise genau so, und würde dann einen Zirkelschluss erhalten), und hatte im Kopf, dass ℕ³ abzählbar ist, und wollte aus der Abzählbarkeit von ℕ³ die Abzählbarkeit von ℕ² × ℕ folgern.
Ja, das auch. (Zumindest, wenn du dich bei „weiß, dass N^3 bijektiv ist“ verschrieben hast, und eigentlich „weiß, dass N^3 abzählbar ist“ gemeint hast.)
======Begründung======
Eine Menge K ist genau dann abzählbar, wenn es eine Bijektion ℕ → K gibt (oder äquivalent dazu, wenn es eine Bijektion K → ℕ gibt).
Wenn man nun weiß, dass eine Menge M abzählbar ist, so gibt es eine Bijektion f: ℕ → M.
Wenn man dann noch weiß, dass es eine Bijektion g: M → K gibt, kann man g ∘ f bilden, was dann eine Bijektion ℕ → K ist, womit man dann gezeigt hat, dass auch K abzählbar ist.
Bzw. wenn man weiß, dass es eine Bijektion h: K → M gibt, kann man h⁻¹ ∘ f bilden, was dann eine Bijektion ℕ → K ist, womit man dann gezeigt hat, dass auch K abzählbar ist.
(Beim Beispiel aus deinen Nachfragen in den Kommentaren ist dann dementsprechend M = ℕ³.)
Erst Mal, was genau meint man mit Identität? Weil ich von N^2 x N auf N^3, also eigentlich auf das gleiche abbilde?
Also im Grunde ist das keine Identitätsabbildung, da (a,b,c) nicht das gleiche ist wie ((a,b),c) ist.
R --> R, also R bildet auf R ab, so habe ich doch auch eine bijektive Abbildung, trotzdem ist doch R nicht abzählbar?
Korrekt, der Beweis gilt nur, wenn man weiß, dass die Bildmenge abzählbar ist. Vielleicht habt ihr ja schon im Skript stehen, dass N^n für alle natürlichen n abzählbar ist.
Wir haben nur stehen, dass N^2 abzählbar ist und nicht N^n, dann meinte er, er macht jetzt N^2xN-->N^3 und dadurch sei bewiesen, dass N^2xN abzählbar ist, weil das bijektiv sei.
Ich weiß und kapiere auch das N^2xN abzählbar ist, aber der Beweis mit der Bijektion ist doch verwirrend, wenn der nur geht, wenn man weiß, dass die Bildmenge abzählbar ist, müsste ja vorher defineirt sein, dass N^2xN abzählbar ist oder nicht?
Wir haben nur stehen, dass N^2 abzählbar ist und nicht N^n, dann meinte er, er macht jetzt N^2xN-->N^3 und dadurch sei bewiesen, dass N^2xN abzählbar ist, weil das bijektiv sei.
Das Argument funktioniert nur, wenn ihr wisst, dass N^3 abzählbar ist. Ansonsten geht das nicht.
dass die Bildmenge abzählbar ist, müsste ja vorher defineirt sein, dass N^2xN abzählbar ist oder nicht?
N^3 ist die Bildmenge.
Hattet ihr vllt, dass das Karthesische Produkt zweier Abzählbarer Mengen anzählbar ist?
Ja, das hatten wir. Dadurch lässt sich auch Schlussfolgern, dass N^2 xN abzählbar ist, weil das zwei Mengen sind, aber warum brauchen wir dann überhaupt noch als Beweis N^2xN-->N^3. Wenn wir sowieso mit der Vorlesung begründen müssen, dass N^2xN abzählbar ist, dadurch ,dass wir sagen das kartesische Produkt zweier abzählbarer Mengen ist azählbar. Warum muss man noch, damit es ein Beweis ist, diese ABbildung N^2 x N--> N^3 erschaffen?
Man hätte auch sagen können N^2 x N--> N, das wäre ja auch bijektiv und dadurch abzählbar oder?
Klar das ist selbstverständlich, aber ich weiß ja zumindest, dass es Bijektiv sein muss, da abzählbar. Dass ich die FUnktion noch finden muss ist klar, hätte dann z. B gesagt f(((a,b),c)=a+b+c so sollte es passen, vermute ich mal
Aso stimmt, aber f((a,b),c)=a*2+b*2+c*2 wäre korrekt oder, wäre ja eine bijektive ABbildung? also N^2xN-->N mit der Funktion
Hi, sorry für die Frage, bezüglich den Fachwörtern. Aber "Du müsstest erst eine solche Funktion finden, die bijektiv ist."
Rein von den Fachwörtern kann man ja N^2xN -->N auch schon als eine Funktion bezeichnen, da das ja eine Abbildung ist oder?
(Mir ist natürlich selbstverständlich klar, was Du mit einer Funktion meinst! Also wie unten dargestellt, aber nennt man das dann auch Funktion, also die Frage klingt vielleicht verwirrend, aber ich nenne N^2xN-->N Abbildung oder Funktion und f((a,b),c)=a*b+1 oder irgendwie sowas nenne ich FUnktion, obwohl das ja auch nochmal einen Unterschied macht oder nicht
Ich kann mir das nur so erklären, dass es da ein paar Missverständnisse zwischen Euch gegeben hat. Im Kern des ganzen steht die Frage, ob N³ abzählbar ist und dass man zunächst einmal zwischen N² x N und N³ unterscheiden muss, weil das NICHT dieselbe Menge ist.
Man hat:
N ist abzählbar.
Das kartesische Produkt N² = NxN ist abzählbar (weil das kartesische Produkt von zwei Mengen immer abzählbar ist).
Damit hat man auch N²xN ist abzählbar.
Man will aber wissen, ob N³ abzählbar ist. Streng genommen ist aber N²xN erstmal nicht dasselbe wie N²xN, denn N³ = {(a, b, c) mit a, b, c aus N} und N²xN {((a, b),c) mit a, b, c aus N}.
Man kann aber jedes Element (a, b, c) aus N³ eindeutig identifizieren mit dem Element ((a,b),c) aus N²xN. Damit hat man eine Bijektion zwischen N³ und N² x N. Damit ist auch N³ abzählbar.
Vielen Dank, aber warum isst es dann noch nötig, dass ich das zeige:
f: ℕ² × ℕ → ℕ³
ich weiß ja, dass die Bijektion nur ein Beweis ist, dass ℕ² × ℕ abzählbar ist, wenn ich schon weiß dass ℕ² × ℕ abzählbar ist. Warum muss ich dann noch die Bijektion: f: ℕ² × ℕ → ℕ³ erschaffen und damit untermauern, dass die abzählbar sind? Die Bijektion bringt mir doch nichts, ich muss doch vorher wissen, dass die abzählbar sind, damit ich die Bijektion als Begründung nutzen kann oder nicht?