2 Integerwerte in einem Integerwert reversibel speichern?

[PeterPanino]

Gibt es ein mathematisches Verfahren, mit dem man 2 Integerwerte a, b mit Hilfe einer Konstante k so in EINEM Integerwert c speichern kann, dass man mit Hilfe dieser Konstante k aus c wieder a, b gewinnen kann?

Irgendwie habe ich das Gefühl, dass das gehen müsste ...

Delphi-Quellcode:

c := Speichern(a, b, k);

a := Extrahieren1(c, k);
b := Extrahieren2(c, k);

[Bernhard Geyer]

Das geht nicht!

Das würde ja bedeuten das man jede Datei ( 4 GB DVD-Video) in einem Integer speichern können müßte wenn man den Dateiinhalt jeweils als Blöcke von 2 Integerwerten (4 Byte) ansehen würde und den Algorithmus rekursiv anwendet.

[mkinzler]

Du könntest höchstens 2 16-Bit Integerwerte in einem 32-Bit Integer speichern. Da sparst du aber nichts

[jfheins]

Da gibt es zwei Möglichkeiten:

1. Weniger (wie mkinzler vorgeschlagen) - du speicherst also keine zwei Integers in einem, sondern zwei Words in einem int oder zwei ints in einem Int64. Einen oben, einen unten -> kein Informationsverlust

2. xor - geht nicht ganz so, wie du es willst: c := a xor b; ==> du kannst mit einem wert den anderen herausfinden.

Aber wenn man zwei beliebige Integers in einem verlustfrei und reversiebel speichern könnte, wäre das ja ein endgeiles Komprimierungsverfahren ;)

[PeterPanino]

Zitat:

Zitat von mkinzler

Du könntest höchstens 2 16-Bit Integerwerte in einem 32-Bit Integer speichern. Da sparst du aber nichts

Es geht mir nicht um's Sparen, sondern um's Verfahren (reimt sich sogar ...)
Wie würde das in Delphi-Code aussehen?

[jfheins]

Ganz einfach? So:

Delphi-Quellcode:

a: Cardinal;
begin
  a := MakeLong(2457, 546);
end;

;)

Rausholen dann so:

Delphi-Quellcode:

b := HiWord(a);
c := LoWord(a);

[SirTwist]

Um die Antwort von mkinzler (die einzig brauchbare soweit ;-) mal etwas zu verallgemeinern.

Eine normale Integer-Variable hat einen gewissen Wertebereich (je nach Typ siehe Online-Hilfe). Wenn Du jetzt zwei Werte speichern möchtest, die aber nur einen kleineren Wertebereich annehmen können, dann kannst du das natürlich umwandeln.

Beispiel: Du möchtest Alter und Gewicht speichern, beim Alter gehst Du von möglichen Werten von 0-200 aus (Sicherheitsreserve!), beim Gewicht von 0-1000kg. Dann multiplizierst Du den einen Wert des einen Parameters (Alter) mit dem Maximalwert des anderen Parameters (Gewicht) und bekommst so eine einzelne Integerzahl. Die kannst Du nun in einer Variable speichern, wenn diese Variable mindestens Zahlen von (Maximalwert Alter)*(Maximalwert Gewicht) aufnehmen kann, in unserem Fall also 200000. Das sollte jede 32bit-Integervariable können.

Um an die Einzelwerte zu kommen, teilst Du Deine Integervariable durch den Maximalwert des einen Parameters, dann erhälst Du als ganzzahliges Ergebnis das Alter und als Rest der Division das Gewicht.

Delphi-Quellcode:

const MaxGewicht = 1000
var   variable:  Integer;
      Alter, Gewicht: Integer;
begin
  // kodieren..
  variable := Alter * MaxGewicht + Gewicht;
  // und wieder zurück
  Alter    := variable div MaxGewicht);
  Gewicht  := variable mod MaxGewicht);
end;

Wenn negative Werte ins Spiel kommen, wird es allerdings etwas komplizierter, aber das Grundprinzip bleibt gleich.

Gruß,
Michael

[SirThornberry]

