Ordnungserhaltende Bijektion

08.11.2012, 23:06	Nashsright	Auf diesen Beitrag antworten »
Ordnungserhaltende Bijektion Hallo, Ich soll entscheiden(und die richtigkeit dieses schlusses natürlich auch beweisen), ob es für die im folgende definierte Ordnungsrelation eine ordnungserhaltende Bijektion $\begin{eqnarray} f: \mathbb N \times \mathbb N \rightarrow \mathbb N \end{eqnarray}$ gibt. Die Ordnungsrelation $\begin{eqnarray} \preceq \end{eqnarray}$ ist folgendermaßen definiert: $\begin{eqnarray} (n,m) \preceq (n',m') \Leftrightarrow n \leq n' \vee (n=n' \wedge m \leq m') \end{eqnarray}$ rein intuitiv würde ich sagen, dass es nicht möglich ist(probieren hat es auch bisher besätigt). die überlegung ist die, dass, sobald ich eine funktion habe, die die ordnung erhält, es mit der injektivität problematisch wird(rein inuitiv); insbesondere auch, weil die zielmenge die natürlichen zahlen sind(leicht zu sehen am bsp f=n). für einen beweisansatz bräucht ich aber trotzdem noch ein paar denkanstöße... ich habe das zu zeigende auch schon prädikatenlogisch komplett ausformuliert, die idee fehlt mir aber noch.
09.11.2012, 08:13	addor	Auf diesen Beitrag antworten »
Ist $\begin{eqnarray} f \colon (n,m) \to k=\begin{pmatrix} n+m+1 \\ 2 \end{pmatrix}+n \end{eqnarray}$ mit der Umkehrung $\begin{eqnarray} n=k-\dbinom{[\sqrt{2k}] }{2} \end{eqnarray}$ mit der Gaussklammer $\begin{eqnarray} [.] \end{eqnarray}$ und $\begin{eqnarray} m=[\sqrt{2k}]-1-n \end{eqnarray}$ eine Bijektion? Bin mir nicht ganz sicher....
09.11.2012, 21:29	Nashsright	Auf diesen Beitrag antworten »
edit: nur schwachsinn geschrieben bis jetzt. die funktion scheint bijektiv zu sein...wie bist du auf die gekommen? allerdings erhält sie ordnung nicht $\begin{eqnarray} [(n,m) \preceq (n',m') \Leftrightarrow n \leq n' \vee (n=n' \wedge m \leq m')] \Rightarrow (4,3) \preceq (5,1) \end{eqnarray}$ allerdings gilt nicht $\begin{eqnarray} f(4,3) \leq f(5,1) \end{eqnarray}$
10.11.2012, 07:33	addor	Auf diesen Beitrag antworten »
Au ja, Du hast recht! Na, war dann wohl nichts. Sorry für die Störung (Die Abbildung ist einfach eine Abwandlung der Bijektion, die Cantor zwischen den Natürlichen Zahlen und den Rationalen Zahlen angegeben hat. Allerdings habe ich sie bisher immer bloss veranschaulicht gesehen. Ich musste sie in eine formale Form bringen)
10.11.2012, 11:33	RavenOnJ	Auf diesen Beitrag antworten »
Es kann keine solche Bijektion geben. Gebe es eine solche bijektive Funktion $\begin{eqnarray} f \end{eqnarray}$ mit $\begin{eqnarray} (1,1)\overset{f}{\leftrightarrow}k \end{eqnarray}$ und $\begin{eqnarray} (2,1)\overset{f}{\leftrightarrow} m \end{eqnarray}$ mit $\begin{eqnarray} k,m \in\mathbb{N}: k < m \end{eqnarray}$ . Betrachte nun die Menge $\begin{eqnarray} M_1:=\{(1,n)\|n \in\mathbb{N}\setminus\{1\}\} \end{eqnarray}$ . Offensichtlich ist die Mächtigkeit von $\begin{eqnarray} M_1 \end{eqnarray}$ abzählbar unendlich. Nun gilt aber $\begin{eqnarray} \forall (1,n)\in M_1: (1,1)\prec (1,n)\prec (2,1) \end{eqnarray}$ . Wenn $\begin{eqnarray} f \end{eqnarray}$ ordnungserhaltend ist, dann muss es eine Bijektion irgendeiner Teilmenge von $\begin{eqnarray} N_m \end{eqnarray}$ auf $\begin{eqnarray} M_1 \end{eqnarray}$ geben. Die Menge $\begin{eqnarray} N_m :=\{i\in \mathbb{N}\|i < m\} \end{eqnarray}$ hat aber nur endliche Mächtigkeit. Daraus ergibt sich ein Widerspruch, da $\begin{eqnarray} M_1 \end{eqnarray}$ abzählbar unendliche Mächtigkeit hat. Gruß Peter
18.11.2012, 19:53	Nashsright	Auf diesen Beitrag antworten »
danke für die erklärung!
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »