Matek (Végtelenek közti különbség)?

"Mi a különbség ha azt mondom hogy van rá algoritmus vagy az hogy van rá egyértelmű hozzárendelés?"

Az algoritmus véges sok lépésben választ ad egy kérdésre. Például arra, hogy ennek az X elemnek mi a hozzárendelt párja. Viszont lehet olyan kölcsönösen egyértelmű megfeleltetés két halmaz között, hogy nincs hozzá algoritmus.

"- Minden elemnek van egy előző, és egy rákövetkező eleme. "

Ez így kevés. A valós számoknak is van olyan rendezése, amelyben minden valós számra van rákövetkező és megelőző:

a < b akkor és csak akkor, ha b törtrésze nagyobb, mint "a" törtrésze, VAGY egyenlők a törtrészek és b egészrésze nagyobb.

Ekkor minden a-hoz van egy rákövetkező elem: a+1, és egy közvetlenül megelőző is: a-1. Csak az nem igaz, hogy létezni fog a távolság két elem között.

"Az algoritmus véges sok lépésben választ ad egy kérdésre. Például arra, hogy ennek az X elemnek mi a hozzárendelt párja. Viszont lehet olyan kölcsönösen egyértelmű megfeleltetés két halmaz között, hogy nincs hozzá algoritmus."

Például melyik leképezés amihez nincs algoritmus?

Amúgy meg hogy az algoritmus választ ad egy kérdésre véges lépésen belül ez "csúsztatás" lásd megállási probléma, post megfelelkezési probléma, vagyis eshet végtelen ciklusba.

----

"Ekkor minden a-hoz van egy rákövetkező elem: a+1, és egy közvetlenül megelőző is: a-1. Csak az nem igaz, hogy létezni fog a távolság két elem között."

Ez meg totál zavaros.

> Ez így kevés. A valós számoknak is van olyan rendezése,

> amelyben minden valós számra van rákövetkező és megelőző:

> a < b akkor és csak akkor, ha b törtrésze nagyobb, mint "a" törtrésze,

> VAGY egyenlők a törtrészek és b egészrésze nagyobb.

Előtte és utána – értsd kisebb, nagyobb – tulajdonságot definiáltál csak ezzel, a rákövetkező elemet és megelőző elemet nem. Ez így valóban kevés.

De legyen a := pi (3,14159265…), legyen b := 5 + 1/2.

Te annyit állapítottál meg, hogy a < b. De nem mondtad meg, hogy mi következik közvetlenül a vagy b után és mi van közvetlenül a vagy b előtt. Ha megtennéd, akkor elegendő lenne.

Pl. ott vannak a racionális számok. Tudjuk(?) hogy megszámlálhatóan végtelen a számosságuk.

Itt egy kép: [link]

Ez egy „algoritmus”, egy eljárás, amivel fel lehet sorolni az összes pozitív racionális számot. Bármely szám esetén elméletileg meg lehet mondani, hogy hányadik lépésben érünk oda. Ez teljesen ekvivalens azzal, hogy egyértelmű megfeleltetésbe hozzuk a racionális számokat a természetes számokkal:

1 - 1/1

2 - 2/1

3 - 1/2

4 - 1/3

5 - 2/2

6 - 3/1

7 - 4/1

8 - 3/2

9 - 2/3

10 - 1/4

stb…

Ez viszont teljesen ekvivalens azzal, hogy létezik olyan algoritmus, amivel bejárható az összes racionális szám: „Menj végig az átlón, majd ha végigértél, lépj a következő átlóra.”. Gyakorlatban persze egy algoritmusról az gondoljuk, hogy véges idő alatt fut le. De itt elméleti algoritmusról, más néven módszerről, eljárásról van szó, ami tulajdonképpen pont az általad említett természetes számoknak való egyértelmű hozzárendelésének a módját, mikéntjét írja le, hogy melyikhez melyiket kell hozzárendelni.

De ez megint ekvivalens azzal, hogy minden elemnek van egy egyértelműen meghatározott következő és előző eleme. Pl.:

Szám: 1/3. Előző: 1/2. Következő: 2/2

Szám: 3/2. Előző: 4/1. Következő: 2/3

Ez pont azt mondja meg, hogy a természetes számokhoz való egyértelmű hozzárendelés esetén melyik halmazelem tartozik az eggyel kisebb, illetve eggyel nagyobb természetes számhoz. Ha ez az előző, következő elem egyértelműen meghatározott, akkor csak egy két irányú lánc építhető fel. Nincs elágazás, hiszen ha két elemnek ugyanaz az előző eleme, akkor annak az előző elemnek nem egyértelmű a következő eleme. Ha egy elem nincs a láncban, akkor annak ugye nincs előző vagy következő eleme. Itt egyedül az lehetne jogos kifogás, hogy mi van akkor, ha két, vagy véges sok lánc alakul ki. De ez sem jelent igazából gondot. A gond ott lenne, ha végtelen sok lánc alakulna ki, amit megint fel tudnánk oldani a racionális számok végtelenje kezelésének módszerével.