ein normaler Integer ist 32bit(4 Byte) groß. Wenn du 2 darin 2 Integer speichern willst dürfen diese jeweils nur 2 Byte groß sein sonst gibts ein Problem.
Funktionieren würde es mit move (speicher direkt kopieren) oder mit Bytes shiften oder durch definieren eines neuen Types oder....

Delphi-Quellcode:

type
  TInteger = packed record
    case Bool of
      True  : (NormalInt: Integer);
      False : (Part1: SmallInt;
               Part2: SmallInt;);
  end;


var
  Variable: TInteger;
begin
  Varialbe.Part1 := Zahl1;
  Variable.Part2 := Zahl2;
  Variable.NormalInt := Variable.NormalInt xor Zahl3;
end;

Die Variante von fJeins ist natürlich um einiges kürzer :mrgreen:

[negaH]

Zitat:

Gibt es ein mathematisches Verfahren, mit dem man 2 Integerwerte a, b mit Hilfe einer Konstante k so in EINEM Integerwert c speichern kann, dass man mit Hilfe dieser Konstante k aus c wieder a, b gewinnen kann?

Ja das geht, hängt aber von bestimmten Randbedinungen ab.

Falls zb. |A| und |B| kleiner 128 wären dann multiplizierst du A mit 128 und addierst B drauf. Das |Resulat| kann dann niemals 127*129 überschreiten und das passt in den Datentyp Integer rein.

Zurückwandeln kannst du mit A := Resultat mod 128, B := Resultat div 128;

Gruß Hagen

[sirius]

Zitat:

Zitat von negaH

Falls zb. |A| und |B| kleiner 128 wären dann multiplizierst du A mit 128 und addierst B drauf. Das |Resulat| kann dann niemals 127*129 überschreiten und das passt in den Datentyp Integer rein.

Hallo Hagen,
wie schnell die doch Zeit vergeht. :mrgreen: Gestern noch 8bit und heute sind wir schon beim 32bit Prozessor. Damit ist die Grenze nicht mehr bei 128, sondern bei 32768.

Sirius :cheers:

PS: Ich weis: Krümelkacker :drunken:
PPS: Soll ich dir nochwas verraten? Ca. 10km von hier wird ein 64bit-Prozessor gebaut :zwinker:

[PeterPanino]

Vielen Dank an alle für die fundierten Antworten!

[idontwantaname]

Zitat:

Zitat von sirius

Gestern noch 8bit und heute sind wir schon beim 32bit Prozessor. Damit ist die Grenze nicht mehr bei 128, sondern bei 32768.

Du meinst wohl "Gestern noch 16bit, heute sind wir schon beim 32bit Prozessor" ;)

[SirThornberry]

er meinte tatsächlich 8 bezogen auf die Grenze von 128 welche eben die Mitte wäre bei 8bit-unsigned

[sirius]

Zitat:

Zitat von idontwantaname

Du meinst wohl "Gestern noch 16bit, heute sind wir schon beim 32bit Prozessor" ;)

Ich dachte damit an den KC87, den man in Thüringen sicherlich auch kannte :mrgreen:

@sir: Hagen meinte aber wie ich "signed". Ich wollte cuh gar nicht darauf weiter rumreiten. Ich musste bei Hagens Beitrag nur schmunzeln. :dp:

[Polynom]

Hallo !
Ich hab auch noch eine Idee, allerdings eher mathematisch und ich weiß nicht genau ob es funktioniert.

Man hat also seine 2 Zahlen, welche ganzzahlig sind und positiv sein müssen.
Jetzt nimmt man eine Primzahlen-Liste und nummeriert die Primzahlen (Im Programm könnte man das z.B. durch einen Array lösen).
Die zu den beiden Zahlen dazugehörigen Primzahlen werden miteinander multipliziert und man erhält eine Zahl.

Da ich denke, dass es etwas schlecht erklärt ist gibt's hier ein kleines Beispiel:
Die beiden Zahlen seien 4 und 6.
Primzahl-Liste:
Nr 1 -> 2
Nr 2 -> 3
Nr 3 -> 5
Nr 4 -> 7
Nr 5 -> 11
Nr 6 -> 13

Daraus folgt, dass man 7 und 13 miteinander multiplizieren muss. Das Ergebnis: 91
Die 91 wäre dann die Zahl, welche ausgegeben wird.

