Viikottainen todistus

Joulutauko…

December 5th, 2008 by Matti Nelimarkka

Juomia

Pahoittelemme hiljaisuutta, toimituksemme on pikkujouluillut ja joutui integraalin käsiin. Kuten kaikilla, meillä integraalin jälkeisen vakion ongelmia — palaamme matematiikkaan kunhan derivoidumme takaisin kuntoon.

Toimitus

Tags: joulu
Posted in Metablogi | 3 Comments »

Hilbertin hotelli

November 19th, 2008 by Janne Korhonen

Hilbertin hotelli on saksalaisen matemaatikon David Hilbertin antama esimerkki äärettömien joukkojen paradoksaalisilta vaikuttavista ominaisuuksista.

Tarkkaan ottaen Hilbertin hotelli on kuin mikä tahansa muukin hotelli, lukuunottamatta sitä seikkaa, että siinä on numeroituvasti ääretön määrä huoneita. Toisin sanoen hotellissa on huone jokaista luonnollista lukua $n \in \mathbb{N}$ kohti. Oletamme, että ensimmäisen huoneen numero on 1.

Hilbertin hotelli tunnetaan eräänä maan parhaista hotelleista, minkä vuoksi se on aina täynnä. Tästä huolimatta hotelliin saapuu jatkuvasti uusia vieraita, joiden majoitusta hotellinjohtaja joutuu setvimään. Onneksi kuitenkin neuvokas hotellinjohtajamme on opiskellut matematiikka, eikä tämä aiheuta hänelle ongelmia.

Lause 1: Hilbertin hotelliin voi aina majoittaa vielä yhden vieraan.

Todistus: Uudelle vieraalle järjestetään tilaa seuraavalla yksinkertaisella tempulla. Jokainen jo hotellissa oleva vieras siirretään huoneeseen, jonka numero on yhtä suurempi kuin hänen nykyisen huoneen numero. Siis huoneessa 1 ollut asukas siirretään huoneeseen 2, huoneessa 2 ollut huoneeseen 3 ja niin edelleen. Koska huoneita on äärettömästi, jokaiselle vieraalle löytyy uusi huone, ja huone 1 jää tyhjäksi. Nyt uusi vieras voidaan majoittaa sinne. $\Box$

Yllättäen kuitenkin Topologinen seura on päättänyt pitää vuosikokouksensa Hilbertin hotellissa, ja he saapuvat bussilla hotellin pihaan. Linja-autosta purkautuu ulos numeroituvasti ääretön määrä matemaatikkoja, jotka kaikki haluavat oman huoneen hotellista. Hotellinjohtajan on jälleen keksittävä jokin ratkaisu.

Lause 2: Täyteen Hilbertin hotelliin voi majoittaa vielä numeroituvasti äärettömän määrän vieraita.

Todistus: Koska matemaatikkoja on numeroituvasti, hotellinjohtaja voi antaa jokaiselle numerolapun, jossa on jokin luonnollinen luku. Nyt hotellinjohtaja siirtää kaikki jo valmiiksi hotellissa olevat vieraat huoneeseen, jonka numero on kaksi kertaa nykyisen huoneen numero, eli huoneesta i siirretään vieras huoneeseen 2i. Tämän jälkeen kaikki parittomalla numerolla varustetut huoneet ovat tyhjiä, joten Topologisen seuran jäsenet voidaan majoittaa niihin numerolappujen perusteella. Numerolapun i saanut matemaatikko laitetaan huoneeseen 2i-1. Näin kaikki saavat jonkin huoneen. $\Box$

Topologisen seuran jäsenet olivat tyytyväisiä Hilbertin hotellin palveluihin ja mainostivat paikkaa matemaatikkotuttavilleen. Niinpä myös kaikki muutkin matemaatikkoseurat päättävät pitää vuosikokouksensa siellä ja seuraavalla viikolla hotellin pihalle saapuu numeroituvasti äärettömän monta bussia, joista jokaisessa on numeroituvasti äärettömän monta matemaatikkoa.

Lause 3: Täyteen hotelliin voidaan vielä majoittaa numeroituvasti äärettömän monta numeroituvasti ääretöntä vierasjoukkoa.

Todistus: Tehtävän suorittamiseksi hotellinjohtaja jälleen numeroi linja-autot ja niissä olevat matemaatikot, niin että jokaisella linja-autolla on eri numero ja jokaisessa linja-autossa matemaatikot on numeroitu alkaen yhdestä. Nyt ensin hotellissa valmiiksi olevat asukkaat siirretään uusiin huoneisiin; huoneessa i oleva asukas laitetaan huoneeseen $2^i$ .

Merkitään nyt $p(i)$ :llä i:ttä alkulukua. Hotellinjohtaja voi nyt majoittaa kaikki matemaatikot huoneisiin laittamalla aina bussin numero i matemaatikon numero j huoneeseen $p(i+1)^j$ . Siis esimerkiksi linja-auton 1 matemaatikko numero 2 laitetaan huoneeseen $p(2)^2 = 3^2 = 9$ ja auton 3 matemaatikko 6 laitetaan huoneeseen $p(4)^6 = 7^6 = 117649$ . Koska jokaisen bussin kohdalla huoneiden valitsemiseen käytetään eri alkuluvun potensseja, ei kahdella eri bussilla tulleet vieraat voi päätyä samaan huoneeseen. Selvästi myös samalla bussilla tulleet vieraat kaikki saavat eri huoneet. Näin siis saadaan määrättyä jokaiselle oma huone. $\Box$

Hilbertin hotelli on hauska tapa havainnollistaa äärettömien joukkojen kummallisia ominaisuuksia, mutta taustalla on toki ihan oikeita matemaattisia väittämiä. Siihen liittyviä käsitteitä ja merkintöjä voi kerrata aikaisemmasta merkinnästä. Tämän merkinnän lauseet tarkan matemaattisesti muotoiltuina ovatkin oikeasti seuraavat.

Lause 1: $(0, 0) \cup (\{ 1\} \times \mathbb{N}) \preccurlyeq \mathbb{N}$ .

Lause 2: $(\{ 0\} \times \mathbb{N}) \cup (\{ 1\} \times \mathbb{N}) \preccurlyeq \mathbb{N}$ .

Lause 3: $\mathbb{N} \times \mathbb{N} \preccurlyeq \mathbb{N}$ .

Todistukset näille siis ovat oleellisesti samat kuin yllä esitetyt, vaikkakin jätämme tarkan formalismin pyörittämisen harjoitustehtäväksi. Lisäksi yksikertaisilla havainnoilla mahtavuusvertailut saadaan yhtäsuuruuksiksi.

Tags: ääretön, Hilbert, Joukko-oppi, joukot
Posted in Joukko-oppi | No Comments »

Zornin lemma, osa I

November 12th, 2008 by Janne Korhonen

Zornin lemma on huomattavan voimakas ja hyödyllinen tulos, jota hyödynnetään useissa keskeisissä olemassaolotulosten todistuksissa usealla matematiikan alalla. Oleellisesti Zornin lemma kuitenkin on ekvivalentti, vaikkakin käytännössä paljon helpommin käytettävä, muotoilu valinta-aksioomalle. Annamme tässä osassa I tarvittavat määritelmät ja todistamme, että Zornin lemma on vähintään yhtä vahva oletus kuin valinta-aksiooma. Myöhemmin ilmestyvässä osassa II todistamme, että valinta-aksioomasta seuraa Zornin lemma.

Valinta-aksiooma

Kaikki matematiikka voidaan nähdä tapahtuvaksi joukko-opin viitekehyksessä. Siis joukko-opin aksioomat muodostavat perussäännöt matemaattisten struktuurien käyttäytymiselle. Historiallisesti kiistellyin näistä aksioomista on valinta-aksiooma.

Valinta-aksiooma: Olkoon $\{ A_i | i \in I \}$ mielivaltainen joukko joukkoja ja $A_i \neq \emptyset$ kaikilla $i \in I$ . Tällöin joukko $\prod_{i \in I} A_i$ on epätyhjä, eli on olemassa funktio $f \colon I \to \bigcup_{i \in I} A_i$ jolla pätee $f(i) \in A_i$ kaikilla $i \in I$ .

Toisin sanoen valinta-aksiooma sanoo, epätyhjien joukkojen karteesinen tulo on aina epätyhjä. Vaikka se voi näyttääkin itsestäänselvyydeltä, valinta-aksiooma on riippumaton muista joukko-opin aksioomista - sitä ei siis voi todistaa vääräksi eikä oikeaksi yleisessä tapauksessa. Jos oletetaan indeksijoukko $I$ äärelliseksi, tuloksen todistaminen on kuitenkin mahdollista.

Valinta-aksiooman historiallinen kiistanalaisuus perustuu siihen, että huolimatta sen luonnollisen oloisesta sisällöstä sen olettaminen todeksi johtaa erikoisiin tai jokseenkin ei-toivottuihin ilmiöihin, kuten ei-mitallisiin joukkoihin, Banach-Tarskin paradoksiin ja hyvinjärjestysperiaatteeseen. Kuitenkin valinta-aksiooma tarvitaan monella modernin matematiikan alalla, ja se nykyään pääasiassa hyväksytään todeksi.

Osittain järjestetyt joukot

Ennen Zornin lemma esittämistä tarvitsemme muutaman määritelmän.

Olkoon $A$ joukko. Sanomme, että $A$ :n kaksipaikkainen relaatio $\le$ on osittainen järjestys $A$ :lla, jos se on refleksiivinen, antisymmetrinen ja transitiivinen. Tällöin sanomme edelleen, että $(A, \le)$ on osittain järjestetty joukko. Jatkossa tulemme tarvitsemaan tietoa, että osajoukkorelaatio on osittainen järjestys millä tahansa joukolla joukkoja, mutta tämän todistuksen jätämme harjoitustehtäväksi.

Osajoukko $C \subset A$ on ketju, jos joukon $A$ järjestys rajoitettuna $C$ :hen on lineaarijärjestys, ts. kaikilla $a,b \in C$ pätee joko $a \le b$ tai $b \le a$ . Alkio $t \in A$ on ketjun $C$ yläraja joukossa $A$ , jos kaikilla $c \in C$ pätee $c \le t$ .

Olkoon $m \in A$ . Sanomme, että $m$ on maksimaalinen alkio $A$ :ssa, jos ei ole olemassa alkiota $a \in A \setminus \{ m \}$ jolla pätee $m \le a$ .

Zornin lemma

Voimme nyt muotoilla Zornin lemman. Emme kuitenkaan esitä sen todistusta välittömästi, vaan tässä osassa tarkastelemme lemman voimakkuutta.

Zornin lemma: Olkoon $A$ osittain järjestetty joukko. Jos jokaisella $A$ :n ketjulla on yläraja $A$ :ssa, niin $A$ :ssa on ainakin yksi maksimaalinen alkio.

Erityisesti kannattaa huomata, että $A$ :n mahtavuus voi olla mielivaltaisen suuri. Pääsemme nyt varsinaiseen tulokseemme, joka siis käytännössä sanoo, että Zornin lemma on ainakin yhtä väite oletus kuin valinta-aksiooma. Yhdistettynä tietoon siitä, että valinta-aksiooma on riippumaton muista joukko-opin aksioomista, tämä takaa, ettei Zornin lemmaa voi todistaa joukko-opista ilman valinta-aksioomaa.

Lause 1: Zornin lemmasta seuraa valinta-aksiooman voimassaolo.

Todistus: Oletetaan että Zornin lemma on voimassa. Olkoon $I \neq \emptyset$ joukko ja $\{ A_i | i \in I \}$ epätyhjiä joukkoja. Haluamme konstruoida funktion $f \colon I \to \bigcup_{i \in I} A_i$ . Tätä varten tutkimme joukkoa $F = \{ f \subset I \times \bigcup_{i \in I} A_i | f$ on osittainen funktio ja jos $(i, a) \in f$ niin $a \in A_i \}$ . Tällöin $(F, \subset )$ on osittain järjestetty joukko ja selvästi epätyhjä. Haluammekin nyt soveltaa siihen Zornin lemmaa.

Olkoon nyt $C \subset F$ ketju. Osoitamme, että $f = \bigcup_{c \in C} c$ on $C$ :n yläraja $F$ :ssä. Selvästi kaikilla $c \in C$ pätee $c \subset f$ , joten riittää osoittaa että $f \in F$ .