> Bármely két elemhez definiálható egy távolság, ami a két elem közötti elemek számánál eggyel nagyobb számot jelent.

Szerintem ez is könnyen belátható. Nem véletlenül írtam távolságot és nem különbséget. A távolság az előbb linkelt ábrán a 3/1 és 2/3 között 3, mivel közöttük két halmazelem található (3/1 , 4/1 , 3/2 , 2/3). A különbségük egészen más kérdés. Valós számok esetén a különbség ugye számolható, de hogy hány valós szám van két kiválasztott valós szám között? Na ez az, ami nem kifejezhető, illetve végtelennek kell mondanunk.

~ ~ ~ ~ ~ ~ ~

> Ekkor minden a-hoz van egy rákövetkező elem: a+1, és egy

> közvetlenül megelőző is: a-1. Csak az nem igaz, hogy létezni fog a távolság két elem között.

Őőőőő…… Miért is? Miért következne a pi után a 4,1415926535, kihagyva mondjuk a 4-et, vagy a 11/3-ot, meg az e*3/2-t? Milyen logika diktálja, hogy a természetes számok rákövetkező és előző elemét összemossuk a valós, vagy racionális számokkal?

~ ~ ~ ~ ~ ~ ~

Amúgy a valós számoknál pont az a probléma, hogy ha elkezdjük a racionális számok felsorolásának módszerével – algoritmusával – hozzárendelni őket a természetes számokhoz, akkor felmerül néhány kérdés:

- És mikor – hányadik lépésben – érünk a pi-hez? Értsd: Mi az "1" mint halmazelem és a "pi" távolsága?

- És mi a pi következő/előző eleme?

Persze lehet, hogy csak rossz az algoritmusunk, ez még nem bizonyítja, hogy a valós számok megszámlálhatatlanul végtelenek lennének. De szerencsére Canton bácsi bizonyítást talált arra, hogy nem lehet ilyen hozzárendelést végezni a valós számok és a természetes számok között. ( [link] ) Pontosan azt mondta ki, hogy amennyiben találni vélünk !bármilyen! módszert a valós és természetes számok egyértelmű megfeleltetésére, úgy alkotható minimum egy – de amúgy végtelen sok – olyan valós szám, ami biztosan nincs benne a felsorolásban, amihez nincs természetes szám hozzárendelve.

Kis módosítás az előző hozzászóláshoz:

„A gond ott lenne, ha végtelen sok lánc alakulna ki, amit megint fel tudnánk oldani a racionális számok végtelenje kezelésének módszerével.”

Helyett:

A gond ott lenne, ha MEGSZÁMLÁLHATÓAN végtelen sok lánc alakulna ki, amit megint fel tudnánk oldani a racionális számok végtelenje kezelésének módszerével.

Ha megszámlálhatatlanul végtelen sok lánc van, akkor ott vagyunk, ahol a part szakad. Lásd: 0-1-ig az összes valós számhoz hozzá lehetne rendelni előző és következő elemet az általad felvetett -1 és +1 módszerrel, ami megszámlálhatatlanul végtelen sok láncot jelentene, minden valós szám esetén lenne egy előző és következő elem definiálva ezzel a módszerrel. Ilyen módon tehát tényleg igaz, hogy az egyértelmű előző és következő elem definiálása önmagában valóban nem elegendő feltétel, hozzá kell tenni azt is, hogy az így meghatározott láncok számának megszámlálhatóan végtelennek kell lennie, vagy csak a másik feltétel a bármelyik két szám közötti távolság definiálhatóságával együtt elegendő. Tehát ez a feltételem valóban nem igaz, csak nem a te indokod miatt, hanem más miatt.

Az általam adott relációról nem mondtam, hogy köze van a hétköznapihoz. Csak azt mondtam, hogy képes arra, hogy antiszimmetrikus, tranzitív, és bármelyik x valós számra van a reláció szerint rákövetkező (x+1) és megelőző (x-1). Ez pont arra példa, hogy hiába van rákövetkező és megelőző elem, kialakulhat több, mint megszámlálhatóan végtelen sok lánc (ez esetben: egy-egy lánc az azonos törtrészű valós számok halmaza, törtrészből viszont kontinuum sok van), és akkor bukta van.

Ahogy te is mondtad.

"Például melyik leképezés amihez nincs algoritmus?"

Nem tudok példát mondani rá. Viszont létezik olyan leképezés, amihez nincs algoritmus. Egyszeűen azért, mert több leképezés van, mint algoritmus.

Vegyük csak a természetes számok halmazának megszámlálhatóan végtelen számosságú részhalmazait! (Pl. ilyen a páros számok halmaza.) Ezek mind msz. végtelen halmazok, viszont kontinuum (több, mint msz.) sok van belőlük.

