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-6ae0ace4533cb' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16518141&origin=www.orulunkvincent.hu&obj_id=192691293-16518141-6ae0ace4533cb&n=1' data-name='like-post-frame-192691293-16518141-6ae0ace4533cb' 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>
Szerintem nem velünk kellene most beszélgetned
Baszki, ha a Sam PhD-bírálata súlyos inside joke volt, akkor EZ MI?! 🙂
Van még abból a barbadosiból? Mer’ anélkül nem megy….
Mondjuk, azzal se, de akkor már nem izgat 🙂
Az általam ismert legjobb rum a híres bermudai Gosling’s Black Seal. Bermudán jártamkor felvilágosítottak, hogy az is Barbadoson készül, lévén Bermudán egy szál cukornád nem terem manapság és szeszgyár se nincsen. Szerintem ez elégséges bizonyíték az Ellis-Numakura Lemmára. Vagy mire. Jó lesz ez, ahogy említettem volt, Newtonnak is jót tett a karantén. Jótündér is elmélyedhet a karibi szeszipar zegzugos rejtekeiben. Nyugodalmas idempotens ultrafiltert kívánok minden kedves komment-társamnak! (Lehet belőle házilag arcmaszkot fabrikálni.)
Igy hosszu evek Vincent olvassa utan bevallhatom, hogy soha egy budos szot sem ertettem a matekos posztokbol. De a barbadian rumokat viszont aranylag jol ismerem.
Mindent értek, csak azt nem, hogy miért Királyhelyi?
@ikaruss: Elírta.
@ikaruss: Barbados…
Ott akadtam el, hogy ha M félcsoport, p egy eleme, úgy, hogy pM =M, akkor miért létezik olyan q M-ben, hogy pq=q? Ehhez bizonyára kell a kompaktság vagy a balról folytonosság, de ez általában nem igaz. Pl. ha M csoport és p nem egységelem, akkor biztosan nem igaz az állítás.
Nem tudom, hogy mi az, hogy kompakt meg balról folytonos, de mi a helyzet a balról folytonos és kompakt csoportokkal, és annak egy p nem egységelemével.
Szóval itt valami zavart érzek az erőben. Persze, ha M csoport, akkor annak a p egységelemére nyilván pp=p, tehát ha valami zűr is van itt a bizonyításban, lehet, hogy megpatkolható.
Vagy valamit rosszul látok?
Mellesleg ha jól látom, a 2. pontban azt bizonyítod(?), hogy ha M minimális kompakt részfélcsoport egy balról folytonos, kompakt félcsoportban, akkor annak minden p elemére pp=p.
Azért fogom még olvasni a vincentet…majd ha elmúlik a lemma, vagy mi. Alkohol meg nem ér szájamhoz.
Gondolom a kompaktság meg a balról folytonosság miatt van olyan fixponttétel, hogy minden p-re létezik olyan q, hogy pq=q. Ezt jól gondolom?
És ha M csoport, akkor a triviális csoport, tehát az eredeti félcsoportban volt (bal)egység.
szerintem ebben a rettenetes járványhelyzetben fel kellene ezeket a csoportokat oszlatni
@kiskii: a csoportokat oldani lehet, de sajnos nem mindegyik csoport feloldható 🙂
Amúgy Bollobástól hallottam egyszer régen egy nyakláncos kombinatorikai tételt, amelybnek szintén topológikus bizonyítása volt.
Minden kompaktra nem lehet fixponttétel, hiszen ahogy mondtad, minden kompakt csoportban a nemtriviális (bal)szorzások fixpontmentesek. Szerintem csak a kvantorok sorrendjét keverte meg a rum, és minden q-hoz van olyan p, amire pq=q, onnan kezdve pedig sínen van a bizonyítás (és nem minden p-re jön ki, ami megnyugtató).
@Egon Estragon: @GHermann:
Azt hiszem, arra gondol, hogy van olyan q, melyre pq=p. És az ilyen M-beli q-k halmazát nevezi N-nek. Ez nyilván kompakt, nyliván félcsoport, M-nek része, tehát maga M. És akkor tartalmazza p-t és pp=p. És onnan megy tovább, ahogy írja.
@GHermann: már javítva van p=pq
@jotunder: Hát akkor ezért nem értettem az egészet! p=pq, hát így már minden világos…
Bergelson tollából: people.math.osu.edu/bergelson.1/ertupdatenov6.pdf, a harmadik fejezet szól erről, nagyon szépen van megírva.
@Ménkűnagy Bundáskutya: bergelson furstenberg tanítvány volt. és pont olyan dolgokra használta az idempotens ultrafiltereket, amiről a vulgárfilozófiai esszét írtam. és én ezt csak három napja értettem meg. nem baj, még egy ideig be leszek zárva.
@Egon Estragon:
Biztosan, mert csak jobbról volt arcmaszkos a parlamenti ülésen, az eredeti kétharmadbalcsoportban. Így naná, hogy kompakt, meg folytonos.
Irigylem azokat, akik a p-kig eljutottak megértésben. Én már itt leakadtam: „bárhogyan színezzük ki a természetes számokat véges sok színnel” — hogyan színezünk ki számokat? Az egyest alul pirosra felül zöldre, a kettest hosszában lila és sárga csíkokkal, a hármast skótkockásra kékkel, lilával és rózsaszínnel…? Maradok a Bruichladdichnál inkább.
@cruickshank: Nem a számjegyeket színezzük ki, hanem a számokat. Mindegyikhez hozzárendelünk egy és csakis egy színt a véges számú választott, azaz konkrétan megnevezhető színünk közül. Mondhatnánk azt is, hogy egy-egy konkrét hullámhosszt rendelünk hozzá minden természetes számhoz.
Régen, a múlt évezred 80-as éveinek elején küldtek engem is megyei matekversenyekre. A megyeszékhely műszaki főiskolájának nagyelőadójában gyűltünk össze 150-en (?), durva többségben fiúk. Azért szerettem főleg, mert aznap nem kellett iskolába menni. Több órányi időt kaptunk 5-6 feladat megoldására. Mindent lehetett használni, a gyakorlatban ez főleg függvénytáblázatot és (akinek volt) zsebszámológépet jelentett. Ültem ott a rafkós feladatok fölött, valahány pontot mindig szereztem is, de a második fordulóba sosem jutottam tovább, és nem is ismertem senkit, aki továbbjutott volna (hát igen, mi nagyjából megrekedtünk a másodfokú egyenletek és a sinus-tétel szintjén). Viszont mindig megjelent két-három excentrikus kinézető fószer, pár vastag könyvvel a hónuk alatt, abba itt-ott belelapoztak, aztán 25-30 perc múltán leadták az elkészült feladatsorukat (akkor én még legfeljebb a második kérdés megértésén fáradoztam-vakaróztam). Valahogy ők lehettek a továbbjutók. Itt veszthettem el a fonalat a Hindman-tételhez.
@balmoral: értem, bár ez a poszt megfogalmazásából egyáltalán nem világos, igaz, utána lehetett volna nézni a nevezett tételnek másutt is. Este meg is teszem, csakazértis.
@kiskii: Sosem lehet tudni mire lesz mindez jó. Lehet, hogy a kórházi maszkokba is lehet tenni idempotens ultrafiltereket.
@cruickshank: Én meg baromira szégyellem, de idáig nem tudtam, mi az a lemma. Azt hittem, valami táplálékkiegészítő. hu.wikipedia.org/wiki/Lemma avagy hu.wikipedia.org/wiki/Lenmag
@balmoral: én egy egzotikus kis állatra tippeltem volna (wiki nélkül).
@cruickshank: nyilván ezért: en.wikipedia.org/wiki/Lemming
@cruickshank: E dolgozat 42 oldalán találhatsz egy egyszerűbb megfogalmazást a Hindman-tételre. A logikai jelekkel nyilván megbirkózol.
@cruickshank: E dolgozat 42 oldalán találhatsz egy egyszerűbb megfogalmazást a Hindman-tételre. A logikai jelekkel nyilván megbirkózol. web.cs.elte.hu/blobs/diplomamunkak/bsc_mat/2017/csernak_tamas.pdf Előbb lemaradt.
@Papadok: Miért, Shakespeare szonettjei, vagy Rodin Gondolkodója jó valamire? Gyönyörködtet, kultúra. Előbb-utóbb nagyon sok tudományos eredmény hozzájárul az emberiség túléléséhez, de rögtön hozzájárul ahhoz, hogy az emberiség méltó legyen rá.
@balmoral: Köszönöm. Igen, a logikai jelekkel megbirkózom.
@cruickshank: Hoppá, azannyamásodikjóska!, h Eglmayert idézzem. Nem baj, karantén idején ezzel büntetem magam. Ha a Zorn-lemma sem pusztítja el a vírust, akkor amúgy sincs segítség.
@GHermann: Jogos 🙂
@jotunder: De akkor ez a p = pq ez egy fixponttétel? Vagy ezt honnan kellene látni?
@jotunder: Jaaaa, ha pM = M, és p M-beli, akkor kell lennie olyan q-nak M-ben, hogy p = pq. Ez tényleg triviális, OK 🙂
@GHermann: de bizony, még mindig minden p-re kijön. Tehát ha M minimális kompakt félcsoport, akkor minden eleme idempotens. Szerintem. De csak így ebéd közben, kutyafuttában, javítsatok, ha tévedek…
Sőt, mintha az lenne, hogy minden félcsoportban a minimális félcsoportok idempotens elemek gyülekezetei. Sehol nem használtuk a kompaktságot vagy a balfolytonosságot.
@Egon Estragon: gondold meg, a pozitív egészek az összeadásra nézve félcsoportot alkotnak, és nincs köztük idempotens elem…
véresen használtuk a kompaktságot a Zorn-lemmánál.
@Egon Estragon: a folytonosságot is használtuk, amikor pM -ről kimondtuk, hogy kompakt. ha nem lenne folytonos a balról szorzás, ezt nem mondhatnánk ki.
@jotunder: de legfeljebb ott használtad, hogy létezik minimális részfélcsoport. Pozitív egészek összeadásra vett félcsoportjában van minimális részfélcsoport? Szerintem nincs, tehát őrájuk is igaz az, hogy „minden minimális részfélcsoportban az összes elem idempotens”. És a 2. pontban leírt bizonyításod pont működni fog rá, onnan, hogy ” Vegyük ennek az M részfélcsoportnak egy p elemét.”, csak húzzad ki belőle az összes olyan sallangot, hogy kompakt meg balfolytonos. Persze M nem létezik, ha az a pozitív egészek összeadásra vett félcsoportjának minimális részfélcsoportja, de ugye nemlétező dologról meg bármit állíthatsz. Viszont ha olyan félcsoportod van, amelynek van minimális részfélcsoportja, akkor annak minden eleme idempotens. Mondom, nézd meg, hogy nem tettél fel semmit p-ről, az M egy eleme, oszt mégis kijött, hogy idempotens.
Ha jól sejtem, akkor az is ki fog jönni, hogy minden véges félcsoport tartalmaz idempotens elemet.
Vicces, hogy erről mennyire nem tanul az ember az iskolában, pedig egyszerű algebra…
Ja, és persze akkor még egy vicces állítás: ha egy félcsoportban nincs idempotens elem, akkor nincs minimális részfélcsoportja. Minden sallangtól mentesen minden félcsoportra ez igaz.
@Egon Estragon: Ha van egy félcsoport, ami nem tartalmaz valódi részfélcsoportot (nevezheted őt minimális félcsoportnak) az pontosan egy darab elemből áll.
@Egon Estragon: A szorzás balról való folytonosságát két helyen is használta.
1) Először is, M zárt halmaz, tehát a kompakt félcsoportban kompakt halmaz. A szorzás balfolytonossága miatt így pM halmaz kompakt. Gondolom azt is feltette a szerző, hogy a félcsoport Hausdorff, csak nem mondta ki: nyilván így következik, hogy a pM halmaz zárt. (Magát az M halmazt úgy kapjuk Zorn-ból, hogy azt bizonyítjuk ugye, hogy a félcsoport zárt részfélcsoportjai között (jelölje ezek halmazát X) létezik tartalmazás tekintetében minimális elem. Hogy tudjuk alkamazni a Zorn-t, be kell látni, hogy minden minden X-beli láncnak van legkisebb eleme, mely X-ben van. A jelölt erre a lánc elemeinek metszete. Be kell látni, hogy ez X-ban van, tehát zárt részfélcsoport. Ez első trivi, a zártság is következik. Ebből azonban látszik, hogy a hausdorffság nem elhagyható, mert az általban kompakt halmazok tetszőleges metszete nem kompakt)
2)Másik ahol szorzás balfolytonossága kell: az N halmaz kompaktságának bizonyításához. Jelen esetben ez ekvivalens N zártságának bozonyításával, ez azonban abból látszik, hogy N nem más, mint az egyelemű (ezért zárt) {p} halmaz m_p általi inverz képe, itt m_p jelöle a p-vel balról való szorzást.
@jotunder: És az pont egy idempotens elem lesz 🙂
@Idomeneusz: OK, OK, de ez nem változtat semmit azon állításon, hogy ha egy félcsoportnak nincs valódi részfélcsoportja, akkor abban minden elem idempotens. Ha elhagyod az összes topológiában használt jelzőt a 2. pontban onnan, ahonnan jelöltem, akkor ennek a bizonyítását kapod. Azaz, legyen M egy félcsoport minimális részfélcsoportja. Ekkor (és innen bemásolom a 2. pont citált részét, csak kihúzom belőle azokat a jelzőket, amelyek a topológiára vonatkoznak):
„Vegyük ennek az M részfélcsoportnak egy p elemét. És tekintsük a pM halmazt. Ez egy 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 félcsoport, tehat egyenlő M-mel. Azaz p az N-ben van, tehát pp=p.”
Persze minden idempotens elem részfélcsoportot ad, tehát ha M-nek nincs valódi részfélcsoportja, akkor M = {p}. De attól még a fenti bizonyítás csont nélkül megy. Szerintem.
Mostha ezt megfejeled a kompaktsággal, meg a balról folytonossággal, akkor lehet, hogy M nem egyetlen elemből fog állni, de akkor is minden eleme idempotens.
@Egon Estragon: Lehet félreértem, mert már amit mondasz, az helyes, ám maga az állítás triviális szerintem. Ahogy JT mondta, haegy félcsoportnak (legyen S) nincsen valódi részfélcsoportja, akkor az egy egy elemű félcsoport: S= {p}. Persze, hogy az a nyomorult p idempotens lesz, hisz S félcsoport a feltétel szerint, tehát pp az S-ben kell legyen, tehát pp =p 🙂
@Idomeneusz: igen, ez triviális, de vannak olyan formái, amelyek nem tűnnek annyira triviálisnak, pl. hogy minden véges félcsoportban van idempotens elem. Vagy: ha egy félcsoportban nincs idempotens elem, akkor minden részfélcsoportja tartalmaz (properly) részfélcsoportot.
Bocsánat azoktól, akiknek ez triviális, sose tanultam félcsoport elméletet, és én pl. eddig nem tudtam azt, hogy minden véges félcsoportban van idempotens elem.