Oletetaan, että $(i, a) \in f$ ja $(i, b) \in f$ . Tällöin $f$ :n määritelmän nojalla $(i, a) \in g \subset f$ ja $(i, b) \in h \subset f$ joillain $g,h \in C$ . Koska $C$ on ketju, joko $g \subset h$ tai $h \subset g$ . Symmetrian nojalla voimme olettaa $g \subset h$ . Siis $(i,a) \in h$ ja $(i,b) \in h$ , joten koska $h$ on osittainen funktio niin $a = b$ . Siis $f$ on osittainen funktio.

Olkoon edelleen $(i, a) \in f$ . Tällöin jälleen $(i, a) \in g \subset f$ jollain $g \in C \subset F$ . Tästä seuraa, että $i \in I$ ja $a \in A_i$ . Siis saadaan, että $f \in F$ .

Voimme nyt käyttää Zornin lemmaan, jonka nojalla $F$ :ssä on ainakin yksi maksimaalinen alkio $f$ . Osoitamme nyt, että $f$ on määritelty kaikilla $i \in I$ . Tehdään vastaoletus, että jollain $i \in I$ $f$ ei ole määritelty. Koska $A_i$ on epätyhjä, voidaan valita mielivaltainen $a \in A_i$ . Nyt selvästi $f \cup (i, a)$ on joukon $F$ alkio ja $f$ on sen osajoukko. Tämä on ristiriidassa $f$ :n maksimaalisuuden kanssa. Siis $f$ on funktio $I \to \bigcup_{i\in I} A_i$ , ja lisäksi $f(i) \in A_i$ kaikilla $i \in I$ . Tämä todistaa väitteen. $\Box$

Palaamme aiheeseen vielä osassa II, jossa todistamme, että Zornin lemma seuraa valinta-aksioomasta.

Tags: Joukko-oppi, valinta-aksiooma, zorn
Posted in Joukko-oppi | No Comments »

Banachin kiintopistelause

November 6th, 2008 by Opqdonut

Banachin kiintopistelause on metrisen topologian klassikkotulos, joka todistaa, että kutistavalla kuvauksella on jokin keskipiste jota kohti se asioita pakkaa. Matemaattisemmin ajateltuna kutistavalla kuvauksella on siis kiintopiste, eli jokin arvo jonka se kuvaa itselleen. Tämä todistus aloittaa sarjan jossa käydään läpi kiintopistelauseita.

Todistuksen ymmärtämiseksi riittää tuntea lukujonon ja raja-arvon käsitteet.

Jotta voisimme puhua kutistamisesta tarvitsemme koon eli etäisyyden käsitteen. Abstraktin tällaisen tarjoaa metrinen avaruus.

Metrinen avaruus $(X,d)$ on joukko pisteitä $X$ ja niille määritelty etäisyysfunktio $d : X^2 \to R^+$ joka täyttää ehdot

$d(x,y)=0 \Leftrightarrow x=y$ ,
$d(x,y)=d(y,x)$ ja
$d(x,y) \le d(x,z)+d(z,y)$ (kolmioepäyhtälö).

Metristä avaruutta sanotaan täydelliseksi jos jokainen Cauchyn ehdon täyttävä jono suppenee. Cauchyn ehto pätee lukujonolle $(x_n)$ jos
$\forall \epsilon \exists n_0: m,n>n_0 \implies d(x_m,x_n)<\epsilon$ .
Cauchyn ehdon täyttävää jonoa sanotaan myös Cauchyn jonoksi.

Metrisen avaruuden täydellisyys voidaan siis ymmärtää niin, että jokainen “suppenevan näköinen” jono, eli jono jonka arvot putoavat yhä pienemmälle ja pienemmälle välille, suppenee johonkin joukon pisteeseen. Reaaliluvut muodostavat täydellisen metrisen avaruuden, mutta esimerkiksi rationaaliluvut eivät, kuten voidaan huomata tarkastelemalla $\sqrt{2}$ kohti suppenevaa rationaalilukujonoa. (Jolla siis ei ole rationaalista raja-arvoa mutta joka täyttää Cauchyn ehdon.)

Käytämme todistuksessa hyväksi faktaa, jonka mukaan jokainen suppeneva jono on Cauchyn jono. Todistus on hyvin suoraviivainen.

Metrisessä avaruudessa voimme määritellä tutun jatkuvuuden käsitteen:
Olkoon $(X,d)$ metrinen avaruus. Kuvaus $f:X\to X$ on jatkuva pisteessä $x\in X$ jos kaikilla jonoilla $(x_n), x_i\in X$ jonka raja-arvo on $x \in X$ pätee että jono $(f(x_n))$ suppenee arvoon $f(x)$ .
Sanotaan että funktio on jatkuva jos se on jatkuva kaikissa määrittelyjoukkonsa pisteissä.

Banachin kiintopistelause:
Olkoon $f:X \to X$ jatkuva kuvaus täydelliseltä metriseltä avaruudelta itselleen. Nyt jos on olemassa positiivinen reaaliluku $q<1$ s.e. $d(f(x),f(y))\le qd(f(x),f(y))$ niin $f$ :llä on yksikäsitteinen kiintopiste $X$ :ssä, ts., on olemassa täsmälleen yksi $x\in X$ jolle $f(x)=x$ . (Tälläista $f$ kutsutaan myös kutistukseksi.)

Todistus: Olkoon $x_0\in X$ mielivaltainen. Määritellään lukujono $(x_n)$ asettamalla $x_{i+1}=f(x_i)$ . Tutkitaan etäisyyttä $d(x_i,x_{i+1})$ . $d(x_i,x_{i+1})=d(f(x_{i-1}),f(x_i))\le q d(x_{i-1},x_i)$ , joten induktiolla $d(x_i,x_{i+1})\le q^i d(x_0,x_1)$ . Merkitään vielä $d(x_0,x_1)=\delta$ .

Seuraavaksi osoitamme että jono $(x_n)$ toteutaa Cauchyn ehdon. Olkoon $\epsilon$ annettu. Tehtävänämme on saada $d(x_m,x_n)<\epsilon$ kun $m$ ja $n$ ovat tarpeeksi suuria.

Voidaan olettaa $m\le n$ . Nyt soveltamalla kolmioepäyhtälöä $n-m-1$ kertaa saadaan:
$d(x_m,x_n)\le d(x_m,x_{m+1})+d(x_{m+1},n) \le \cdots \le \sum_{m < i\le n} d(x_i,x_{i+1}),$
jota voidaan aikaisemmalla tuloksellamme vielä arvioida ylöspäin
$d(x_m,x_n)\le \sum_{m < i\le n} q^i\delta$ .

