Milyen bijektív leképzés van az R számhalmaz és az N->N függvények között?

@10:36

Ennek a mondatnak mi értelme van?

Mit jelent az hogy "rész-értékkészlete" ? Ennek a kifejezésnek a definíciója hol található?

A kérdés jó, egy tudományos matematikai kérdés.

Tudjuk hogy a 0-1 sorozatok számossága is continum mint a valós számok számossága, így létezik bijetív leképezés a valós számok és ezen sorozatok között is.

A 0-1 sorozatok és N->N függvények között egyszerűbb bijetív leképezést találni mint az eredeti kérdésre, ezért vezessük vissza erre a problémára.

Kétféle "iskola" van, van amelyik a 0-át is természetes számnak veszi van amelyik nem. Igazából ez nem matematikai kérdés, hogy a 0 természetes szám -e hanem konvencionális. Azt a szemantikát alkalmazom ahol természetes számok a nemnegatív egészek, így a nulla is.

Egy N->N leképezés megfeleltethető egy természetes számokból álló sorozattal, amely lista indexelhető az indexek is természtes számok. Bármelyik i indexen található sorozatelem az l leképezésben l(i) értékű.

Bármely 0-1 sorozat megfeleltethető binárisan kódolva egy-egy adott természetes számok sorozatának, ezen sorozat pedig meg megfeleltethető egy N->N leképezésnek.

Szekvenciálisan egymás után legyenek a sorozatelemek binárisan kódolva tetszőlegesen nagy természtes számok bináris kódolását is lehetővé téve, úgy hogyha az egyik szám bináris reprezentációja végetér akkor következik a következő szám bináris reprezentációja. Legyen mindig egyértelmű hogy hol kezdődik és hol végződik egy bináris szám reprezentációja.

A kódolási szabály legyen a következő:

Először a szám hosszát jelöljük, ez után következik a szám binárisan kódolt értékes jegyei.

A szám hosszát unáris kódolással írjuk le azzal a kiterjesztéssel, hogy nulla is lehet a hossza ezt 0-val jelöljük.

Ha a hossza 0 akkor nem adunk meg sosem értékes jegyeket, a szám értéke ez esetben 1.

Ha több mint nulla a szám hossza akkor unárisan kódoljuk a hosszt, azaz annyi darab 1-es amennyi a szám hossza.

Így például az egy hosszú lehetséges számok bináris reprezentációja 1 0 és 1 1. Az 1 0 értéke 2, 1 1 értéke 3.

Ha a hossza kettő akkor a lehetséges kettő hosszú számok 11 00 , 11 01 , 11 10 , 11 11.

11 00 értéke 4, 11 01 -> 5 , 11 10 -> 6, 11 11 -> 7.

A példákban azért hogy jól látható legyen elválasztottam szóközzel a hosszt és az értékes számjegyeket, természetesen a kódolásban nincs semmi szóköz mert csak 0-át és 1-et lehet használni semmi plusz jelet.

Máshogy összefoglalva a példák:

hossz(0) -> {1}

hossz(1) -> {2,3}

hossz(2) -> {4,5,6,7}

Adott hosszú számok ezen értékeket vehetik fel.

Mivel végtelen hosszú 1-esekből álló sorozat is előfordulhat, vagy elejétől fogva vagy egy adott pozíciótól kezdődően, így ez esetben ha az unáris kódolás szerint végtelen 1-es akkor a szám értéke 0.

Definíció:

ha n=0 akkor hossz(n) -> {1}

különben

ha hossz(n) = ∞ akkor hossz(n) -> {0}

különben

hossz(n) -> {2^n ... 2^(n+1)-1}

ahol n ∈ N.

Ezzel megalkottunk egy bijetív leképezést a 0-1 sorozatok és a természtes számokból álló sorozatok között. Mivel tudjuk hogy az N->N leképezések és a természetes számokból álló sorozatok egymással mefeleltethetőek így beláttuk, hogy ezen definíció szerint kaptunk egy bijektív leképezést a 0-1 sorozatok és az N->N leképezések között.

Tudjuk, hogy a [0-1] között lévő valós számok bináris ábrázolásában léteznek számok melyeknek különböző az alakja, de mégis ugyanazon értékűek. Megszámlálhatóan végtelen ilyen valós szám van. Ilyen bináris szám például 0.011111 ... = 0.1 . (Ahol az 1-esek végtelenségig folytatódnak az egyenlőség bal oldalán.) Ezért nem triviális a bijektív leképezés a 0-1 sorozatok és a [0-1] valósak között.

Ezért csináljuk a következőt:

Az összes ilyen reprezentációt lexikografikusan csökkenő sorrendben írjuk egymás mellé, azaz alkossunk belülük egy sorozatot: 1, 0.1... , 0.1, 0.01...,0.01, 0.001... . A 0. részt vegyük ki, transzormáljuk át 0-1 sorozatokká triviálisan. a transzformáció után : 10...,01...,010...,001..., ... ezt kapjuk. Kaptunk egy olyan sorozatot melynek elemei 0-1 sorozatok. Vegyük még hozzá azt a két esetet is ahol csupa 0 és csupa 1-es, így lesz :