Und über Primfaktorzerlegung müsste man die ursprünglichen Primzahlen wieder herausfinden, welche dann anhand der Liste wieder in die Ausgangszahlen umgewandelt werden können.
Ich bin mir nur nicht sicher ob das Ergebnis eindeutig ist, oder ob es noch eine zweite Möglichkeit gibt...

Mit freundlichen Grüßen, Michael

[BenjaminH]

Primfaktorzerlegung ist eindeutig, das Verfahren wäre theoretisch also machbar.
Das Problem dabei ist, dass die zugeordneten Primzahlen unverhältnismäßig groß würden und man so durch die Zusammenführung der beiden Werte nichts gewinnen würde.
Außerdem dauert die Primfaktorzerlegung einfach zu lang(der Grund, weshalb RSA nicht geknackt werden kann). Und beim Suchen der x-ten Primzahl verhält sich das genauso(Natürlich in beiden Fällen erst bei Zahlen bestimmter Größenordnungen)

[thkerkmann]

Und ausserdem kannst Du nicht sagen, welches die erste und welches die zweite Zahl war.

Gruss

[negaH]

Ich meinte garnicht Bit, sondern beschrieb in pseudo-Mathematik den Sachverhalt so das der pfiffige Fragesteller eigentlich selbst in der Lange sein müsste das auf 8Bit,16,32,64 oder meintewegen auch 1024 Bit, mit oder ohne Vorzeichen, zusammenzureimen.

Es ist egal wieviel Bit man als Datentyp hat, die Fragestellung war

"wie kann man zwei Ganzzahlen, programmierdeutsch Integer, so kombinieren das man sie in einer anderen Zahl kodiert".

Nun, dazu wählt man eine neue Zahlenbasis die so groß ist das alle seine zu kombinierenden Zahlen da rein passen. Dann multipliziert man seine zusammenzubauenden Zahlen mit Potenzen zu dieser Basis.

Möchte man zb. 3 solcher Zahlen zwischen 0 bis 127 in eine Zahl packen wählen wir die Basis 128.

R := A * 128^2 + B * 128^1 + C * 128^0;

Und das beste daran ? Ganz einfache Mathemtik Klasse 4 oder 5 spätestens. Denn so funktionieren unsere Zahlen.

Mag sich jetzt belehrerisch und arrogant anhören, vielleicht sogar sarkastisch, aber so ist es.

Wir als Programmierer gewöhnen uns es allzuschnell an in unserer Sprache ein simples Problem zu beschreiben. Dabei benutzen wir aber garnicht die Basis der Informatik als Sprache, also die Mathematik, sondern wie Straßenjungen den Dialekt unserer Programmiersprache. Ich nehme mich da nicht aus in keinster Weise. Aber bestimmte Sachverhalte, eben wie die Zahlensysteme, müssen echt sitzen bei uns.

Gruß Hagen

[negaH]

Zitat:

Die zu den beiden Zahlen dazugehörigen Primzahlen werden miteinander multipliziert und man erhält eine Zahl.

Also du meinst das so ?

12 = 2*2*3
20 = 2*2*5

2*2*2*2*3*5 = 12 * 20

2*2*2*3 = 24
2*5 = 10

2*2*2*2*3*5 = 10 * 24

Gruß Hagen

[Apollonius]

Nein. Er meinte, das die 12. und die 20. Primzahl miteinander multipliziert werden. Dann ist es selbstverständlich eindeutig (natürlich nicht bezüglich p*q=q*p). Allerdings werden die Zahlen sehr schnell sehr groß.

[3_of_8]

Außerdem "verschwendet" man dann recht viel Speicherplatz und man erhält die Zahlen nicht mehr in konstanter Zeit (O(1)), sondern in O(sqrt(pq)).

[negaH]

Zitat:

Nein. Er meinte, das die 12. und die 20. Primzahl miteinander multipliziert werden. Dann ist es selbstverständlich eindeutig (natürlich nicht bezüglich p*q=q*p). Allerdings werden die Zahlen sehr schnell sehr groß.

