Seiten

  • Startseite
  • Impressum
  • Inhalt
  • MINT
  • Sprache
  • Soziales
  • Geist
  • Kunst
  • Gemischtes
  • Gedichte

Freitag, 13. Februar 2015

Eine bijektive Abbildung auf ℚ
 A bijective function to ℚ


DeutschEnglish

Nachtrag: Die folgenden Überlegungen enthalten einen kleinen Fehler, man sollte daher anschließend den zweiten Teil lesen: Eine bijektive Abbildung auf ℚ #2.

Ei­ne Men­ge M heißt abzähl­bar un­end­lich, wenn es ei­ne bi­jek­ti­ve Ab­bil­dung f:ℕ→M gibt. Wir wis­sen, dass ei­ne Bi­jek­ti­on zwi­schen den natürli­chen Zah­len und den gan­zen Zah­len so­wie ei­ne Bi­jek­ti­on zwi­schen und den ra­tio­na­len Zah­len gibt. Dem­zu­fol­ge gibt es ei­ne Funk­ti­on f, wel­che auf ab­bil­det und de­ren Um­kehr­funk­ti­on f auf ab­bil­det. Und in der Tat, die­se fin­det man leicht:
f(x)=(-1)x⋅⌈x/2⌉

f(x)=|2⋅x|-(x<0)

Wie sieht aber ei­ne ent­spre­chen­de Funk­ti­on g:ℕ→ℚ aus? Da­zu ma­che ich einen Zwi­schen­schritt und su­che zu­erst ein­mal ei­ne bi­jek­ti­ve Ab­bil­dung g+:ℕ→ℚ+. Dass abzähl­bar un­end­lich ist, wis­sen wir, in­dem wir sie in Zei­len und Spal­ten an­ord­nen und dann ein­fach abzählen:

1/11/2 1/31/4 1/5
2/1 2/2 2/3 2/4 2/5
3/1 3/2 3/3 3/4 3/5
4/1 4/2 4/3 4/4 4/5
5/1 5/2 5/3 5/4 5/5

Ge­sucht ist al­so ei­ne Funk­ti­on, die fol­gen­der­maßen Wer­te zu­weist:
x123456789101112
g+(x)1/11/22/13/12/21/31/42/33/24/15/14/2


Es soll x↦p/q mit p,q∈ℕ sein. Dann kann man die fol­gen­de Ta­bel­le zeich­nen (die Spal­ten für (x-p) und (x-q) brau­chen wir später):

xpq(x-p)(x-q)
11100
21210
32112
43113
52233
61353
71463
82365
93267
104169
1151610
1242810