Ylläoleva näyttää erehdyttävästi geometriselta sarjalta. Jo lukiossa opimme, että geometrinen sarja $\sum_{i>0}\delta q^i$ suppenee kun $q<1$ . Toisinsanoen siis jonolla $(S_n)$ jossa $S_n=\sum_{n\ge i>0} \delta q^i$ on raja-arvo $S$ eli Cauchyn ehto pätee sille, eli
$\forall \epsilon \exists n_0: m,n>n_0 \implies |S_n-S_m|<\epsilon.$ (*)

Nyt riittää huomata että $|S_n-S_m|=\sum_{m< i\le n} \delta q^i \ge d(x_m,x_n)$ . Voimme siis valita $\epsilon$ :a vastaavaksi $n_0$ :ksi sen $n_0$ jonka olemassaolon ehto (*) takaa, koska tällöin $d(x_m,x_n) \le |S_n-S_m| < \epsilon$ . Lukujono $(x_n)$ siis täyttää Cauchyn ehdon eli täydellisyyden nojalla suppenee $X$ :ssä arvoon $x$ .

Nyt $x$ :n on oltava $f$ :n kiintopiste, sillä $f$ :n jatkuvuuden nojalla
$x = \lim x_n = \lim f(x_{n-1}) = f(x)$ .
Yksikäsitteisyys seuraa siitä, että jos $x'$ on $f$ :n kiintopiste niin jono $(x',f(x'),f(f(x')),\ldots)$ on vakiojono $(x')$ mutta toisaalta juuri todistetun nojalla ( $x_0$ oli mielivaltainen) suppenee kohti $x$ :ää, eli $x'=x$ .

Posted in Analyysi, Topologia | No Comments »

Lagrangen lause

October 29th, 2008 by opottone

Ehkä tärkein algebrallinen rakenne on ryhmä. Joukko $G$ on ryhmä, jos siinä on määritelty laskutoimitus, jolla on seuraavat ominaisuudet:

Kaikilla $x, y, z \in G$ pätee $(x \cdot y) \cdot z = x \cdot (y \cdot z)$ .
On olemassa $e \in G$ siten että jokaisella $x \in G$ pätee $e \cdot x = x \cdot e = x$ .
Jokaisella $x \in G$ on olemassa $x^{-1} \in G$ siten, että $x \cdot x^{-1} = x^{-1} \cdot x = e$ (missä $e$ on sama kuin edellisessä kohdassa).

Jos $G$ on ryhmä, sen osajoukko $H$ on aliryhmä, jos se on ryhmä samalla laskutoimituksella kuin $G$ .

Olkoon $G$ ryhmä ja $H$ sen aliryhmä, ja $x \in G$ mielivaltainen. Joukko $xH = \{x \cdot h : h \in H\}$ on $x$ :n määrittämä (vasen) sivuluokka.

Sivuluokat ovat varsin näppärä aliryhmiin liittyvä käsite. Seuraavaksi todistamme pari niihin liittyvää perustulosta.

Lause Ylläolevin oletuksin sivuluokat muodostavat ryhmän $G$ osituksen.

Todistus Selvästi sivuluokat sisältävät kaikki $G$ :n alkiot, sillä sivuluokka $xH$ sisältää alkion $x = x \cdot e$ . Vielä pitää osoittaa, että kaksi sivuluokkaa $xH, yH$ ovat joko samat tai pistevieraat. Oletetaan siis, että ne leikkaavat: $z \in xH \cap yH$ , eli $z = x \cdot h_1 = y \cdot h_2$ jollain $h_1, h_2 \in H$ . Valitaan mielivaltainen $r \in xH$ . Nyt $r = x \cdot h_3 = x \cdot h_1 \cdot h_1^{-1} \cdot h_3 = y \cdot h_2 \cdot h_1^{-1} \cdot h_3 = y \cdot (h_2 \cdot h_1^{-1} \cdot h_3) \in yH$ , sillä $h_2 \cdot h_1^{-1} \cdot h_3 \in H$ . Siis $xH \subseteq yH$ . Symmetrian perusteella myös $yH \subseteq xH$ , eli $xH = yH$ . Q. E. D.

Lause (Lagrange) Jos $G$ on äärellinen ryhmä ja $H$ sen aliryhmä, $|H|$ jakaa $|G|$ :n.

Todistus Edellisen lauseen perusteella riittää osoittaa, että jokaisen sivuluokan $xH$ mahtavuus on sama kuin $H$ :n mahtavuus. Tarkastellaan siis funktiota $f: H \rightarrow xH, h \mapsto x \cdot h$ . Määritelmän perusteella se on surjektio. Koska sillä on käänteisfunktio $z \mapsto x^{-1} \cdot z$ , se on bijektio. Q. E. D.

Tags: ryhmä
Posted in Algebra ja lukuteoria | No Comments »

Alaraja Ramseyn luvuille

October 23rd, 2008 by opottone

Aiemmassa merkinnässä määriteltiin Ramseyn luvut, todistettiin niiden olemassaolo ja samalla johdettiin yläraja $R(k) \le 4^k$ . Nyt johdamme alarajan käyttäen probabilistista metodia. Vaikka todistus on varsin yksinkertainen, ei oleellisesti parempaa alarajaa tunneta.

Aluksi pari sanaa probabilistisesta metodista. Kyseessä on kombinatoriikassa käytetty todistustekniikka, jossa sovelletaan satunnaisuutta ja todennäköisyyksiä yllättävällä tavalla ja yllättävässä yhteydessä. Tyypillisesti metodia käytetään, kun halutaan todistaa jonkin rakenteen olemassaolo—esimerkiksi halutaan graafi, jolla on $n$ solmua ja ominaisuus X. Jos satunnaisesti valitulla $n$ -solmuisella graafilla on ominaisuus X positiivisella todennäköisyydellä, on haluttu graafi olemassa. Sen löytäminen voi tosin olla hankalaa.

Lause: $R(k) \ge (1 - o(1)) \frac{k}{e} 2^{k/2}$ .

Tässä $o(1)$ tarkoittaa jotain funktiota $h$ , jolle pätee $\lim_{n \to \infty} h(n) = 0$ . Yleisesti $o(f(n))$ tarkoittaa funktiota, jolle pätee $\lim_{n \to \infty} h(n)/f(n) = 0$ . Kyseessä on siis melkein sama asia kuin tietojenkäsittelijöille tuttu $O(f(n))$ , ks. wikipedia.

Todistus: Olkoon $n$ mielivaltainen kokonaisluku. Muodostetaan $n$ solmun verkko satunnaisesti siten, että kahta solmua yhdistää kaari todennäköisyydellä $1/2$ , muista kaarista riippumattomasti. Jokainen $k$ solmun joukko on klikki todennäköisyydellä $2^{-{k \choose 2}}$ ja riippumaton joukko samalla todennäköisyydellä. Siis odotusarvo klikkien ja riippumattomien joukkojen määrälle on ${n \choose k}2^{1 - {k \choose 2}}$ ; erityisesti on olemassa jokin verkko, jossa on enintään näin monta klikkiä ja riippumatonta joukkoa. Olkoon tämä verkko $G$ .

Poistetaan jokaisesta $G$ :n $k$ -solmuisesta klikistä ja riippumattomasta joukosta yksi solmu. Jäljelle jää graafi, jossa ei ole $k$ -solmuisia klikkejä tahi riippumattomia joukkoja, ja solmuja on yhteensä vähintään $n - {n \choose k} 2^{1 - {k \choose 2}}$ ; tämä on alaraja eikä tarkka arvo, sillä sama solmu saatetaan poistaa kahdesti.

Ylläolevan perusteella $R(k) \ge n - {n \choose k} 2^{1 - {k \choose 2}}$ millä tahansa $n \in \mathbb{N}$ . Kun valitaan $n = \lfloor \frac{k}{e} 2^{k/2} \rfloor$ ja käytetään estimaattia ${n \choose k} \le (\frac{ne}{k})^k$ , saadaan haluttu tulos; tarvittava sieventäminen jätetään lukijalle harjoitustehtäväksi. Q. E. D.

Tags: probabilistinen metodi, ramseyn teoria, verkko
Posted in Kombinatoriikka | No Comments »

Ramseyn lause äärellisille verkoille

October 15th, 2008 by Janne Korhonen

Osoitimme aikaisemmassa merkinnässä, että kuuden ihmisen joukossa on aina kolme ihmistä, jotka joko tuntevat kaikki toisensa tai eivät tunne toisiansa ollenkaan. Harjoitustehtäväksi jäi miettiä, kuinka paljon ihmisiä tarvitaan, että varmasti löytyisi neljän tai viiden ihmisen vastaavanlainen joukko. Palaamme nyt tähän kysymykseen.

Ramseyn lause äärellisille verkoille osoittaa, että kunhan otamme tarpeeksi suuren joukon ihmisiä, niin joukosta löytyy haluamme määrä toisilleen tuntemattomia tai toisilleen tuttuja ihmisiä. Lauseen täsmällistä muotoilua varten tarvitsemme taas muutaman käsitteen.

Määritelmä: Pari $G = (V, E)$ on (äärellinen) verkko, jos $V \not= \emptyset$ on äärellinen joukko ja $E \subset V \times V$ on symmetrinen ja irrefleksiivinen relaatio, ts. kaikilla $x, y \in V$ pätee $(x,y) \in E \Rightarrow (y,x) \in E$ ja $(x,x) \notin E$ . Osajoukko $K \subset V$ on klikki, jos kaikilla eri alkioilla $x,y \in K$ pätee $(x,y) \in E$ . Vastaavasti $I$ on riippumaton joukko jos kaikilla $x, y \in I$ pätee $(x, y) \notin E$ .

Klikki siis vastaa toisensa tuntevien ihmisten joukkoa ja riippumaton joukko taas toisilleen tuntemattomia ihmisiä.

Pääsemme nyt itse lauseeseen. Jotta todistus olisi menisi helpommin läpi, muotoilemme tuloksen näennäisesti voimakkaammassa muodossa. Todistus on jälleen oleellisesti sama kuin Helsingin yliopiston Ramseyn teoria -kurssin luentomonisteessa, vaikkakin pyrimme esittämään yksityiskohdat hieman eksplisiittisemmin.

Lause (Ramseyn lause äärellisille verkoille): Olkoon $k, l \in \mathbb{N}$ mielivaltaisia lukuja. Tällöin on olemassa sellainen luku $r \in \mathbb{N}$ , että jokaisessa verkossa $(V, E)$ , jossa on vähintään $r$ solmua, on joko $k$ :n alkion klikki tai $l$ :n alkion riippumaton joukko.

Todistus: Todistamme väitteen induktiolla summan $k+l$ suhteen.

1) Alkuaskel: Haluamme todistaa, että väite pätee, kun $k + l = 1$ . Pystymme kuitenkin helposti jopa parempaan. Katsomalla klikin ja riippumattoman joukon määritelmiä tarkkaan huomaamme, että yhden solmun joukko on aina sekä klikki että riippumaton joukko. Siispä mikäli $k = 1$ tai $l = 1$ , mikä tahansa verkko on halutunlainen, eli $r = 1$ kelpaa.