Ok, macht aber noch weniger Sinn. Es gibt weniger Primzahlen als Nichtprimzahlen, logisch. Das bedeutet gäbe es unendlich viele Nichtprimzahlen dann benötigen wir mehr als unendlich viele Primzahlen. Soweit die methematrische Unmöglichkeit des Vorschlages.

Technisch gesehen betrachten wir ja nur Zahlen im Bereich von Integer etc.pp. Dann entsteht aber das problem diese beiden Zahlen wieder zu extrahieren, das ist eine sehr aufwendige Operation. Hat aber Manuel im vorherigen Posting korrekt erklärt.

Es gibt Zahlensysteme die modulare Merhfachringe zu den kleinen Primzahlen benutzen, siehe D.J.Bernstein. Deren "Packungsdichte" entspricht den natürlichen Zahlen und man kann jede Ganzzahl damit eineindeutig darstellen. Allerdings benutzt man solche Ringe nur deswegen um sehr große Ganzzahlen > 1024 Bit in ein Zahlensystem zu überführen -> modulare multiple Ringe zu Primzahlen, um alle Berechnungen mit solchen großen Zahlen zb. auf 32 Bit Ebene durchführen zu können. Man benutzt also das Zahlendarstelung zb. alle Reste der modularen Division der kodierten Zahl zu den kleinen Primzahlen bis < 2^32. Die maximal so kodierbare Zahl wäre dann exakt so groß wie das Primzahlprodukt aller Primzahlen < 2^32 -1. Der benötigte Speicherverbrauch wäre dann die Anzahl aller Primzahlen kleiner 2^32 -> P(2^32-1) * 4 Bytes. Jede mathematische Operation wie Addition/Subtraktion usw. würde nun dieses Array[] von Modularen Resten zu Primzahlen addieren per 32 Bit Operationen und somit entsteht kein Überlauf/Unterlauf mehr innerhalb dieser Ringe. Die Umrechnung dieser Zahlendarstellung wieder zurück in natürliche Zahlen erfolgt mit Garner's Version des Chinisischem Restsatzes.

Gruß Hagen

[Der_Unwissende]

Zitat:

Zitat von negaH

Ok, macht aber noch weniger Sinn. Es gibt weniger Primzahlen als Nichtprimzahlen, logisch. Das bedeutet gäbe es unendlich viele Nichtprimzahlen dann benötigen wir mehr als unendlich viele Primzahlen. Soweit die methematrische Unmöglichkeit des Vorschlages.

[OT]
Wie zeigt man das denn? Also ich denke mal wir reden über Natürliche Zahlen (oder Ganze, da Integer-Datentyp). Natürlich gibt es dort jeweils abzählbar-viele Zahlen, die keine Primzahl sind. Aber wurde gezeigt, dass es nur endlich viele Primzahlen gibt? Ich meine man kann auch ganze Zahlen abzählen, was ja auch heißt, dass die Menge der ganzen und der natürlichen Zahlen gleich mächtig ist.

Wie gesagt OT, würde mich nur interessieren, falls also jmd. weiß dass das bewiesen wurde wäre ein Hinweis auf den entsprechenden Beweis oder dessen Idee sehr nett, danke!
[/OT]

Gruß Der Unwissende

[Klaus01]

Zitat:

Zitat von Der_Unwissende

Zitat:

Zitat von negaH

Ok, macht aber noch weniger Sinn. Es gibt weniger Primzahlen als Nichtprimzahlen, logisch. Das bedeutet gäbe es unendlich viele Nichtprimzahlen dann benötigen wir mehr als unendlich viele Primzahlen. Soweit die methematrische Unmöglichkeit des Vorschlages.

[OT]
Wie zeigt man das denn? Also ich denke mal wir reden über Natürliche Zahlen (oder Ganze, da Integer-Datentyp). Natürlich gibt es dort jeweils abzählbar-viele Zahlen, die keine Primzahl sind. Aber wurde gezeigt, dass es nur endlich viele Primzahlen gibt? Ich meine man kann auch ganze Zahlen abzählen, was ja auch heißt, dass die Menge der ganzen und der natürlichen Zahlen gleich mächtig ist.

