Játék a végtelennel avagy a kurvaanyját a koronavírusnak
Eredeti szerző: jotunder
Az elmúlt napokat kvázikaranténban töltöttem ( kétszer lementem a kisboltba és tegnap vettem ezt a barbadosi cuccot, amiből a poszt megírása alatt elfogy féldeci ) és Királyhegyi Pállal szólva, most ment el teljesen a kedvem a koronavírustól.
Ami most jön, az egy filozófiai példabeszéd: Néha bonyolultan hangzó trivialitások állnak az egyszerűen hangzó nehéz állítások mögött.
Az egyszerűen hangzó és elég rafkós állítás az, hogy bárhogyan színezzük ki a természetes számokat véges sok színnel, lesz egy olyan színosztály, ami tartalmaz végtelen sok olyan elemet, amelyek tetszőleges véges részösszege is benne van a színosztályban. Ez a Hindman-tétel. És most tiltakozásul a koronavírus, orbánviktor és még pár dolog ellen, leírom ide a híres idempotens-ultrafilteres bizonyítását a Hindman-tételnek. Mostanában folyamatosan ezekkel az izékkel foglalkozom, és ezt az alkalmazást nem bírtam otthagyni, annyira kis csinos.
Nyugi, mostantól majd írom a jó kis orbánozós, koronavírusozós posztokat (vagy nem).
1. A bonyolultan hangzó állítás az Ellis-Numakura Lemma. Az Ellis-Numakura Lemma azt mondja ki, hogy minden olyan kompakt félcsoportban, amelyben a balról szorzások folytonosak, van idempotens elem, azaz létezik egy p elem, amire p=pp.
2. A bizonyítás teljesen triviális. A Zorn-lemma szerint van a kompakt félcsoportunkban egy M kompakt részfélcsoport, ami minimális, tehát nem tartalmaz valódi részhalmazként kompakt részfélcsoportot. Vegyük ennek az M részfélcsoportnak egy p elemét. És tekintsük a pM halmazt. Ez egy kompakt részfélcsoport, tehát a minimalitás miatt pM=M. Azaz, létezik olyan q, amelyre pq=p. Vegyük most azon q elemek N halmazát M-ben, amelyre pq=p. N nyilván kompakt és nyilván félcsoport, tehat egyenlő M-mel. Azaz p az N-ben van, tehát pp=p.
3. Vegyük a természetes számok Cech-Stone kompaktifikációját. Az egy félcsoport. Nem csoport, de fél. Fogod az X ultrafiltert és az Y ultrafiltert és a szorzatuk úgy van definiálva, hogy egy A részhalmaz akkor van benne XY-ben, ha Y-sok eltoltja X-beli. Elég creepy, de ez tényleg félcsoport és a folytonossági tulajdonság is megvan benne.
4. Tehát az Ellis-Numakura Lemma szerint vannak idempotens ultrafilterek. Ezek tehát olyan ultrafilterek, hogy akkor van bennük egy részhalmaz, ha ultrasok eltoltjuk is benne van.
5. A természetes számok egy részhalmaza Hindman-nagy, ha van benne egy végtelen részhalmaz, aminek minden véges részösszege is benne van a halmazban. Állítás: egy idempotens ultrafilter minden egyes eleme Hindman-nagy. Ez pedig elég a Hindman-tételhez, hiszen ha véges sok színnel kiszínezzük a természetes számokat, akkor legalább az egyik színosztály a kedvenc ultrafilterünkben lesz.
6. Vegyük tehát az X idempotens ultrafiltert és ennek egy A elemét. Róla szeretnénk bebizonyítani, hogy Hindman-nagy. Legyen A halmaz duálisa az az A* halmaz, ami pont azokból az elemekből áll, akikkel eltolva A-t X-ben maradunk. Mivel X idempotens A* is benne van X-ben. Vegyük tehát A és A* metszetét. Ez egy végtelen halmaz (triviális módon idempotens ultrafilter nem lehet principális) vegyünk belőle egy x0 elemet. És most vegyük az A-x0 halmaz metszetét az A-val és nevezzük el A1-nek. Az idempotens tulajdonság miatt A1 is benne van az ultrafilterben.
7. Most vegyük az A1 duálisának metszetét A1-gyel és vegyünk belőle egy x1 elemet, ami nagyobb, mint x0. És induktíve konstruáljuk meg az x0, x1,…. sorozatot. Könnyű látni, hogy minden véges kombinációjuk az A halmazban van. Tehát az A halmaz Hindman-nagy.
Ha el nem basztam, ahogy az egyszeri székely favágó mondta volt…. Aránylag sok helyen van ez leírva, ha valakit érdekelnek a részletek. A barbadosi cucc jó.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16518141-6ae0a26a5a85f' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16518141&origin=www.orulunkvincent.hu&obj_id=192691293-16518141-6ae0a26a5a85f&n=1' data-name='like-post-frame-192691293-16518141-6ae0a26a5a85f' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>
@Idomeneusz: és ugye az is egy kérdés, hogy hogyan bizonyítod máshogy azt, hogyha egy félcsoportnak nincs valódi részfélcsoportja, akkor az egy elemű? Mert a fenti bizonyítás pont ezt is bizonyítja: ha pM =M, és utána az N is egyenlő M-mel, akkor pp=p, tehát a N’ ={p} egy valódi részfélcsoport, és akkor M ={p} (mert feltettük, hogy nincs valódi részfélcsoportja).
Tehát az egész hajcihő itt akkor felesleges, ha valami más úton is tudod bizonyítani, azt, hogy ha egy célcsoportnak nincs valódi részfélcsoportja, akkor az egy elemű.
Ezt a hármat hagyjuk magára, hagy beszélgessenek, mi pedig, a nem idempotens, hanem matematikailag impotens elemek váltsunk témát. Pl. mit szóltok az üss tököshöz:
index.hu/techtud/2020/03/26/fenyesebb_lesz_a_c_2019_y4_ustokos_mint_a_felhold/
Ha most vallásos lennék, aszondanám, hogy e baljós események – Covid járvány, cunami ázsiában, földrengés a balkánon, sáskajárás Afrikában, madárinfluenza, Hanta-láz Nagy-Britanniában, meg ez a „fényes csillag” Krisztus második eljövetelét
készíti elő, de ha ez tényleg igy van(lenne), akkor mi baromi rosszul jönnénk ki belőle. Felkészül Lót. Ugyanitt só rövid határidőre eladó.
@DarthVader: Bennem felmerült, hogy betrollkodok valami közbevetést a részfélcsoportok nemtriviális topológiájával kapcsolatban, ahol ppnq de rájöttem, hogy nem tudnék olyat fabrikálni, ami legalább egy másodpercre is hihető lenne nekik és megakasztaná a gondolatmenetet.
@ámbátor: én annyira nem értem, hogy még trollkodni se tudnék 🙂
@Egon Estragon:
„vannak olyan formái, amelyek nem tűnnek annyira triviálisnak, pl. hogy minden véges félcsoportban van idempotens elem.”
Ez azért elég könnyű: ha nem lenne idempotens elem, akkor p, p^2, p^4, p^8, … stb. csupa különböző elem lenne, ami a végesség miatt nem megy.
„Vagy: ha egy félcsoportban nincs idempotens elem, akkor minden részfélcsoportja tartalmaz (properly) részfélcsoportot.”
Ez meg csak átfogalmazása az eredetinek, hiszen ha van idempotens elem, akkor is van valódi részfélcsoport (mint írtad is), kivéve ha egy elemű a félcsoport.
Ez az egész igazából egyáltalán nem algebra. Ha van hibája JT írásának, az az, hogy a nem matematikusok azt hiszik, hogy ez a dolog nehéz vagy esetleg nagyon nehéz, miközben a „nagyon”-t még jópárszor kéne iterálni…
@ámbátor: Szerintem csak bátortalan vagy 🙂 Attól még, hogy koca-algebrista vagyok, még nem jelenti azt, hogy a topológiához bármit is konyítok 🙂 Próbáltam ezt a Cech-Stone kompaktifikációt megérteni, de a wiki is tele van topológiai szakzsargonnal, a math.stackexchange-en meg ezt találtam:
„The object βN is notoriously elusive. It is an important object of study in set theoretic topology and is highly sensitive to various set-theoretic axioms. Generally speaking, non-principal ultrafilters are very elusive, their general existence requiring a weak form of the axiom of choice. Thus, it is very difficult to imagine what ultrafilters look like, let alone what βN looks like.”
Öööö, hát köszi 🙂
Mondjuk ez:
„One thing for instance is that one can extend the addition of natural numbers to an addition operation on βN but it is not commutative. You can further read quite a lot on βN on any text on set-theoretic topology, but as said, this is far from conclusive or straightforward.”
már kicsit jobban tetszik, mert legalább algebra-szaga van, de attól még egy szót sem értek belőle 🙂
@Egon Estragon: Szerintem egyáltalán nem nehéz elképzelni, hogy néz ki egy ultrafilter. Alíg láthatóan porózus vajfehér tömbnek képzelem, lilás kerettel és felül egy sárga fémkupakkal.
@Egon Estragon: Egy ultrafilter azt csinálja, hogy a természetes számok bizonyos részhalmazait NAGY-nak, bizonyos részhalmazait pedig KICSI-nek nyilvánítja.
A szabály az, hogy ha A NAGY és B tartalmazza A-t, akkor B-is nagy, két NAGY halmaz
metszete is NAGY, egy halmaz pontosan akkor NAGY, ha a komplementere KICSI.
A principális ultrafilterek a természetes számokhoz vannak rendelve. Az U(k) nevű ultrafilterben azok a halmazok NAGY-ok, akik tartalmazzák a k elemet. A lényeg az, hogy a halmazelmélet axiómáiból következik, hogy vannak nem-principális ultrafilterek, de ezek nem konstruálhatók, nem lehet őket felépíteni valamiféle belátható módon. Vannak és kész. És ezek az ultrafilterek alkotják a Cech-Stone kompaktumot, de nincs rajtuk távolságfogalom, csak egy kompakt Hausdorff topológia.
@vgab: ne haragudj, ezeket nem látom… :/
Ha p^8=p^2, akkor hol látunk idempotens elemet?
Ezt:
„Ez meg csak átfogalmazása az eredetinek, hiszen ha van idempotens elem, akkor is van valódi részfélcsoport (mint írtad is), kivéve ha egy elemű a félcsoport.”
meg aztán végleg nem értem. Olyan mintha egy „A -> B” típusú állításra mondanád azt, hogy „persze, hiszen a nem-A -> nem-B is igaz…” :/ Az én állításom úgy kezdődik, hogy „ha nincs idempotens elem”, a tiéd meg úgy kezdődik, hogy „van idempotens elem”… :/
@Egon Estragon: Ha p^8=p^2, akkor (p^2*p^4)^2=p^4*p^8=p^4*p^2=p^2*p^4, tehát p^2*p^4 idempotens.
@Ménkűnagy Bundáskutya: Wow, köszi 🙂 Még mindig maradnak olyan esetek, hogy ha p^16 = p^2, akkor mi van, amit most a reggeli rohanásban nem tudok fél perc alatt kisakkozni, de ne mondd meg a megoldást, még gondolkodom reggelikészítés közben 🙂
@jotunder: OK, azt hiszem értem, majd írok, de most éppen holnaptól itt kijárási tilalom van, most kicsit fontosabb, mint a Cech-Stone kompaktifikáció 🙂
@Egon Estragon: ez az amiben biztosan tévedsz:)
Kérdésem az, hogy kijárási tilalom esetén mi lesz a Lemmákkal?
A lemma az nem a Norvég lemming (Lemmus lemmus) genitivusa??
@Ménkűnagy Bundáskutya: OK, és általában is, ha p^(2^k_1) = p^(2^k_2), k_2>k_1+1 (mert különben már p^(2^k_1) idempotens lenne, akkor p^(2^k_2-k_1) idempotens lesz, mert a négyzete p^2^k_2 * p^(2^k_2-2*2^k_1) = p^(2^k_2-2^k_1).
És gondolom, azért kell a kettő hatvány hatványkitevőket venni, hogy p^(2^k_2-2*2^k_1) értelmezhető legyen. Mármint általában ez p^k =p^m-re nem megy, mert lehet, hogy 2m-2k <m.
OK, ez tényleg a fentitől eltérő bizonyításnak tűnik arra, hogy véges félcsoportban van idempotens elem.
@Egon Estragon: a Cech Stone kompaktifikáció a kijárási tilalom leglényege. Ha nem lenne, akkor természetes számok mindenfelé kijárhatnának, de be vannak zárva a Cech Stone kompaktifikációba. És a Cech Stone kompaktifikáció is rendeleti úton keletkezett, a tizenkilencedik században még nem volt értelme, kormányozni kellett hozzá a matematikát.
@jotunder: Mind megittad?
@balmoral: nálam két féldeci a barbadosi anyagból a maximum.
@jotunder: De látom, használ.
@heptakontanonaéder: dehogynem, ld. fentebb. 🙂
apropos ultrafilter: „Tehát az abszolút legnagyobb abszolút ténylegesen mindaz, amivé lehet; mégpedig annyira ellentétmentesen, hogy a legnagyobbal egybeesik a legkisebb is. Ezért fölötte áll minden állításnak és ugyanígy minden tagadásnak is.” Szóval csak egy kicsit kell az ultrafilteren túl pillantani, s minden kisimul. 🙂
Persze mindenki azzal kínozza magát, amivel kedve szottyan. Én pl. nekiállok megint a ‘Vocalise’ megtanulásának, de hagyom a Kocsis-féle átiratot, mert baromi nehéz (nekem), ma megnézem Alan Richardson és Earl Wild átiratát is, aztán döntök.
Egy zordon lemma: http://www.es.hu/cikk/2020-03-27/bokros-lajos/reccsen-a-koponya.html
@jotunder: Szóval akkor, ha jól értem, egy véges posetben minden filterben van egy legkisebb elem, mert ha micimackónyi aggyal is látok neki egyre kisebb z-ket keresni (mert minden x és y-ra létezik olyan z, hogy z <=x és z<=y), akkor is a végesség miatt idővel találok egy legkisebbet. És akkor véges posetben az ultrafilterek a legkisebb elemet fedő elemek által generált ultrafilterek, ha van legkisebb elem (ezek lesznek a természetes számok esetén az U(k) ultrafilterek, amely a természetes számok összes részhalmazát tartalmazó posetben az üres halmazt fedő egyelemű halmazok), vagy a minimális elemek által generált filterek lesznek az ultrafilterek, ha nincs legkisebb elem.
És akkor azt mondod, hogy a természetes számok végtelensége miatt nem lesz igaz az, hogy minden filterben van legkisebb elem? És ezek között is lesznek ultrafilterek, de ezek pont annyira konstruálhatóak meg, mint a nyílt meg a zárt körlemez közötti bijekció?
@Egon Estragon: Oh, persze p^(2^k_2-2^k_1) lesz idempotens, és a négyzete meg p^(2^k_2) * p^(2^k_2-2*2^k_1), stb. elnézést a gépelési hibákért, értelemszerűen javítsátok ki 😛 Ezért nem jó autóban várakozva mobiltelefonról kommentelni… :/
@Egon Estragon: a Zorn-lemma miatt minden filter benne van egy maximális filterben, a maximális filterek ultrafilterek. és a Zorn-lemma sajnos nemkonstruktív. ennyi az egész. nem lehet látni a nem-principális ultrafiltereket.
index.hu/kulfold/2020/03/27/boris_johnson_is_koronavirusos/
BoJo …
Ha valakinek nem tűnt volna még fel, Jótündér tanár úr karanténszülte digitális távoktatásának lehetünk szerencsés részesei, avagy értetlen szemlélői. Kalapkúra helyett Numakura szeminárium.
@jotunder: OK, OK, de a Zorn lemmán felül kell még az is, hogy van olyan filter, amiben nincs legkisebb elem, különben az nem jönne ki, hogy nincs nem-principális ultrafilter, nem? Pl. ha azokat a halmazokat veszed, amelyek véges sok számot nem tartalmaznak a természetes számokból, azok jók lesznek ilyen filternek, ugye?
@Egon Estragon: vegyed azokat a halmazokat, amelyek egyre ritkábbak, tehát egy idő után minden n-re igaz, hogy egy n hosszúságú intervallumban maximum egy darab elem van. ezen halmazoknak vedd a komplementereit. ezek egy filtert alkotnak. és ebben teljesen világosan nincs minimális elem.
@balmoral: naaaa…. ez nem távoktatás. ez egy filozófiai performance.
@jotunder: És „nem középiskolás fokon”. Teljesen mindegy, minek szánod, ha a végén úgyis tank lesz belőle. Vagy fogpiszkáló…
@Egon Estragon: igen, ezt hívják ko-véges szűrőnek, kibővíthető ultraszűrővé (mellesleg elég sokféleképp), és bármelyik bővítésére igaz, hogy csupa végtelen halmazt tartalmaz. ez a szabványos példa arra, hogy végtelen halmazon van ultraszűrő, ami nem főszűrő.
@jotunder:@dr Brcskzf Gröőő: köszi, akkor eddig minden világos.
A következő napirendi pont, hogy mi az, hogy „Y-sok eltoltja X-beli”?
(Közben dolgozni is kell, amihez valljuk meg, sokkal kevesebb kedvem van, mint a posztban közölt bizonyítás megértéséhez, de ezvan 🙂 )
@Egon Estragon: ha X és Y ultrafilterek, A pedig a természetes számok halmazának egy részhalmaza, akkor bizonyos n-ekre A+n X-beli (X szerint nagy), más n-ekre A+n nem X-beli (X szerint kicsi). Vegyük az összes olyan n-t, melyre A+n X-beli, ez a természetes számok halmazának egy B részhalmaza. Ez a B halmaz vagy Y-beli (Y szerint nagy) vagy nem Y-beli (Y szerint kicsi). Az A akkor lesz XY-ban, ha ez a belőle származtatott B Y-beli (Y szerint nagy). Ezt érti a szerző azalatt, hogy „[A-nak] Y-sok eltoltja X-beli”.
@Egon Estragon: ha Y egy szűrő, akkor az „egy állítás Y-sok elemre teljesül” azt jelenti, hogy azon elemek halmaza, amire az állítás igaz, Y-beli. jelen esetben: azon elemek halmaza, amivel eltolva X-beli részhalmazt kapsz, Y-beli.
@cruickshank:
„Tehát az abszolút legnagyobb abszolút ténylegesen mindaz, amivé lehet; mégpedig annyira ellentétmentesen, hogy a legnagyobbal egybeesik a legkisebb is. Ezért fölötte áll minden állításnak és ugyanígy minden tagadásnak is.”
Ez kitől származik?
Akit a poszt Győrfi Pál-mentes része megmozgatott, bátran nézze meg ezt is:
terrytao.wordpress.com/2008/01/21/254a-lecture-5-other-topological-recurrence-results/
@ikaruss: Cusanustól, 1440-ből. 🙂
Kösz! Régen olvastam – mindenképpen 1440 után 🙂 – , de most előszedem.
@ikaruss: Cusanust mindig jó olvasni. Ajánlom hozzá Cristobal Morales valamely miséjét. Ha végeztél vele, jó folytatás lehet Schelling (a tridealizmus vagy bármely más fiatalkori opusa) — szigorúan Hendrixszel.
@cruickshank:
Schelling-Hendrix : elég merész párosításnak tűnik.
A Cech-Stone kompaktifikáció a kijárási tilalom leglényege…
Barbados, you say.
Meg ne sértődjön, mert visszaüt.
@Csingiz: másfél deci lehet még belőle, ez már nem tesz nagy kárt
El nem tudtam volna képzelni, hogy egy ilyen írásra ennyi hozzászólás érkezik. Úgy tűnik, mindenki úgy érzi, hogy ha érti, akkor azért kell hozzászólnia, ha meg nem, akkor azért.
@Egon Estragon: Ez a necklace problem gyönyörűszép, itt egy link: http://www.sciencedirect.com/science/article/pii/0001870887900557
Volt amúgy egy hasonló Schweitzer feladat is 1997 környékén, Totik Vilmos volt a kitűzője, én ismertem a fenti cikket, így megoldottam a feladatot, de itt van, amit Totik írt erről: shorturl.at/hiBIY, és idézem őt: „Aki ismert bármilyen nemtriviális topologikus fixponttételt, az megoldotta ezt a feladatot.”
A Brouwer fixponttétel a legegyszerűbb ilyen. „Ha a d-dimenziós zárt körlapnak vesszük egy önmagára való folytonos leképezését, akkor annak van fixpontja.” A „zárt” azt jelenti, hogy a határa is benne van. Ha a körlapot egy határpontjából lekicsinyítjük felére, akkor csak az a határpont a fix, így ha az nem volna része az univerzumnak, akkor nem volna fixpont. De része, mert zárt. A körlap hozzávetőleges alakja is fontos: ha egy zárt körgyűrűt vennénk, akkor a középpont körüli forgatásnak nincs fixpontja a körgyűrűn belül.
Az, hogy az alak itt fontos, az szerintem egy algebrai dolog. Ilyen, nem olyan, körlap, nem körgyűrű, pár lehetőség közül az egyik, és ennek következményei vannak. A Hindman tételben viszont csak kompaktság van, az meg analízis: ha két dolog közel van egymáshoz, és folytonos függvénnyel visszük őket arrébb, akkor a képek is közel lesznek. (A folytonosság definíciója.) epsilon, delta, becslések. Azt akarom mondani, hogy ez a Hindman tétel sokkal alapvetőbb, mint a necklace theorem.
@keletita: szerintem erre való egy blog: aki nem érti, az kérdez, aki érti, az válaszol. Ennek kellene természetesnek lennie, szerintem.
@Mister Gumpy: köszi, mindenképp ránézek!
@Egon Estragon:
Igazad van, és érdekes is az értők párbeszéde. De! valahol a sok pq ,meg egyéb betű közt elveszett a poszt címébe foglalt mondandó. Tisztelet a posztolónak, de szerintem egyéb mondanivalója is volt a matek szépsége mellett.
Magam részéről úgy gondolom, hogy vírus ide, vírus oda, a matematika örök. Meg azok hülyesége is, akik ezt, és a matematikai módszereket a vírus elleni harcban figyelmen kívül hagyják.
@jotunder: „de nincs rajtuk távolságfogalom” – ezt hadd árnyaljam azzal, hogy ez egy Hausdorff és M_2 tér kompaktifikáltja, tehát ő is Hausdorff és M_2, mivel pedig kompakt, ezért T_4 is, következésképpen metrizálható. Ettől még persze könnyen lehet, hogy minden olyan metrika, ami ezt a topológiát adja, ronda és emberi ész által átláthatatlan.
@GHermann: a Cech-Stone topologia nem metrizálható. nagyon nem.
legyen A egy valódi részhalmaza a természetes számoknak, és U(A) azon ultrafilterek halmaza, amelyek tartalmazzák A-t. U(A) bázisa a Cech-Stone-nak.
ha a Cech Stone metrizálható, akkor van megszámlálhatóan sok bázishalmaz, U(A1), U(A2), U(A3)…. amire igaz, hogy minden U(B) alakú halmaz tartalmaz legalább egyet közülük.
namost ez nyilván nem igaz, mert van induktíve konstruálhatok egy B halmazt, ami minden egyes An komplementerét metszi. ekkor U(B) nem tartalmazza U(An)-t egyetlen n-re sem, hiszen van olyan ultrafilter, amiben benne van a B és nincs benne az An.
Ez az érvelés pont nem jó, mert ha A egyelemű, akkor U(A) is csak az A-hoz tartozó principális ultrafilter, tehát minden U(B)-ben van egy U({n}) alakú. Ettől függetlenül nem igaz, hogy M_2 kompaktifikáltja M_2, az intuíciómmal ellentétben semmi nem garantálja azt, hogy két olyan nyílt, melynek N-beli nyoma megegyezik, a kompaktifikációban is megegyezzen (és a Cech-Stone már az M_1-séget is elveszti).