2) Induktioaskel: Tutkitaan nyt tapausta $k + l = n$ , $n \ge 2$ . Induktio-oletuksena on nyt, että väite on voimassa aina kun $k + l \le n -1$ . Voimme myös olettaa, että $k$ ja $l$ ovat molemmat vähintään $2$ , koska muuten tapaus sisältyisi alkuaskeleeseen. Siispä on olemassa luvut $r_{k, l-1}, r_{k-1, l} \in \mathbb{N}$ niin että kaikissa vähintään $r_{k, l-1}$ solmua sisältävissä verkoissa on joko $k$ :n alkion klikki tai $l-1$ :n alkion riippumaton joukko, ja vastaavasti kaikissa $r_{k, l-1}$ :n solmun verkoissa on joko $(k-1)$ -klikki tai $l$ :n alkion riippumaton joukko.

Valitsemme $r = r_{k, l-1} + r_{k-1, l}$ . Osoittautuu, että tämä valinta on väitteessä haluttu luku. Sen todistamiseksi olkoon $G = (V, E)$ mielivaltainen verkko, jossa on vähintään $r$ solmua. Kiinnitetään mielivaltainen solmu $a \in V$ . Määritellään edelleen joukot

$V_+ = \{ x \in V | (a,x) \in E \}$

$V_- = \{ x \in V | x \not= a, (a, x) \notin E \}$ .