Wie gesagt OT, würde mich nur interessieren, falls also jmd. weiß dass das bewiesen wurde wäre ein Hinweis auf den entsprechenden Beweis oder dessen Idee sehr nett, danke!
[/OT]

Gruß Der Unwissende

Ist es nicht so, das es unendlich viele Primzahlen und unendlich viele Ganzzahlen gibt.
Und mehr als unendlich geht nicht.
Es sollte dann also auch möglich sein jeder Ganzzahl eine Primzahl zuzuordnen.
Wie groß die Primzahlen dann sein müssen steht dann auf einem anderen Blatt.

Hoffe nicht ganz falsch zu liegen.

Grüße
Klaus

[Der_Unwissende]

Zitat:

Zitat von Klaus01

Ist es nicht so, das es unendlich viele Primzahlen und unendlich viele Ganzzahlen gibt.

Mir ist eben auch so, deswegen würde mich eben der Gegenbeweis interessieren (könnte auch die Sicherheit der Verschlüsselungen, die auf Primzahlen aufbauen ziemlich senken, da man nur die endlich vielen Primzahlen berechnen muss - was lange genug dauert - und ziemlich effizient all diese Verschlüsselungen knacken kann).

[jfheins]

Es gibt unendlich viele Primzahlen - aber in einem Zahlenraum von MinInt..MaxInt gibt es bedeutend mehr nicht-Primzahlen, weshalb man Probleme hätte, die 2.000.000.000-te Primzahl in einen Integer zu bekommen ;)

Beweis, Kurzversion:

Angenommen, es gibt endlich viele Primzahlen.

:arrow: Multipliziere alle bekannten Primzahlen miteinander und addiere 1
Entweder:
:arrow: Ergebnis ist eine Primzahl :arrow: Annahme wiederlegt
oder:
:arrow: Das Ergebnis ist keine Primzahl - Primfaktorzerlegung ergibt eine Primzahl, die größer als alle anderen ist (Da ja alle Primzahlen multipliziert wurden und noch 1 addiert wurde) :arrow: Annahme widerlegt

;)

[3_of_8]

Natürlich kann man jeder ganzen Zahl eine Primzahl bijektiv zuordnen.

Das könnte man zum Beispiel so machen:
f: Z x N
f(x)=p(1) für x=0
f(x)=p(2x) für x>0
f(x)=p(-2x+1) für x<0

p: N x N
p(x)=Die x. Primzahl


Wie man sieht, ist damit jeder ganzen Zahl eine Primzahl bijektiv zugeordnet. Möglich ist das, wie bereits angesprochen, weil |N|=|Z|=aleph.

Sobald man allerdings nicht mehr mit Z und N arbeitet, sondern mit Teilmengen von diesen (wie es bei Computern nun mal der Fall ist) ist diese Zuordnung natürlich nicht mehr ganz möglich, da die Größe der Primzahlen schneller nach unendlich strebt als die der Zahlen, die man mit ihnen verknüpft. Ich habe vor kurzem mal ein paar Millionen Primzahlen berechnen lassen, und ich weiß es jetzt nicht mehr genau, aber ich glaube, dass man mit den Primzahlen im Cardinal-Bereich nur Zahlen von ~-100 Mio. bis +100 Mio. darstellen könnte. (nach obiger Methode)

[Apollonius]

Zitat:

Es gibt unendlich viele Primzahlen - aber in einem Zahlenraum von MinInt..MaxInt gibt es bedeutend mehr nicht-Primzahlen, weshalb man Probleme hätte, die 2.000.000.000-te Primzahl in einen Integer zu bekommen

Man sollte auch noch den Teil nach dem aber beweisen, also: im Zahlenraum 0..n gibt es mindestens genausoviele nicht-Primzahlen wie Primzahlen.
Für n<3 ist der Fall klar; bei n>=3 gibt es genau eine gerade Primzahl und mindestens eine ungerade nicht-Primzahl (1).
Die Behauptung folgt direkt.

[Der_Unwissende]

Zitat:

Zitat von jfheins

Es gibt unendlich viele Primzahlen - aber in einem Zahlenraum von MinInt..MaxInt gibt es bedeutend mehr nicht-Primzahlen, weshalb man Probleme hätte, die 2.000.000.000-te Primzahl in einen Integer zu bekommen ;)