Es ist leich­ter, ei­ne Funk­ti­on x↦((x-a(x)/(x-b(x))) zu su­chen. Und ich neh­me gleich einen Schritt vor­weg: Wir su­chen ei­ne Funk­ti­on x↦((x-a(x)/(x-b(x)))c(x). Was sind al­so die von x abhängi­gen Kom­po­nen­ten a(x), b(x) und c(x)?

Wir er­hal­ten die Ant­wort, wenn wir uns die Wer­te von (x-p) und (x-q) noch ein­mal ge­nau­er an­se­hen, und fol­gen­de Zu­sam­menhänge er­ken­nen:

x(x-p)(x-q)a(x)b(x)c(x)
10000-1
210101
312121
41331-1
53333-1
65335-1
763631
865651
967671
1069691
11610106-1
12810108-1


Er­klärung: Wenn c(x)=-1, dann wird das Re­zi­pro­ke des Bruchs ge­bil­det, an­sons­ten (bei 1) bleibt der Bruch un­verändert. Durch die­sen Ex­po­nen­ten können wir (x-p) und (x-q) ver­tau­schen und so die Zah­len­rei­hen, wie sie in den Spal­ten a(x) und b(x) ste­hen ein­zeln be­trach­ten. Ge­nau­er ge­sagt brau­chen wir Funk­tio­nen a(x), b(x) und c(x), die die fol­gen­den Wer­te lie­fern:

x123456789101112
a(x)01133366661010
b(x)002135357968
c(x)-111-1-1-11111-1-1

Bei a(x) han­delt es sich um die Fol­ge der größten Drei­ecks­zah­len klei­ner oder gleich (x-1), wo­bei die n-te Drei­ecks­zahl (n+1)-mal hin­ter­ein­an­der ge­schrie­ben wird.[1] Dar­aus er­hal­ten wir die For­mel:

a(x)=1/2⋅⌊(√1+8⋅(x-1)-1)/2⌋⋅⌊(√1+8⋅(x-1)+1)/2⌋


Bei b(x) han­delt es sich um x mi­nus das x-te Ele­ment der Fol­ge von den zei­len­wei­se ge­le­se­nen Zah­len ei­nes Drei­ecks, wo­bei in der n-ten Zei­le die ers­ten n natürli­chen Zah­len ste­hen und in ab­stei­gen­der Rei­hen­fol­ge ge­schrie­ben wer­den.[2] Dar­aus er­hal­ten wir die For­mel:

b(x)=x-1/2⋅(2-2⋅x+[√2⋅x]+[√2⋅x]2),


wo­bei die ecki­gen Klam­mern für kaufmänni­sches Run­den ste­hen. Schließlich brau­chen wir noch c(x), wel­ches ich ein­fach aus­drücke durch:

c(x)=(-1)b(x)-a(x)+1


So­mit ha­ben wir al­le Kom­po­nen­ten für die Ab­bil­dung g+:ℕ→ℚ+ mit x↦((x-a(x)/(x-b(x)))c(x) zu­sam­men. Nun muss die Ab­bil­dung noch von +=ℕ/ℕ auf ℚ=ℤ/ℕ er­wei­tert wer­den. Da­zu ge­hen wir wie bei der Ab­bil­dung f:ℕ→ℤ vor und las­sen das Vor­zei­chen al­ter­nie­ren. Die 0 muss eben­falls noch mit ins Boot ge­holt wer­den:

g(x)=  {   0 falls x=0
-g+((x+1)/2) falls 2∤x
 g+(x/2) sonst


Es fehlt nun noch die Um­kehr­funk­ti­on g:ℚ→ℕ. Da­zu ma­che ich aber­mals einen Zwi­schen­schritt durch g±:ℚ→ℤ. Da­zu stel­len wir uns einen Zah­len­strahl vor:

-2/2-2/1-1/2-1/101/11/22/12/21/32/33/13/2
-4-3-2-1012345678


Dar­aus lässt sich mehr oder we­ni­ger leicht fol­gen­de For­mel ab­le­sen:

g±(x)=(-1)(x<0)⋅  {  ∑[2⋅i-1,{i,1,q(x)-1}]+p(x) falls p(x)<q(x)
∑[2⋅i-1,{i,1,p(x)-1}]+(p(x)-1)+q(x) sonst


Da­bei soll p(x) den Zähler und q(x) den Nen­ner (bei­de vor­zei­chen­los) von x lie­fern. Um den Auf­bau die­ser bei­den Funk­tio­nen soll es nicht wei­ter ge­hen, die unschöne, aber ein­fa­che In­for­ma­ti­ker­va­ri­an­te wäre:

Eingabe als Dezimalzahl:

q(x)=|m/ggT(x⋅m,m)| | m=10len(x-⌊x⌋)-2

p(x)=|x⋅q(x)|

Oder – noch einfacher – Eingabe als Bruch in der Form p/q:

q(x)=x.split("/")[1]

p(x)=x.split("/")[0]


Nun nut­zen wir die Funk­ti­on f vom An­fang, um g:ℚ→ℕ zu er­hal­ten:

g(x)=f(g±(x))


So­mit er­hal­ten wir die Wer­te:

-2/2-2/1-1/2-1/101/11/22/12/21/32/33/13/2
75310246810121416


Al­ler­dings ist dies noch nicht ganz die Ta­bel­le, die wir ha­ben wol­len. Wir ha­ben zwar ei­ne Ab­bil­dung von nach , da­bei han­delt es sich aber nicht um die ge­such­te Um­kehr­funk­ti­on g:ℚ→ℕ, wel­che die fol­gen­den Wer­te ha­ben müss­te:

75310246810121416
-3/1-2/1-1/2-1/101/11/22/13/12/21/31/42/3


An­ders aus­ge­drückt su­chen wir nun noch ei­ne Um­sor­tier­funk­ti­on s:ℕ→ℕ.

xs(x)
1-1/11
21/12
3-1/23
41/24
5-2/15
62/16
7-2/29
82/210
9-1/311
101/312

Die­ses Pro­blem löse ich al­go­rith­misch. Schau­en wir uns noch ein­mal den Weg des Abzählens von + in ei­nem Ko­or­di­na­ten­sys­tem an:

X
y\x012345
012671516
13581417
2491318
3101219
41120
521
          
S
y\x012345
01251017
13461118
27891219
31314151620
421
5


Man erhält die Ko­or­di­na­ten aus X und S zu ei­nem be­stimm­ten Wert x fol­gen­der­maßen aus:

XS
0. x=y=0
1. if(get(x,y)=x)
    return (x,y)
2. //do
   //nothing
3. moveTo(x+1,y)
   do(1.)
4. while(x≠0)
    moveTo(x-1,y+1)
    do(1.)
5. moveTo(x,y+1)
   do(1.)
6. while(y≠0)
    moveTo(x+1,y-1)
    do(1.)
7. goTo(3.)
           0. x=y=0
1. if(get(x,y)=x)
    return (x,y)
2. moveTo(x+1,0)
   do(1.)
3. moveTo(0,y+1)
   do(1.)
4. while(x<y)
    moveTo(x+1,y)
    do(1.)
5. moveTo(x+1,0)
   do(1.)
6. while(y<x-1)
    moveTo(x,y+1)
    do(1.)
7. goTo(3.)


Wir er­hal­ten die Funk­ti­on s(x), in­dem wir x aus dem Sys­tem S auf sei­ne Ent­spre­chung im Sys­tem X ab­bil­den. Un­ter Be­ach­tung des al­ter­nie­ren­den Vor­zei­chens er­gibt sich:

s(x)=2⋅X.get(S.getX(⌈x/2⌉),S.getY(⌈x/2⌉))-(⌈x/2⌉-⌊x/2⌋)

Und somit erhalten wir schließlich:

g(x)=s(f(g±(x)))


Fa­zit: Wir[3] ha­ben ge­zeigt, dass die gan­zen Zah­len und die ra­tio­na­len Zah­len abzähl­bar sind, in­dem wir je­weils ei­ne bi­jek­ti­ve Ab­bil­dung zwi­schen ih­nen und den natürli­chen Zah­len ge­fun­den ha­ben. D. h., dass es je­weils Funk­ti­on gibt, die je­der natürli­chen Zahl ein­ein­deu­tig ei­ne gan­ze Zahl so­wie ei­ne ra­tio­na­le Zahl zu­weist. Oder auch: F:ℕ→ℕ×ℤ×ℚ mit x↦(x,f(x),g(x)); bspw. 3↦(3,-2,-1/2). Eben­so gibt es ent­spre­chen­de Ab­bil­dun­gen G:ℚ→ℕ×ℤ×ℚ und H:ℤ→ℕ×ℤ×ℚ.

Für den CAS-Rech­ner (ich ha­be einen TI-Nspi­re CX) se­hen die For­meln dann so aus:
f(x):
f(x):
a(x):
b(x):
c(x):
g+(x):
g(x):
q(x):
(funktioniert hier nur bis zu drei Nachkommastellen)
p(x):
g±(x):
g(x):
s(x):(dafür reichen meine CAS-Kenntnisse nicht aus)

[1]s. OEIS: A057944
[2]s. OEIS: A004736
[3]Plu­ra­lis Mo­des­tiae be­ach­ten ;-)

Edit: There's a little mistake in this post, you should also read the second part: A bijective function to ℚ #2.

A set S ist called count­ably in­fin­ite if there is a biject­ive func­tion f:ℕ→S. We know that there is a biject­ive func­tion between the nat­ur­al num­bers and the in­teg­ral num­bers and also between and the ra­tion­al num­bers . There­fore there is func­tion f, which maps to and whose in­verse func­tion f maps to . And, in­deed, this func­tion is easy to find:

But how does the sim­il­ar func­tion g:ℕ→ℚ look like? Ther­for I make a in­ter­me­di­ate step and look for the biject­ive func­tion g+:ℕ→ℚ+ first. We know that is count­able, be­cause of we can ar­range them in rows and columns and eas­ily count them:

So we look for a func­tion, which maps the val­ues as fol­lows:

Let x↦p/q with p,q∈ℕ. Then you can draw the fol­low­ing table (the columns for (x-p) and (x-q) we need later):


It is easi­er to search a func­tion x↦((x-a(x)/(x-b(x))). And let me be­fore­hand make this step: We are search­ing a func­tion x↦((x-a(x)/(x-b(x)))c(x). So what are the de­pend­ing on x com­pon­ents a(x), b(x) and c(x)?

We get the an­swer when we have a more in­tens­ive look at the val­ues of (x-p) and (x-q) and see the fol­low­ing co­her­ences:


Ex­plan­a­tion: If c(x)=-1 the frac­tion's re­cip­roc­al is formed, oth­er­wise (c(x)=1) the frac­tion won't be changed. Us­ing this ex­po­nent we can swap (x-p) and (x-q) and sep­ar­ately work with the nu­mer­ic­al series as they are in the columns a(x) and b(x). More pre­cisely, we need func­tions a(x), b(x) and c(x) which map to the fol­low­ing val­ues:


We get a(x) as the largest tri­an­gu­lar num­ber less than or equal to (x-1), wherby the n-th tri­an­gu­lar num­ber is writ­ten n+1 times.[1]


We get b(x) as a tri­angle read by rows, wherby row n lists the first n pos­it­ive in­tegers in de­creas­ing or­der.[2]


The square brack­ets in­dic­ate nor­mal round­ing. Fi­nally we need c(x) which I write as:


So we have all com­pon­ents which we need for the func­tion g+:ℕ→ℚ+ with x↦((x-a(x)/(x-b(x)))c(x) to­geth­er. Now we have to ex­tend the func­tion from +=ℕ/ℕ to ℚ=ℤ/ℕ. Ther­for we do it like with the func­tion f:ℕ→ℤ and let the sign al­tern­ate. The zero has to be in­cluded, too:

At least we are in need for the in­verse func­tion g:ℚ→ℕ. Ther­for I make an in­ter­me­di­ate step again by g±:ℚ→ℤ. Ima­gine a num­ber­line:



This gives us in a more or less easy way the fol­low­ing for­mula:


Thereby p(x) re­turns the nu­mer­at­or and q(x) re­turns the de­nom­in­at­or (both un­signed) of a frac­tion. The work­ing of these two func­tions shall not be of fur­ther in­terest; the nasty, but simple com­puter sci­ent­ist's vari­ant would be:

Now we use the func­tion f(x) of the be­gin­ning to get g:ℚ→ℕ:


There­with we get the val­ues:



But these aren't ex­actly the val­ues, which we want to have. We in­deed have a func­tion from to , but this isn't the in­verse func­tion g:ℚ→ℕ which we are look­ing for. That one should give us the fol­low­ing val­ues:



In oth­er words, we still have to find a re­sort func­tion s:ℕ→ℕ.


This prob­lem I solve al­gorith­mic­ally. Let's have a look at the way of count­ing + in a co­ordin­ate sys­tem again:



You get the co­ordin­ates of a spe­cif­ic value x and the sys­tem X or S do­ing the fol­low­ing:


We get the func­tion s(x) by map­ping x out of S to its equi­val­ent ele­ment in X. With the al­tern­at­ing sign in mind we get:



Con­clu­sion: We[3] il­lus­trated the count­ab­il­ity of the in­teg­ral and ra­tion­al num­bers by find­ing for each one a biject­ive map­ping on the nat­ur­al num­bers. That means that there is a func­tion which maps every nat­ur­al num­ber one-to-one on a in­teg­ral num­ber and a ra­tion­al num­ber. Or also: F:ℕ→ℕ×ℤ×ℚ with x↦(x,f(x),g(x)); e.g. 3↦(3,-2,-1/2). There are also sim­il­ar map­pings G:ℚ→ℕ×ℤ×ℚ and H:ℤ→ℕ×ℤ×ℚ.

These are the for­mu­las in the CAS syn­tax (I've got a TI-Nspire CX):

[1]see OEIS: A057944
[2]see OEIS: A004736
[3]at­ten­tion to the plural­is mod­esti­ae ;-)

Kommentare:

  1. Auf jeden Fall interessant, aber ich habe es grade auch nicht durchgeschafft. Dafür ist es grade einfach zu spät.^^" Aber du verlässt manchmal den grauen Bereich. Gute Arbeit.^^

    AntwortenLöschen
    Antworten
    1. Bei großen Formeln o. Ä. geht es manchmal nicht anders.
      Was mich an diesem Beitrag schon die ganze Zeit wurmt, ist, dass bspw. 1/1 und 2/2 oder 1/2 und 2/4 als verschiedene Elemente betrachtet werden. Irgendeine Bemerkung dazu?

      Löschen
  2. Naja, es stört ja nicht bei der Abbildung auf die Reellen Zahlen, da die Elemente zwar doppelt erreicht werden, aber trotzdem in der Zielmenge nur einmal vorkommen. Allerdings macht das ja die eineindeutige Zuordnung der Bijektion unmöglich, da eine Umkehrfunktion von 1/1 und 2/2 auf 2 verschiedene Werte abbilden würde. Oder was meinst du?

    AntwortenLöschen
    Antworten
    1. Ich meine, dass wir die rationalen Zahlen im Gegensatz zu den reellen Zahlen zwar abzählen können, aber die Funktion, die ich gebaut habe, nicht bijektiv ist. Wendet man Cantors erstes Diagonalargument auf die Menge der positiven Brüche an (s. hier), werden kürzbare Brüche ja ausgelassen. D. h. im Klartext: Meine Funktion ist falsch bzw. nicht bijektiv, da sie die kürzbaren Brüche nicht überspringt. Also werde ich mich wohl nochmal dransetzen und eine neue bauen. Das stelle ich mir momentan gar nicht so schwer vor (ich müsste ja lediglich eine Art Zähler hinzufügen).

      Löschen
  3. Antworten
    1. There's a little mistake; you should check out the second part: A bijective function to ℚ #2

      Löschen