Eli siis $V_+$ on $a$ :n naapurit verkossa $G$ ja vastaavasti $V_-$ koostuu niistä solmuista, joista ei ole kaarta $a$ :han.

Nyt $V_+ \cup V_- = V \setminus {a}$ , joten yhdisteessä $V_+ \cup V_-$ on ainakin $r - 1 = r_{k, l-1} + r_{k-1, l} - 1$ solmua. Siis laatikkoperiaatteen nojalla joko $V_+$ :ssä on vähintään $r_{k-1,l}$ solmua tai $V_-$ :ssä on $r_{k,l-1}$ solmua. (Jos laatikkoperiaate ei ole tuttu, äskeisen todistus on helppo harjoitustehtävä.)

Kaksi tapausta:

i) $V_+$ :ssa on vähintään $r_{k-1, l}$ alkiota. Siispä aliverkossa $G_+ = (V_+ , E \cap V_+ \times V_+)$ on vähintään $r_{k-1, l}$ solmua, joten siitä löytyy luvun $r_{k-1, l}$ valinnan nojalla joko $k-1$ :n alkion klikki tai $l$ :n alkion riippumaton joukko. Jos $G_+$ :ssa on $l$ :n alkion riippumaton joukko $I$ , niin $I$ on halutunlainen riippumaton joukko myös koko verkossa $G$ . Muuten verkossa $G_+$ on $k-1$ :n alkion klikki $K$ . Tällöin $K \cup \{a\}$ on $k$ -klikki koko verkossa $G$ , sillä $K \subset V_+$ eli kaikilla $x \in K$ pätee $(x, a) \in E$ .

ii) $V_-$ :ssa on vähintään $r_{k, l-1}$ alkiota. Vastaavilla argumenteilla kuin tapauksessa i) aliverkosta $G_- = (V_- , E \cap V_- \times V_-)$ löytyy joko suoraan $k$ -klikki tai sitten $l-1$ :n alkion riippumaton joukko $I$ , jolloin $I \cup \{a\}$ on $l$ :n alkion riippumaton joukko.

Siis kaikista vähintään $r$ :n solmun verkoissa on $k$ -klikki tai $l$ :n alkion riippumaton joukko. Tämä todistaa induktioaskeleen.

Induktioperiaatteen nojalla siis väite pätee. $\Box$

Todistetun lauseen nojalla voidaan määritellä kuvaus $R \colon \mathbb{N}^2 \to \mathbb{N}$ asettamalla $R(k, l)$ :ksi pienin $r \in \mathbb{N}$ , jolla kaikissa vähintään $r$ :n solmun verkoissa on $k$ -klikki tai $l$ :n solmun riippumaton joukko. Edelleen määritellään $R(n) = R(n,n)$ kaikilla $n \in \mathbb{N}$ . Lukuja $R(n)$ sanotaan Ramseyn luvuiksi.

Ramseyn lause äärellisille verkoille antaa Ramseyn luvuille vain ylärajan. Suoraan todistuksesta saadaan $R(n) \le 4^n$ . Luonnollinen kysymys on tietysti lukujen $R(n)$ tarkat arvot, mutta se on kuitenkin osoittautunut hyvin vaikeaksi ongelmaksi. Voidaan lisäksi osoittaa, että $R(n) \ge \sqrt(2)^n$ , kun $n$ on vähintään kolme, mutta oleellisesti näitä parempia ylä- ja alarajoja ei tunneta. Yksittäisistä Ramseyn luvuista tiedetään triviaalit tapaukset $R(1)$ ja $R(2)$ sekä $R(3) = 6$ ja $R(4) = 18$ . Tästä eteenpäin tarkkoja arvoja ei tunneta; luvusta $R(5)$ tiedetään vain että $43 \le R(5) \le 49$ . Tutkimuksen nykytilan ja lisää pieniä lukuja $R(k, l)$ voi tarkistaa Stanislaw Radziszowskin päivittyvästä katsauksesta aiheeseen (erityisesti taulukko sivulla 4).

Tags: Kombinatoriikka, ramseyn teoria, verkko, verkot
Posted in Kombinatoriikka | 1 Comment »

Cantorin teoreema

October 8th, 2008 by Janne Korhonen

Cantorin teoreema on aikaisemman Schröder-Bernsteinin teoreeman tavoin perustulos liittyen joukkojen kokojen vertailuun. Samaan tapaan sillä on syvällisiä seuraamuksia joukko-opissa huolimatta sen suhteellisesta yksinkertaisuudesta. Teoreemasta tekee vielä mielenkiintoisemman se, että sen todistus on erityisen kaunis esimerkki niin sanotusta diagonalisointiargumentista. Tarvitsemme kuitenkin taas pari käsitettä ennen itse teoreemaan paneutumista.

Kuten määrittelimme jo aikaisemmassa blogimerkinnässä, sanomme mielivaltaisten joukkojen $A$ ja $B$ olevan yhtä mahtavat jos on olemassa bijektio $A \to B$ . Tätä merkitään $A \approx B$ . Tarkemmin tämän luokkarelaation ominaisuuksia tarkastelimme jo Schröder-Bernstein -merkinnässä.

Tarvitsemme vielä toisen käsitteen Cantorin teoreeman muotoiluun. Olkoon jälleen $A$ mielivaltainen joukko. $A$ :n potenssijoukko $P(A)$ on joukko $\{ B | B \subset A \}$ . Potenssijoukko koostuu siis kaikista $A$ :n osajoukoista.

Lause (Cantor): Kaikilla joukoilla $A$ pätee $A \not\approx P(A)$ .

Todistus: Tehdään vastaoletus $A \approx P(A)$ ja johdetaan tästä ristiriita. Nyt koska $A \approx P(A)$ , on suoraan määritelmän nojalla olemassa bijektio $f \colon A \to P(A)$ . Tällöin siis $f$ kuvaa jokaiselle $B \in P(A)$ jonkin $A$ :n alkion.

Tutkitaan nyt joukkoa $X = \{ x \in A | x \notin f(x) \}$ . Nyt siis $X$ on $A$ :n osajoukko ja siten sen potenssijoukon alkio. Koska $f$ on bijektio, se kuvaa jonkin $A$ :n alkion myös $X$ :lle, eli on olemassa $x \in A$ jolla $f(x) = X$ .