Das ist klar, bezog mich auch nur auf

Zitat:

Zitat von negaH

Es gibt weniger Primzahlen als Nichtprimzahlen, logisch. Das bedeutet gäbe es unendlich viele Nichtprimzahlen dann benötigen wir mehr als unendlich viele Primzahlen. Soweit die methematrische Unmöglichkeit des Vorschlages

Soweit ich mich nicht irre ist eben die Implikation, dass es mehr als unendliche vieler Primzahlen bedarf um alle Nichtprimzahlen zu kodieren würde ich eben als falsch ansehen. Und wenn es eine Bijektion zwischen einer abzählbaren Menge und eben der Menge aller Primzahlen gibt, dann sind diese Mengen gleich mächtig und die mathematische Möglichkeit des Vorschlags bleibt gewahrt (wenn auch der Ansatz nicht unbedingt sehr effizient ist). Dem Threadsteller geht es aber eben auch nur um die theoretische Möglichkeit und für einen unendlichen Zahlenraum denke ich, dürfte dies eine eindeutige Möglichkeit sein, zwei Zahlen zu kodieren un diese wieder zu dekodieren.

[negaH]

Hm warum sollte das falsch sein ?

Es gibt in einem begrenzten Zahlenbereich immer mehr zusammengesetzte Zahlen als Primzahlen. (mal abgeshen vom Bereich 2 bis 5 oä.).
Das bedeutet das wenn man die Zahlen in diesem Beeich per Primzahlen kodieren wollte so reichen die Primzahlen innerhalb dieses Breiches dafür nicht aus.

Nun definieren wir diesen Bereich als unendlich groß, also benötigen wir mehr als unendlich viele Primzahlen. Es stimmt schon, unendlich bedeutet unendlich. Das heist aber nicht das wenn man die Menge von Zahlen betrachtet im Verhältnis zu einer unendlichen Menge von Zahlen wir denoch mehr als unendlich viele Primzahlen benötigen. Wir definieren also die Menge A aller Zahlen und versuchen diese Zahlen in die Menge B von Primzahlen zu mappen. Wenn Menge A eine Kardinalität von unendlich besitzt so muß Menge B ebenfalls unendlich sein, dann existiert aber denoch keine Schnittmenge C aus A und B die gleich groß unendlich wäre. Da dann die Menge der Primzahlen B in der Menge aller Zahlen A vollständig aufgeht. Menge A die unendlich groß wäre ist denoch größer als Menge B die ebenfalls unendlich groß wäre und Menge B ist nur eine Teilmenge von A. Wir wollen aber alle Zahlen der Menge A kodieren und dazu reicht die Anzahl der Primzahlen (Menge B) die in Menge A enthalten sind nicht aus. Also selbst wenn Menge A unendlich groß wäre so benötigten wir eine Menge B von primzahlen mit gleicher Größe wie Menge A.

Hm, schwer zu erklären ;)

Nochmal

Menge A, alle ganzen Zahlen inklusive Primzahlen
Menge C, alle Primzahlen aus Menge A
Menge B, nur Primzahlen

Menge A und B müssen gleiche Kardinalität besitzen, also exakt gleiche Anzahl von Zahlen
Menge C wird immer weitaus kleiner sein als Menge A, logisch gibt es doch weniger Primzahlen als zusammengesetzte Zahlen

Ergo die Menge C wird immer kleiner Menge B sein.
Wenn Menge A unendlich groß ist dann wird Menge C auch unendlich groß sein aber denoch kleiner als Menge A
Wenn Menge B exakt gleich groß Menge A sein muß aber Menge C immer kleiner als Menge A ist dann heist dies,

das größte Element=Zahl aus Menge A ist Zahl unendlich und das größte Element in Menge C ist größer unendlich.

Wir rechnen eben nicht mehr mit Zahlen sondern mit Mengen deren Elemente Zahlen sind.

Jetzt ist die Frage, gibt es eine Zahl die großer ist als unendlich groß ?
Und gibt es eine Menge A die unendlich viele Zahlen enthält die aber denoch kleiner sein kann als eine andere Menge B mit unendlich vielen Zahlen.


Gruß Hagen