0...,1..., 10...,01...,010...,001..., ... ez a sorozat. Ennek a sorozatnak minden 2-vel osztható indexe szerinti értéket rendeljük hozzá minden természetes számhoz sorban haladva, a többit pedig a negatív egészekhez, szintén sorban haladva (abszolút értékben sorban, azaz csökkentő sorrendben a negatív egészeken haladva). Eddig megvan minden elejétől vagy egy adott ponttól végtelenségig ismétlődő csupa 0 vagy csupa 1-et tartalmazó 0-1 soroztatnak a valós képe, amely minden esetben egész szám lesz (mármint a képe egész szám).

A sorozat többi elemének a képe :

Speciálisan módosított unáris kódolás adja a számnak az egészrészét. A már fentebb hossz módszer szerint kódoljuk unárisan, ahol a reprezentáció az hogyha az unáris kép 2-vel osztható akkor osszuk kettővel az lesz az egész része, ha nem osztható kettővel akkor kerekítsük felfele egészre és váltson negatív előjelre. Így pl. 111 -> 3/2 -> -2 ; 1 -> 1/2 -> -1; 0 -> 0 ; 11 -> 2/2 -> 1 ; 1111 -> 4/2 -> 2 .

A speciális módosítással lévő unárisan kódolt reprezentáció után a szám törtrészét kódoljuk binárisan a szokásos módon (ahogy kell számítani 0-1 közötti bináris számot fixpontos ábrázolással), úgy hogy az előjelet ne vegyük figyelembe, az előjelet a módosított unáris kódolás definiálja.

Ezt az utóbbi 0-1 sorozat bijektíven valóssá leképezését az N->N 0-1 sorozattá bijektív leképezéssé házasításával kapjuk meg az eredeti kérdésre egy bijektív leképezést.

"Speciálisan módosított unáris kódolás adja a számnak az"[...]

Javítok:

A nulla az előjel nélküli önmagában, de ezen esetekre melyekre definiáltam mindig nulla egész valamennyi ami vagy pozitív vagy negatív lehet csak, pontosan nulla nem lehet mert azon esetet már fentebb lefedtem, sőt az összes egészet már előtte lefedtem. Így nem lesz bijektív mert a mínusz egy nulla intervallum kimaradt.

Probléma megoldva hogy egyel elcsúsztatom a reprezentációt, a -0 és +0-át is berakva a sima 0-át meg kivéve (természetesen nulla egész valamennyi, a törtrész megmondja mennyi pontosan).

Dehát javítva :

Ha a spec. unáris páros akkor változik a transzformáció, még ki kell vonni belőle 1-et mindegyikből, ha -1-et kapunk kivonás után akkor lesz -0, ha 0 lesz kivonás után akkor lesz +0 a többinél simán csak kivonni, vagyis a példák:

111 -> 3/2 -> -2 ; 1 -> 1/2 -> -1; 0 -> -0 ; 11 -> 2/2 -> +0 ; 1111 -> 4/2 -> 1

Nem szóltatok, de (nem gondolkodtam rajta egyszer csak beugrott), hogy mindig van egy hiba.

A hiba az hogy amit mondtam definíciót, illeve amit magyaráztam a végtelen hosszú 0-1 sorozatokról ezzel kapcsolatban : "Definíció:

ha n=0 akkor hossz(n) -> {1}

különben

ha hossz(n) = ∞ akkor hossz(n) -> {0}

különben

hossz(n) -> {2^n ... 2^(n+1)-1}

ahol n ∈ N."

Ha végtelen sok 1-es van akkor ott elakadt a sorozat, csak véges elemű lehet ez esetben és nem tartalmazhat nulla után semmit.

Ezt úgy kikorrigálhatjuk, hogy amit írtam hogy két fajta fixpontos bináris reprezentációja van megszámlálhatóan végtelen sok számnak a hozzárendelést magamtól idézve " A 0. részt vegyük ki, transzormáljuk át 0-1 sorozatokká triviálisan. a transzformáció után : 10...,01...,010...,001..., ... ezt kapjuk. Kaptunk egy olyan sorozatot melynek elemei 0-1 sorozatok. Vegyük még hozzá azt a két esetet is ahol csupa 0 és csupa 1-es, így lesz ..." végezzünk el előbb egy efféle transzformációt hogy kiküszöböljük transzformáció után az ilyen hülye esetet hogy végtelen sok 1-es legyen. (A bijekció miatt minden kombináció lefedve.) A kritikus rész utáni sorozatot transzformáljuk át az alábbi párosodik páratlanadik szerint ahogy már leírtam azzal a kiegészítéssel hogy mindig annak az adott páros vagy páratlan számnak vegyük végtelen bináris jegyik a fixpontos képét a végtelen nullás helyiértékek ábrázolás szerint. Vagyis így a 0-1 sorotatból 0-1 sorozatba bijektív leképezést hajtottunk végre ahol a képelemek között nincsennek már bonyodalmat okozó a végtelenségig folytatódó csupa 1-esek.

Így egy értékkel elcsúsztatásra kerülnek a lehetséges számhalmazok (avagy relációk) a hossz függvényében.

A példák :

hossz(0) -> {0}

hossz(1) -> {1,2}

hossz(2) -> {3,4,5,6}

Így a definíció így alakul:

ha n=0 akkor hossz(n) -> {0}

különben

hossz(n) -> {2^n-1 ... 2^(n+1)-2}

ahol n ∈ N.