Koska $X = f(x)$ , $x \in X$ pätee jos ja vain jos $x \in f(x)$ pätee. Toisaalta joukon $X$ määritelmästä seuraa suoraan, että $x \notin f(x)$ jos ja vain jos $x \in X$ . Siis saadaan $x \in f(x) \Leftrightarrow x \in X \Leftrightarrow x \notin f(x)$ . Tämä on ristiriita, joten vastaoletus ei voi päteä. Väite siis on voimassa. $\Box$

Cantorin lause siis yksinkertaisesti ilmaistuna sanoo, että joukon potenssijoukko on aina erisuuri kuin joukko itse. Voidaan osoittaa hyvin suoraviivaisella konstruktiolla, että lisäksi $A \preccurlyeq P(A)$ , mutta jätämme tämän osoittamisen lukijoille harjoitustehtäväksi. Tämän lisätiedon kanssa saamme lopputulokseksi, että joukon potenssijoukko on aina aidosti itse joukkoa suurempi. Erityisesti tämä tarkoittaa, että on olemassa mielivaltaisen suuria äärettömiä joukkoja. Esimerkiksi luonnollisten lukujen joukko $\mathbb{N}$ on ääretön, mutta $P(\mathbb{N})$ on edelleen suurempi ääretön joukko.

Alussa mainittu diagonalisointiargumentti on tässä todistuksessa joukon $X$ valinta. Yleisemmin diagonalisaatio viittaa vastaavanlaiseen todistukseen, jossa osoitetaan kaksi joukkoa eri kokoisiksi valitsemalla samaan tyyliin suuremmasta joukosta alkio, joka eroaa jokaisesta pienemmän joukon alkion kuvasta. Vastaavanlaisella tekniikalla voidaan esimerkiksi osoittaa, että reaalilukuja on enemmän kuin luonnollisia lukuja tai että laskentaongelmia on enemmän kuin tietokoneohjelmia.

Tags: cantor, joukot, mahtavuus, potenssijoukko
Posted in Joukko-oppi | No Comments »

Summauksen järjestyksen vaihto

October 1st, 2008 by opottone

Olkoon $S = \sum_{i=1}^\infty s_i$ suppeneva summa. Siis osasummien jonolla $\sum_{i=1}^n s_i$ on äärellinen raja-arvo. Summa suppenee itseisesti (converges absolutely), jos vastaava itseisarvojen summa suppenee—siis $\sum_{i=1}^\infty |s_i| < \infty$ .

Mitä tapahtuu, jos järjestämme summan termit uudelleen?

Muodollisemmin, olkoon $g$ bijektio luonnollisten lukujen joukolta itselleen, ja $T = \sum_{i=1}^\infty s_{g(i)}$ . Uudelleenjärjestelyn vaikutus on seuraava:

Jos summa $S$ suppenee itseisesti, myös $T$ suppenee itseisesti, ja $T = S$ .
Jos $S$ ei suppene itseisesti (mutta suppenee), valitsemalla $g$ sopivasti saadaan summan $T$ arvoksi mikä tahansa (äärellinen tai ääretön) arvo.

Todistusten keskeinen idea on summien jakaminen negatiivisiin ja positiivisiin termeihin.

Apulause: Jos $s_i \ge 0$ kaikilla $i$ , summan $\sum_{i=1}^\infty s_i$ uudelleenjärjestäminen ei muuta summan arvoa.

Todistus: Valitaan mielivaltainen $n$ . On olemassa $N$ siten, että $\{1,2,\ldots, n\} \subseteq \{g(1), g(2), \ldots, g(N)\}$ , jolloin $\sum_{i=1}^n s_i \le \sum_{i=1}^N s_{g(i)}$ . Kun $n \to \infty$ , saadaan $\sum_{i=1}^\infty s_i \le \sum_{i=1}^\infty s_{g(i)}$ . Symmetrian perusteella pätee myös $\sum_{i=1}^n s_i \ge \sum_{i=1}^N s_{g(i)}$ . Q.E.D.

Lause: Jos summa $S$ suppenee itseisesti, myös $T$ suppenee itseisesti, ja $T = S$ .

Todistus: Itseinen suppeneminen seuraa suoraan apulauseesta, sillä itseisarvojen summan kaikki termit ovat ei-negatiivisia. Summien yhtäsuuruus saadaan soveltamalla apulausetta kummankin summan positiivisiin termeihin, ja negatiivisiin termeihin—summan arvo saadaan laskemalla yhteen negatiivisten termien summa ja positiivisten termien summa. Q.E.D.

Lause: Jos $S$ ei suppene itseisesti (mutta suppenee), valitsemalla $g$ sopivasti saadaan summan $T$ arvoksi mikä tahansa arvo (äärellinen tai ääretön).

Todistus: Olkoon $P = \{i : s_i \ge 0\}$ , $N = \{i : s_i < 0\}$ . Olkoot $p_1, p_2, \ldots$ joukon $P$ luvut suuruusjärjestyksessä, ja $n_1, n_2, \ldots$ vastaavasti.

Nyt $\sum_{i \in P} s_i = \infty$ ja $\sum_{i \in N} s_i = -\infty$ : jos molemmat olisivat äärellisiä, summa $S$ suppenisi itseisesti, ja jos vain toinen olisi äärellinen, olisi $S = \pm \infty$ .

Esitämme algoritmin, jonka avulla saadaan haluttu $g$ . Olkoon haluttu summan arvo $x \in \mathbb{R}$ ; tapaus $x = \pm \infty$ jätetään harjoitustehtäväksi.

(Alustus) $i \gets 1, j \gets 1, k \gets 1$ , $R \gets 0$ .
(Kasvata summan arvoa) while $R \le x$ do $g(k) \gets p_i$ , $i \gets i+1$ , $R \gets R + s_{p_i}$ , $k \gets k+1$
(Vähennä summan arvoa) while $R \ge x$ do $g(x) \gets n_j$ , $j \gets j+1$ , $R \gets R + s_{n_j}$ , $k \gets k+1$
Palaa kohtaan 2.

Koska $\sum_{i \in P} s_i = \infty$ , algoritmi ei juutu äärettömän pitkäksi aikaa kohtaan 2. Vastaavasti kohtaan 3 ei juututa, sillä $\sum_{i \in N} s_i = -\infty$ . Tämän takia tuotettu funktio $g$ on bijektio kokonaislukujen joukolta itselleen.