Algoritmusokból viszont csak msz. végtelen sok van. (A pontosság igénye nélkül: minden algoritmust leírhatsz egy előre megállapított nyelven egy véges hosszú szövegben - viszont a véges hosszú szövegek száma is msz. végtelen.)

Na tehát: több, mint msz. sok msz. végtelen halmaz - de csak msz. végtelen sok algoritmus van összesen. Akkor van olyan halmaz, amelynek a bijektív leképezését a természetes számok halmazára biztosan nem tudod algoritmussal leírni.

Ez persze ott nem stimmel, hogy ahogy az algoritmusok száma msz. végtelen, ugyanazzal a gondolatmenettel a definiálható halmazok száma is végtelen.

Tehát van olyan msz. végtelen részhalmaza a természetes számoknak, amit még definiálni sem tudsz.

Ami igaz, az igaz: arra nem tudok példát mondani, hogy két DEFINIÁLHATÓ és msz. végtelen halmaz között ne legyen algoritmus. Ez lehet, hogy mindig igaz, nem tudok ellenpéldát rá.

Csak szerettem volna felhívni a figyelmet, hogy a "létezik" és a "meg is tudod mondani, mi az" (vagy a "van rá algoritmus") nem feltétlen ugyanazt jelenti.

+ megjegyzés:

Erre a különbségtételre a kérdezőnek nem hiszem, hogy szüksége lesz.

#16: No akkor a végén még meg is értem, miért volt problémád az egyik szeletével a dolognak, miért tartottad az egyik általam felsorolt feltételt aggályosnak. Innen nézve úgy tűnik, jogosan. Viszont még mindig tartom azt, hogy a „definiálható előző és következő elem” és a „ilyen módon bármelyik két elem között értelmezhető a távolság” együttesen kielégítő feltétel ahhoz, hogy egy halmaz megszámlálhatóan végtelen legyen.

Az algoritmus vs. egyértelmű megfeleltetés felett nehéz vitát nyitni, ez inkább definíciós, filozófiai kérdés. Számomra az van, hogy ha létezik megfeleltetés, akkor azt valamilyen módon meg lehet fogalmazni, akár csak a párok – természetesen végtelen hosszú – felsorolásával is. Számomra ez is algoritmus, eljárás, módszer. A létezik mindkét esetben számomra azt jelenti, hogy nem feltétlenül biztos, hogy ismerjük is ezt. Tehát az, hogy létezik és az, hogy ismerjük az mindkét esetben egészen más tészta.

Most gondolkodom tovább, mert találtam olyan esetet, aminél újfent elbizonytalanodtam kicsit.

> Vegyük csak a természetes számok halmazának

> megszámlálhatóan végtelen számosságú részhalmazait!

> (Pl. ilyen a páros számok halmaza.) Ezek mind msz.

> végtelen halmazok, viszont kontinuum (több, mint msz.)

> sok van belőlük.

> viszont csak msz. végtelen sok van.

Ez érdekes aspektusa a kérdésnek. Pl. ugye ott a példád. Vegyünk egy tetszőleges valós számot 0 és 1 között (a[0]). Legyen egy megfeleltetés az egész számok (amelyek megszámlálhatóan sokan vannak) és a pozitív valós számok között.

n egész számhoz – ha az nem nulla – rendeljük hozzá a[n]-t, ahol a[n] = a[0]+n

Az előző, következő definiálásával:

a[n+1] = a[n]+1

a[n-1] = a[n]-1

(Kicsit pongyola megfogalmazás, de szerintem érthető.)

Kapunk egy megszámlálhatóan végtelen halmazt. Ilyenből megszámlálhatatlanul sok van, attól függően, hogy mit választunk a[0]-nak. Mégis ennek a megszámlálhatatlanul sok végtelen halmaz esetén egyetlen algoritmus írja le a valós számok egy végtelen halmaza és az egész számok közötti megfeleltetést. Az algoritmus ugyanaz, csak a kezdeti paraméter, az a[0] változik. Persze számítógépen nem lehet minden válós számot ábrázolni, de itt nem számítástechnikai értelemben értettem az algoritmust, hanem matematikai eljárásként.

Röviden egyetlen algoritmus képes kontinuumnyi megszámlálhatóan végtelen halmazt leírni.

> + megjegyzés:

> Erre a különbségtételre a kérdezőnek nem hiszem, hogy szüksége lesz.

Nem, de attól még jó móka. Valamelyikünk okosabb lesz általa. Én már találtam egy hibát a gondolatmenetemben, tehát én már tanultam belőle, tehát nem válik káromra a dolog. Persze ha téged untat, vagy nincs kedved, időd, energiát boncolgatni a témát, azt is megértem. Mindenesetre nekem tetszik ez a „gondolkodjunk együtt” téma.

#17-es 16:49-kor

"Nem tudok példát mondani rá. Viszont létezik olyan leképezés, amihez nincs algoritmus. Egyszeűen azért, mert több leképezés van, mint algoritmus...."

Köszönöm, kielégítő válasz volt. (Ment a zöld kéz.)