[3_of_8]

Bist du dir da sicher? Also ich bin mir ziemlich sicher, dass die Menge der Primzahlen und die Menge der ganzen Zahlen/natürlichen Zahlen die gleiche Kardinalität besitzen. Ich habe das ja oben sogar bewiesen, indem ich eine bijektive Abbildung angegeben habe. (Die Beweisführung ist ähnlich wie beim Cantor'schen Diagonalverfahren)

[Der_Unwissende]

Zitat:

Zitat von 3_of_8

Die Beweisführung ist ähnlich wie beim Cantor'schen Diagonalverfahren

Das wäre auch der Hauptgrund, warum ich sagen würde dass Hagens Argumentation falsch ist. Ich meine das die Kardinalität der Natürlichen Zahlen gleich der Kardinalität der Ganzen Zahlen ist würde doch auch schon mehr als unendlich viele Zahlen benötigen, denn es gibt zwei Bedingungen, die für jede Natürliche Zahl (> 0) erfüllt sind:

1. Jede Natürliche Zahl hat einen Nachfolger
2. Zu jeder Natürlichen Zahl n gibt es zwei Ganze Zahlen, die den gleichen Betrag wie n haben

Ích denke der Fehler in der Argumentation besteht in dem Übergang aus einer endlichen Menge in eine unendliche Menge. Nimmst Du eine beliebige, endliche Teilmenge der Natürlichen Zahlen, so lässt sich eine gleichmächtige Menge von aufsteigenden Primzahlen finden (was möglich ist, da beide Mengen unendlich viele Elemente besitzen). Damit ist eine Bijektion möglich (eine besser/genauere Argumentation kam ja schon von Manuel).

[Phoenix]

Wir wollen einer Zahl n die n-te Primzahl zuordnen.

Nehmen wir den Satz von Euklid her: Es gibt unendlich viele Primzahlen.
Dann können wir in einer unendlichen Menge von Zahlen jeder einzelnen Zahl eine eindeutige Primzahl (derer es ja auch unendlich gibt) zuordnen.

Befinden wir uns in einem Zahlenraum der unendlich groß ist, dann liegt die zu einem beliebigen n gehörige n-te Primzahl bei sehr großen n zwar ein umso mehr verdammt großes Stückchen 'weiter hinten' im unendlichen Zahlenraum, aber sie liegt trotzdem immer drin.

Interessanterweise hat diese verdammt große Primzahl (da sie in unserem Zahlenraum liegt) wieder eine ihr zugeordenete Primzahl, die halt noch viel größer ist.

Hagen hat schon recht: Betrachten wir einen begrenzten Zahlenraum, dann benötigen wir genauso viele (nicht mehr!) Primzahlen wie normale Zahlen in unserem Raum sind. Nur die Wertigkeit dieser Primzahlen überschreitet irgendwann zwangsläufig den größten Wert in unserem begrenzten Zahlenraum. Das kann also nicht klappen.

In der Unendlichkeit jedoch ist ein bisschen 'mehr' an Wertigkeit ziemlich irrelevant.

[Apollonius]

Schlicht und einfach: Wenn Menge B eine echte Teilmenge aus Menge A ist, dann können sie trotzdem gleichmächtig sein.

[3_of_8]

...solange sie beide unendlich sind, wohlgemerkt. ;)

[Apollonius]

Wobei das auch nicht immer so ist: N ist eine Teilmenge von R, aber echt schmächtiger.

[mkinzler]

Ist ja kein Widerspruch, da ja R + N beide nicht endlich sind.

[Phoenix]

Bei gleicher Mächtigkeit haben wir aber keine Teilmenge sondern die Identität ;-)

[Apollonius]

Zitat:

Zitat von Phoenix

Bei gleicher Mächtigkeit haben wir aber keine Teilmenge sondern die Identität ;-)

N ist gleichmächtig zu Z, aber eine echte Teilmenge.

[3_of_8]

@Phoenix: Es seien A=B zwei endliche Mengen. Dann gilt A Teilmenge B und B Teilmenge A. Man muss Unterscheiden zwischen Teilmenge und echter Teilmenge (so ähnlich wieder Unterschied zwischen <= und <)