Sen jälkeen, kun algoritmi on kerran päässyt kohtaan 4, se pitää yllä invarianttia $|R - x| \le |g(k)|$ . Koska alkuperäinen summa suppenee, $s_i \to 0$ kun $i \to \infty$ , jolloin myös $g(k) \to \infty$ kun $k \to \infty$ . Q.E.D.

Posted in Analyysi | No Comments »

Schröder-Bernstein

September 24th, 2008 by Janne Korhonen

Schröder-Bernsteinin teoreema, joka tunnetaan myös nimellä Cantor-Bernstein-Schröder, on joukkojen kokojen vertailuun liittyvä perustulos. Vaikka sen voisi esittää ilman enempää konteksia, esitämme ensin hieman taustaa joukon koon käsitteeseen liittyen.

Joukkojen koon vertailu

Sanomme, että mielivaltaiset joukot $A$ ja $B$ ovat yhtä mahtavat, merkitään $A \approx B$ , jos on olemassa bijektio $A \to B$ . Tämä yleistää joukkojen koon yhtäsuuruuden käsitteen kaikille joukoille. Huomaamme erityisesti, että jos kaksi äärellistä joukkoa on yhtä mahtavat, niissä on yhtä monta alkiota. Seuraavat tulokset saadaan yksinkertaisilla argumenteilla ( $A, B, C$ ja $D$ ovat jatkossa mielivaltaisia joukkoja):

$A \approx A$
Jos $A \approx B$ niin $B \approx A$
Jos $A \approx B$ ja $B \approx C$ , niin $A \approx C$

Yhtä mahtavuus siis voidaan tulkita “ekvivalenssikäsitteeksi” kaikkien joukkojen luokassa. Se ei kuitenkaan ole relaatio, sillä $\{(A,B)|A \approx B\}$ on liian suuri ollakseen joukko.

Vastaavasti sanomme että $A$ on korkeintaan yhtä mahtava kuin $B$ , $A \preccurlyeq B$ , jos on olemassa injektio $A \to B$ . Ajatuksena on, että tämä toimisi järjestyksenä joukkojen luokassa, vaikka se ei myöskää ole relaatio. Saamme jälleen triviaalisti seuraavat tulokset:

$A \preccurlyeq B$
Jos $A \preccurlyeq B$ ja $B \preccurlyeq C$ , niin $A \preccurlyeq C$
Jos $A \approx C$ , $B \approx D$ ja $A \preccurlyeq B$ , niin $C \preccurlyeq D$

Kaksi ensimmäistä on jälleen järjestyksen perusominaisuuksia, kolmas takaa yhteensopivuuden yhtä mahtavuuden kanssa. Luonnollista olisi odottaa, että myös seuraavat ominaisuudet ovat voimassa:

$A \preccurlyeq B$ tai $B \preccurlyeq A$
Jos $A \preccurlyeq B$ ja $B \preccurlyeq A$ , niin $A \approx B$

Ensimmäinen näistä (ns. kardinaalien vertailtavuus) on itse asiassa ongelmallisempi - se on nimittäin ekvivalenttia valinta-aksiooman kanssa. Tähän seikkaan palaamme ehkä myöhemmin tässä blogissa. Jälkimmäinen ominaisuus on kuitenkin voimassa, vaikkei sen todistaminen olekaan aivan triviaalia. Se onkin alussa mainittu Schröder-Bernsteinin teoreema.

Schröder-Bernstein

Lause (Schröder-Bernstein): Olkoon $A$ ja $B$ mielivaltaisia joukkoja. Jos $A \preccurlyeq B$ ja $B \preccurlyeq A$ , niin $A \approx B$ .

Todistus: Oletaan, että $A \preccurlyeq B$ ja $B \preccurlyeq A$ . Tällöin on olemassa injektiot $f \colon A \to B$ ja $g \colon B \to A$ .

Määritellään $C_0 = A \setminus g(B)$ ja $C_{n+1} = g(f(C_n))$ kaikilla $n \in \mathbb{N}$ . Edelleen asetamme $C = \bigcup_{n=0}^\infty C_n$ . Nyt määritellään funktio $h \colon A \to B$ seuraavasti:

Jos $x \in C$ , asetetaan $h(x) = f(x)$ .
Muuten $h(x) = g^{-1}(x)$ .

Selvästi $h$ on hyvin määritelty, sillä $A \setminus C \subset g(B)$ . Osoitamme, että $h$ on bijektio.

Osoitetaan ensin, että $h$ on injektio. Olkoon $x, y \in A$ ja $x \neq y$ . Jos $x, y \in C$ , niin $f$ :n injektiivisyydestä seuraa suoraan $h(x) = f(x) \neq f(y) = h(y)$ . Vastaavasti mikäli $x, y \in A \setminus C$ niin $h(x) = g^{-1}(x) \neq g^{-1}(y) = h(y)$ , sillä $g$ on injektio. Voimme siis olettaa, että $x \in C$ ja $y \in A \setminus C$ . Tällöin $x \in C_n$ jollain $n \in \mathbb{N}$ , joten $h(x) \in f(C_n)$ . Toisaalta, jos olisi $h(y) \in f(C_n)$ , niin $g(h(y)) = g(g^{-1}(y)) = y \in g(f(C_n)) = C_{n+1}$ , mikä on ristiriita. Siis $h(y) \notin C_n$ , mistä seuraa välittömästi $h(x) \neq h(y)$ .

Lopuksi näytetään vielä, että $h$ on surjektio. Olkoon $x \in B$ mielivaltainen. Voimme olettaa, että $x \notin f(C_n)$ kaikilla $n \in \mathbb{N}$ , koska muuten $x$ :lle kuvautuva alkio on triviaalisti olemassa. Siis $x \in B \setminus \bigcup_{n=0}^\infty f(C_n)$ . Tutkitaan nyt alkiota $g(x)$ . Selvästi $g(x) \notin C_0$ suoraan $C_0$ :n määritelmän nojalla. Edelleen millään $n \in \mathbb{N}$ ei voi olla $g(x) \in C_{n+1}$ , koska $C_{n+1} = g(f(C_n))$ ja $g$ on injektio, eli silloin olisi voimassa $x \in f(C_n)$ . Siis $g(x) \in A \setminus C$ , joten $h(g(x)) = g^{-1}(g(x)) = x$ .