Issuu

BUTLLETÍ

El Butlletí de la Societat Catalana de Matemàtiques publica, en llengua catalana, exposicions matemàtiques de qualitat, que puguin interessar a un nombre elevat de lectors. Es donarà prioritat a aquells treballs en què destaquin la claredat d’exposició i l’interès general del tema. El Butlletí està obert a tots els camps de la matemàtica i també als aspectes matemàtics de les ciències experimentals, la tecnologia, l’economia, etc., així com a altres àrees, com la història, la didàctica i la filosofia, sempre que els treballs tinguin un component matemàtic important. També tenen cabuda al Butlletí aquells articles que desenvolupin un aspecte significatiu de la problemàtica de la professió matemàtica al nostre país.

DE LA SOCIETAT CATALANA DE MATEMÀTIQUES Institut d’Estudis Catalans

El Butlletí publica un volum a l’any, dividit en dos números, que es trameten gratuïtament a tots els socis. El Butlletí es publica també en format electrònic. L’edició electrònica del Butlletí pot obtenir-se des del portal de revistes científiques en línia de l’IEC o al servidor http://scm.iec.cat. La correspondència administrativa s’ha d’adreçar a la Societat Catalana de Matemàtiques.

Editor en cap

Editora adjunta

Antoni Guillamon

Rosa Camps

Departament de Matemàtiques

Universitat Politècnica de Catalunya

Universitat Autònoma de Barcelona

í n d e x q Pere Ara q Júlia Moreno, Mònica Blanco i Pere Pascual La compacitat, una noció seminal en l’evolució de la topologia general (1895–1930) ----------------------------------------------------

Marc Noy Departament de Matemàtiques Universitat Politècnica de Catalunya

Bartomeu Coll Dep. de Matemàtiques i Informàtica Universitat de les Illes Balears

Francesc Planas Departament de Matemàtiques Universitat Politècnica de Catalunya

Núria Fagella Dep. de Matemàtiques i Informàtica Universitat de Barcelona

Joan Saldaña Dep. d’Informàtica, Mat. Aplicada i Estadística Universitat de Girona

Armengol Gasull Departament de Matemàtiques Universitat Autònoma de Barcelona

Marta Sanz-Solé Dep. de Matemàtiques i Informàtica Universitat de Barcelona

Gábor Lugosi ICREA i Departament d’Economia Universitat Pompeu Fabra

Gil Solanes Departament de Matemàtiques Universitat Autònoma de Barcelona

Vo lum 35 • Núm er o 1 • A n y 2020

Comitè editorial Carme Cascante Dep. de Matemàtiques i Informàtica Universitat de Barcelona

tel. 933 248 583 - fax 932 701 180 scm@iec.cat - http://scm.iec.cat

BUTLLETÍ

Carrer del Carme, 47 - 08001 Barcelona

q Oriol Serra Límits de grafs ------------------------------------------------------------------------------------------

q English summaries ---------------------------------------------------------------------------------

Vo l u m 3 5

Societat Catalana de Matemàtiques

La paradoxa de Banach–Tarski i el semigrup de tipus ---------------------

•

Número 1

•

Any 2020

BUTLLETÍ DE LA SOCIETAT CATALANA DE MATEMÀTIQUES Institut d’Estudis Catalans

Volum 35 • Número 1 • Juny 2020

BARCELONA 2020

© dels autors dels articles Editat per la Societat Catalana de Matemàtiques filial de l’Institut d’Estudis Catalans Carrer del Carme, 47 08001 Barcelona Text revisat lingüísticament per la Unitat de Correcció del Servei Editorial de l’IEC Imprès a Open Print, SL ISSN: 0214-316-X Dipòsit Legal: B 19272-1987 Són rigorosament prohibides, sense l’autorització escrita dels titulars del copyright, la reproducció total o parcial d’aquesta obra per qualsevol procediment i suport, incloent-hi la reprografia i el tractament informàtic, la distribució d’exemplars mitjançant lloguer o préstec comercial, la inclusió total o parcial en bases de dades i la consulta a través de xarxa telemàtica o d’Internet. Les infraccions d’aquests drets estan sotmeses a les sancions establertes per les lleis.

Butlletí de la Societat Catalana de Matemàtiques Vol. 35, núm. 1, 2020

Índex

Pere Ara La paradoxa de Banach-Tarski i el semigrup de tipus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Júlia Moreno, Mònica Blanco i Pere Pascual La compacitat, una noció seminal en l’evolució de la topologia general (1895–1930) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Oriol Serra Límits de grafs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 English summaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

Butlletí de la Societat Catalana de Matemàtiques Vol. 35, núm. 1, 2020. Pàg. 5–22. DOI: 10.2436/20.2002.01.91

La paradoxa de Banach-Tarski i el semigrup de tipus Pere Ara

Resum: En aquest article estudiarem un concepte clau en relació amb la coneguda paradoxa de Banach-Tarski. Es tracta del concepte d’equidescomponibilitat de subconjunts d’un conjunt X sobre el qual actua un grup discret G. Un subconjunt E de X és G-paradoxal si existeixen dos subconjunts disjunts E1 i E2 de E de manera que cadascun d’ells és equidescomponible amb E. L’estudi d’aquesta relació es pot sistematitzar mitjançant la introducció d’un cert semigrup S(X, G), anomenat semigrup de tipus d’equidescomponibilitat de X (o, simplement, semigrup de tipus). Farem una exposició del teorema de Tarski, per a la demostració del qual utilitzarem el semigrup de tipus S(X, G). Veurem algunes generalitzacions d’aquest concepte a un context topològic, i estudiarem la possible validesa del teorema de Tarski en aquest nou context. També explicarem un resultat recent de Grabowski, Máthé i Pikhurko que dona una resposta afirmativa al problema de la quadratura del cercle (en la seva versió moderna). Paraules clau: paradoxa de Banach-Tarski, semigrup de tipus, teorema de Tarski, espai topològic, quadratura del cercle.

Classificació MSC2010: 43A07, 03E25, 20E05.

La paradoxa de Banach-Tarski

En la seva versió més coneguda, la paradoxa de Banach-Tarski diu que podem partir una taronja en un nombre finit de peces de manera que, reorganitzant aquestes peces d’una altra forma, obtenim dues taronges idèntiques a la inicial.1 Una altra versió de la mateixa paradoxa afirma que podem subdividir un pèsol en un nombre finit de trossos de manera que reorganitzant-los obtenim una bola de la mateixa mida que el Sol. Aquesta paradoxa aparent (en qualsevol de les dues versions) és, de fet, un teorema demostrat per Stefan Banach i Alfred Tarski [4]. La seva demostració requereix l’axioma de l’elecció i, a la vegada, 1 O sigui, tenim una versió «valenciana» del miracle de la multiplicació dels pans i els peixos.

Pere Ara

com ja va observar John von Neumann, està íntimament connectada amb una certa propietat dels grups, anomenada mitjanabilitat.2 En aquest Butlletí han aparegut sengles articles sobre la paradoxa de BanachTarski. Un d’ells ([13]) tracta de la connexió entre la paradoxa de Banach-Tarski i l’axioma de l’elecció, i l’altre ([5]) és sobre la connexió entre la mateixa paradoxa i la teoria de grups. En el nostre treball tractarem d’un altre tema relacionat amb la paradoxa de Banach-Tarski, com és la noció bàsica de la relació d’equidescomponibilitat de conjunts respecte de l’acció d’un grup. L’estudi d’aquest concepte es pot sistematitzar gràcies a la consideració d’un semigrup commutatiu, el semigrup de tipus d’equidescomponibilitat, al qual ens referirem simplement com el semigrup de tipus. Estudiarem les propietats d’aquest semigrup, i n’estendrem la definició al context topològic. Veurem que en aquest context més general, l’anomenada alternativa de Tarski falla per l’aparició en escena d’un nou tipus de paradoxalitat, que podem anomenar (m, n)-paradoxalitat per a 1 < m < n. També descriurem un resultat recent espectacular, degut a Grabowski, Máthé i Pikhurko [8], sobre la versió moderna del problema de la quadratura del cercle. Primer de tot enunciarem el teorema de Banach-Tarski. En tot l’article usarem la notació t per a referir-nos a una unió disjunta, o sigui, una unió de subconjunts d’un cert conjunt de manera que els subconjunts són disjunts dos a dos. Teorema 1 (Teorema de Banach-Tarski). Sigui B la bola unitat a R3 . Llavors existeix una descomposició B = A 1 t · · · t A n t B1 t · · · t Bm i isometries g1 , . . . , gn , h1 , . . . , hm de R3 tals que B = g1 A1 t · · · t gn An = h1 B1 t · · · t hm Bm . Es pot demostrar que el nombre mínim de peces és n + m = 5. Podeu veure una demostració d’aquest resultat a l’article [5] aparegut en aquest Butlletí. Una referència imprescindible per a l’estudi de la paradoxa de Banach-Tarski és el llibre de Tomkowicz i Wagon [20]. Presentem ara el marc general. Sigui G un grup que actua sobre un conjunt X. Dos subconjunts E, E 0 de X són G-equidescomponibles, denotat per E ∼G E 0 , si E = A1 t A2 t · · · t An ,

E 0 = B1 t B2 t · · · t Bn

i existeixen g1 , g2 , . . . , gn ∈ G tals que Bi = gi Ai per a tot i = 1, . . . , n. Un subconjunt E ⊆ X s’anomena paradoxal si existeixen E1 , E2 tals que E1 t E2 ⊆ E amb E1 ∼G E i E2 ∼G E. El semigrup de tipus S(X, G) es defineix mitjançant l’anterior relació d’equidescomponibilitat: 2 Els termes mitjanable i mitjanabilitat que usem en aquest article provenen dels termes anglesos amenable i amenability, respectivament.

La paradoxa de Banach-Tarski i el semigrup de tipus

Definició 2. Sigui G un grup que actua sobre un espai X. Aleshores S(X, G) és el semigrup commutatiu generat per símbols [E], on E ⊆ X, subjecte a les relacions següents: (1) [∅] = 0, (2) [E ∪ F ] = [E] + [F ] si E ∩ F = ∅, (3) [gE] = [E] per a tot E ∈ P(X) i tot g ∈ G. Observació. Es pot demostrar, utilitzant la proposició 4, que veurem a continuació, que per a E, E 0 ⊆ X, tenim que [E] = [E 0 ] a S(G, X) si, i només si, E ∼G E 0 . Per tant, els elements de S(X, G) són les sumes finites de classes d’equidescomponibilitat [E], per a E ⊆ X. Encara que la definició anterior és conceptualment simple, moltes vegades es necessita una descripció més detallada dels elements del semigrup S(X, G). Això és el que va fer Tarski en el seu treball [19] (vegeu també el capítol 10 de [20]). La idea fonamental és ampliar l’acció de G sobre X a una acció sobre una quantitat numerable de còpies de X, de manera que tinguem «prou espai» per a representar tots els elements del semigrup. Aquesta idea és, de fet, prou similar a la que es fa servir en teoria K, on passem per exemple d’un anell R al seu estabilitzat M∞ (R), que és una unió inductiva de matrius finites de totes les mides. El lector interessat a conèixer més detalls sobre teoria K pot consultar l’excel.lent llibre de Jonathan Rosenberg ([17]). Definició 3. Sigui G un grup que actua sobre un conjunt X. Definim una acció ampliada com segueix. Sigui X ∗ = X × N, i sigui G∗ = G × Σ(N), on Σ(N) denota el grup de permutacions de N. El grup G∗ actua sobre X ∗ de forma natural: (g, π )(x, n) = (gx, π (n)). Si A és un subconjunt de X ∗ , els nivells de A són aquells enters n tals que existeix un element de A amb segona coordenada igual a n. Observem que per a E ⊆ X tenim que E × {n} ∼G∗ E × {m} per a n, m ∈ N. Això permet considerar còpies disjuntes de qualsevol subconjunt de X. Un subconjunt A de X ∗ s’anomena fitat si té només un nombre finit de nivells. Denotem la classe d’equivalència d’un subconjunt fitat A respecte de la relació de G∗ -equidescomponibilitat per [A]. Sigui S la col.lecció de totes les classes d’equivalència de subconjunts fitats de X ∗ . Llavors S admet una estructura de semigrup commutatiu, on [A] + [B] = [A ∪ B 0 ] per a subconjunts fitats A i B de X ∗ , on B 0 és una còpia de B que és disjunta de A. Ara podem demostrar que la construcció anterior ens dona un semigrup isomorf al semigrup de tipus S(X, G). Proposició 4. Sigui G un grup que actua sobre un conjunt X. Existeix un isomorfisme natural S(X, G) → S, que envia [A] a [A × {1}] per a A ⊆ X.

Pere Ara

Prova. Definim una aplicació ϕ : S(X, G) → S per la regla ϕ([A]) = [A × {1}] per a A ⊆ X. Per tal de veure que aquesta regla està ben definida i dona un morfisme de semigrups, cal observar que preserva les relacions definidores de S(X, G). Però això és clar per la relació de G∗ -equidescomponibilitat. També ∗ és clar que ϕ 2 , . . . , kr , llavors Frés exhaustiva, ja que, si A ⊆ X té nivells k1 , kP r posem A = i=1 Ai × {ki }, amb Ai ⊆ X, i tenim que [A] = ϕ( i=1 [A Pin]). Queda, doncs, per comprovar que ϕ és injectiva. Suposem que ϕ( i=1[Ai ])= Pm ϕ( i=1 [Bi ]). Aleshores tenim que A :=

n [

[Ai × {i}] ∼G∗ ,

B :=

i=1

m [

[Bi × {i}].

i=1

Per tant, existeixen subconjunts W1 , . . . , Wl , elements g1 , . . . , gl de G i enters positius n1 , . . . , nl , m1 , . . . , ml tals que A=

l G

Wk × {nk },

k=1

l G

gk Wk × {mk }.

k=1

Fn Fm Llavors tenim dues particions {1, . . . , l} = Fi=1 Ii i {1, . . . , l} = i=1 Ji tals que per a cada i ∈ {1, F . . . , n} tenim que Ai = j∈Ii Wj i per a tot j ∈ {1, . . . , m} tenim que Bj = i∈Jj gi Wi . S’obté la igualtat següent a S(X, G): n X i=1

[Ai ] =

n X X i=1 j∈Ii

[Wj ] =

l X

[Wj ] =

j=1

l X j=1

[gj Wj ] =

m X X

[gi Wi ] =

j=1 i∈Jj

Això demostra que ϕ és injectiva, i es completa l’argument.

m X

[Bj ].

j=1

Com a conseqüència d’aquest resultat, utilitzarem de manera indistinta qualsevol de les dues descripcions anteriors del semigrup de tipus S(X, G). Ara podem expressar la qualitat de paradoxalitat dels subconjunts de X en termes del semigrup de tipus. Primer introduïm el preordre ≤ en qualsevol semigrup commutatiu M mitjançant la relació x ≤ y si, i només si, existeix un element z de M tal que y = x + z. Aquest preordre s’anomena preordre algebraic de M. Ara observem que E ⊆ X és paradoxal si, i només si, 2[E] ≤ [E] a S(X, G). L’estudi del concepte de paradoxalitat va portar a la important noció de grup mitjanable: Un grup discret Γ s’anomena mitjanable si Γ Γ no és paradoxal, on Γ Γ denota el conjunt Γ amb l’acció del grup Γ definida mitjançant multiplicació per l’esquerra. El lector pot consultar [5] pel que fa a la relació entre la paradoxa de Banach-Tarski i la teoria de grups. Un fet bàsic en la teoria és que qualsevol grup lliure no commutatiu és no mitjanable.

La quadratura del cercle

En el segle xx, Tarski va enunciar una versió diferent del conegut enigma dels grecs sobre la quadratura del cercle, que consisteix en la constructibilitat amb regle i compàs d’un cercle d’àrea 1.

La paradoxa de Banach-Tarski i el semigrup de tipus

En aquesta nova versió ([18]) es pregunta si un cercle i un quadrat de la mateixa àrea són equidescomponibles respecte del grup de totes les isometries de R2 . La primera observació important és que, perquè siguin equidescomponibles, han de tenir necessàriament la mateixa àrea. Això es deu al fet que el grup G2 de les isometries de R2 és un grup mitjanable; de fet, és un grup resoluble, i és ben conegut que tots els grups resolubles són mitjanables. Hom pot demostrar que la mesura de Lebesgue sobre R1 i sobre R2 es pot estendre a una mesura finitament additiva definida a tots els subconjunts. De fet, tenim el resultat següent: Teorema 5. Si G és un grup mitjanable d’isometries de Rn , llavors existeix una extensió de la mesura de Lebesgue λ a una mesura finitament additiva i G-invariant definida sobre tots els subconjunts de Rn . En particular, existeix una extensió de la mesura de Lebesgue a tots els subconjunts de R1 o R2 que és invariant per isometries. Per a una demostració del teorema 5, el lector pot consultar el capítol 12 de [20]. Així doncs, si tenim dues regions mesurables A i B de R2 que són Fnequi2 descomponibles respecte del grup G d’isometries de R , amb A = 2 i=1 Ai , Fn B = i=1 gi Ai , gi ∈ G2 , i λ és una extensió de la mesura de Lebesgue λ com en el teorema 5, aleshores tenim λ(A) =

n X

λ(Ai ) =

i=1

n X

λ(gi Ai ) = λ(B),

i=1

de manera que A i B tenen la mateixa àrea. El 1924, Tarski va demostrar que dos polígons de la mateixa àrea són equidescomponibles entre si (vegeu el capítol 3 de [20]). Finalment, Laczkovich va demostrar el resultat sobre la quadratura del cercle ([10, 11]), però les peces obtingudes en la seva demostració no són mesurables. En un resultat recent, Grabowski, Máthé i Pikhurko ([8]) han demostrat que es pot fer la quadratura del cercle amb peces que són a la vegada mesurables en el sentit de Lebesgue i mesurables en el sentit de Baire. Recordem que un subconjunt és mesurable en el sentit de Baire si és la diferència simètrica d’un conjunt de Borel i un conjunt magre. El teorema de Grabowski, Máthé i Pikhurko és, de fet, a la vegada més fort i més general que el que hem esmentat en el paràgraf anterior. Per a enunciar-lo necessitem algunes definicions prèvies. Primer definim la dimensió per caixes (box dimension) de X ⊆ Rk com dim (X) := k − lim inf + ε→0

log λ({x ∈ Rk : dist(x, X) ≤ ε}) , log ε

on dist(x, X) és la distància L∞ des del punt x al conjunt X.

Pere Ara

Per a conjunts A i B de Rk , diem que A i B són congruents per translaTr

cions (A ∼ B), si A i B són equidescomponibles respecte al grup de totes les translacions de Rk , és a dir, existeix una descomposició A = A1 t A2 t · · · t An i translacions σ1 , . . . , σn de Rk tals que B = σ1 (A1 ) t σ2 (A2 ) t · · · t σn (An ). Denotant per ∂A la frontera topològica de A, podem enunciar el teorema com segueix: Teorema 6 ([8, teorema 1.2]). Sigui k ≥ 1, i siguin A i B subconjunts mesurables Tr

i fitats de Rk tals que λ(A) = λ(B), dim(∂A) < k, i dim(∂B) < k. Llavors A ∼ B amb peces que són a la vegada mesurables en el sentit de Lebesgue i en el sentit de Baire. Com a conseqüència immediata hom obté la següent versió moderna de la quadratura del cercle: Corol.lari 7. Un cercle i un quadrat de la mateixa àrea són congruents per translacions a R2 .

El teorema de Tarski

El teorema de Tarski permet connectar dues definicions aparentment diferents de grup mitjanable. Aquí presentem la versió més general sobre accions en conjunts, seguint [20, capítol 11]. Recordem que una mesura µ : P(X) → [0, +∞] s’anomena finitament additiva si µ(A t B) = µ(A) + µ(B) per a tots A, B ∈ P(X) mútuament disjunts, i que, si G és un grup que actua sobre X, la mesura µ s’anomena G-invariant si µ(gA) = µ(A) per a tot g ∈ G i tot A ∈ P(X). Observem en aquest punt el fet important que les mesures finitament additives i G-invariants sobre X es corresponen naturalment amb els morfismes de semigrups µ : S(X, G) → [0, +∞], on S(X, G) és el semigrup de tipus corresponent a l’acció de G sobre X. Teorema 8 (Teorema de Tarski). Sigui G un grup que actua sobre un conjunt X. Donat E ⊆ X, les propietats següents són equivalents: (a) E no és paradoxal. (b) Existeix una mesura finitament additiva i G-invariant µ : P(X) → [0, +∞] tal que µ(E) = 1.

La paradoxa de Banach-Tarski i el semigrup de tipus

La implicació (b) =⇒ (a) és trivial. De fet, si existeix una tal mesura µ i E és un conjunt paradoxal, amb E1 t E2 ⊆ E i E ∼G Ei per a i = 1, 2, llavors tenim que µ(E) = µ(Ei ), i = 1, 2, i, per tant, obtenim la contradicció 2 = µ(E1 t E2 ) ≤ µ(E) = 1. La demostració de (a) =⇒ (b) usa una mena de teorema de Hahn-Banach per a semigrups, que Tarski va demostrar: Teorema 9 (Tarski). Sigui (S, +) un semigrup commutatiu i e ∈ S. Aleshores les condicions següents són equivalents: (a) Per a tot n ∈ N, es compleix (n + 1)e ne. (b) Existeix un morfisme de semigrups µ : S → [0, ∞] tal que µ(e) = 1. A més, la demostració usa també les propietats següents de S(X, G): Axioma de Schröder-Bernstein:

a ≤ b i b ≤ a =⇒ a = b.

Llei de cancel.lació:

na = nb =⇒ a = b.

∀n ∈ N,

De fet, per l’observació que hem fet tot just abans del teorema 8, tenim que, pel semigrup S = S(X, G) i l’element e = [E] de S, la condició (b) del teorema 8 es correspon exactament amb la condició (b) del teorema 9. Per tant, per demostrar la implicació (a) =⇒ (b) del teorema 8 a partir del teorema 9, només cal veure que la condició (a) del teorema 8 és equivalent a la condició (a) del teorema 9 per l’element e = [E]. Això és el mateix que demostrar que, per a e ∈ S(X, G), tenim 2e ≤ e ⇐⇒ (n + 1)e ≤ ne

per a algun n.

La implicació =⇒ és trivial. Per a demostrar l’altra implicació, suposem que (n + 1) ≤ ne per a algun n ≥ 1. Llavors (n + 1)e = ne per Schröder-Bernstein, i (n + 1)e = ne =⇒ n(2e) = ne =⇒ 2e = e

per la llei de cancel.lació.

Per tant, hem vist que el teorema de Tarski (teorema 8) es deriva del teorema 9, que és un resultat general de teoria de semigrups i que no demostrarem aquí, i del fet que els semigrups de la forma S(X, G) satisfan l’axioma de Schröder-Bernstein i la llei de cancel.lació. En la resta d’aquesta secció, donarem les idees principals que permeten demostrar aquestes dues propietats del semigrup de tipus S(X, G). Cal tenir present que cap d’aquestes dues propietats se satisfà en el context més general que estudiem en les properes seccions. La propietat de Schröder-Bernstein per a S(X, G) és, de fet, la propietat antisimètrica del preordre algebraic ≤ sobre S(X, G), o sigui que aquesta propietat es compleix si, i només si, ≤ és un ordre parcial sobre S(X, G). Aquesta propietat es dedueix del teorema de Banach-Schröder-Bernstein (vegeu [20, teorema 3.6]), que és una generalització del conegut teorema de SchröderBernstein per a conjunts. Aquest resultat és molt útil a l’hora de demostrar que

Pere Ara

dos conjunts donats són equidescomponibles. Observem que una conseqüència immediata de la propietat de Schröder-Bernstein és que un subconjunt E de X és G-paradoxal si, i només si, 2[E] = [E] a S(G, X), de manera que podem descompondre E exactament com la unió de dos subconjunts disjunts E1 i E2 amb E ∼G Ei per a i = 1, 2. Pel que fa a la llei de cancel.lació per a S(X, G), aquesta es demostra utilitzant el teorema de Hall-Rado-Hall per a grafs bipartits. Recordem que un graf bipartit és un graf els vèrtexs del qual es divideixen en dos conjunts A i B de forma que totes les arestes del graf connecten un vèrtex de A amb un vèrtex de B. Un aparellament (matching en anglès) és un conjunt d’arestes tals que els vèrtexs incidents són mútuament diferents. Segons el clàssic teorema de Hall-Rado, si tenim un graf bipartit finit Γ amb parts A i B, llavors Γ té un aparellament que cobreix tots els vèrtexs de A si, i només si, per a cada k, tot conjunt de k vèrtexs de A té com a mínim k veïns (o sigui, existeixen com a mínim k elements de B que es connecten amb aquests k elements de A mitjançant arestes de Γ ). Aquest resultat es deu a Phillip Hall i Richard Rado i s’anomena també teorema del matrimoni (marriage theorem). Marshall Hall el va generalitzar al cas de grafs infinits: Teorema 10 (Teorema de Hall-Rado-Hall). Sigui Γ un graf bipartit amb parts A i B de manera que cada vèrtex de A té un grau finit. Llavors Γ admet un aparellament que cobreix tots els vèrtexs de A si, i només si, per a cada nombre natural k, tot conjunt de k vèrtexs de A té com a mínim k veïns a B. Podem esbossar una demostració d’aquest resultat a partir del teorema de Hall-Rado com segueix: Donem a B la topologia discreta i a B A la topologia producte. Per a cada a ∈ A, sigui NaQ el subconjunt finit de B format per tots els veïns de a. Llavors el producte Y := a∈A Na és un subconjunt compacte de B A pel teorema de Tikhonov. Ara, per a cada subconjunt finit i no buit H de A, sigui M(H) el conjunt de totes les funcions f ∈ Y ⊆ B A tals que f |H és un aparellament. Pel teorema de Hall-Rado, M(H) 6= ∅. A més, els conjunts M(H) són claramemt subconjunts tancats de Y . Si H1 , H2 , . . . , Hn són subconjunts finits i no buits de Y , aleshores M(H1 ∪ H2 ∪ · · · ∪ Hn ) ⊆

n \

M(Hi ),

i=1

i, per tant, la família {M(H)}, on H varia en tots els subconjunts finits i no buits de A, compleix la propietat de la intersecció finita i així la intersecció de tots aquests conjunts és no buida (ja que Y és compacte). Un element f d’aquesta intersecció ens dona el aparellament desitjat. Ara ja podem donar la demostració de la llei de cancel.lació. De fet, provarem el resultat següent, que és més fort que la llei de cancel.lació atès que ≤ és un ordre parcial a S(X, G). Per a la demostració seguim bàsicament [20, teorema 10.20]. Teorema 11. Sigui G un grup que actua sobre un conjunt X, i siguin α, β ∈ S(X, G) i n ∈ N tals que nα ≤ nβ. Llavors tenim que α ≤ β.

La paradoxa de Banach-Tarski i el semigrup de tipus

Prova. Si nα ≤ nβ, llavors podem trobar dos conjunts disjunts, fitats i G∗ equidescomponibles E i F de X ∗ tals que E = A1 t · · · t An ,

F = B1 t · · · t Bn ,

i de manera que [Ai ] = α i [Bj ] = β per a tot i, j. Sabem que E ∼ E 0 per a cert E 0 ⊆ F . Sigui χ : E → E 0 ⊆ F la corresponent G∗ -congruència. Siguin φi : A1 → Ai i ψi : B1 → Bi G∗ -congruències, amb φ1 i ψ1 iguals a la identitat. Per a a ∈ A1 , posem a = {a, φ2 (a), . . . , φn (a)} i per a b ∈ B1 , posem b = {b, ψ2 (b), . . . , ψn (b)}. Observem que {a : a ∈ A1 } i {b : b ∈ B1 } donen particions de E i E 0 respectivament. Formem un graf bipartit amb dues parts A = {a : a ∈ A1 } i B = {b : b ∈ B1 }. Posem n arestes que connectin a amb vèrtexs de B. De fet, posem una aresta entre a i b si, i només si, χφi (a) ∈ b per a algun i = 1, . . . , n. Aquest graf és n-regular en A i de grau màxim n en B. Per veure que es compleix la hipòtesi del teorema de Hall-Rado-Hall, suposem que Y és un subconjunt de A amb k elements. Llavors existeixen exactament nk arestes que connecten Y amb elements de B. Si Z denota el conjunt dels veïns de Y i |Z| és menor que k, llavors tindrem un nombre d’arestes que connecten Z amb Y menor que kn; per tant, tenim que |Z| ≥ k, com volíem. Ara el teorema 10 ens dona un aparellament M que cobreix tots els vèrtexs de A. Donat a ∈ A, existeix un sol vèrtex b ∈ B tal que (a, b) ∈ M, i, pert tant, tenim que χφi (a) = ψj (b) per a certs i, j. Sigui Cij = {a ∈ A1 : (a, b) ∈ M i χφi (a) = ψj (b)}, i, similarment, sigui Dij = {b ∈ B1 : (a, b) ∈ M i χφi (a) = ψj (b)}. Aleshores, ψj−1 χψi envia Ci a Dj i és una G∗ congruència perquè ψi , χ i ψj ho són. Com que {Cij } és una partició de A1 i {Dij } són subconjunts mútuament disjunts de B1 , obtenim que α ≤ β. 2

Una generalització topològica del semigrup de tipus

El semigrup de tipus S(X, G) de l’acció d’un grup G sobre un conjunt X ha estat generalitzat de diverses maneres; vegeu, per exemple, el capítol 10 de [20]. Aquí tractarem una generalització topològica que ha despertat recentment l’atenció d’alguns investigadors; vegeu [9, 12, 14, 15, 16]. Per començar considerem un grup G que actua sobre un conjunt X. Recordem que una àlgebra de conjunts de X és una família de subconjunts de X que conté ∅ i X, és tancada per interseccions i unions finites, i també és tancada per complements. Diem que una àlgebra de conjunts D és G-invariant si g(D) ∈ D per a cada g ∈ G i D ∈ D. Sigui G un grup que actua sobre un conjunt X i sigui D una àlgebra G-invariant de conjunts de X. Llavors podem restringir la relació de G-equidescomponibilitat a elements de D, i així obtenim un semigrup de tipus S(X, G, D) relatiu a D. Més concretament, el semigrup S(X, G, D) és el semigrup commutatiu amb generadors [D] per a D ∈ D, i amb les mateixes relacions que les usades a la definició 2. Si A, B ∈ D, posem A ∼G B si podem descompondre A en unió disjunta de subconjunts A1 , . . . , An , tots ells pertanyents a D, i podem trobar

Pere Ara

elements g1 , . . . , gn ∈ G tals que B és la unió disjunta de g1 A1 , . . . , gn An . Es pot obtenir amb la mateixa demostració, bàsicament una descripció de S(G, X, D) similar a la donada al teorema 4. En articles recents de Rørdam-Sierakowski [16] i Kerr-Nowak [9], s’ha considerat el cas particular següent. Recordem que un espai topològic es diu que té dimensió zero si admet una base de conjunts que són a la vegada oberts i tancats. Sigui G un grup que actua per homeomorfismes sobre un espai de Hausdorff compacte i de dimensió zero X. Prenem com a àlgebra de conjunts de X l’àlgebra K de tots els oberts i tancats de X. Un exemple d’aquests espais és el conjunt de Cantor. Aquest espai es pot caracteritzar topològicament per la propietat de ser un espai compacte Hausdorff metritzable de dimensió zero perfecte. (Un espai topològic s’anomena perfecte si no té punts aïllats.) Existeixen nombrosos models de conjunt de Cantor, com ara el clàssic que s’obté suprimint intervals centrals successius, començant amb l’interval [0, 1]. Un model important és de la forma AN , un espai producte on A és un conjunt finit amb més d’un element. Obtenim així, en les condicions anteriors, el semigrup de tipus S(X, G, K). Una pregunta natural és quina mena de condicions satisfà el semigrup de tipus S(X, G, K). Es compleix un anàleg del teorema de Tarski? En l’estudi dels invariants associats a les C ∗ -àlgebres, s’ha demostrat que és important la condició anomenada de quasi-no-perforat. Un semigrup M és quasi-no-perforat si per a x, y ∈ M i n ∈ N, (n + 1)x ≤ ny implica que x ≤ y. Pel teorema 9 és clar que, si S(X, G, K) és quasi-no-perforat, llavors es compleix el teorema de Tarski en la seva versió topològica. Aquí el tipus de mesures que s’obtenen en el teorema de Tarski són finitament additives sobre l’àlgebra K en valors a [0, ∞]. Quan l’espai és metritzable, aquestes mesures es poden estendre de manera única a mesures de Borel regulars sobre X ([16, lema 5.1]).

Accions parcials

Podem generalitzar el que acabem de presentar al cas d’accions parcials de grups, que s’usen, per exemple, en construccions com les que trobem en [2]. Com a motivació esmentem un exemple fonamental: hom obté una acció parcial d’un grup G sobre un conjunt X restringint una acció global a un subconjunt que no és invariant. Aquí ens limitarem a accions parcials de grups sobre espais topològics. Per a més informació sobre accions parcials, el lector pot consultar el llibre de Ruy Exel [7] Definició 12. Una acció parcial d’un grup G sobre un espai topològic X consisteix en una col.lecció {Xg } de subconjunts oberts de X, junt amb homeomorfismes θg : Xg −1 → Xg tals que θ1 = IdX i θgh ⊇ θg ◦ θh per a g, h ∈ G.

La paradoxa de Banach-Tarski i el semigrup de tipus

En aquesta definició cal fer alguns aclariments. En primer lloc, dues aplicacions parcialment definides, diguem f : Y → X i g : Z → X, on Y , Z són subconjunts de X, es poden compondre amb la regla que el seu domini sigui el més gran possible. Concretament, g ◦ f és una aplicació parcialment definida sobre X amb domini Y ∩ f −1 (Z) i imatge g(f (Y ) ∩ Z). En segon lloc, si f i g són dues aplicacions parcialment definides sobre un conjunt X, llavors el símbol g ⊆ f significa que f estén g, és a dir, que el domini de g està contingut en el domini de f , i que la restricció de f al domini de g coincideix amb g. Ara, si β defineix una acció global de G per homeomorfismes sobre un espai topològic Y i X és un subespai obert de Y , podem definir una acció parcial de G sobre X posant per a cada g ∈ G, Xg = X ∩ βg (X). Observem que Xg és un obert de X per a cada g ∈ G i que βg (Xg −1 ) = βg (X ∩ βg −1 (X)) = βg (X) ∩ X = Xg . Per tant, podem definir αg : Xg −1 → Xg com la restricció de βg a Xg −1 , i hom pot demostrar que α és una acció parcial de G sobre X, anomenada restricció de β a X. El procés invers del procés anterior s’anomena globalització d’una acció parcial. Per a una acció parcial α de G sobre X, aquest procés consisteix a trobar una acció global β de manera que la seva restricció a X sigui l’acció parcial α. Vegeu [1] per a més detalls. Considerem una acció parcial ({Xg : g ∈ G}, {θg : g ∈ G}) de G sobre un conjunt compacte Hausdorff de dimensió zero X, i sigui K l’àlgebra dels subconjunts oberts i tancats de X. Suposem també que Xg ∈ K per a tot g ∈ G. Llavors clarament K és G-invariant en el sentit que per a cada element g ∈ G i cada U ∈ K, tenim que θg (U ∩ Xg −1 ) ∈ K. En aquestes condicions, podem definir també el semigrup de tipus S(X, G, K). Els generadors són també les classes [U ] amb U ∈ K, i només cal modificar la relació (3) a la definició 2 per la condició (3’) [U ] = [gU ] per a tot g ∈ G i tot U ∈ K tal que U ⊆ Xg −1 . En aquest nivell de generalitat, ens podem preguntar quines són les propietats que satisfan els semigrups de tipus S := S(X, G, K). És clar que aquests semigrups són commutatius i amb element neutre 0 = [∅], és a dir, són monoides commutatius. També tenen una altra propietat que és òbvia: • S(X, G, K) és cònic, en el sentit que x + y = 0 =⇒ x = y = 0. Finalment, es compleix una condició que és força important, i que s’obté del fet que estem treballant amb una àlgebra de conjunts. Es tracta de l’anomenada propietat de refinament de Riesz. Definició 13. Un semigrup S satisfà la propietat de refinament de Riesz si sempre que a + b = c + d existeixen x, y, z, t ∈ S tals que a = x + y, b = z + t, c = x + z i d = y + t.

Pere Ara

Aquesta propietat es pot expressar en la forma d’una matriu, anomenada matriu de refinament: c d a x y b z t En aquesta matriu, les files i les columnes sumen l’element que indica la fila o columna corresponent. Es pot demostrar fàcilment per inducció que en un semigrup de refinament tota identitat a1 + a2 + · · · + an = b1 + b2 + · · · + bm admet una matriu de refinament n × m. Ara podem establir la propietat de refinament de Riesz per al semigrup de tipus S(X, G, K): Proposició 14. Sigui G un grup que actua parcialment sobre un espai compacte Hausdorff de dimensió zero X i sigui K l’àlgebra dels subconjunts oberts i tancats de X. Llavors S(X, G, K) satisfà la propietat de refinament de Riesz. Prova. Per a provar-ho, farem servir la descripció de S(X, G, K), que és anàloga a la presentada a la definició 3. Veiem, per tant, els elements de S(X, G, K) S com a classes [A], on A = i∈I Ai × {i}, I és un subconjunt finit de N i Ai ∈ K per a tot i. Suposem que tenim [A] + [B] = [C] + [D] a S(X, G, K). Siguin N1 i N2 els conjunts de nivells de A i B respectivament, i siguin M1 i M2 els conjunts de nivells de C i D respectivament. Sense pèrdua de generalitat, podem considerar que N1 ∩ N2 = ∅ i M1 ∩ M2 = ∅. Ara tenim que A ∪ B ∼G∗ C ∪ D, amb la G∗ -equidescomponibilitat implementada únicament amb membres de K. Així doncs, podem trobar elements g1 , . . . , gl ∈ G; subconjunts Z1 , . . . , Zl de X tals que Zi ∈ K i Zi ⊆ Xg −1 , i enters positius n1 , . . . , nl , m1 , . . . , ml tals que i

A∪B =

l G

Zi × {ni },

C ∪D =

i=1

l G

θgi (Zi ) × {mi }.

i=1

Definim G

A1 =

Zi × {ni },

A2 =

ni ∈N1 , mi ∈M1

B1 =

Zi × {ni },

ni ∈N1 , mi ∈M2

Zi × {ni },

ni ∈N2 , mi ∈M1

B2 =

Zi × {ni }.

ni ∈N2 , mi ∈M2

Llavors tenim A = A1 t A2 , B = B1 t B2 , i també C ∼G∗ A1 t B1 , D ∼G∗ A2 t B2 . Per tant, obtenim el refinament [A] = [A1 ]+[A2 ], com volíem.

[B] = [B1 ]+[B2 ],

[C] = [A1 ]+[B1 ],

[D] = [A2 ]+[B2 ],

La paradoxa de Banach-Tarski i el semigrup de tipus

Fallida de l’alternativa de Tarski per a accions sobre espais topològics

Sigui G un grup que actua sobre un conjunt X i E, un subconjunt de X. Segons l’alternativa de Tarski, o bé E és paradoxal, o bé existeix una mesura finitament additiva sobre P(X) tal que µ(E) = 1 (vegeu el teorema 5). En aquesta secció veurem certes construccions que ens permetran afirmar que l’alternativa de Tarski no es compleix en el context topològic introduït a les dues seccions anteriors. Sigui ara G un grup amb una acció parcial sobre un espai compacte Hausdorff de dimensió zero X. De les construccions de [2] se segueix que el semigrup S(X, G, K) és bàsicament arbitrari, amb la sola restricció de ser un monoide commutatiu cònic i de refinament. La idea per a demostrar aquest resultat sobre el semigrup de tipus S(X, G, K), i en particular la fallida de l’alternativa de Tarski en el context topològic, és utilitzar la teoria de grafs. En aquest cas, els nostres grafs seran grafs dirigits. Per veure un exemple senzill i il.lustratiu, descriurem el sistema dinàmic parcial associat a l’anomenada àlgebra de Cuntz On (vegeu [6] i les seves referències). Hom defineix una acció parcial del grup lliure amb n generadors Fn sobre l’espai de Cantor X = {1, . . . , n}N . L’espai X es pot descriure com l’espai de camins infinits sobre el graf dirigit Rn que té un únic vèrtex i n arestes, anomenat de vegades la rosa de n-pètals: 3

·· •vQ g s ·

1 n

Per a 1 ≤ i ≤ n, posem Xi = {(i, a2 , a3 , . . . )} ⊆ X, i definim si : X → Xi com si (a1 , a2 , . . . ) = (i, a1 , a2 , . . . ). Denotant per si∗ la inversa de si (que és una aplicació parcialment definida sobre X), tenim que n X si∗ sj = δij , sj sj∗ = 1. j=1

Aquestes importants relacions van ser considerades per Cuntz en el seu article [6]. Es pot demostrar que existeix una acció parcial de Fn sobre X que envia els generadors del grup lliure Fn a s1 , s2 , . . . , sn . L’àlgebra de Cuntz On es pot obtenir a partir de l’acció parcial anterior gràcies a una construcció algebraicoanalítica anomenada producte creuat parcial (vegeu [7]). Es pot demostrar que el semigrup de tipus S(X, Fn , K) és isomorf al monoide cíclic Cn = ha | a = nai. No entrarem en detalls sobre aquests punts, però observem d’entrada que això implica que el semigrup S(X, Fn , K) no satisfà l’axioma de Schröder-Bernstein si n ≥ 3, ja que en aquest cas tenim que a ≤ 2a ≤ a, però a 6= 2a en el monoide Cn .

Pere Ara

Fn Observem que en l’exemple anterior tenim una descomposició X = i=1 Xi junt amb homeomorfismes si : X → Xi . Això és el que determina la relació [X] = n[X] en el semigrup de tipus S(X, Fn , K). Podem obtenir una classe molt més àmplia d’exemples prenent grafs dirigits amb certes particions de les arestes. Això es pot visualitzar pensant que donem diferents colors a les arestes, i pensem que les arestes que tenen el mateix color estan al mateix conjunt de la partició. Concretament, tenim la definició de graf separat, que va ser introduïda a [3]. Per entendre-la bé cal recordar que un graf dirigit és una quàdrupla E = (E 0 , E 1 , r , s), on E 0 és el conjunt dels seus vèrtexs, E 1 és el conjunt de les seves arestes, i r , s : E 1 → E 0 són aplicacions que descriuen, respectivament, el vèrtex terminal i el vèrtex inicial de les arestes. 0 1 Definició 15. Un Fgraf separat és una parella (E, C), on E = (E , E , r , s) és un graf dirigit, C = v∈E 0 Cv , i Cv és una partició de r −1 (v) (en subconjunts no buits i mútuament disjunts) per a cada vèrtex v de E.

Encara que no és estrictament necessari, és convenient utilitzar grafs dirigits bipartits. Això permet visualitzar millor les propietats. En general, considerant un graf bipartit, podem trobar una versió «externa» del nostre sistema dinàmic que conté dues còpies disjuntes del conjunt que volem estudiar. Definició 16. Diem que un graf separat (E, C) és bipartit si E 0 = E 0,0 t E 0,1 i totes les arestes van de E 0,1 a E 0,0 . Cada graf separat bipartit finit (E, C) ens dona un model diferent de sistema dinàmic (parcial), amb unes relacions determinades en el seu semigrup de tipus. Definició 17. Sigui (E, C) un graf separat bipartit finit. Un (E, C)-sistema dinàmic és un espai topològic compacte Hausdorff Ω amb una família {Ωv }v∈E 0 de subconjunts oberts i tancats tal que G Ω= Ωv v∈E 0

i, per a cada v ∈ E 0,0 , una família de subconjunts oberts i tancats {He }e∈r −1 (v) de Ωv tal que G Ωv = Hx e∈A

per a cada A ∈ Cv , junt amb una família d’homeomorfismes θe : Ωs(e) → He per a cada e ∈ E 1 . Donats dos (E, C)-sistemes dinàmics (Ω, θ) i (Ω0 , θ 0 ), hi ha una noció natural de morfisme equivariant f : (Ω, θ) → (Ω0 , θ 0 ). Diem que una aplicació f : Ω → Ω0 és equivariant si f (Ωv ) ⊆ Ωv0 per a tot v ∈ E 0 , f (He ) ⊆ He0 per a tot e ∈ E 1 i f (θe (t)) = θe0 (f (t)) per a tot e ∈ E 1 i t ∈ Ωs(e) . Establim que (Ω, θ) és un (E, C)-sistema dinàmic universal si existeix una única aplicació contínua i equivariant de qualsevol altre (E, C)-sistema dinàmic en (Ω, θ).

La paradoxa de Banach-Tarski i el semigrup de tipus

Teorema 18 ([2]). Donat un graf separat bipartit (E, C), existeix un (E, C)-sistema dinàmic universal (Ω(E, C), θ(E,C) ). El grup lliure F(E 1 ) en les arestes de E actua parcialment per homeomorfismes sobre Ω(E, C) de manera que l’homeomorfisme parcial associat a un generador e ∈ E 1 del grup lliure és precisament (θ(E,C) )e . Observem que tenim G

Ω(E, C) =

Ωv

v∈E 0

i per a cada v ∈ E 0,0 i A ∈ Cv , [Ωv ] =

[Ωs(e) ]

e∈A

en el semigrup de tipus S(Ω(E, C), F(E 1 ), K). Descrivim ara una generalització del sistema dinàmic associat a les àlgebres de Cuntz, que hem vist anteriorment. Siguin m i n enters tals que 1 ≤ m ≤ n. Considerem parelles d’espais compactes Hausdorff (X, Y ) tals que X=

n [

Hi =

i=1

m [

Vj ,

j=1

on els Hi són subconjunts oberts i tancats mútuament disjunts de X, cadascun d’ells homeomorf a Y via homeomorfismes hi : Y → Hi , per a 1 ≤ i ≤ n. Anàlogament, suposem que els Vj són subconjunts oberts i tancats mútuament disjunts de X, cadascun d’ells homeomorf a Y via homeomorfismes vj : Y → Vj , per a 1 ≤ j ≤ m. m Ens referirem llavors a un (m, n)-sistema dinàmic (X, Y , {hi }n i=1 , {vj }j=1 ). Observem que els (m, n)-sistemes dinàmics corresponen als (E(m, n), C(m, n))-sistemes dinàmics, on (E(m, n), C(m, n)) és el graf separat amb E(m, n)0,0 = {v}, E(m, n)0,1 = {w}, i C(m, n) = {A, B}, on A i B tenen n i m arestes respectivament, i totes les arestes van de w a v. L’exemple on m = 2 i n = 3 es mostra a la figura 1. v

w Figura 1: El graf separat (E(2, 3), C(2, 3)).

Pere Ara

m Si (X, Y , {hi }n i=1 , {vj }j=1 ) és un (m, n)-sistema dinàmic, tenim la relació següent en el semigrup de tipus S(X t Y , Fm+n , K):

n[Y ] =

n X i=1

[Hi ] = [X] =

m X

[Vj ] = m[Y ],

j=1

o sigui, m[Y ] = n[Y ]. n u m Denotem per (X u , Y u , {hu i }i=1 , {vj }j=1 ) el (m, n)-sistema dinàmic universal, que existeix com a conseqüència del teorema 18. Observem que tenim Ω(E(m, n), C(m, n)) = X u t Y u ,

Xu =

n [

Hiu =

i=1

m [

Vju ,

j=1

u u u u u i homeomorfismes hu i : Y → Hi , vj : Y → Vj . . Es demostra a [2, corol lari 7.6] que el semigrup de tipus

S := S(Ω(E(m, n), C(m, n)), Fn+m , K) n u m associat al (m, n)-sistema dinàmic universal (X u , Y u , {hu i }i=1 , {vj }j=1 ) conté el monoide Cm,n := ha : ma = nai.

Més precisament, existeix un morfisme de monoides injectiu ι : Cm,n → S tal que, per a x, y ∈ Cm,n , tenim x ≤ y a Cm,n si, i només si, ι(x) ≤ ι(y) a S. (Un morfisme injectiu amb aquesta propietat s’anomena injecció d’ordre.) A més, tenim que ι(a) = [Y u ]. Per a 1 < m < n, el monoide Cm,n té una estructura peculiar. Podem dir que és cíclic d’ordre n − m «a partir de m». Més concretament, Cm,n = {0} ∪ {a, . . . , (m − 1)a} ∪ {ma, (m + 1)a, . . . , (n − 1)a}, amb ia 6= ja per a i 6= j si 1 ≤ i ≤ m − 1, j ∈ N, i ia = ja si, i només si, i − j ∈ (n − m)Z si i, j ≥ m. En particular, tenim que 2a a a Cm,n i, per tant, 2[Y u ] = 2ι(a) ι(a) = [Y u ] a S, atès que ι és una injecció d’ordre. Deduïm que Y u no és un conjunt paradoxal. En canvi, no pot haver-hi una mesura invariant sobre l’àlgebra K d’oberts i tancats de Ω(E(m, n), C(m, n)) tal que µ(Y u ) = 1. De fet, si aquesta mesura µ existís, llavors, denotant també per µ l’homomorfisme de semigrups S → [0, ∞] associat i tenint en compte la relació m[Y u ] = n[Y u ] a S, tindríem: m = µ(m[Y u ]) = µ(n[Y u ]) = n, fet que contradiu la hipòtesi que m < n. Per tant, podem concloure que l’alternativa de Tarski no es compleix en el context topològic. Finalment observem que, utilitzant els resultats de globalització d’accions parcials d’Abadie [1], es pot demostrar que existeixen accions globals que satisfan les propietats esmentades anteriorment (vegeu [2, secció 7]), de manera que l’alternativa de Tarski no es compleix tampoc en el context d’accions globals sobre espais topològics.

La paradoxa de Banach-Tarski i el semigrup de tipus

Referències [1] Abadie, F. «Enveloping actions and Takai duality for partial actions». J. Funct. Anal., 197 (1) (2003), 14–67. [2] Ara, P.; Exel, R. «Dynamical systems associated to separated graphs, graph algebras, and paradoxical decompositions». Adv. Math., 252 (2014), 748–804. [3] Ara, P.; Goodearl, K. R. «Leavitt path algebras of separated graphs». J. Reine Angew. Math., 669 (2012), 165–224. [4] Banach, St.; Tarski, A. «Sur la décomposition des ensembles de points en parties respectivement congruentes». Fund. Math., 6 (1924), 244–277. [5] Burillo, J. «Grups i la paradoxa de Banach-Tarski». Butlletí de la Societat Catalana de Matemàtiques, 23 (2) (2008), 181–199. [6] Cuntz, J. «Simple C ∗ -algebras generated by isometries». Comm. Math. Phys., 57 (2) (1977), 173–185. [7] Exel, R. Partial Dynamical Systems, Fell Bundles and Applications. Providence, RI: American Mathematical Society, 2017. (Mathematical Surveys and Monographs; 224) [8] Grabowski, Ł.; Máthé, A.; Pikhurko, O. «Measurable circle squaring». Ann. of Math. (2), 185 (2) (2017), 671–710. [9] Kerr, D.; Nowak, P. W. «Residually finite actions and crossed products». Ergodic Theory Dynam. Systems, 32 (5) (2012), 1585–1614. [10] Laczkovich, M. «Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem». J. Reine Angew. Math., 404 (1990), 77–117. [11] Laczkovich, M. «Decomposition of sets with small boundary». J. London Math. Soc. (2), 46 (1) (1992), 58–64. [12] Ma, X. «Comparison and pure infiniteness of crossed products». Trans. Amer. Math. Soc., 372 (10) (2019), 7497–7520. [13] Pla Carrera, J. «L’axioma de l’elecció i la paradoxa de Banach-Tarski». Butlletí de la Secció de Matemàtiques de la Societat Catalana de Ciències Físiques, Químiques i Matemàtiques, 15 (1983), 103–168. [14] Rainone, T. «Noncommutative topological dynamics». Proc. Lond. Math. Soc. (3), 112 (5) (2016), 903–923. [15] Rainone, T. «Finiteness and paradoxical decompositions in C∗ -dynamical systems». J. Noncommut. Geom., 11 (2) (2017), 791–822. [16] Rørdam, M.; Sierakowski, A. «Purely infinite C ∗ -algebras arising from crossed products». Ergodic Theory Dynam. Systems, 32 (1) (2012), 273–293. [17] Rosenberg, J. Algebraic K-Theory and its Applications. Nova York: Springer-Verlag, 1994. (Graduate Texts in Mathematics; 147) [18] Tarski, A. «Problème 38». Fund. Math., 7 (1925), 381.

Pere Ara

[19] Tarski, A. «Algebraische Fassung des Maßproblems». Fund. Math., 31 (1938), 207–223. [20] Tomkowicz, G.; Wagon, S. The Banach-Tarski Paradox. 2a ed. Nova York: Cambridge University Press, 2016. (Encyclopedia of Mathematics and its Applications; 163) [Amb un pròleg de Jan Mycielski]

Departament de Matemàtiques Universitat Autònoma de Barcelona 08193 Bellaterra para@mat.uab.cat

Butlletí de la Societat Catalana de Matemàtiques Vol. 35, núm. 1, 2020. Pàg. 23–56. DOI: 10.2436/20.2002.01.92

La compacitat, una noció seminal en l’evolució de la topologia general (1895–1930) Júlia Moreno, Mònica Blanco i Pere Pascual

Resum: En aquest article es revisa l’evolució de la definició d’espai topològic compacte des de la primera definició de Fréchet el 1904, que va generalitzar la propietat de Bolzano-Weierstrass, passant per la relació amb el teorema de Borel del 1895 per a recobriments numerables de l’interval [0, 1], fins a arribar a la definició general a partir de la propietat de Heine-Borel dels recobriments oberts arbitraris l’any 1929. Centrem l’anàlisi en quatre publicacions clau: les tesis de Borel i de Fréchet, el llibre de Hausdorff en el qual s’estableixen les bases de la topologia general, i la memòria d’Alexandroff i Urysohn.

Paraules clau: història de la topologia, espai compacte, propietat de Heine-Borel, Fréchet, Hausdorff.

Classificació MSC2010: 01-02, 54-03.

Introducció

Els espais compactes són els espais més importants de la topologia general. La definició de la compacitat mitjançant recobriments oberts pot semblar poc natural i és lícit preguntar-se quin n’és l’origen. En els seus inicis, la topologia general es proposava estendre alguns dels resultats de la topologia de R a situacions més generals, com ara als espais de funcions, i entre aquests destacava el teorema de Weierstrass, que assegura l’existència d’extrems per a funcions contínues definides en un interval [a, b]. Aquest va ser el punt de partida en la definició d’espai compacte, però quina és la propietat d’un interval [a, b] que dona lloc al teorema de Weierstrass? Quin és el context en el qual la podem expressar? En aquest article analitzem el sorgiment de la noció d’espai compacte i descrivim, succintament, l’aparició de la topologia general com a nova disciplina de les matemàtiques. Ens centrem en treballs posteriors al 1895, que és quan apareix per primer cop la propietat de Heine-Borel dels recobriments oberts de [a, b], propietat que a la fi serà la que definirà els espais compactes. En anys anteriors s’havia aprofundit en la comprensió del continu real i, amb Georg Cantor (1845–1918), havia començat l’anàlisi de la topologia dels conjunts de

Júlia Moreno, Mònica Blanco i Pere Pascual

punts del continu, orientats majoritàriament a problemes derivats de l’anàlisi (vegeu [28, 34, 35]). A finals del segle xix, les idees en geometria de Bernhard Riemann (1826–1866) i els treballs sobre conjunts de funcions dels matemàtics italians mostraven la conveniència de disposar d’espais abstractes en els quals tingués sentit analitzar la continuïtat de funcions, la qual cosa abocaria a la definició dels espais mètrics per part de Maurice Fréchet (1878–1973) i dels espais topològics per part de Felix Hausdorff (1868–1942). Com veurem a la subsecció 3.1, l’extensió del teorema de Weierstrass als espais mètrics donarà lloc a la primera definició d’espai compacte. Tant per a Fréchet com per a Hausdorff, la compacitat comportava analitzar configuracions numerables. Acabarem l’anàlisi el 1930, quan els treballs de l’escola russa deslliuren la compacitat de la numerabilitat i determinen l’estabilitat de la (bi)compacitat per productes. Més enllà d’aquesta data, van sorgir dues caracteritzacions més de la compacitat: la caracterització mitjançant xarxes (o successions generalitzades) de Moore-Smith i la dels filtres de Cartan, en els quals no entrarem (vegeu-ne un panorama general a [37]). Ens hem centrat en quatre moments que, creiem, són els més significatius: la introducció de la propietat dels recobriments oberts per part d’Émile Borel (1871–1956), la definició d’espai mètric i d’espai compacte per part de Fréchet, la definició d’espai topològic de Hausdorff i l’anàlisi que fan de la compacitat, i la definició dels espais bicompactes de Pàvel S. Alexandroff (1896–1982) i Pàvel S. Urysohn (1898–1924), així com del teorema d’Andrei N. Tychonoff (1906–1993). Aquests treballs van ser els més influents en el desenvolupament de la topologia i, d’una manera més concreta, en la noció d’espai compacte; tot i que, lògicament, això representa una simplificació de la complexitat del sorgiment de la nova disciplina, la topologia general, amb contribucions de molts altres matemàtics del moment. Aquest article deriva del treball de final de grau de la primera autora [31]. El format d’article, necessàriament més reduït, aconsella no analitzar totes les demostracions dels resultats que anirem presentant; tanmateix, n’hem seleccionat algunes que permeten copsar com es van desenvolupar les idees analitzades. Hem procurat mantenir-nos fidels a les demostracions originals, tot i que hem adaptat les notacions per tal de facilitar-ne la lectura.

La tesi de Borel

Émile Borel va presentar la tesi doctoral «Sur quelques points de la théorie des fonctions» el 14 de juny del 1894 a la Facultat de Ciències de París i la va publicar l’any següent als Annales Scientifiques de l’École Normale Supérieure [6]. El seu director de tesi va ser Gaston Darboux (1842–1917), i els examinadors, Paul Appell (1855–1930) i Henri Poincaré (1854–1912). La tesi de Borel està dedicada a la teoria de funcions de variable complexa. En una nota al final del treball, s’enuncia i es demostra per primera vegada la propietat d’existència de subrecobriments finits per a recobriments numerables per intervals oberts d’un interval [a, b]. Comencem contextualitzant on necessita Borel la propietat dels recobriments oberts.

Evolució de la noció de compacitat

2.1

El context de la tesi de Borel

En la introducció de [6] Borel demana: Étant données deux fonctions d’une variable complexe, définies, l’une lorsque la variable est dans un certain domaine, l’autre lorsque elle est dans un domaine différent, dans quels cas peut-on dire que c’est la même fonction? [Donades dues funcions d’una variable complexa, l’una definida quan la variable és en un determinat domini, l’altra quan és en un domini diferent, quan es pot dir que és la mateixa funció?]

Hawkins ([23]) assenyala que l’any 1851 Bernhard Riemann havia plantejat la qüestió de si la classe de les funcions analítiques és la mateixa que la classe de funcions de variable complexa definides per les operacions algebraiques bàsiques, aplicades un nombre finit o infinit de vegades; i que Karl Weierstrass (1815–1897) va analitzar la sèrie f (z) =

1 , zn + z−n

que representa dues funcions analítiques diferents, l’una per a |z| < 1 i l’altra per a |z| > 1: la sèrie no és fitada a l’entorn de cap punt de la circumferència |z| = 1, per la qual cosa no és possible fer una continuació analítica a través de la circumferència unitat. Diversos autors van presentar altres exemples de sèries complexes amb un comportament similar al descrit per Weierstrass. Possiblement, el més influent per a Borel va ser el publicat per Poincaré l’any 1883 amb el títol «Sur les fonctions à espaces lacunaires» [36], en el qual estudia les funcions de la forma f (z) =

An , z − an n>0 X

P tals que la sèrie An és absolutament convergent i els punts an formen un conjunt dens d’una corba de Jordan C, sobre la qual li cal imposar determinades restriccions (per fixar idees suposarem que C és la circumferència unitat). La sèrie defineix una funció a l’interior del disc unitat i una altra a l’exterior i, per la densitat del conjunt dels an , aquestes dues funcions no es poden connectar per continuació analítica. Borel reprèn l’estudi d’aquestes sèries i proposa un punt de vista nou ([6, p. 10]): j’ai montré qu’il est possible, dans certains cas, de donner du prolongement analytique au delà d’une ligne singulière essentielle fermée une définition qui ne soit contradictoire, ni avec elle même, ni avec les notions antérieures. [he provat que és possible, en alguns casos, donar una definició de continuació analítica més enllà d’una corba singular tancada essencial que no entra en contradicció, ni amb ella mateixa, ni amb les nocions anteriors.]

Júlia Moreno, Mònica Blanco i Pere Pascual

Més Borel demostra que, imposant la condició que la sèP concretament, |An |1/2 sigui convergent, existeixen camins γ que uneixen un punt P rie interior del disc amb un punt Q exterior tals que la sèrie que defineix f (z) és absolutament i uniformement convergent al llarg de γ. En conseqüència, defineix una funció contínua en aquest camí que travessa la circumferència de tall entre els dominis de les dues funcions analítiques. Indiquem breument les idees de la prova de Borel que conduiran al resultat de la propietat per als recobriments de l’interval [0, 1]. Donats els punts P , Q, Borel considera la mediatriu de P Q i un segment AB sobre aquesta. Per a cada punt O del segment AB, traça l’arc de la circumferència de centre O que passa per P i per Q, arc que denota per CO . El camí γ buscat serà un d’aquests arcs. Sigui On el punt O tal que l’arc de la circumferència corresponent passa per an . S’obté un subconjunt numerable {On } del segment AB i, com que un interval és no numerable, hi ha una infinitat de punts O que no pertanyen a {On }; o sigui, hi ha una infinitat d’arcs que no passen per cap dels punts an . No tots aquests arcs són vàlids per a establir el resultat que es persegueix; s’ha de veure que entre tots ells se’n pot escollir un en el qual la sèrie definida per f (z) sigui absolutament i uniformement convergent. Per a l’elecció γ, Borel argumenta de la manera següent: de la P del camí 1/2 convergència de |A | dedueix l’existència d’una sèrie convergent de termes n P P positius un tal que |An |/un és convergent. Per la convergència de la sèrie de terme un , hi ha un nombre N tal que ∞ X

un <

n=N

1 d(A, B). 2

Per a n ≥ N, considerem els subintervals In de AB de centre On i longitud 2un , de manera que se satisfà ∞ X m=N

long(In ) = 2

∞ X

un < d(A, B).

(1)

n=N

D’aquesta desigualtat S dedueix que hi ha una infinitat no numerable de punts en el conjunt AB \ ( n In ). Si O és un d’aquests punts, Borel demostra que l’arc CO és el camí γ amb les propietats desitjades. Per inferir l’existència del punt O a partir de la desigualtat anterior, Borel remet, per a una demostració rigorosa, a la nota al final de l’article. En aquesta nota, hi enuncia i demostra el teorema que ens ocupa. El punt clau rau, doncs, en el pas de la desigualtat (1) a l’existència dels punts O que no pertanyen a cap interval In . Borel l’expressa de la manera següent ([6, p. 25–26]): La somme de tous les segments (en nombre infini), tels que Ai Bi tous situés sur le segment AB ou sur son prolongement, est inférieure à la longeur ` de AB; donc il existe sur AB une infinité non dénombrable de points n’appartenant à aucun de ces segments (1 ). [La suma de tots els segments (en nombre infinit) tals que Ai Bi estan situats sobre el segment AB o sobre el seu perllongament és inferior a la longitud `

Evolució de la noció de compacitat

de AB; per tant, existeix una infinitat no numerable de punts de AB que no pertany a cap d’aquests segments (1 ).]

A més, afegeix una nota a peu de pàgina que remet a l’apèndix del treball per a una demostració rigorosa, que analitzem a continuació. 2.2

L’apèndix: la primera demostració del teorema

Borel comença la nota final de la tesi precisant el resultat que ha utilitzat per a l’elecció dels punts O aptes per a trobar els camins γ del seu teorema de continuació ([6, p. 50–51]): Nous nous sommes appuyés (p. 26) sur ce lemme que, si l’on a une infinité d’intervalles partiels donnés sur une droite, dont la somme est inférieure à un intervalle total également donné, il existe au moins un point de l’intervalle total n’appartenant à aucune des intervalles partiels. [Ens hem basat (p. 26) en el lema segons el qual, si hi ha una infinitat d’intervals parcials sobre una recta tals que la suma és inferior a un interval total igualment donat, existeix almenys un punt de l’interval total que no pertany a cap dels intervals parcials.]

Conscient de la importància d’aquesta propietat de l’interval, uns paràgrafs més avall assenyala ([6, p. 51]): On peut considérer ce lemme à peu près évident; néamoins, à cause de son importance je vais en donner une démonstration reposant sur un théorème intéressant par lui même; il en existe d’autres démonstrations plus simples. Voici ce théorème: Si l’on a sur une droite une infinité d’intervalles partiels, tels que tout point de la droite soit intérieur à l’un au moins des intervalles, on peut déterminer effectivement un nombre limité d’intervalles choisis parmi les intervalles donnés et ayant la même propieté (tout point de la droite est intérieur à au moins l’un d’eux). [Podem considerar aquest lema com més o menys evident; tot i això, a causa de la seva importància, oferiré una demostració basada en un teorema interessant per si mateix; n’hi ha de més senzilles. Aquest és el teorema: Si tenim en una recta una infinitat d’intervals parcials tals que tot punt de la recta és interior a almenys un dels intervals, es pot determinar efectivament un nombre limitat d’intervals triats entre els donats que compleixen la mateixa propietat (que tot punt de la recta és interior a almenys un d’ells).]

Assenyalem que Borel entén per recta un interval tancat [A, B] i per interval parcial, un interval que no cobreix el segment predeterminat. A més, quan es refereix a l’infinit és l’infinit numerable, mentre que per nombre limitat entén un nombre finit. La demostració que proposa Borel ([6, p. 51–52]) és per inducció transfinita i, en un cert pas, es basa en el teorema de Cantor, segons el qual el conjunt dels ordinals numerables és no numerable. Posteriorment, l’any 1898, el mateix Borel proposaria una demostració més elemental basada en el mètode de bipartició de l’interval [7, p. 42].

Júlia Moreno, Mònica Blanco i Pere Pascual

Prova del teorema de Borel. Sigui [A, B] el segment predeterminat, i [Ai ,Bi ], i ∈ N, els intervals del recobriment. Sigui [Ai1 , Bi1 ] un interval del recobriment que conté A. Seguidament, escollim un interval [Ai2 , Bi2 ] que conté Bi1 , i iterem el procés; obtenim una successió d’intervals [Ai1 , Bi1 ], [Ai2 , Bi2 ], . . . La successió de punts B1 , Bi1 , Bi2 , . . . , que és creixent i fitada, tindrà un límit Biω , on ω designa el primer ordinal infinit de Cantor; si aquest límit assoleix l’altre extrem, B, aleshores el segment [A, B] està inclòs en un nombre finit d’intervals: en efecte, si B és a l’interior de [Aiω , Biω ], l’extrem Aiω , que és del segment [A, B], estarà inclòs en un interval [Aij , Bij ], per a cert j (aquí és fonamental tenir present que els interiors dels intervals [Ai , Bi ] cobreixen [A, B]), i aleshores els intervals numerats i1 , . . . , ij , iω són suficients per a cobrir [A, B]. En cas contrari, Bω < B i, atès que el segment [A, Bω ] pot cobrir-se per un nombre finit d’intervals, podem recomençar la demostració partint del segment [Bω , B] i obtenir una successió de punts Biω+1 , Biω+2 , . . . que convergeix cap a un cert punt Bi2ω , de manera que amb un nombre finit d’intervals es cobreix [Biω , Bi2ω ]. Iterem el procediment tantes vegades com faci falta. Si no atenyéssim B en un nombre finit d’iteracions, en resultaria una successió d’intervals d’extrems superiors Bi1 , Bi2 , . . . , Biω , Bi2ω , . . . , Biω2 , . . . Biωω , . . . en la qual apareixen entre els índexs tots els nombres de segona classe definits per Cantor, de manera que el resultat seria una bijecció entre els intervals del recobriment inicial (o una part d’ells) i aquests nombres, cosa que entra en contradicció amb el teorema de Cantor assenyalat anteriorment. 2 Aquesta demostració ha estat analitzada per diversos autors [29, 4, 20]. L’article de Hildebrandt, [25], recull les diferents proves que es van donar del teorema fins a l’any 1925. 2.3

Impacte del resultat de Borel

La propietat de subrecobriments finits havia estat utilitzada de manera implícita per altres autors en diferents contextos, com ara en un lema demostrat per Pierre Cousin (1867–1933) en la seva tesi que fa referència a un recobriment d’un domini compacte del pla mitjançant discs oberts [29]. El mèrit de Borel seria haver identificat la propietat de subrecobriment finit dels intervals, com assenyalaria més endavant Henri Lebesgue. El resultat de Borel es produeix en un moment d’intensa activitat al voltant de les emergents teories de conjunts, de la mesura i de la topologia del continu, amb les quals tenia contacte, fet pel qual va suscitar gran interès. El treball de Cousin que hem esmentat, per posar-ne un exemple, mostrava la necessitat d’estendre el resultat a espais de dimensió superior alhora que invitava a generalitzar-lo a conjunts que no fossin necessàriament intervals, a recobriments donats per conjunts generals i als recobriments no numerables. En aquestes extensions hi van contribuir diversos matemàtics d’arreu, que hi

Evolució de la noció de compacitat

van aportar noves demostracions segons la generalització buscada, com el mateix Borel per a la dimensió superior, Henri Lebesgue (1875–1941) i Arthur Schönflies (1853–1928) per a recobriments no necessàriament numerables, Oswald Veblen (1880–1960), qui va assenyalar que la propietat dels subrecobriments finits per a un conjunt de l’espai és equivalent al fet que sigui tancat i fitat i qui va assenyalar, també, la relació del teorema amb la propietat de Bolzano-Weierstrass, o com W. H. Young (1863–1942), que va proposar altres demostracions [46]. Destacarem les contribucions de Schönflies i de Lebesgue. L’any 1899, Schönflies va escriure l’informe Jahresbericht der deutschen MathematikerVereinigung sobre la teoria de conjunts de punts per encàrrec de l’Associació Alemanya de Matemàtics, que es publicaria l’any següent, el 1900. En aquest informe Schönflies associa per primera vegada el teorema de la continuïtat uniforme d’una funció contínua sobre un interval [a, b], demostrat per Eduard Heine (1821–1881) en el seu llibre Die Elemente der Funktionenlehre (Els elements de la teoria de funcions), publicat el 1872, i la propietat de subrecobriments finits de Borel, propietat que estén prèviament a recobriments no necessàriament numerables: [. . .] Um ein letztes Beispiel zu geben, beweise ich folgenden Satz Borel’s, der einen bekannten Satz von Heine erweitert: V. Giebt es auf einer Geraden eine unendliche Reihe von Intervallen δ, so dass jeder Punkt des Intervalls a . . . b innerer Punkt mindestens eines Intervalles δ ist, so giebt es auch stets eine endliche Teilmenge solcher Intervalle. [[. . .] Com a darrer exemple, demostraré el següent teorema de Borel, que estén un conegut teorema de Heine: V. Si en una línia recta hi ha una successió infinita d’intervals δ tal que cada punt de l’interval a . . . b és un punt interior a almenys un interval δ, llavors també hi ha un subconjunt finit d’aquests intervals.]

La demostració del teorema de Borel que Schönflies va publicar el 1900 es basa en un raonament de recurrència transfinita similar a l’usat per Borel a la seva tesi estès al cas no numerable. El teorema de la convergència uniforme hauria estat demostrat per P. Lejeune Dirichlet (1805–1859) abans de l’aparició del treball de Heine. A [14] i [29] s’analitzen les proves de Dirichlet i Heine d’aquest resultat, en les quals es raona a partir de la continuïtat local per a obtenir la continuïtat uniforme sobre un interval [a, b]; d’aquí ve la citació de Schönflies i l’associació dels noms Heine-Borel per a referir-se a la propietat d’existència de subrecobriments finits, tot i que en els treballs de Dirichlet i Heine no apareixen d’una manera explícita els recobriments. Henri Lebesgue va estudiar matemàtiques a l’École Normale Supérieure de París entre 1894 i 1897, on va entrar en contacte amb el treball de Borel mentre feia la tesi. Lebesgue va publicar la seva prova de l’extensió a recobriments generals al seu llibre, del 1904, Leçons sur l’intégration et la recherche des fonctions primitives [27], i el va enunciar de la manera següent:

Júlia Moreno, Mònica Blanco i Pere Pascual

Si l’on a une famille d’intervalles I tels que tout point d’un intervalle (a, b) y compris a et b, soit intérieur à l’un au moins des I, il existe une famille formée d’un nombre fini des intervalles I et qui jouit de la même propieté (tout point (a, b) est intérieur à l’un d’eux). [Si tenim una família d’intervals I tals que qualsevol punt de l’interval (a, b), incloent-hi a i b, és interior a almenys un dels de I, llavors existeix una família formada per un nombre finit dels intervals de I que tenen la mateixa propietat (tot punt de (a, b) és interior a un d’ells).]

La demostració de Lebesgue es basa en la propietat del suprem dels conjunts fitats. Aquesta és la prova adoptada posteriorment en molts textos docents, com per exemple a [32]. Arran de la generalització de Lebesgue, es va popularitzar el nom de teorema de Borel-Lebesgue entre els matemàtics francesos, mentre que, mitjançant els treballs de Schönflies i Young, es va adoptar el nom de teorema de HeineBorel entre la comunitat anglosaxona per a referir-se al mateix resultat. Tot plegat va produir certa polèmica, no només pel nom, sinó també sobre l’autoria del teorema generalitzat. Pierre Dugac ([14]) ha analitzat aquesta polèmica a través, sobretot, de l’anàlisi de l’arxiu de Borel i, en especial, de les cartes de Lebesgue a Borel (Lebesgue no va conservar les cartes de Borel, per la qual cosa la informació és parcial). En una d’aquestes cartes, d’agost del 1904, Lebesgue assenyala com va arribar a l’extensió del teorema de Borel ([14, p. 102]): Pour ma part je n’ai compris qu’il y avait là matière à énoncer qu’après avoir vu, dans la suite, votre thèse. Alors naturellement j’ai remplacé votre démonstration par la mienne, sans m’apercevoir qu’il y avait changement de l’énoncé. Par la suite je n’ai plus jamais repensé à votre énoncé et à votre démonstration de sorte que, quand j’ai appliqué le théorème, je n’ai pas été arrêté par les difficultés qui proviendraient du dénombrable. C’est Montel [. . .] qui m’a indiqué la différence entre les énoncés, laquelle m’avait tout à fait échappé bien qu’elle soit fondamentale en un certain sens. [Per la meva part, no vaig entendre que hi hagués res a enunciar fins que, més endavant, vaig llegir la vostra tesi. De forma natural vaig reemplaçar la vostra demostració per la meva, sense adonar-me que hi havia un canvi d’enunciat. En endavant no vaig tornar a pensar més ni en la vostra demostració ni en el vostre resultat, de manera que, quan vaig aplicar el teorema, no vaig trobar que les dificultats que poguessin provenir de la numerabilitat fossin un impediment. Va ser Montel [. . .] qui em va assenyalar la diferència entre els enunciats, la qual m’havia passat desapercebuda tot i ser fonamental en cert sentit.]

En una altra carta, de gener del 1907 ([14, p. 104]), assenyala respecte a les reivindicacions de Schönflies ([38]) que és just atorgar-li un paper rellevant en l’extensió no numerable: La réclamation de Schönflies est bien fondée. D’après vos démonstrations, il n’était prouvé que pour le dénombrable, explicitement du moins, et les seules applications que vous en avez faites sont relatives au fond à ceci: démontrer que certains points existent. C’est a Schönflies que revient le mérite d’avoir

Evolució de la noció de compacitat

montré tout le parti que l’on pouvait tirer dans la théorie des fonctions de vôtre théorème, étendu au non dénombrable, en mettant, à l’ocassion de la démonstration de Heine, ce fait en évidance qu’il permet d’étendre à un intervalle (et aussi bien évidemment à un ensemble fermé) des proprietés vrais autour des points de cet intervalle. [La reclamació de Schönflies està ben fonamentada. Segons les vostres demostracions, només estava provat el cas numerable, si més no explícitament, i les úniques aplicacions que n’havíeu fet es redueixen a aquest cas: demostrar l’existència de certs punts. És a Schönflies que hem de donar el mèrit d’haver mostrat l’avantatge que es pot treure en la teoria de funcions del vostre teorema, estès al cas no numerable, posant en evidència, amb motiu de la demostració de Heine, el fet que permet estendre a un interval (i també evidentment a un conjunt tancat) propietats vàlides entorn dels punts d’aquest interval.]

Segons cita Dugac, Lebesgue considerava que no es podia atribuir cap tipus de mèrit a Heine respecte del teorema de Borel, ja que Heine no tenia la noció de recobriment i no treballava ni amb conjunts ni amb col.leccions infinites de punts. El mèrit principal de Borel seria haver enunciat el teorema aïllant la noció de recobriment i la importància d’extreure’n un subrecobriment finit, i haver aplicat després aquest fet per a desenvolupar una teoria de la mesura. Més enllà del nom que li atorguem, el que cal destacar és el paper fonamental que va anar adquirint el teorema tant en les seves aplicacions com en el desenvolupament de la noció de compacitat en situacions abstractes.

Els espais abstractes de Fréchet

Pel tombant del segle xx, la definició de funció y de variable x quan a tot valor numèric de x li correspon un valor determinat de y estava ben establerta, així com l’anàlisi de les propietats de continuïtat i derivabilitat d’aquestes funcions. Els treballs pioners dels anys 1880 de Vito Volterra (1860–1940), Giulio Ascoli (1843–1896) i Cesare Arzelà (1847–1912) analitzaven funcions que depenien d’una corba variable, la gràfica d’una funció, i suggerien l’estudi més sistemàtic de les propietats d’aquestes funcions de funcions, com va assenyalar J. Hadamard (1865–1963) en la intervenció al Primer Congrés Internacional de Matemàtics del 1897 [19]: Il ne me semble pas inutile de signaler l’intérêt qu’il y aurait à étudier des ensembles composés de fonctions. [No em sembla pas inútil assenyalar l’interès que hi hauria a estudiar els conjunts compostos de funcions.]

Hadamard remarca la importància que tindria aquest estudi en la teoria d’equacions en derivades parcials, ja que permetria donar arguments sòlids als raonaments coneguts a l’època segons els quals la definició d’integral d’aquestes equacions es reduïa a qüestions de mínims. Aquestes qüestions estan relacionades amb la natura del domini, així com de la funció que s’analitza.

Júlia Moreno, Mònica Blanco i Pere Pascual

Maurice Fréchet es va proposar establir una teoria abstracta que permetés l’anàlisi de la continuïtat en situacions generals i que contingués els casos estudiats pels autors italians. Hadamard havia estat mentor de Fréchet des que aquest era jove i va dirigir la seva tesi, per la qual cosa és raonable pensar que l’origen dels treballs de Fréchet deriva de la influència del seu mentor, alhora que el focus inicial del seu treball és la caracterització d’espais generals sobre els quals les funcions contínues atenyen un valor màxim. El treball més rellevant de Fréchet és la seva tesi doctoral, «Sur quelques points du calcul fonctionnel» («Sobre alguns aspectes del càlcul funcional»), publicada l’any 1906 [16]. Abans, però, publica algunes notes que contenen la gènesi de les idees que desenvoluparà a la seva tesi. En particular, ens referim a l’article titulat «Généralisation d’un théorème de Weierstrass» («Generalització d’un teorema de Weierstrass»), publicada el 1904 a Comptes Rendus [15], on apareix per primera vegada la noció de compacte. 3.1

Generalització del teorema de Weierstrass

Al primer paràgraf de [15], Fréchet escriu: On sait l’importance qu’il y aurait, dans un grand nombre de problèmes, à savoir si une quantité U dépendant de certains éléments (points, fonctions, etc.) atteint effectivement un minimum dans le champ consideré. Le principe de Dirichlet offre des justifications les plus frappantes de cette remarque. [Sabem la importància que tindria, en un gran nombre de problemes, saber si una quantitat U que depèn de certs elements (punts, funcions, etc.) assoleix efectivament un mínim en el camp considerat. El principi de Dirichlet ofereix les justificacions més impressionants d’aquesta observació.]

Fréchet es planteja donar una versió general del teorema de Weierstrass, segons el qual les funcions contínues en un interval [a, b] tenen màxim i mínim sobre aquest interval, de manera que sigui aplicable a conjunts de punts «de naturalesa qualsevol» (nombres, superfícies, etc.). El concepte sobre el qual basarà la continuïtat d’una funció serà el de límit d’una successió. En lloc d’analitzar conjunts amb una definició de límit ben determinada, com seria el cas de la convergència puntual o de la convergència uniforme en espais de funcions, Fréchet proposa una teoria abstracta buscant les condicions comunes de les definicions particulars de límit, en la línia del que havien fet recentment De Séguier per a la definició de grup abstracte o Borel en la definició d’una teoria de la mesura general [16]. La nota, de només dues pàgines, no conté demostracions, que apareixerien poc després a la seva tesi. Fréchet introdueix la classe (L) de conjunts en els quals imposa que es pugui determinar quan dos elements són diferents i on hi ha una noció, no especificada, de límit: donada una successió A1 , A2 , . . . és possible determinar si existeix o no un límit B, que satisfaci les dues condicions següents:

Evolució de la noció de compacitat

(1) Si la successió A1 , A2 , . . . , An , . . . té un límit A, tota subsuccessió Ap1 , Ap2 , . . . , Apn , . . . té el mateix límit A. (2) Si la successió A1 , A2 , . . . , An , . . . és constant de valor A, aleshores té com a límit A. Seguint Cantor, Fréchet defineix el conjunt derivat d’un subconjunt E d’una classe (L) com el conjunt dels seus punts límit, i defineix conjunt tancat com aquell que conté el seu derivat. És clar, llavors, com cal definir la continuïtat d’una funció (operació funcional, en la terminologia de Fréchet) sobre un conjunt tancat. Fréchet defineix conjunt compacte extrapolant la propietat dels conjunts fitats de la recta real que li permetrà enunciar l’extensió del teorema de Weierstrass: Enfin nous appellerons ensemble compact tout ensemble E tel qu’il existe toujours au moins un élément commun à une suite infinie quelconque d’ensembles E1 , E2 , . . . , En , . . . contenus dans E, lorsque ceux ci (possédant au moins un élément chacun) sont fermés et chacun contenu dans le précédent. [Finalment, anomenarem conjunt compacte tot conjunt E tal que existeix sempre un element en comú en qualsevol successió infinita de conjunts E1 , E2 , . . . , En , . . . continguts en E tals que (tenint almenys un element cadascun) són tancats i cadascun d’ells està contingut en l’anterior.]

Observem que els conjunts compactes així definits no són necessàriament tancats; els punts de la intersecció no cal que pertanyin a E. Fréchet entenia aquesta definició com una generalització dels conjunts fitats de la recta real. Finalment, enuncia la generalització del teorema de Weierstrass ([15, p. 849]): Théorème. Toute opération fonctionelle UA uniforme et continue dans un ensemble compact et fermé E: 1. Est bornée dans E; 2. Atteint au moins une fois sa limite supérieure. [Teorema. Qualsevol operació funcional UA uniforme i contínua en un conjunt compacte i tancat E: 1. Està fitada en E; 2. Assoleix almenys una vegada el seu límit superior.]

De fet, Fréchet anomena extremal tot conjunt compacte i tancat. La nota també inclou la caracterització de la compacitat per la propietat que avui en diem de Bolzano-Weierstrass: La condition nécessaire et suffisante pour qu’un ensemble E soit compact est que tout ensemble E1 formé d’une infinité d’éléments distincts contenus dans E donne lieu à un élément-limite au moins. [La condició necessària i suficient perquè un conjunt E sigui compacte és que tot conjunt E1 format per una infinitat d’elements diferents continguts en E doni lloc a almenys un element límit.]

que, en la tesi, que comentarem tot seguit, va adoptar com a definició de conjunt compacte.

Júlia Moreno, Mònica Blanco i Pere Pascual

3.2

La tesi de Fréchet

La tesi de Fréchet ([16]) és el seu treball més rellevant en el context de la naixent topologia d’espais generals. Consta de dues parts: la primera està dedicada a la teoria general, en la qual amplia l’estudi de les classes (L) amb noves classes (V ) i (E) i demostra l’extensió del teorema de Weierstrass per a aplicacions contínues en compactes tancats entre d’altres resultats; i la segona està dedicada a l’aplicació de la teoria desenvolupada a diversos exemples, com ara la compacitat en espais de funcions contínues o a l’espai de dimensió infinita numerable, introduït aquí per primer cop. En aquesta anàlisi de la tesi de Fréchet, ens centrarem en la relació que estableix entre la compacitat i la propietat de recobriments de Borel. Després de presentar la categoria (L) i analitzar algunes de les seves propietats, Fréchet observa, al capítol ii, que el conjunt derivat d’un conjunt no és necessàriament tancat, propietat que apareix en molts dels exemples que havia analitzat. Fréchet dona un exemple de successió de funcions reals fn (x) convergent a una funció f (x) i que al seu torn són límit de succes(p) sions limp fn (x) = fn (x), de manera que no existeixen subsuccessions pi , ni (p )

amb limi fni i (x) = f (x) per a tot x. Taylor ([39, p. 247]) esmenta una carta de Hadamard a Fréchet en la qual comenta aquest exemple: (p)

On pourra prendre fn aussi voisin qu’on voudra de f , puis fn aussi voissin qu’on voudra de fn , etc. Le raisonnement s’étendra, quell que soit la significa(p) tion des fn , du moment que la notion de voisinage peut être définie, puisque cette notion est la seule sur laquelle il repose. (p)

[Es pot prendre fn tan a prop com es vulgui de f , després fn tan a prop com es vulgui de fn , etc. El raonament s’estendrà, independentment del significat de (p) les fn , sempre que la noció d’entorn pugui definir-se, perquè aquesta noció és l’única sobre la qual reposa.]

Al capítol ii [16, p. 18], Fréchet proposa una caracterització d’entorn que li permetrà seguir el raonament de Hadamard i aconseguir que els conjunts derivats siguin tancats introduint la classe (V ), de voisinage en francès: Considérons une classe (V ) d’éléments de nature quelconque [. . .] et tels que, de plus, qu’à deux quelconques d’entre eux A, B, on puisse faire correspondre un nombre (A, B) = (B, A) ≥ 0 qui jouit des deux propriétés suivantes: 1. La condition nécessaire et suffisante pour que (A, B) soit nul est que A et B soient identiques. 2. Il existe une fonction positive bien déterminée f (ε) tendant vers zéro avec ε, telle que les inégalités (A, B) ≤ ε, (B, C) ≤ ε entraînent (A, C) ≤ f (ε), quels que soient les éléments A, B, C. [Considerem una classe (V ) d’elements de naturalesa arbitrària [. . .] i tals que, a més, a qualsevol parell A, B, se li pugui assignar un nombre (A, B) = (B, A) ≥ 0 que satisfà les propietats següents: 1. La condició necessària i suficient perquè (A, B) sigui nul és que A i B siguin idèntics. 2. Existeix una funció positiva ben determinada f (ε) que tendeix a zero amb ε tal que les desigualtats (A, B) ≤ ε, (B, C) ≤ ε impliquen que (A, C) ≤ f (ε), per a qualssevol A, B, C.]

Evolució de la noció de compacitat

Donada una successió A1 , A2 , . . . en una classe (V ), defineix el límit com aquell element A de la classe tal que (An , A) tendeix a zero com 1/n. És clar que tota classe (V ) és una classe (L), amb l’avantatge ara que els límits són únics i que el conjunt derivat d’un conjunt és un tancat. Fréchet estén el teorema de Borel als espais de classe (V ) ([16, p. 22]): 36. Théorème. Soit E un ensemble extrémal formé d’éléments d’une classe (V ). S’il existe une suite indéfinie G d’ensembles I1 , I2 , . . . telle que tout élément de E soit intérieur au sens étroit à l’un au moins de ces ensembles In , on peut extraire de G un nombre fini des ces ensembles formant une famille H jouissant de la même propriété que G. [36. Teorema. Sigui E un conjunt extremal format per elements d’una classe (V ). Si existeix una successió infinita G de conjunts I1 , I2 , . . . tal que tot element de E és interior a almenys un d’aquests conjunts In , es pot extreure de G un nombre finit d’aquests conjunts que formen una família H que satisfà la mateixa propietat que G.]

Prova. Si suposem que el resultat no és cert, aleshores existeix A1 ∈ E que no és interior a I1 . Sigui Iq1 el primer conjunt de la successió G que conté A1 (q1 > 1). Existeix A2 ∈ E tal que A2 6∈ I1 ∪ · · · ∪ Iq1 ; sigui Iq2 el primer conjunt de G amb A2 ∈ Iq2 . Es forma així una successió d’elements de E, diferents entre ells, A1 , A2 , . . . , Ar 6∈ Int(I1 ∪ · · · ∪ Iqr ). Com que E és extremal, aquesta successió té un element límit, A = lim Anp ∈ E, que serà interior a un dels conjunts de G, Ik . Se segueix la impossibilitat que existeixi una successió parcial de punts de An1 , An2 , . . . que no siguin a l’interior de Ik : si existís una parcial A0n1 , A0n2 , . . . amb els A0np ∉ Int(Ik ), aleshores podríem definir una successió B1 , B2 , . . . amb  A 0 si Anp 6∈ Ik , np Bp = Bfp altrament, on Bfp és un punt qualsevol de E \ Ik tal que (Bfp , Anp ) < p1 ; en canvi, A seria un punt límit, la qual cosa és impossible. En definitiva, els elements de la successió An1 , An2 , . . . són tots interiors a Ik a partir d’un cert rang, fet que es contradiu amb l’elecció de la successió A1 , A2 , . . . 2 En una nota a peu de la pàgina 22, Fréchet remarca que més endavant estendrà el resultat per a recobriments no necessàriament numerables. Per fer-ho, Fréchet introdueix dues propietats que haurà d’imposar als espais que considera: que satisfacin les condicions de Cauchy (és a dir, que siguin complets, en la terminologia que després introduiria Hausdorff) i que siguin separables (és a dir, que continguin un conjunt numerable dens). A una classe (V ) que satisfà aquestes dues propietats l’anomena normal. Finalment, Fréchet enuncia i demostra l’equivalència entra la noció de conjunt extremal i la propietat de Heine-Borel general:

Júlia Moreno, Mònica Blanco i Pere Pascual

Théorème. Soit E un ensemble d’éléments d’une classe normale (V ). Pour que de toute famille H dénombrable ou non d’ensembles I tels que tout élément de E soit intérieur au sens étroit à au moins l’un d’eux, on puisse extraire un nombre fini d’ensembles I . formant une famille G jouissant de la même propriété que H, il faut et il suffit que E soit extrémal. [Teorema. Sigui E un conjunt d’elements d’una classe normal (V ). Per tal que de tota família H numerable o no de conjunts I tals que tot element de E és interior almenys a un d’ells, es pugui extraure un nombre finit de conjunts I . que formin una família G la qual satisfaci la mateixa propietat que H, és necessari i suficient que E sigui extremal.]

Fréchet acaba la primera part de la tesi introduint una nova classe, la classe (E), la qual més endavant Hausdorff anomenaria d’espais mètrics. La lletra E per a designar aquesta classe prové de la paraula francesa écart, ‘distància’, que havia emprat Camille Jordan al seu Cours d’analyse, publicat el 1893. Una classe (E) és un cas particular de classe d’entorn (V ) en el qual f (ε) = 2ε i, per tant, la darrera condició esdevé la desigualtat triangular: 1. (A, B) = (B, A) > 0 si A és diferent de B. 2. (A, B) = (B, A) = 0 si, i només si, A = B. 3. Donats tres elements A, B i C, sempre es compleix (A, B) ≤ (A, C) + (C, B). Fréchet necessita restringir-se a aquesta classe per a obtenir el resultat que justifica la denominació extremal per als conjunts que són compactes i tancats i que culmina la primera part de la tesi ([16, p. 31]): 51. Théorème. La condition necéssaire et suffisante pour que toute opération continue dans un ensemble E d’éléments d’une classe (E), 1◦ soit bornée dans cet ensemble, 2◦ y atteigne sa limite supérieure, est que cet ensemble soit extrémal. [51. Teorema. La condició necessària i suficient perquè tota operació contínua en un conjunt E d’elements d’una classe (E), 1r sigui fitada en aquest conjunt, i 2n atenyi el límit superior, és que aquest conjunt sigui extremal.]

Fréchet va conjecturar que el resultat anterior era cert, més generalment, per a la classe (V ). Comenta al llibre Les espaces abstraits, escrit i publicat anys més tard, el 1928 ([17, p. 219]): [. . .] l’auteur était peu à peu amené [. . .] qu’au point de vue topologique, il ne devait y avoir aucune différence essentielle entre les espaces (D) et ceux qu’il avait alors appelés espaces (V ). [[. . .] l’autor es va convèncer a poc a poc [. . .] que, des del punt de vista topològic, no hi havia d’haver cap diferència essencial entre els espais (D) i els que havia anomenat espais (V ).]

Evolució de la noció de compacitat

En aquesta citació denota amb (D) el que anteriorment havia denotat amb (E), és a dir, els espais mètrics. E. W. Chittenden (1896–1977) va provar, en un article publicat l’any 1917, que sobre un espai (V ) es pot definir una distància que el converteix en un espai (E) que, en la terminologia actual, defineix la mateixa topologia. 3.3

Altres comentaris al voltant del treball de Fréchet

Després de la tesi, Fréchet va seguir treballant en diferents aspectes de la teoria d’espais abstractes [17]. La tesi de Fréchet va obrir un camp nou que seguirien treballs de diversos matemàtics d’arreu, ja sigui fent noves propostes de definició d’espais abstractes, com ara la duta a terme per F. Riesz (1880– 1956) que prenia com a noció bàsica la de punt de condensació, o profunditzant en l’anàlisi de les propietats dels espais (V ). Això canviaria substancialment amb l’aparició de l’obra de Hausdorff que comentarem a la propera secció, tot i que durant uns quants anys van conviure ambdues propostes. Segons explica Taylor [39, p. 287], la filla de Fréchet li hauria comentat que aquest considerava que el grup Bourbaki no li havia reconegut adequadament el seu paper en el desenvolupament de la topologia. En l’apunt històric adjunt al capítol de topologia, Bourbaki es refereix a Fréchet de la manera següent ([8, p. I–125–126]): Les premières tentatives pour dégager ce qu’il y a de commun aux propriétés des ensembles de points et des fonctions (sans intervention d’une notion de «distance») furent faites par Fréchet et Riesz; mais le premier partant de la notion de limite dénombrable, ne réussit pas à construire, pour les espaces non métrisables, un système d’axiomes commode et fécond; du moins reconnuit-il la parenté entre le principe de Bolzano-Weierstrass et le théorème de BorelLebesgue; c’est à ce propos qu’il introduisit le mot «compact», bien que dans un sense quelque peu différent de celui qu’on lui donne dans ce traité. [Els primers intents per extreure allò que tenen en comú les propietats dels conjunts de punts i de funcions (sense la intervenció d’una noció de distància) van ser fets per Fréchet i Riesz; però el primer, que partia de la noció de límit numerable, no va reexir a construir, per als espais no metritzables, un sistema d’axiomes còmode i fecund; almenys va reconèixer el parentiu entre el principi de Bolzano-Weierstrass i el teorema de Borel-Lebesgue; va ser en relació amb això que va introduir la paraula compacte, tot i que usant-la en un sentit lleugerament diferent del que se li dona en aquest tractat.]

Anys més tard, J. Dieudonné (1906–1992), destacat membre del grup Bourbaki, faria en el llibre History of Functional Analysis [13, p. 117], un comentari més elogiós de les aportacions de Fréchet relatives a les aplicacions a l’anàlisi funcional: The greatest merit of Fréchet lies in the emphasis he put on three notions which were to play a fundamental part in all later developments of Functional Analysis: compactness, completeness and separability.

Júlia Moreno, Mònica Blanco i Pere Pascual

[El mèrit més important de Fréchet rau en l’èmfasi que va donar a tres nocions que van tenir un paper fonamental en tots els desenvolupaments posteriors de l’anàlisi funcional: compacitat, completesa i separabilitat.]

En la propera secció estudiarem les aportacions de Hausdorff a l’anàlisi d’espais més generals, referint-nos especialment als conjunts compactes i comparant-los amb els resultats de Fréchet.

Els compactes als Grundzüge der Mengenlehre de Hausdorff

L’any 1914 Felix Hausdorff va publicar el llibre Grundzüge der Mengenlehre (Fonaments de la teoria de conjunts). Aquest text va esdevenir una obra emblemàtica de les matemàtiques del segle xx, tant per les seves aportacions originals com per l’organització i desenvolupament de les nocions i teoremes que presentava. Hausdorff va publicar els Grundzüge mentre era professor a la Universitat de Greifswald i, com assenyala a la introducció, el va dissenyar com a manual per als estudiants de matemàtiques avançades. El llibre està dividit en deu capítols. Als sis primers Hausdorff presenta la teoria de conjunts de Cantor de forma sistemàtica, incloent-hi els resultats de les seves investigacions. Els capítols 7–9 versen sobre la teoria de conjunts de punts, el que avui anomenem topologia general, mentre que el desè i últim tracta qüestions relacionades amb els treballs de Borel i Lebesgue sobre els conjunts mesurables. Abans d’analitzar l’aparició dels espais compactes a l’obra de Hausdorff, assenyalem que anys més tard, el 1927, Hausdorff va publicar una nova edició dels Grundzüge en què reescrigué completament algunes parts del text original, abandonant, en part, la teoria general d’espais topològics i centrant-se en els espais mètrics. Nosaltres analitzarem l’edició original del 1914, tot i que destaquem que la segona edició és un text de fàcil lectura i una mostra del mestratge de Hausdorff en l’exposició de la teoria de conjunts i la topologia (la versió anglesa, basada en la tercera edició, va ser publicada per Chelsea [22]). 4.1

Els espais topològics als Grundzüge

En els capítols intermedis 7–9 de la seva obra, Hausdorff defineix el concepte d’espai topològic i n’analitza algunes de les propietats; aquests capítols serien, segurament, els de més impacte dels Grundzüge en el desenvolupament de la matemàtica del segle xx. Hausdorff proposa una definició d’espai topològic a partir de la noció d’entorn, uns entorns donats axiomàticament i que difereixen de (de fet, generalitzen) la idea d’espais (V ) de Fréchet. Diversos autors han assenyalat que Hausdorff s’inspira en les idees de Riemann, de David Hilbert (1862–1943) i de Hermann Weyl (1885–1955). Arboleda ([5]) cita l’article de Hilbert [24] en el qual proposa considerar el pla com un espai abstracte constituït per punts en què a cada punt s’associa una família d’entorns amb la intenció de

Evolució de la noció de compacitat

caracteritzar la continuïtat com una propietat local del pla. Weyl fa un pas més per remarcar la rellevància dels entorns en el seu llibre sobre les superfícies de Riemann [44]. A la pàgina 14 es llegeix: Der Begriff der «zweidimensionalen Mannigfaltigkeit» oder der «Fläche» soll fur uns also nicht an die Idee des Raumpunktes geknüpft sein, sondern eine viel allgemeinere abstrakte Bedeutung erhalten. Wenn überhaupt irgendeine Gesamtheit von Dingen (die die Rolle der «Punkte» übernehmen werden) gegeben ist und definitionsgemäss zwischen ihnen ein ähnlicher kontinuierlicher Zusammenhang besteht wie zwischen den Punkten einer Ebene, so sprechen wir von einer zweidimensionalen Mannigfaltigkeit. Da sich aber alle Kontinuitätsbegriffe auf den einen der Umbegung zurückführen lessen, so gehört zur Erklärung einer zweidimensionalen Mannigfaltigkeit zweierlei: 1. Angabe derjenigen Dinge, welche als «Punkte» der Mannigfaltigkeit gelten sollen; 2. eine Erklärung des Begriffes der «Umgebung». [Per a nosaltres, el concepte de varietat de dimensió dos o superfície no hauria d’anar lligat a la idea de punt de l’espai sino que hauria de tenir un significat abstracte més general. Si hi ha algun conjunt de coses (que prenen el paper de «punts») i, com a resultat de les definicions que les determinen, hi ha una connexió contínua entre elles similar a la que hi ha entre els punts d’un pla, parlem de varietat bidimensional. Tots els conceptes relatius a la continuïtat poden reduir-se al d’entorn; per això, la descripció d’una varietat de dimensió dos requereix: 1. L’especificació dels objectes, que seran considerats com a punts de la varietat; 2. una explicació del concepte d’entorn.]

Weyl se centra en aquelles varietats amb entorns homeomorfs a un disc del pla euclidià, per fixar les bases per a l’actual definició de varietat topològica o diferencial. Arboleda ([5]) remarca que en unes notes manuscrites no publicades de l’any 1912, Hausdorff havia analitzat les propietats dels entorns esfèrics dels espais mètrics (de les boles, en diríem ara), anàlisi que anticiparia la definició dos anys més tard d’espai topològic ([21, p. 213]): Unter einem topologischen Raum verstehen wir eine Menge E, worin den Elementen (Punkten) x gewisse Teilmengen Ux zugeordnet sind, die wir Umgebungen von x nennen, und zwar nach Massgabe der folgenden Umgebungsaxiome: (a) Jedem Punkt x entspricht mindestens eine Umgebung Ux ; jede Umgebung Ux enthält den Punkt x. (b) Sind Ux , Vx zwei Umgebungen desselben Punktes x, so gibt es eine Umgebung Wx die Teilmenge von beiden ist. (c) Liegt der Punkt y in Ux , so gibt es eine Umgebung Uy , die Teilmenge von Ux ist. (d) Für zwei verschiedene Punkte x, y gibt es zwei Umgebungen Ux , Uy ohne gemeinsamen Punkt.

Júlia Moreno, Mònica Blanco i Pere Pascual

[Per espai topològic ens referim a un conjunt E, en el qual als seus elements (que són punts) x se’ls assigna determinats subconjunts Ux , que reben el nom d’entorns de x i que han de complir: (a) A cada punt x li correspon almenys un entorn Ux ; tot entorn Ux conté el punt x. (b) Si Ux i Vx són dos entorns del mateix punt x, llavors hi ha un entorn Wx que és un subconjunt dels dos. (c) Si el punt y està a Ux , llavors existeix un entorn Uy , que és un subconjunt de Ux . (d) Per a dos punts diferents x i y hi ha dos entorns Ux i Uy amb intersecció buida.]

Aquesta definició no es correspon exactament amb la definició d’espai topològic que presentem a les facultats. Hi ha dues diferències que cal tenir presents: la primera és que, segons l’axioma (c), els entorns són oberts. Això fa que, per exemple, si E és un conjunt amb més d’un punt i, per a qualsevol x ∈ E, només hi ha un únic entorn Ux = {x} que conté x, s’obté una família de subconjunts de E que satisfà tots els axiomes i, per tant, defineixen una topologia, mentre que el mateix E no és entorn de cap dels seus punts. Hausdorff està definint, de fet, una base d’entorns. La segona diferència correspon a l’axioma (d), que no s’imposa en general i que ha donat nom als espais de Hausdorff com aquells que el satisfan. A partir d’aquesta definició d’espai topològic, Hausdorff va desenvolupar conceptes bàsics, com ara el de punt interior, el de punt frontera i el d’obert de l’espai, i va demostrar que la unió arbitrària d’oberts és un obert i la intersecció finita d’oberts és un obert. Hausdorff defineix els punts d’acumulació (els anomena punts β) d’un subconjunt A com aquells punts tals que qualsevol dels seus entorns conté infinits punts de A, definició que coincideix amb la de punt límit donada per Cantor per als conjunts de punts del continu real, i demostra que un conjunt és tancat si conté tots els seus punts d’acumulació, així com les propietats d’unió i intersecció dels tancats. En la secció 5 del capítol 7, Hausdorff hi introdueix els espais compactes que comentarem a continuació. Abans, però, esmentem que Hausdorff també estudia molts altres aspectes de forma original, com ara la connexió, o que al capítol 8 analitza diferents espais topològics, on introdueix els axiomes de numerabilitat i els espais mètrics, i on estudia la topologia de l’espai euclidià ordinari, mentre que el capítol 9 està dedicat a la continuïtat. 4.2

Els espais compactes als Grundzüge

Hausdorff va adoptar la definició de conjunt compacte de Fréchet. Si A és un conjunt d’un espai topològic X i x ∈ X, anomena x β-punt d’acumulació de A si, per a tot entorn U de x, la intersecció U ∩ A conté infinits punts, i diu que A és divergent si no té punts d’acumulació ([21, p. 230]). Per comoditat, ens referirem als β-punts d’acumulació simplement com a punts d’acumulació,

Evolució de la noció de compacitat

cosa que és consistent amb la definició usual si tenim present que en els espais de Hausdorff els punts d’acumulació en el sentit actual són β-punts d’acumulació ([21, teorema 17.9]). Amb aquestes premisses, Hausdorff defineix conjunt compacte: Eine Menge ohne divergente Teilmenge nennen wir (nach M. Fréchet) kompakt; dazu rechnen wir natürlich auch die endlichen Mengen inkl der Nullmenge. Jede unendliche Teilmenge einer kompakten Menge A hat also mindestens einen (nicht notwendig zu A gehörigen) Häufungspunkt. [Anomenarem compacte (segons Fréchet) un conjunt sense cap subconjunt divergent; no cal dir que també comptem les quantitats finites incloent-hi el conjunt buit. Cada subconjunt infinit d’un conjunt compacte A té, per tant, almenys un punt d’acumulació (que no necessàriament pertany a A).]

Com Fréchet, Hausdorff tampoc suposa que un conjunt compacte sigui tancat; comenta, a peu de pàgina, que Fréchet anomena extremals els conjunts compactes i tancats perquè les funcions contínues definides sobre ells són fitades i assoleixen els seus extrems, cosa que demostrarà al capítol ix, dedicat a la continuïtat, en el context dels espais topològics. En aquesta secció Hausdorff demostra quatre teoremes, dels quals comentem els tres primers i les demostracions que en va fer. En el quart, caracteritza els compactes a partir de les dues nocions de punt d’acumulació a què ens hem referit més amunt, ja sigui com a β-punt d’acumulació o en el sentit del terme en l’actualitat. I. (Durchschnittssatz von Cantor). Eine absteigende Folge A1 ⊇ A2 ⊇ · · · kompakter, abgeschlossener, von Null verschiedener Mengen hat einen von Null verschiedenen Durchschnitt. [I. (Teorema de la intersecció de Cantor). Una successió descendent de conjunts A1 ⊇ A2 ⊇ · · · compactes, tancats i no buits té intersecció no buida.]

Prova. Escollim un punt an de cada conjunt An ; denotem amb Bn ⊆ An el conjunt format pels punts an , an+1 , . . . Si B1 és finit, hi haurà un punt a tal que an = a per a infinits índexs. Així, a ∈ An per a tot n ≥ 0 i, en conseqüència, D = A1 ∩ A2 ∩ · · · 6= ∅. Si B1 és infinit, B1 admet un punt d’acumulació a, ja que A1 és compacte; a també és punt d’acumulació de Bn , per a tot n, i, per tant, també de An . Com que els An són tancats, a pertany a An i també a D. 2 II. (Satz von Borel). Ist eine kompakte abgeschlossene Menge in der Summe einer Folge von Gebieten enthalten, so ist sie bereits in einer Summe von endlich vielen Gebieten dieser Folge enthalten. [II. (Teorema de Borel). Un conjunt compacte i tancat que està contingut en la unió d’una successió de conjunts oberts, també ho estarà en una subfamília finita d’aquest mateix conjunt d’oberts.]

Júlia Moreno, Mònica Blanco i Pere Pascual

Prova. Sigui A un compacte de l’espai topològic E i G1 , G2 , . . . un recobriment obert de A, A ⊆ S = (G1 ∪ G2 ∪ · · · ). Volem demostrar que existeix un n a partir del qual es compleix A ⊆ Sn = G1 ∪ G2 ∪ · · · ∪ Gn . Posem que Bn = A ∩ Sn i An = A \ Bn , de manera que es tenen les inclusions S1 ⊆ S2 ⊆ · · ·

B1 ⊆ B2 ⊆ · · ·

A1 ⊇ A2 ⊇ · · ·

A més, S1 ∪ S2 ∪ · · · = G1 ∪ G2 ∪ · · · = S i, per tant, si fem la intersecció amb A, en resulten les igualtats B1 ∪ B2 ∪ · · · = A ∩ S = A, A1 ∩ A2 ∩ · · · = A \ (B1 ∪ B2 ∪ · · · ) = ∅. Com que els Gn i els Sn són oberts, E\Sn és tancat i An = A∩(E\Sn ) és compacte i tancat. Si An 6= ∅ per a tot n, pel teorema anterior la seva intersecció seria no buida. Per tant, hi ha un n tal que An = ∅; és a dir, A = Bn i A = A ∩ Sn , és a dir, A ⊆ Sn . 2 III. (Umkehrung des Borelschen Satzes). Wenn für jedes System von Gebieten, in deren Summe die Menge A enthalten ist, A bereits in einer Summe von endlich vielen Gebieten dieses Systems enthalten ist, so ist A kompakt und abgeschlossen. [III. (Recíproc del teorema de Borel). Si per a cada sistema de conjunts oberts, en la unió dels quals està contingut el conjunt A, A ja està contingut en la unió finita d’alguns oberts d’aquest sistema, llavors A és compacte i tancat.]

Prova. Considerem que A no és compacte i sigui B un subconjunt divergent. Per a cada punt a de A existeix un entorn Ua tal que la intersecció B ∩ Ua és finita (o buida). Els oberts Ua formen un recobriment de A i, per hipòtesi, en podem extreure un subrecobriment finit. Però, aleshores, B és un conjunt finit, i arribem a una contradicció. Suposem ara que A no és tancat. Sigui x un punt d’acumulació. Per l’axioma de separació de Hausdorff, per a tot a que pertany a A, existeixen entorns Ua de a i Va de x tals que Ua ∩ Va = ∅ i, per tant, x no és de l’adherència de Ua . Els oberts Ua formen un recobriment de A i, per hipòtesi, existeix un subrecobriment finit, A ⊂ Ua1 ∪· · · Uam . Com que l’adherència d’una unió finita de conjunts és la unió de les adherències, en resulta x 6∈ U a1 ∪ · · · ∪ U am = Ua1 ∪ · · · ∪ Uam , i, per tant, x 6∈ A, que és una contradicció amb l’elecció del punt x.

Evolució de la noció de compacitat

Veiem que el teorema de Borel i el recíproc del teorema de Borel es refereixen a recobriments oberts de tipus diferent. Per al teorema de Borel, Hausdorff es redueix als recobriments numerables, mentre que per al recíproc ha d’usar recobriments generals. Al capítol següent, Hausdorff introdueix el primer i segon axiomes de numerabilitat i, entre altres aspectes, realitza una anàlisi de la cardinalitat del conjunt d’oberts i tancats d’un espai topològic que satisfà el segon axioma de numerabilitat, cosa que li permet establir que d’un recobriment obert qualsevol és possible extreure’n un subrecobriment numerable ([21, teorema V, p. 272]). En particular, per a aquests espais, l’enunciat del recíproc del teorema de Borel es pot reduir a recobriments numerables o, d’una manera alternativa, el del teorema de Borel, a recobriments generals. Els resultats establerts per Hausdorff sobre la compacitat en espais topològics són aproximadament els equivalents als demostrats per Fréchet en el context de les classes (V ): obté el teorema de Borel per a recobriments numerables, que seria l’anàleg del teorema 36 de Fréchet, i l’equivalència de la compacitat amb la propietat de Heine-Borel general per a espais que satisfan el segon axioma de numerabilitat, que seria l’anàleg del teorema 42 de Fréchet, enunciat per als espais normals que, recordem, són separables (propietat similar al segon axioma de numerabilitat) i complets (propietat que és innecessària a posteriori). 4.3

L’establiment de la definició d’espai topològic

Els Grundzüge suposen l’inici del veritable desenvolupament de la teoria general dels espais topològics, que va prendre com a punt de partida els axiomes formulats per Hausdorff. Va ésser una obra pionera en la branca de la topologia i que va contribuir al desenvolupament de l’estructura de les matemàtiques modernes. Al primer quart del segle xx figures importants com Kazimierz Kuratowski (1896–1980), Heinrich Tietze (1880–1964), Pàvel S. Alexandroff (1896–1982) o Wacław Sierpiński (1882–1969) van proposar sistemes d’axiomes alternatius per definir els espais topològics, alguns basats en la idea de punts d’acumulació o adherents (com ara Sierpiński i Kuratowski) i d’altres que proposaven una primera axiomàtica a través dels oberts, com va fer Alexandroff [1]. No seria fins a l’aparició de la Topologie del grup Bourbaki, el 1940, que es fixaria la definició actual mitançant els oberts. André Weil (1906–1998) assenyala a [43, p. 37] el panorama dispers del moment: Les mathématiciens qui, depuis une trentaine d’annés, se sont occupés de topologie générale, ont introduit dans cette branche des mathématiques un ensemble complètement désordonné de notions et d’axiomes [. . .]. [Els matemàtics que, els darrers trenta anys, s’han ocupat de la topologia general, han introduït en aquesta branca de les matemàtiques un conjunt completament desordenat de nocions i axiomes [. . .].]

Júlia Moreno, Mònica Blanco i Pere Pascual

A continuació, afegeix que els únics espais que és útil considerar són els que, en aquell moment (1937), ell anomena espais topològics, els que satisfan que tota reunió de conjunts oberts és un conjunt obert. Per a aquesta definició, Weil segueix l’exposició d’un altre membre fundador del grup Bourbaki, R. de Possel, en el Séminaire de M. (Julia) (1935–1936) [11], qui parteix de la propietat de la reunió d’oberts i va imposant més condicions, com la d’intersecció finita, segons els resultats que es vulguin establir. Moore ([30]) cita la tesi no publicada de Liliane Beaulieu, arxivera del llegat Bourbaki, presentada el 1989, per explicar la decisió del grup de fundar la noció d’espai topològic en els oberts. Segons aquesta citació, Weil hauria proposat començar pels espais mètrics i després arribar als espais més generals formulats a partir de la funció clausura definida per Kuratowski, mentre que Claude Chevalley (1909–1984) considerava que era necessari crear les bases dels espais topològics generals abans que les dels espais mètrics i va decantar la decisió cap a la presentació per oberts, que és de la manera que apareixerien en l’edició del 1940. Bourbaki va fer un reconeixement elogiós de l’obra de Hausdorff a les notes històriques referents a la topologia general ([8, p. I–126]): Avec Hausdorff commence la topologie générale telle qu’on l’entend aujourd’hui. Reprenant la notion de voisinage, il sut choisir, parmi les axiomes de Hilbert sur les voisinages dans le plan, ceux qui pouvaient donner à sa théorie à la fois toute précision et toute la généralité désirables. [. . .] Le chapitre où il en développe les conséquences est resté un modèle de théorie axiomatique, abstrait mais d’avance adaptée aux applications. Ce fut là, tout naturellement, le point de départ des recherches ultérieures sur la topologie générale, et principalement des travaux de l’école de Moscou, orienté, en gran partie vers le problème de métrisation. [Amb Hausdorff comença la topologia general tal com se l’entén avui en dia. Reprenent la noció d’entorn, va saber escollir entre els axiomes de Hilbert per als entorns del pla, aquells que podien donar simultàniament a la seva teoria tota la precisió i tota la generalitat desitjable. [. . .] El capítol en el qual en desenvolupa les conseqüències ha romàs un model de teoria axiomàtica, abstracta però per endavant adaptada a les aplicacions. Aquest va ser, naturalment, el punt de partida dels treballs posteriors sobre la topologia general, i sobretot dels treballs de l’escola de Moscou, en gran part orientada cap al problema de la metrització.]

En la propera secció analitzarem la contribució de l’escola de Moscou a l’establiment de la noció de compacitat.

L’escola russa

A [9], Cameron assenyala que durant la darrera dècada del segle xix es va produir un canvi radical en l’ensenyament de les matemàtiques a la Universitat de Moscou; es van abolir els cursos obligatoris i es deixà llibertat als professors

Evolució de la noció de compacitat

per a la selecció dels continguts, fet que acabaria beneficiant la creativitat científica. En aquest context, destaquen les figures de Dmitri Fiódorovitx Egorov (1869–1931) i Nikolai Nikolàievitx Luzin (1883–1950), que van transformar per complet l’ensenyament de les matemàtiques, passant d’una formació «esclerotitzada» a una visió que despertava la curiositat dels estudiants i els dirigia cap a la recerca en matemàtiques. La joventut dels estudiants, el seu entusiasme i el sentiment de pertinença al grup farien que els membres del seminari de Luzin anomenessin Lusitania el col.lectiu. Alguns dels participants a Lusitania esdevindrien matemàtics de primer nivell, com M. Y. Suslin, A. Y. Kinchin, A. N. Kolmogorov, M. A. Laurentiev, o L. A. Lusternik [9]. En el llibre de Graham i Kantor, [18], es pot llegir una descripció interessant d’aquest grup, en contrast amb l’escola francesa liderada per Borel, Lebesgue i Baire. Entre els membres de Lusitania hi havia Pàvel Serguéievitx Alexandroff (1896–1982) i Pàvel Samuílovitx Urysohn (1898–1924). Es van interessar, sobretot, en les noves idees introduïdes per Hausdorff als Grundzüge i van fundar el Seminari de Topologia de la Universitat de Moscou. Els treballs d’Alexandroff i Urysohn, ja siguin conjunts o individualment, recorren un ampli espectre de la topologia del moment. Pel que fa als compactes, l’any 1929 van publicar la «Mémoire sur les espaces topologiques compacts» [3], que suposava el primer estudi sistemàtic de la compacitat deslliurant-la dels problemes associats a la numerabilitat subjacent en els treballs de Fréchet i Hausdorff. En aquesta memòria es tracten aspectes que van més enllà de la definició d’espai compacte, aspectes que no tractarem aquí. Des del punt de vista desenvolupat posteriorment pel grup Bourbaki, el de la teoria d’estructures, hi havia un aspecte que no s’havia tractat a la memòria, l’anàlisi de l’estabilitat de la compacitat per productes. Tychonoff, deixeble d’Alexandroff, va introduir la topologia producte i va demostrar que la compacitat es conservava per a un producte d’espais compactes. 5.1

La memòria d’Alexandroff i Urysohn

Durant l’estiu del 1922, Alexandroff i Urysohn van llogar una casa de camp i van començar la seva col.laboració en l’estudi de la topologia general. El primer manuscrit de la «Mémoire sur les espaces topologiques compacts» és fruit d’aquella trobada, tot i que la seva publicació es va endarrerir uns quants anys. Al gener del 1923 el manuscrit estava preparat per a ser publicat i el van enviar a la revista Fundamenta Mathematicae, on el van acceptar. Aquesta revista acabava de rebre l’extens article d’Urysohn titulat «Mémoire sur les multiplicités cantoriennes», que es va publicar en dos volums, per la qual cosa l’editor del Fundamenta va considerar que no podia publicar l’article que li havien enviat, també extens, en un futur immediat. Luitzen E. J. Brouwer (1881–1966) va suggerir la revista Verhandelingen der Kon. Akademie van Wetenschappen te Amsterdam per accelerar la publicació de la memòria, on finalment es publicaria. La necessitat d’enviar els documents i les proves corresponents entre Moscou i Amsterdam, amb les dificultats que això suposava en aquell moment, va

Júlia Moreno, Mònica Blanco i Pere Pascual

endarrerir la publicació fins l’any 1929. Entre el 1922 i el 1929, Alexandroff i Urysohn van fer diversos viatges per Europa, a Alemanya per visitar Hausdorff o a Holanda per visitar Brouwer, per exemple, en els quals van divulgar les idees contingudes a la memòria i van fer diverses publicacions parcials en què anunciaven alguns dels resultats que hi apareixen ([2], pel que fa a la compacitat). Així, tot i el retard en la publicació del treball i les dificultats de comunicació entre la comunitat matemàtica del moment, les idees i resultats d’Alexandroff i Urysohn van disseminar-se al llarg de la dècada dels vint. La memòria ha estat reeditada en rus en diverses ocasions, en les quals hi han estat afegits apèndixs i comentaris pel mateix Alexandroff. Tot i que no hem tingut accés directe a les edicions russes, Cameron ([9]) recull alguns comentaris de la introducció d’Alexandroff a la tercera edició, publicada l’any 1971. Consideraven Fréchet i Hausdorff els fundadors de la topologia general; mentre que atorgaven a Fréchet el mèrit de la introducció d’alguns conceptes fonamentals (en un entorn proper a l’anàlisi), com la compacitat i la completesa; consideraven que Hausdorff havia establert les bases de la teoria de conjunts en els Grundzüge. A [9, p. 360], Cameron cita el següent paràgraf dels comentaris d’Alexandroff: In this Memoir, P. S. Urysohn an I stood entirely on the basis of Hausdorff «theory of sets», but the distinction from Hausdorff was that we were interested not in questions of the logical analysis of classical theory, but within the newly discovered topological spaces, we saw fascinating new topics of mathematical investigation, and we decided actually to undertake the investigation with all possible systematicness, beginning with that end which seemed to us the most promising — the concept of compactness. [En aquesta Memòria, P. S. Urysohn i jo ens manteníem en el context de la teoria de conjunts de Hausdorff, però a diferència de Hausdorff no estàvem interessats en qüestions de l’anàlisi lògica de la teoria clàssica, sinó que, en els recentment descoberts espais topològics, vam veure nous temes d’investigació matemàtica fascinants, i vam decidir emprendre la investigació de la manera més sistemàtica possible, començant per aquest propòsit que ens semblava el més prometedor —el concepte de compacitat.]

La memòria d’Alexandroff i Urysohn és el primer estudi sistemàtic dels espais compactes. A més dels resultats que s’hi presenten, construeixen diversos exemples que han esdevingut paradigmàtics de les propietats que representen, com ara el quadrat amb l’ordre lexicogràfic, la doble circumferència, etc. Com veurem més endavant, l’aproximació a la compacitat és mitjançant punts d’acumulació completa, cosa que va donar lloc a una interacció profunda entre els espais compactes i algunes tècniques i mètodes de la teoria de conjunts. Van introduir i estudiar els espais absolutament tancats, els espais normals, els espais regulars i els espais localment compactes; en particular, per exemple, van provar que un espai compacte Hausdorff és normal. Del teorema de metritzabilitat d’Urysohn ([32]), se’n deduïa que els espais normals (que satisfan el

Evolució de la noció de compacitat

segon axioma de numerabilitat) admetien un submergiment en un espai compacte Hausdorff i plantejava la qüestió de caracteritzar els espais que tenen aquesta propietat, qüestió que estarà al centre de l’anàlisi de la compacitat d’un producte. A continuació, ens centrem en les pàgines 7–11 de la memòria, on es defineixen els espais bicompactes. En la pàgina 7 de la memòria es refereixen a la definició de compacitat i adopten la noció establerta per Fréchet i Hausdorff segons la qual un espai topològic R és compacte si tot conjunt infinit contingut en R té almenys un punt d’acumulació. Seguidament es troba la definició d’una nova noció, la de punt d’acumulació completa: Un point ξ est dit point d’accumulation complète de l’ensemble A, si quel-que soit le voisinage V (ξ), la puissance de A ∩ V (ξ) est égale à celle de A tout entier. [Un punt ξ s’anomena punt d’acumulació completa del conjunt A si, per a qualsevol entorn V (ξ), el cardinal de A ∩ V (ξ) és el mateix que el cardinal de A.]

Utilitzen aquest concepte per a establir un resultat que resumeix i completa els continguts als Grundzüge sobre els espais compactes que hem comentat a la subsecció 4.2: 1. Chacune des propiétés ci-dessous est nécessaire et suffisante pour la compacité de l’espace topologique R: (a) Tout ensemble dénombrable situé dans R possède au moins un point d’accumulation complète. (b) (Théorème de Cantor): toute suite décroissante dénombrable d’ensembles fermés F1 ⊃ F2 ⊃ · · · ⊃ Fn ⊃ · · · non vides situés dans R, possède au moins un point appartenant à tous les ensembles Fn . (c) (Théorème de Heine-Borel): de toute infinité dénombrable de domaines recouvrant l’espace R de façon que tout ξ ⊂ R est intérieur à un (ou plusieurs) de ces domaines, on peut extraire un nombre fini jouissant de la même propieté. [1. Cadascuna de les propietats següents és necessària i suficient per a la compacitat de l’espai topològic R: (a) Tot conjunt numerable dins de R té almenys un punt d’acumulació completa. (b) (Teorema de Cantor): tota successió decreixent numerable de conjunts tancats F1 ⊃ F2 ⊃ · · · ⊃ Fn ⊃ · · · no buits i situats dins de R, té almenys un punt pertanyent a tots els conjunts Fn . (c) (Teorema de Heine-Borel): de tota infinitat numerable de conjunts que recobreixen l’espai R de manera que tot punt ξ ⊂ R és interior a un (o més) dels conjunts, se’n pot extreure un nombre finit que compleixen la mateixa propietat.]

Júlia Moreno, Mònica Blanco i Pere Pascual

Els autors remarquen que la necessitat d’aquestes propietats, així com la suficiència de la condició (c), apareixen al llibre de Hausdorff, i que la implicació (b) ⇒ (a) és immediata, raonant per reducció a l’absurd. La possibilitat de limitar-se als conjunts numerables en la condició (a) no havia aparegut en la literatura científica degut al fet que les nocions de punt d’acumulació i punt d’acumulació completa es confonen per als conjunts numerables. En aquest punt, Alexandroff i Urysohn conclouen que la propietat d’un espai topològic de ser compacte es pot reduir a propietats de «formacions numerables», cosa que no comprèn la idea intuïtiva de compacitat, aquella de posseir un caràcter de tancament absolut [3, p. 8]. El teorema següent permet alliberar-se de la numerabilitat: I. Les trois propriétés suivantes d’un espace topologique R, sont équivalents: (A) Tout ensemble infini situé dans R possède au moins un point d’accumulation complète. (B) Toute suite infinie bien ordonnée d’ensembles fermés decroissants possède au moins un point appartenant à tous les ensembles de la suite. (C) De toute infinité de domaines recouvrant l’espace R, on peut extraire un nombre fini de domaines jouissant de la même propriété. [I. Les tres propietats següents d’un espai topològic R són equivalents: (A) Tot conjunt infinit dins de R té almenys un punt d’acumulació completa. (B) Tota successió infinita ben ordenada de conjunts tancats decreixents té almenys un punt pertanyent a tots els conjunts de la successió. (C) De qualsevol infinitat de dominis que recobreixen l’espai R, se’n pot extreure un nombre finit de dominis amb la mateixa propietat.]

La prova d’Alexandroff i Urysohn d’aquest resultat segueix de prop les demostracions dels teoremes de Hausdorff sobre els espais compactes, tenint una cura especial en les cardinalitats que cal preservar. Per fer-ho introdueixen les propietats (Ar ), (Br ), (Cr ) com les enunciades al teorema però involucrant infinits de cardinal r , i utilitzen el circuit (C) ⇒ (A) ⇒ (Br ) ⇒ (B) ⇒ (C) per a tot cardinal regular r a fi de concloure les equivalències enunciades. A més, proven que (Cr ) ⇒ (Br ), per la qual cosa (Ar ), (Br ), (Cr ) són, també, equivalents. Un resultat similar, en el context del espais (V ) de Fréchet va ser provat per Kuratowski i Sierpiński [26]. No s’observen referències creuades entre un i altre article, fet que potser es deu a les dificultats de comunicació del moment. De fet, Alexandroff i Urysohn, en referir-se a Fréchet, assenyalen en una nota a peu de pàgina ([3, p. 2]) que han conegut els seus treballs després d’haver elaborat la memòria, i remarquen les dificultats d’accés a la literatura científica per als membres de la Universitat de Moscou.

Evolució de la noció de compacitat

Alexandroff i Urysohn defineixen un espai bicompacte com aquell que satisfà una de les condicions del teorema i, per tant, totes elles. La bicompacitat provenia de la conjunció de dues propietats: la compacitat de Fréchet (o compacitat numerable) i la compacitat final, que permetia passar del cas no numerable al cas numerable. La distinció entre els espais compactes i els espais bicompactes va clarificar l’anàlisi de les propietats topològiques que condueixen a un teorema d’existència d’extrems per a les funcions contínues. Des de les dècades dels quaranta i els cinquanta del segle xx, s’ha imposat la definició d’espai compacte com aquell que satisfà la propietat dels recobriments oberts expressada en la condició (C) del teorema, la propietat anomenada de Heine-Borel. Observem, però, que la propietat (A) és la més propera a la definició original de Fréchet, basada en la propietat de Bolzano-Weierstrass; això explicaria el comentari d’Alexandroff en la introducció a la tercera edició de la memòria reflectit per Cameron [9, p. 373–374]: Alexandroff noted that at the time he and Urysohn developed the concept of bicompactness it was done by means of complete accumulation points with a secondary formulation in terms of completely ordered sequences of nonempty decreasing closed sets, and a tertiary formulation by means of open covers. Both of them felt that the order of the formulations represented the order of importance but, as Alexandroff pointed out, paracompactness (the most important generalization of bicompactness) is defined by means of open covers and its importance in the resolution of the general metrization theorem has shown this first impression to be incorrect. [Alexandroff va observar que en el moment que ell i Urysohn van desenvolupar el concepte de bicompacitat ho van fer mitjançant els punts d’acumulació completa amb una formulació secundària en termes de successions ordenades decreixents de conjunts tancats, i una formulació terciària a partir de recobriments oberts. Ambdós creien que l’ordre de les formulacions representava l’ordre d’importància, però, com Alexandroff va fer notar, la paracompacitat (la generalització més important de la bicompacitat) es defineix a partir de recobriments oberts i la seva importància en la resolució del teorema de metrització general ha evidenciat que la primera impressió era incorrecta.]

Fem notar que la noció d’espai paracompacte fou introduïda per Dieudonné quinze anys més tard, a l’article [12]. 5.2

Sobre el teorema de Tychonoff

En l’article «Über die topologische Erweiterung von Räumen» («Sobre l’extensió topològica dels espais») publicat l’any 1930 a Mathematische Annalen, vegeu [40], Tychonoff analitza en quines condicions un espai topològic (de Hausdorff) X admet un submergiment en un espai compacte (per submergiment o encaix s’entén una aplicació contínua i injectiva de X en un altre espai que indueix un homeomorfisme entre X i la seva imatge). El plantejament del problema hauria sorgit a partir de les sessions del Seminari de Topologia

Júlia Moreno, Mònica Blanco i Pere Pascual

dirigit per Alexandroff i s’inspiraria, com hem remarcat a la secció anterior, en el teorema de metritzabilitat d’Urysohn [42], que havia provat que un espai normal que satisfà el segon axioma de numerabilitat és metritzable veient que admet un submergiment en el cub I ω . La compacitat del cub I ω era ben coneguda, atès que es tractava d’un subconjunt de l’espai mètric Rω estudiat per Fréchet. A la introducció de l’article, Tychonoff anuncia que demostrarà el teorema següent: Satz I. Zu jeder Kardinalzahl τ gibt es einen nur von dieser Kardinalzahl abhängenden bikompakten Raum Rτ von der Eigenschaft, dass jeder normale topologische Raum, der ein Umgebungssystem von einer Mächtigkeit ≤ τ besitzt, einer Teilmenge des Raumes Rτ homöomorph ist. [Teorema I. Per a cada nombre cardinal τ existeix un espai bicompacte Rτ que depèn només d’aquest nombre cardinal tal que qualsevol espai topològic normal que té una base d’entorns de cardinal menor o igual que τ és homeomorf a un subconjunt de Rτ .]

Tychonoff s’inspira en el lema d’Urysohn ([32]) i introdueix els espais completament regulars, amb els quals caracteritza els espais que admeten un submergiment en un espai compacte Hausdorff [40, teorema ii]. La demostració de Tychonoff del teorema i segueix la mateixa línia que la demostració establerta per Urysohn per al seu teorema de metritzabilitat. L’existència de suficients funcions contínues sobre un espai normal, i de fet també sobre un espai completament regular, permet construir una aplicació de X en Rτ = I τ , on I = [0, 1] (per a Tychonoff, τ és un ordinal que representa un cardinal de tipus particular, que és un conjunt ben ordenat). A diferència, però, del cas numerable, ara I τ no és un espai mètric, per la qual cosa s’ha de començar donant un sentit a l’espai topològic Rτ . A la pàgina 546 defineix, per primera vegada en la literatura, la topologia producte de I τ : Es sei Jα eine Menge von der Mächtigkeit τ von abstrakt gegebenen zueinander fremden Einheitsstrecken 0 ≤ t ≤ 1. Ein Punkt x des Raumes Rτ is definitionsgemäss der Inbegriff {t1 , t2 , . . . , tα , . . . } von «Koordinaten» tα , wobei tα ein Punkt von Jα , also eine reelle Zahl 0 ≤ tα ≤ 1 ist. Die Umgebungsdefintion geschieht folgendermassen: Es sei x0 = {t10 , t20 , . . . , tα0 , . . . } ein Punkt von Rτ . Wir wählen beliebig endlichviele Jα1 , . . . , Jαk und auf jedem dieser Intervalle Jαi zwei rationale Zahlen τα0 i < tα0 i < τα00i ; eine Umgebung von x0 = {t10 , t20 , . . . , tα0 , . . . } besteht dann definitionsgemäss aus allen Punkten x = {t1 , t2 , . . . , tα , . . . }, die den Bedingungen τα0 i < tαi < τα00i genügen. [Sigui Jα un conjunt d’intervals de cardinal τ. Un punt x de l’espai Rτ està definit per l’expressió {t1 , t2 , . . . , tα , . . . } de les «coordenades» tα , on tα és un punt de Jα , és a dir, un nombre real 0 ≤ tα ≤ 1. Es defineixen els entorns de la manera següent: Sigui x0 = {t10 , t20 , . . . , tα0 , . . . } un punt de Rτ . Triem un nombre finit d’intervals Jα1 , . . . , Jαk i per a cadascun d’aquests intervals Jαi , dos nombres racionals τα0 i < tα0 i < τα00i ; un entorn de x0 = {t10 , t20 , . . . , tα0 . . . } és per definició el conjunt de punts x = {t1 , t2 , . . . , tα , . . . } que satisfan τα0 i < tαi < τα00i .]

Evolució de la noció de compacitat

El sistema d’entorns definit determina, en efecte, un espai topològic de Hausdorff. Tychonoff imposa la racionalitat dels nombres τα0 i i τα00i per mantenir el control sobre el cardinal de I τ , ja que llavors ℵ0 · τ = τ. L’altre ingredient que necessita Tychonoff per a adaptar la demostració d’Urysohn és provar que l’espai topològic Rτ = I τ així definit és bicompacte. La demostració, que desenvolupa en la secció 2, Beweis der Bikompaktheit von Rτ (‘demostració de la bicompacitat de Rτ ’), utilitza inducció transfinita per a construir coordenada a coordenada un punt d’acumulació completa per a un subconjunt infinit E ⊆ Rτ donat. En un article posterior, «Ein Fixpunktsatz» («Un teorema de punt fix»), publicat l’any 1935 [41], Tychonoff necessita la compacitat d’un producte d’espais bicompactes de Hausdorff arbitraris; a la pàgina 772 comenta: Das Produkt von bikompakten Räumen ist wieder bikompakt. Diesen Satz beweist man wörtlich so wie die Bikompaktheit des Produktes von Strecken. [El producte d’espais bicompactes és també bicompacte. Aquest teorema es demostra literalment com la bicompacitat dels productes d’intervals.]

La versió general d’aquest teorema és el que es coneix com a teorema de Tychonoff, resultat que es considera un dels més importants de la topologia general. Comentarem una variant de la demostració, essencialment equivalent a la demostració de Tychonoff, deguda a Eduard Čech (1893–1960). Un bon exercici consisteix a seguir la prova per al producte de dos espais bicompactes (cf. [45]). En l’article publicat l’any 1937 a Annals of Mathematics que porta per títol «On bicompact spaces», Čech va estendre els resultats de Tychonoff i va introduir el que s’anomenaria més tard la compactificació de Stone-Čech (que va ser introduïda simultàniament i de forma independent per Marshall Stone (1903–1989)) [32]. En la primera part de l’article [10], Čech exposa les idees i definicions que utilitzarà en el seu treball i, en particular, demostra el teorema de Tychonoff general; a la pàgina 830, enuncia: The cartesian product S = Pi Si of any family of bicompact spaces is a bicompact space. [El producte cartesià S = Pi Si de qualsevol conjunt d’espais bicompactes és un espai bicompacte.]

La demostració que planteja, que és la que presentem a continuació, segueix bàsicament la línia de la que havia fet Tychonoff anys enrere amb algunes modificacions menors, com usar recobriments oberts allà on Tychonoff utilitzava sistemes de tancats amb interseccions finites no buides. Prova del teorema de Tychonoff. Per a facilitar la lectura de la prova, reformularem algunes de les notacions de l’article de Čech. El resultat que volem provar és que, donada una família d’espais topològics bicompactes, Xα , α ∈ I, Q el producte X = α∈I Xα és un espai bicompacte. Per veure-ho és suficient provar que tot conjunt infinit E ⊂ X té un punt d’acumulació completa.

Júlia Moreno, Mònica Blanco i Pere Pascual

Pel teorema de Zermelo, podem suposar que els elements de I són de tots els ordinals menors o iguals a un ordinal donat. Tal com està definida la topologia producte, n’hi ha prou de veure que es pot construir un punt z = (zα ) definint les coordenades per inducció transfinita de manera que se satisfaci la propietat següent: (Aα ) Per a qualsevol nombre finit d’índexs α1 , . . . , αn ≤ α i qualssevol oberts Uαi ⊂ Xαi , 1 ≤ i ≤ n, el cardinal de Uα1 × · · · × Uαn ×

Xβ ∩ E

Y β6=αi

és igual al cardinal de E. Suposem definides les coordenades zα per a α < λ i provem que existeix zλ de manera que se satisfà (Aλ ): en cas contrari, per a tot yλ ∈ Xλ hi ha: — un entorn yλ ∈ Uyλ ⊂ Xλ , — un subconjunt finit d’índexs I(yλ ) menors que λ, y

— i entorns oberts zα ∈ Vzαλ ⊂ Xα, per a α ∈ I(yλ ), tals que, si escrivim U (yλ ) =

Uyα ×

α∈I(yλ )

Xβ ,

V (yλ ) =

α∈I(yλ )

β6∈I(yλ )

Vyα ×

Xβ ,

β6∈I(yλ )

el cardinal de E ∩ U (yλ ) ∩ V (yλ ) és menor que el cardinal de E. Els oberts Uyλ formen un recobriment de Xλ , i per la bicompacitat de Xλ en podem extreure un subrecobriment finit, Xλ = Uy 1 ∪ · · · ∪ Uyλm . λ

(2)

Així, el cardinal del conjunt E ∩ (U (yλ1 ) ∩ V (yλ1 )) ∩ · · · ∩ (U(yλ1 ) ∩ V (yλ1 )) és menor que el cardinal de E. Per (2), aquest conjunt conté E ∩ V (yλ1 ) ∩ · · · ∩ V (yλm ), que, per tant, tindrà cardinal menor que el de E. Però això és absurd ja que es compleix (Aµ ) per a qualsevol µ tal que α ≤ µ < λ, per a tot α ∈ I(λy ). 2 Čech va preguntar si el producte d’espais compactes és un espai compacte. Anys més tard, el 1949, J. Novák va mostrar un exemple de dos espais compactes amb producte no compacte; és a dir, la compacitat de Fréchet no és estable per a productes ([33]), i referma així la noció d’espai bicompacte per damunt de la d’espai compacte.

Evolució de la noció de compacitat

Reflexions finals

La noció de compacitat és una abstracció de les propietats topològiques dels intervals [a, b] de la recta real, que es remunten als teoremes de Bolzano i de Weierstrass. El teorema de Borel i les extensions de Schönflies i Lebesgue afirmen que tot recobriment obert d’un interval [a, b] admet un subrecobriment finit. Com en molts altres teoremes importants, la conclusió del teorema ha esdevingut la definició d’un nou concepte, el d’espai (bi)compacte. Desprendre la propietat de Heine-Borel dels recobriments dels intervals del teorema Bolzano-Weierstrass fins a consolidar la definició d’espai compacte no va ser immediat. D’una banda, hem vist com sorgeix aquesta propietat per a recobriments numerables en la tesi de Borel. Per a Borel, el teorema permetia en certes situacions provar l’existència de punts d’un interval fora d’una unió numerable de subintervals, i el va utilitzar en la seva proposta de teoria de la mesura definida a partir de recobriments numerables i no pas finits, com els que s’empraven en la definició de contingut de Jordan. D’altra banda, l’anàlisi dels espais de funcions o la de les varietats geomètriques de Riemann aconsellaven estudiar espais generals en què es pogués definir la continuïtat d’una funció i, en particular, caracteritzar aquells espais en els quals les funcions contínues estan fitades i assoleixen els seus extrems. Fréchet va desenvolupar uns espais abstractes propers a l’anàlisi i va proposar la definició d’espai compacte basant-se en la propietat de Bolzano-Weierstrass dels intervals. A més, va relacionar la compacitat amb el teorema de Borel. Per la seva banda, Hausdorff va desenvolupar una teoria més geomètrica, la dels espais topològics, a la qual va estendre els resultats sobre espais compactes de Fréchet. Alexandroff i Urysohn van tancar el cercle amb la noció d’espai bicompacte, deslligant els espais compactes de formacions numerables, i analitzant aquesta nova categoria d’espais d’una manera profunda i sistemàtica. Finalment, el treball de Tychonoff confirmava la rellevància dels espais bicompactes, importància que no deixaria de créixer en anys posteriors. Sovint els estudiants dels cursos de grau troben difícil d’entendre la definició d’espai compacte mitjançant la propietat de Heine-Borel; pensem que conèixer l’origen de la noció de compacitat i el camí seguit fins a consolidar-la pot ajudar-nos en la presentació que en fem a classe.

Agraïments La segona autora ha estat parcialment finançada pel Ministeri d’Economia i Competitivitat, HA2016-75871-R. El tercer autor ha estat parcialment finançat per l’Agència de Gestió d’Ajuts Universitaris i de Recerca, 2017SGR-932 i el Ministeri de Ciència i Innovació, 2015-069135P.

Júlia Moreno, Mònica Blanco i Pere Pascual

Referències [1] Alexandroff, P. «Zur Begründung der n-dimensionalen mengentheoretischen Topologie». Math. Ann., 94 (1) (1925), 296–308. [2] Alexandroff, P.; Urysohn, P. «Sur les espaces topologiques compacts». Bull. Acad. polon. (A) (1923), 5–8. [3] Alexandroff, P. S.; Urysohn, P. S. «Mémoire sur les espaces topologiques compacts». Verhandelingen der Koninklijke (Nederlandse) Akademie van Wetenschappen, Afdeeling Natuurkunde, Sectie 1, 14 (1929), 93 p. [4] Andre, N. R.; Engdahl, S. M.; Parker, A. E. «An analysis of the first proofs of the Heine-Borel Theorem». Convergence. MAA Publications, (2013). [5] Arboleda, L. C. «Introducción de la topología de vecindades en los trabajos de Fréchet y Hausdorff». Rev. Acad. Colombiana Cienc. Exact. Fís. Natur., 41 (161) (2017), 528–537. [6] Borel, É. «Sur quelques points de la théorie des fonctions». Ann. Sci. École Norm. Sup. (3), 12 (1895), 9–55. [7] Borel, É. Leçons sur la théorie des fonctions. París: Gauthier-Villars et fils, 1898. [8] Bourbaki, N. Éléments de mathématique. Topologie générale. Chapitres 1 à 4. París: Hermann, 1971. [9] Cameron, D. E. «The birth of Soviet topology». Topology Proc., 7 (2) (1982), 329–378. [10] Čech, E. «On bicompact spaces». Ann. of Math. (2), 38 (4) (1937), 823–844. [11] de Possel, R. «Espaces topologiques». Séminaire de Mathématiques (Julia), 3 (1935–1936), exp. no 1, 1–18. [12] Dieudonné, J. «Une généralisation des espaces compacts». J. Math. Pures Appl. (9), 23 (1944), 65–76. [13] Dieudonné, J. History of Functional Analysis. Amsterdam-Nova York: North-Holland Publishing Co., 1981. [Notas de Matemática; 77] (NorthHolland Mathematics Studies; 49) [14] Dugac, P. «Sur la correspondance de Borel et le théorème de DirichletHeine-Weierstrass-Borel-Schoenflies-Lebesgue». Arch. Internat. Hist. Sci., 39 (122) (1989), 69–110. [15] Fréchet, M. «Généralisation d’un théorème de Weierstrass». C. R. Acad. Sci. Paris Sér. I Math., 139 (1904), 848–850. [16] Fréchet, M. M. «Sur quelques points du calcul fonctionnel». Rend. Circ. Mat. Palermo, 22 (1906), 1–72. [17] Fréchet, M. Les espaces abstraits et leur théorie considérée comme introduction à l’analyse générale. París: Gauthier Villars, 1928. [18] Graham, L.; Kantor, J.-M. Naming Infinity. A true story of religious mysticism and mathematical creativity. Cambridge, MA: The Belknap Press of Harvard University Press, 2009. [Traducció al castellà: El nombre del

Evolució de la noció de compacitat

infinito. Un relato verídico de misticismo religioso y creatividad matemática. Barcelona: Acantilado, 2012] [19] Hadamard, J. «Sur certains applications possibles de la théorie des ensembles». A: Proceedings of the First International Congress of Mathematicians. Zuric: Teubner Verlag, 1899, 201–202. [20] Hallett, M. «Towards a theory of mathematical research programmes. I». British J. Philos. Sci., 30 (1) (1979), 1–25. [21] Hausdorff, F. Grundzüge der Mengenlehre. Leipzig: Verlag Von Veit & Comp., 1914. [22] Hausdorff, F. Set Theory. Nova York: Chelsea Publishing Company, 1957. [Traduït per John R. Aumann et al.] [23] Hawkins, T. Lebesgue’s Theory of Integration: Its Origins and Development. Nova York: Chelsea Publishing Co., 1975. [Reimpressió de l’original] [24] Hilbert, D. «Ueber die Grundlagen der Geometrie». Math. Ann., 56 (3) (1902), 381–422. [25] Hildebrandt, T. H. «The Borel theorem and its generalizations». Bull. Amer. Math. Soc., 32 (5) (1926), 423–474. [26] Kuratowski, C.; Sierpiński, W. «Le théorème de Borel-Lebesgue dans la théorie des ensembles abstraits». Fund. Math., 2 (1921), 172–178. [27] Lebesgue, H. L. Leçons sur l’intégration et la recherche des fonctions primitives, professées au Collège de France. París: Gauthier-Villars, 1904. [28] Manheim, J. H. The Genesis of Point Set Topology. Oxford-París-Frankfurt: Pergamon Press; Nova York: The Macmillan Co., 1964. [29] Maurey, B.; Tacchi, J.-P. «La genèse du théorème de recouvrement de Borel». Rev. Histoire Math., 11 (2) (2005), 163–204. [30] Moore, G. H. «The emergence of open sets, closed sets, and limit points in analysis and topology». Historia Math., 35 (3) (2008), 220–241. [31] Moreno, J. «Gènesi del concepte d’espai compacte (1895–1925)». Treball de fi de grau. Facultat de Matemàtiques i Estadística, UPC, maig 2019. [32] Munkres, J. Topología. 2a ed. Madrid: Prentice Hall, 2002. [33] Novák, J. «On the Cartesian product of two compact spaces». Fund. Math., 40 (1953), 106–112. [34] Pier, J. «Genèse et évolution de l’idée de compact». Revue d’histoire des sciences et de leurs applications, 14 (2) (1961), 169–179. [35] Pier, J.-P. «Historique de la notion de compacité». Historia Math., 7 (4) (1980), 425–443. [36] Poincaré, H. «Sur les fonctions à espaces lacunaires». Acta Societatis scientiarum Fennicae, 12 (1883), 343–350; Amer. J. Math., 14 (3) (1892), 201–221. [37] Raman-Sundström, M. «A pedagogical history of compactness». Amer. Math. Monthly, 122 (7) (2015), 619–635.

Júlia Moreno, Mònica Blanco i Pere Pascual

[38] Schönflies, A. «Sur un théorème de Heine et un théorème de Borel». C. R. Acad. Sci. Paris Sér. I Math., 144 (1907), 22–23. [39] Taylor, A. E. «A study of Maurice Fréchet. I. His early work on point set theory and the theory of functionals». Arch. Hist. Exact Sci., 27 (3) (1982), 233–295. [40] Tychonoff, A. «Über die topologische Erweiterung von Räumen». Math. Ann., 102 (1) (1930), 544–561. [41] Tychonoff, A. «Ein Fixpunktsatz». Math. Ann., 111 (1) (1935), 767–776. [42] Urysohn, P. «Zum Metrisationsproblem». Math. Ann., 94 (1) (1925), 309–315. [43] Weil, A. «Sur les espaces à structure uniforme et sur la topologie générale». París: Hermann & cie, 1937. (Publications de l’Institut de mathématique de l’Université de Strasbourg; 1. Actualités scientifiques et industrielles; 551) [44] Weyl, H. Die Idee der riemannschen Fläche. Leipzig: B. G. Teubner, 1913. [45] Wright, D. G. «Tychonoff’s theorem». Proc. Amer. Math. Soc., 120 (3) (1994), 985–987. [46] Young, W. H.; Young, G. C. The Theory of Sets of Points. Cambridge: Cambridge University Press, 1906.

Júlia Moreno julsmorenomontes@gmail.com Mònica Blanco, Pere Pascual Departament de Matemàtiques Universitat Politècnica de Catalunya 08028 Barcelona {monica.blanco,pere.pascual}@upc.edu

Butlletí de la Societat Catalana de Matemàtiques Vol. 35, núm. 1, 2020. Pàg. 57–79. DOI: 10.2436/20.2002.01.93

Límits de grafs Oriol Serra

Resum: La teoria dels límits de grafs es va desenvolupar la primera dècada del segle xxi amb l’objectiu de donar un model matemàtic de les grans xarxes que han aparegut amb l’eclosió d’Internet i que també són presents a la biologia, la física, la medicina o les ciències socials. La creació d’aquesta teoria ha estat liderada pel matemàtic hongarès László Lovász, que el febrer del 2019 va rebre el Premi Europeu de Ciència Hipàtia atorgat pel Barcelona Knowledge Hub de l’Academia Europaea. En aquest article es descriuen les nocions i resultats bàsics de la teoria de límits de grafs. Paraules clau: grans xarxes, teoria de grafs, grafons, combinatòria extremal. Classificació MSC2010: 05C35, 05C25, 05C80, 05C82, 90B15.

Introducció

En el moment d’escriure aquest article, la pàgina https://www.internet livestats.com/ indica que hi ha 1705 226 930 pàgines web actives i 4300 014 560 usuaris d’Internet. Xarxes d’aquesta mida no són infreqüents a la natura. S’estima que al cervell humà hi ha uns 100 miliards (100 × 109 ) de neurones. En deu grams de diamant hi ha uns 1023 àtoms cohesionats per una xarxa d’interaccions químiques, enriquides per una ínfima proporció d’impureses que caracteritzen el seu comportament. Tant des del punt de vista tecnològic com científic, el repte de tractar, entendre o gestionar xarxes amb un nombre molt gran de nodes s’ha convertit en un objectiu prioritari. La teoria de grafs ofereix un model matemàtic natural per a les xarxes d’interconnexió. Un graf és un parell G = (V , E) format per un conjunt V , els elements del qual s’anomenen vèrtexs o nodes, i un conjunt E de parells de vèrtexs, anomenats arestes. Un graf és un objecte matemàtic que formalitza les relacions binàries entre elements d’un conjunt. L’origen de la noció matemàtica de graf se situa en la solució que va donar Euler el 1736 a l’anomenat problema dels ponts de Königsberg, un problema de naturalesa topològica i combinatòria; vegeu, per exemple, [1]. El desenvolupament de la teoria de grafs es va produir sobretot al segle xx, impulsat d’una manera especial pel progrés de les ciències

Oriol Serra

de la computació, però també per la seva versatilitat com a model natural en moltes àrees de la matemàtica, les ciències i la tecnologia. El matemàtic hongarès László Lovász va ser un dels protagonistes del desenvolupament de la teoria de grafs en la segona meitat del segle xx, pel fet d’establir relacions profundes amb altres àrees de la matemàtica, com la topologia, la geometria, la probabilitat, l’àlgebra, l’anàlisi o l’optimització. Quan era professor a la Universitat de Yale, va acceptar una proposta per a incorporar-se al Theory Group of Microsoft Research a Redmond (Washington), on des del 1996 fins al 2006 va liderar el projecte de creació de la teoria matemàtica dels límits de grafs, esperonat pel repte de proporcionar una eina matemàtica per a l’anàlisi de grans xarxes. El resultat d’aquesta aventura està recollit en una extensa monografia, Large Networks and Graph Limits [11], publicada el 2012 per l’American Mathematical Society, i que està tenint un impacte enorme en l’estudi de les grans xarxes. El text estableix d’una banda el context teòric que ha esdevingut definitiu i, de l’altra, planteja diverses direccions de desenvolupament de la teoria que formen un projecte de recerca de gran abast. Entre les múltiples distincions, premis i reconeixements que Lovász ha obtingut en la seva carrera professional com a matemàtic, trobem el Premi Europeu de Ciència Hipàtia, en la seva primera edició el 2019, instituït pel projecte conjunt de la Barcelona Knowledge Hub de l’Academia Europaea.

L’alcadessa de Barcelona Ada Colau en l’entrega del Premi Hipàtia a László Lóvasz el 5 de febrer del 2019.

En el seu discurs d’acceptació, Lovász va expressar el seu convenciment que l’anàlisi de grans xarxes serà un dels motors del desenvolupament científic i tecnològic en les properes dècades. Entre les moltes aplicacions naturals de la teoria a les ciències de la computació, l’enginyeria, la biologia o la física, va aventurar que les eines d’anàlisi de grans xarxes havien de contribuir també a millorar el coneixement del món que ens envolta, vist des de l’òptica d’una immensa xarxa d’interaccions. Aquest article vol oferir una introducció a la teoria de límits de grafs, esbossant les intuïcions que hi ha darrere l’elecció de les seves nocions bàsiques i descrivint els resultats més bàsics de convergència de grafs.

Límits de grafs

Per tal de presentar una visió global, hem optat per descriure la línia argumental que porta a les nocions bàsiques i hem obviat algunes de les demostracions que, o bé tenen una naturalesa molt tècnica, o bé tenen una complexitat que excedeix el format d’un article d’exposició com aquest. Dit això, hem volgut recollir tots els elements que condueixen a la definició de successions convergents de grafs i els seus límits, i presentar les proves d’alguns dels teoremes clau en aquesta teoria. La teoria va molt més enllà del que s’exposa en aquest article. Les prop de cinc-centes pàgines de la monografia de Lovász [11], escrites amb la seva usual claredat i transparència, donen una perspectiva molt més àmplia del tema i són una referència excel.lent per a qualsevol lector interessat en el tema. Hi ha també exposicions més succintes que poden resultar útils, com les notes de Dan Král’ [9] o l’article expositiu d’Andrzej Grzesik i Dan Král’ [5]. Per situar el context, cal dir que hi ha dues teories generals de límits de grafs: la dels grafs anomenats densos i la dels grafs dispersos. Aquí ens centrarem només en la primera classe, grafs en els quals el nombre d’arestes és una proporció positiva del nombre total possible d’arestes. Si G és un graf amb n = |V | vèrtexs, aleshores el nombre de possibles parells de vèrtexs és n 2 ∼ n2 /2. Els grafs densos tenen cn2 arestes per a alguna constant 0 < c < 1/2. Com que l’objectiu és tractar límits, aquestes afirmacions s’han d’entendre des del punt de vista asimptòtic. Els grafs dispersos, en canvi, tenen una quantitat subquadràtica d’arestes. No totes les grans xarxes es corresponen amb grafs densos, i alguns dels casos més interessants justament no ho són. Tot i així, la teoria de límits de grafs densos il.lustra d’una manera efectiva els problemes que es plantejen i el tipus de resultats que es persegueixen. D’altra banda, els grafs són només un dels objectes combinatoris, potser el més simple, per al qual s’ha desenvolupat la teoria. L’objectiu general és establir una noció de límits d’estructures combinatòries, que inclouen permutacions, hipergrafs o complexos simplicials, entre d’altres. Fins i tot en l’àmbit dels grafs hi ha variants, com ara grafs etiquetats, grafs acolorits, grafs dirigits o grafs signats, que tenen un interès especial en les aplicacions. La teoria dels límits d’estructures combinatòries ha estat estesa a cadascun dels exemples mencionats prenent com a base la teoria dels límits de grafs. En l’article es fa servir terminologia estàndard de teoria de grafs. El text de Reinhard Diestel [2] n’és una referència excel.lent. La majoria dels termes estan definits quan es fan servir per primera vegada. D’altres s’avenen a interpretacions naturals i confiem que el lector agrairà que s’obviïn algunes definicions formals. Per exemple, una aresta d’un graf és un parell de vèrtexs, i es diu també que l’aresta uneix els dos vèrtexs, que aquests li són incidents i que els dos vèrtexs són adjacents, totes elles denominacions que reflecteixen la representació gràfica usual d’un graf en el pla, en la qual els vèrtexs són punts i les arestes, arcs simples que els uneixen. Un graf es pot definir sobre qualsevol conjunt, discret o no. En la teoria de grafs clàssica, hi ha molts problemes que tracten grafs amb conjunts de vèrtexs no numerables, per exemple, grafs geomètrics en espais euclidians.

Oriol Serra

A continuació, però, assumirem sempre que els grafs tenen un conjunt finit de vèrtexs. De fet, és usual imaginar que el terme Gn d’una successió de grafs (Gn : n ∈ N) té n vèrtexs. La teoria de límits de grafs fa referència a successions de grafs en què les successions de nombres de vèrtexs dels termes de la successió no són fitades. El primer objectiu de la teoria és definir una bona noció de convergència d’una successió de grafs i identificar un objecte matemàtic adient per a la noció de límit d’una successió convergent.

Grafons

La noció de límit ha resultat fonamental en el desenvolupament de la matemàtica, ja que ha permès passar de l’enumeració a la mesura, del discret al continu. El conjunt de nombres reals és un concepte ideal construït a través de la noció de límit que, si bé té un referent difós a la natura i és sobretot una construcció intel.lectual, ha resultat d’una utilitat extraordinària. En la història de la matemàtica, la noció de límit ha estat estesa a objectes més complexos que els conjunts de nombres, com ara funcions, espais, estructures algebraiques, etc. El bagatge analític proporciona les eines necessàries per a saber entendre i manipular límits d’objectes matemàtics complexos. En el cas dels límits d’estructures combinatòries la novetat està en el fet que, tot i els precedents en el món de les estructures aleatòries discretes, no s’havia plantejat explícitament quins són els objectes límit adequats per a aquestes estructures. Un dels objectius de la teoria de límits de grafs és capturar en un objecte límit algunes de les propietats raonables que pot interessar estudiar en l’anàlisi de grans xarxes: qüestions relatives a la connectivitat, l’existència de subestructures, la distribució de les arestes, particions de nodes amb graf quocient estructurat, etc. Per exemple, no té gaire sentit preguntar-se per la paritat del nombre de nodes o l’existència d’un nombre específic de triangles. En el cas dels grafs, que descriuen relacions binàries en un conjunt, la definició de límit que resulta natural és la següent: Definició 1 (Grafó). Un grafó és una funció mesurable (entès sempre respecte de la mesura de Lebesgue) W : [0, 1] × [0, 1] → [0, 1], que és simètrica en les seves variables: W (x, y) = W (y, x) per a tot (x, y) ∈ [0, 1] × [0, 1]. El nom grafó prové de la contracció de graf i funció. Denotem per W0 l’espai d’aquestes funcions, és a dir, l’espai de funcions simètriques de L∞ ([0, 1] × [0, 1]) que prenen valors a [0, 1]. Donat un graf G, es pot definir un grafó assocïat a G de la manera següent. Si G té un conjunt de vèrtexs {1, 2, . . . , n}, considerem una partició de [0, 1] en intervals I1 = [0, 1/n), I2 = [1/n, 2/n), . . . , In = [(n − 1)/n, 1] de la mateixa mida. Denotem per WG el grafó ( 1 (x, y) ∈ Ii × Ij , {i, j} ∈ E(G), WG (x, y) = 0 (x, y) ∈ Ii × Ij , {i, j} 6∈ E(G).

Límits de grafs

De fet, qualsevol partició de [0, 1] en n intervals, o n conjunts mesurables, serviria per a fer aquesta associació, però la nostra notació per al grafó WG estarà relacionada amb una equipartició de l’interval. A la figura 1 s’il.lustra aquesta associació per al cas del graf bipartit complet K5,5 , en què el conjunt de vèrtexs està partit en dos subconjunts de cinc vèrtexs cadascun i les seves arestes són tots els parells amb un vèrtex a cada part. 1 1

Figura 1: El graf bipartit complet K5,5 i el seu grafó associat. Així doncs, a cada graf se li pot associar un grafó de manera natural, que pren valors a {0, 1}. Veurem que en la definició de convergència de grafs no n’hi ha prou amb els grafons que prenen valors a {0, 1}. Totes les funcions de W0 són necessàries per a completar l’espai dels grafs. Una manera gràfica de relacionar grafs i grafons s’obté a través de la matriu d’adjacència del graf. Si G = (V , E) és un graf amb un conjunt de vèrtexs V = {1, 2, . . . , n}, la matriu d’adjacència de G és una matriu quadrada A = A(G) d’ordre n amb entrades a {0, 1}, on Ai,j val 1 si {i, j} és una aresta del graf i Ai,j = 0 altrament. La figura 2 il.lustra el graf complet bipartit K5,5 i la seva matriu d’adjacència. 0 0  0   0  0  1  1   1  1 1 

0 0 0 0 0 1 1 1 1 1

1 1 1 1 1 0 0 0 0 0

 1 1  1   1  1  0  0   0  0 0

Figura 2: El graf bipartit complet K5,5 , la seva matriu d’adjacència i el grafó complet bipartit.

Oriol Serra

Més endavant veurem que la successió {Kr ,r , r ∈ N} de grafs bipartits complets és convergent i té per límit el grafó bipartit complet WK1,1 definit com

W (x, y) =

( 1 0

(x, y) ∈ [0, 1/2) × [1/2, 1], altrament.

S’obté una representació gràfica d’un grafó dibuixant al quadrat [0, 1]×[0, 1] les imatges com a punts del blanc (0) al negre (1) passant per diferents intensitats de grisos per a valors a (0, 1). D’aquesta manera es pot interpretar el grafó com un límit de les matrius d’adjacència quan l’ordre n de la matriu tendeix a infinit. Amb aquesta representació, el grafó bipartit complet està representat a la figura 2 (observem que, respectant la notació matricial, el sentit creixent de l’ordenada és de dalt a baix). Una altra manera de relacionar grafs i grafons ve donada pels grafs aleatoris. L’anomenat graf aleatori d’Erdős-Rényi d’ordre n i probabilitat p, G(n, p), s’obté posant cada aresta {i, j} independentment amb probabilitat p en el conjunt de vèrtexs {1, 2, . . . , n}. Per a p = 1/2 és fàcil comprovar que l’objecte aleatori que resulta correspon a escollir aleatòriament amb la distribució uniforme un graf entre tots els possibles grafs de n vèrtexs. A cada grafó W se li pot associar un graf aleatori GW de n vèrtexs de la manera següent. Un W -graf aleatori d’ordre n és el graf GW que té per conjunt de vèrtexs n punts x1 , . . . , xn escollits independentment amb la distribució uniforme a [0, 1], i posant cada aresta {xi , xj } a GW amb probabilitat W (xi , xj ) independentment. Quan W és un grafó constant, W ≡ p, aleshores GW és el graf aleatori G(n, p). Veurem que la successió {G(n, 1/2) : n ∈ N} de grafs aleatoris amb p = 1/2 convergeix al grafó W ≡ 1/2. La figura 3 il.lustra una possible realització del graf aleatori G(6, 1/2) i el grafó W ≡ 1/2. 2

1 0 1  1   0  1 0 

1 0 0 1 0 0

1 0 0 0 0 1

0 1 0 0 0 1

1 0 0 0 0 0

 0 0  1   1  0 0

Figura 3: Una realització del graf aleatori G(6, 1/2), la seva matriu d’adjacència i el grafó W ≡ 1/2. A continuació es donarà una noció natural de convergència de successions de grafs i es veurà que els grafons són els objectes límit naturals per a aquesta noció.

Límits de grafs

Homomorfismes de grafs

La definició dels grafons com a objectes naturals de límits de successions de grafs té diverses justificacions. Una de les més il.lustratives prové de la noció d’homomorfisme de grafs. Donats dos grafs G i H, una aplicació f : V (G) → V (H) és un homomorfisme de grafs si respecta les adjacències: per a cada aresta {x, y} de G, {f (x), f (y)} és una aresta de H. Aquesta és la noció natural de morfisme en la categoria dels grafs. Si hi ha un homomorfisme del graf G al graf H, escrivim G → H. Observem que un homomorfisme f : G → H pot enviar un parell {x, y} que no és una aresta de G a un parell {f (x), f (y)} que pot ser o no una aresta de H. 0

1 7

0,5

-→ 6

2 1,4

3 6 5

Figura 4: Un homomorfisme del cicle C8 al graf de la dreta. Si f : G → H és un homomorfisme bijectiu tal que el seu invers és també un homomorfisme, aleshores f és un isomorfisme i els grafs G i H són isomorfs, és a dir, indistingibles llevat d’una permutació dels vèrtexs. Els homomorfismes permeten descriure moltes de les propietats d’un graf. Per exemple, si Kk denota el graf complet amb k vèrtexs (tots els parells de {1, 2, . . . , k} són arestes de Kk ), aleshores Kk → G indica que el graf G conté una clica d’ordre k (un subgraf de G isomorf a Kk ). D’altra banda, G → Kk indica que G admet una k-coloració pròpia, és a dir, una partició dels vèrtexs de G en k parts de manera que cada part indueix un subgraf sense arestes. En altres paraules, si f : G → Kk és un homomorfisme i acolorim cada vèrtex x ∈ V (G) amb el «color» f (x), cada aresta de G és incident amb vèrtexs de colors diferents (no hi ha arestes monocromàtiques). Un graf G que és 2-acolorible es diu que és un graf bipartit: el conjunt de vèrtexs de G admet una partició en dues parts de manera que les arestes de G tenen un sol vèrtex a cada part. No és difícil comprovar que si G és un graf bipartit connex (cada parell de vèrtexs es pot unir per una successió de vèrtexs cadascun adjacent al següent), aleshores la bipartició és única. La complexitat algorísmica del problema de decidir, donats dos grafs G i H, si G → H, reflecteix la complexitat dels homomorfismes. Si el graf de sortida G és fixat, decidir per a cada H si G → H és un problema que es pot resoldre en temps que és polinòmic en la mida de l’entrada H del problema. Més específicament, el problema és polinòmic en el nombre n = |V (H)| de vèrtexs de H: només cal inspeccionar cadascuna de les aplicacions de V (G) → V (H), de les quals n’hi ha n|V (G)| (una quantitat polinòmica en n) i comprovar si és un homomorfisme. Un teorema cèlebre de Pavol Hell i Jaroslav Nešetřil ([6])

Oriol Serra

estableix que, si fixem el graf d’arribada H, el problema de decidir per a cada G si G → H és polinòmic en la mida n = |V (G)| de l’entrada del problema només si H és bipartit, i és en canvi NP-complet si H no és bipartit. Per als lectors no familiaritzats amb la complexitat algorísmica, n’hi ha prou de saber que la classe de problemes NP-complets es considera a la cúspide d’una jerarquia de dificultat en la resolució d’una àmplia classe de problemes de manera algorísmica. Segons el teorema, doncs, per a H fix, decidir si G → H és o bé senzill o bé molt difícil. Per això el resultat és conegut com la dicotomia dels homomorfismes. La monografia [7] dels mateixos autors és una referència excel.lent sobre homomorfismes de grafs. Denotem per Hom(G, H) el conjunt de tots els homomorfismes de G en H i amb hom(G, H) el seu nombre. Ocasionalment serà útil considerar només homomorfismes injectius, el nombre dels quals es denota per inj(G, H). També serà útil el nombre dels homomorfismes injectius que respecten la no adjacència, és a dir, homomorfismes injectius f : G → H tals que, per a cada parell de vèrtexs x, y de G, la imatge {f (x), f (y)} és una aresta de H si, i només si, {x, y} és una aresta de G. En aquest cas, f (G) és un subgraf induït de H, és a dir, hi ha un subconjunt de vèrtexs U ⊂ V (H) tal que el subgraf H[U ] de H format pels vèrtexs de U és isomorf a G. Diem aleshores que f és una immersió de G en H i denotem per ind(G, H) el nombre d’immersions de G en H. Les tres quantitats, hom(G, H), inj(G, H) i ind(G, H), estan relacionades entre elles. Per exemple, X inj(G, H) = ind(G0 , H), G0 ⊇G

on el sumatori s’estén a tots els grafs G0 que contenen G amb el mateix conjunt de vèrtexs, i X hom(G, H) = inj(G/P , H), P

on el sumatori s’estén a totes les particions P del conjunt de vèrtexs de G i G/P denota el graf quocient, que té per vèrtexs els elements de P i dues parts són adjacents si hi ha una aresta de G que uneix un vèrtex de cada part. Les relacions inverses es poden obtenir fent servir la fórmula d’inversió de Möbius. Per a un graf G, el conjunt de nombres hom(·, G) = {hom(H, G) : H ∈ G}, on G és la classe de tots els grafs, s’anomena perfil de G per l’esquerra. De manera anàloga, hom(G, ·) = {hom(G, H) : H ∈ G} és el perfil de G per la dreta. Un resultat rellevant, obtingut per Lovász fa més de cinquanta anys, és el següent. Teorema 2 (Lovász [10]). Els nombres hom(·, G) determinen G llevat d’isomorfisme. El mateix és cert per als nombres hom(G, ·). Prova. Si G i G0 tenen el mateix perfil per l’esquerra, se satisfà també que inj(H, G) = inj(H, G0 ), per a tots els grafs H. En particular, inj(G, G) = inj(G, G0 ) = inj(G0 , G) = inj(G0 , G0 ),

Límits de grafs

i tots quatre nombres són no nuls. Per tant, hi ha un homomorfisme injectiu de G en G0 i un de G0 en G. Així doncs, els dos grafs són isomorfs. Un argument semblant prova el cas del perfil per la dreta. 2 Els nombres hom(G, H) permeten expressar moltes de les propietats d’un graf. De l’extensa llista de relacions entre paràmetres de grafs i nombres d’homomorfismes, en donem només alguns exemples senzills (les denominacions dels grafs implicats estan il.lustrades a la figura 5). 1. Denotem per Sk l’estrella de k vèrtexs. El conjunt d’arestes de Sk és {{1, i} : i = 2, . . . , k − 1}. El grau d(x) d’un vèrtex x en un graf G és el nombre d’arestes de G que són incidents amb x. El nombre hom(Sk , G) dona els moments d’ordre k − 1 dels graus: X hom(Sk , G) = (d(x))k−1 . x∈V (G)

2. Denotem per Ck el cicle de k vèrtexs. El conjunt d’arestes de Ck és {{i, i+1 (mod k)} : i = 1, . . . , k}. Aleshores, hom(Ck , G) = tr(A(G)k ) =

n X

λki ,

i=1

on tr(A(G)) denota la traça de la matriu d’adjacència de G i λ1 , . . . , λn són els valors propis de A(G) (com que és real i simètrica, la matriu d’adjacència diagonalitza i té n valors propis reals). No és difícil comprovar que limk→∞ hom(C2k , G)1/2n existeix i que el seu valor és el valor propi més gran de A(G). 3. Si Kk denota el graf complet de k vèrtexs, hom(G, Kk ) és el nombre de coloracions pròpies de G. 4. Si H2 denota el graf complet K2 amb un llaç a un dels dos vèrtexs, aleshores hom(G, H2 ) és el nombre de conjunts estables de G, subconjunts U ⊂ V (G) tals que el subgraf induït per U no té cap aresta.

Figura 5: Exemples d’estrelles, cicles, grafs complets i H2 . Aquests exemples il.lustren com els nombres hom(H, G) recullen informació estructural del graf G en relació amb el graf H. L’estudi dels límits de grafs, però, no pot ser sensible només a la noció de grafs isomorfs, la qual cosa donaria una eina poc útil, sinó que ha de comportar un compromís entre propietats locals i propietats globals que puguin ser reflectides en el límit.

Oriol Serra

Convergència de successions de grafs

El paràmetre que ens interessarà de cara a formular la noció de convergència de grafs és la densitat d’homomorfismes. Si G és un graf amb n vèrtexs i H és un graf amb k vèrtexs, la densitat d’homomorfismes de H en G és t(H, G) =

hom(H, G) . nk

En altres paraules, t(H, G) és la probabilitat que una aplicació aleatòria de H en G sigui un homomorfisme. De manera anàloga es defineixen les densitats d’homomorfismes injectius i d’immersions, tinj (H, G) =

inj(H, G) (n)k

tind (H, G) =

ind(H, G) , (n)k

on (n)k = n(n−1) · · · (n−k+1) és el nombre d’aplicacions injectives de V (H) en V (G). En particular, tind (G, H) és la probabilitat que una aplicació aleatòria injectiva de V (H) en V (G) tingui com a imatge un subgraf induït de G isomorf a H, és a dir, una còpia de H en G. De la mateixa manera que els conjunts de nombres hom(·, G), hominj (·, G) i homind (·, G) estan relacionats entre ells, es pot obtenir cadascun dels conjunts t(·, G), tind (·, G) i tind (·, G) de qualsevol dels altres dos per relacions lineals entre els seus membres. A diferència dels nombres hom(·, G), els nombres de densitats t(·, G) no determinen el graf G llevat d’isomorfisme. El motiu és que, si se substitueix cada vèrtex de G per r còpies, mantenint les adjacències, aleshores el graf resultant té el mateix conjunt de densitats. Més precisament, donat un graf G i un enter positiu r , denotem per G(r ) el graf obtingut de G substituint cada vèrtex x ∈ V (G) per r vèrtexs x1 , . . . , xr , i xi , yj són adjacents a G(r ) si, i només si, x, y són adjacents a G. Es diu que G(r ) és un graf expandit de G. De la definició de densitat d’homomorfismes es pot comprovar fàcilment que t(·, G) = t(·, G(r )).

Figura 6: El graf K3 i el graf expandit K3 (2). No és difícil verificar que el recíproc també és cert: si t(·, G) = t(·, G0 ), aleshores G és isomorf a G0 (r ) per a algun r o viceversa, G0 és isomorf a G(r ) per a algun r .

Límits de grafs

Amb aquestes definicions es pot formular la noció de convergència d’una successió de grafs. Definició 3. Una successió de grafs (Gn : n ∈ N) amb limn→∞ |V (Gn )| = ∞ és convergent si, per a cada graf H, la successió (t(H, Gn ) : n ∈ N) és convergent. Recordem que els nombres t(·, G) de densitats d’homomorfismes i tind (·, G) de densitats d’immersions estan relacionats de manera que es poden obtenir l’un de l’altre. Per tant, una successió de grafs és convergent si, i només si, les successions tind (H, G) són convergents per a cada H. Aquesta és la intuïció que hi ha darrere la definició de convergència. Es mesura l’estructura d’un graf en termes dels estadístics dels subgrafs que conté. Si dos grafs tenen la mateixa densitat d’immersions d’un graf donat H, és a dir, el mateix nombre de còpies de H, aleshores els grafs són semblants en relació amb H. Si aquest és el cas per a tots els grafs H, aleshores els dos grafs són indistingibles. Per exemple, resulta immediat comprovar que la successió de grafs complets (Kn : n ∈ N) és convergent. Per a cada graf H, cada aplicació injectiva f : V (H) → V (Kn ) és un homomorfisme, de manera que tinj (H, Kn ) = 1 per a tot n i la successió (tinj (H, Kn ) : n ∈ N) és convergent. Un altre exemple és el dels grafs aleatoris G(n, p). Per a p ∈ (0, 1) i un graf H fixats, la probabilitat que una aplicació aleatòria injectiva f : V (H) → V (G(n, p)) sigui un homomorfisme és igual a p |E(H)| , per a n ≥ |V (H)|, i la successió tinj (H, G(n, p)) és convergent per a cada H. Un tercer exemple és la successió de grafs bipartits complets (Kn,n : n ∈ N). En aquest cas, si H no és bipartit, aleshores t(H, Kn,n ) = 0 per a tot n (un graf bipartit es caracteritza perquè conté un cicle imparell i la imatge per un homomorfisme d’un cicle imparell és un cicle imparell), mentre que si H és bipartit amb bipartició V (H) = A ∪ B, aleshores una aplicació f : V (H) → V (Kn,n ) és un homomorfisme si, i només si, envia A i B a parts diferents de V (Kn,n ), de manera que tinj (H, Kn,n ) = 1/2|A|+|B|−1 . La bipartició d’un graf bipartit és única només si el graf és connex, però una modificació de l’argument anterior fa veure que, per a qualsevol graf bipartit H, connex o no, t(H, Kn,n ) és una constant que depèn només de H per a tot n prou gran. Per tant, la successió (Kn,n : n ∈ N) és convergent. Observem que la definició de convergència que hem donat és rellevant només per a grafs densos. El motiu és que, en la normalització que s’ha fet servir en la definició de la densitat d’homomorfismes, si el nombre d’arestes dels termes de la successió és o(n2 ), aleshores t(H, Gn ) convergeix trivialment a zero per a cada H fixat. En altres paraules, si Gn és una successió de grafs dispersos, aleshores és trivialment convergent. Tot i que una noció de convergència adequada és suficient per a definir una teoria de límits, perquè una definició com aquesta sigui satisfactòria cal aclarir algunes qüestions. En primer lloc, quin és el significat d’aquesta convergència

Oriol Serra

en termes d’una mètrica adequada. Per tal que una successió de grafs sigui convergent, cal que els termes de la successió siguin semblants quan n és gran i que la seva distància respecte d’alguna mètrica tendeixi a zero. Quina és aquesta mètrica i què representa en termes de comparar dos grafs grans? En segon lloc, si una successió és convergent s’ha de poder identificar el límit i aquest ha de ser únic. Ja hem avançat que l’objecte límit és un grafó. Novament, cal definir una mètrica per la qual els termes d’una successió de grafs convergent estan a una distància cada vegada més petita d’un grafó. Finalment, si l’espai dels grafons ha de ser la compleció de l’espai dels grafs, cada grafó hauria de ser el límit d’una successió convergent de grafs. A continuació veurem com es dona resposta a aquestes preguntes.

La distància de tall

L’objectiu és definir una mètrica en l’espai G dels grafs que mesuri la diferència estructural entre dos grafs. Aquesta mètrica es defineix primer per a grafs sobre el mateix conjunt de vèrtexs i s’estén després a parells arbitraris de grafs. Una manera natural de comparar dos grafs és mesurar el nombre d’arestes que cal modificar per a transformar l’un en l’altre. Convenientment normalitzada, aquesta mesura dona lloc al que s’anomena distància d’edició. Donats dos grafs G, G0 amb el mateix conjunt de vèrtexs, la distància d’edició entre G i G0 és |E(G)∆E(G0 )| d1 (G, G0 ) = , n2 on ∆ denota la diferència simètrica de conjunts i n és el nombre de vèrtexs. Una mesura més sensible a l’estructura dels grafs és el que s’anomena distància de tall. Per a dos subconjunts de vèrtexs S, T denotem per eG (S, T ) = P a i∈S, j∈T ij , on aij és l’entrada de la matriu d’adjacència A(G), el nombre d’arestes que uneixen vèrtexs de S amb vèrtexs de T en el graf G. Comencem per definir el que s’anomena distància de tall etiquetada. Donats dos grafs G, G0 amb el mateix conjunt de vèrtexs, la distància de tall etiquetada entre G i G0 és δ2 (G, G0 ) =

|eG (S, T ) − eG0 (S, T )| , n2 S,T ⊂V (G) max

on n és el nombre de vèrtexs. No és difícil comprovar que d1 i δ2 són efectivament distàncies en el conjunt de grafs sobre el mateix conjunt de vèrtexs i que δ2 (G, G0 ) ≤ d1 (G, G0 ), tot i que les dues distàncies poden ser ben diferents. Des del punt de vista estructural, la distància entre dos grafs isomorfs hauria de ser zero. Resulta natural doncs definir, per a dos grafs G i G0 amb el mateix nombre de vèrtexs, la menor distància entre grafs isomorfs a l’un i a l’altre: δc2 (G, G0 ) = min0 0 δ2 (H, H 0 ). H G, H G

Límits de grafs

No és difícil comprovar que δc2 és una distància en el conjunt de classes de grafs isomorfs. És clar que δc2 (G, G0 ) ≤ δ2 (G, G0 ). Finalment, si G té n vèrtexs i G0 té n0 vèrtexs, aleshores els grafs expandits G(n0 ) i G0 (n) tenen el mateix nombre de vèrtexs, i els grafs G i G(n0 ) són estructuralment semblants. En particular, t(·, G) = t(·, G(n0 )). D’aquesta manera s’arriba a la definició de la distància de tall (cut-distance en anglès). Definició 4 (Distància de tall). La distància de tall entre dos grafs G i G0 és d2 (G, G0 ) = lim δc2 (G(kn0 ), G0 (kn)), k→∞

on n és el nombre de vèrtexs de G i n0 és el nombre de vèrtexs de G0 . La denominació distància de tall prové del fet que la distància es mesura en termes del nombre d’arestes que uneixen dos subconjunts S i T de vèrtexs, és a dir, del nombre d’arestes que s’han de tallar per a separar aquests dos conjunts en el graf. Una vegada més, es pot comprovar que d2 (G, G0 ) = 0 si, i només si, hi ha un graf H i dos nombres k, k0 tals que G H(k) i G0 H(k0 ), de manera que d2 és una distància en el conjunt de classes de grafs equivalents per a aquesta noció d’isomorfia. Equipats amb aquesta mètrica, es pot formular el teorema que dona resposta a la primera pregunta sobre successions convergents. Teorema 5. Sigui (Gn : n ∈ N) una successió de grafs convergent. Aleshores la successió és de Cauchy respecte de la distància de tall, és a dir, per a tot enter k, lim d2 (Gn , Gn+k ) = 0.

n→∞

Com passa en altres processos de compleció, la prova del teorema anterior és més abordable i transparent quan es pot fer referència al límit de la successió. Així doncs, abans de discutir la prova del teorema, discutirem com s’estén la mètrica de la distància de tall i les densitats d’homomorfismes als grafons.

Distància de tall entre grafons

La distància de tall es pot estendre de manera natural al conjunt de grafons. De fet, en el context dels grafons, les definicions són més transparents i els resultats més senzills de provar. Donats dos grafons W , W 0 , la distància de tall etiquetada entre W i W 0 és Z 0 δ2 (W , W ) = sup (W (x, y) − W 0 (x, y)) dx dy . S,T ⊂[0,1]

S×T

Oriol Serra

Com s’ha fet en el cas dels grafs, la distància hauria de reflectir una propietat estructural i ser, per tant, invariant per simetries. Anomenem S[0,1] el grup de funcions invertibles φ : [0, 1] → [0, 1] que preserven la mesura. Per a un grafó W i φ ∈ S[0,1] , denotem per W φ el grafó definit com W φ (x, y) = W (φ(x), φ(y)). Dos grafons W , W 0 són isomorfs si W 0 = W φ per a alguna φ ∈ S[0,1] . Per exemple, els grafons de la figura 7 són isomorfs a través de la transformació ( 1 − x x ∈ (1/4, 3/4), φ(x) = x altrament. De manera informal, tots dos són límits dels grafs complets bipartits, com s’ha suggerit a la figura 2.

Figura 7: Dos grafons isomorfs. Definició 6 (Distància de tall). Donats dos grafons W , W 0 , la distància de tall entre W i W 0 és d2 (W , W 0 ) =

inf

φ,φ0 ∈S[0,1]

δ2 (W φ , (W 0 )φ ).

Es pot provar que l’ínfim en la definició anterior és assolit per algun parell φ, φ0 ∈ S[0,1] . Amb una mica més de feina es pot provar també que dos grafons estan a distància zero si, i només si, són isomorfs. Així, d2 és una distància en el conjunt de classes d’isomorfia de grafons. Un resultat important és que l’espai mètric que en resulta és compacte. Teorema 7 (Lovász i Szegedy [12]). L’espai mètric dels grafons amb la distància de tall d2 és compacte.

Densitat de grafs en grafons

El darrer ingredient per a relacionar grafs i grafons és la densitat d’immersions d’un graf H en un grafó W . La idea és la mateixa que en la definició de la densitat d’immersions de H en un graf G: la densitat d’immersions mesura el nombre de còpies de H en W .

Límits de grafs

El que cal és definir què s’entén per una còpia de H en W . Recordem que, donat un grafó W , un W -graf aleatori d’ordre n és el graf que s’obté escollint n punts x1 , . . . , xn amb la distribució uniforme a [0, 1] i construint el graf GW amb n vèrtexs posant cada aresta {xi , xj } a G amb probabilitat W (xi , xj ) independentment. La mesura del nombre de còpies de H en W és la probabilitat que el graf GW d’ordre n = |V (H)| sigui isomorf a H; més precisament, tenim la definició següent. Definició 8 (Densitat). Donat un graf H amb un conjunt de vèrtexs {1, 2, . . . , n} i un grafó W , la densitat d’immersions de H en W és Z Y Y n! W (xi , xj ) (1−W (xi , xj )) dx1 · · · dxn . tind (H, W ) = |Aut(H)| [0,1]n ij∈E(H) ij6∈E(H) El terme n!/|Aut(H)| en la definició anterior té en compte les possibles n! immersions en un conjunt donat de n punts, normalitzat pel nombre |Aut(H)| d’automorfismes de H, que donen lloc a la mateixa còpia de H. La integral mesura la probabilitat que les arestes de H siguin presents en la immersió i que les no arestes de H no hi figurin. De la definició de grafons isomorfs es conclou fàcilment que si dos grafons W , W 0 són isomorfs, aleshores tind (H, W ) = tind (H, W 0 ), ja que les funcions invertibles que preserven la mesura deixen invariant la integral. De forma anàloga a com hem definit una successió convergent de grafs, es defineix la convergència d’una successió de grafs a un grafó. Definició 9 (Successió convergent). Una successió (Gn : n ∈ N) convergeix a un grafó W si la successió (tind (Gn , W ) : n ∈ N) és convergent. Veurem que la definició anterior és equivalent a la definició 3 de successions convergents de grafs, és a dir, que una successió de grafs és convergent segons la definició 3 si, i només si, hi ha un grafó W tal que la successió hi convergeix. Abans, però, veiem que cada grafó és el límit d’una successió convergent de grafs. Aquesta successió és precisament la dels W -grafs aleatoris d’ordre n associats al grafó W . La idea de la prova consisteix a anar revelant un a un els vèrtexs d’un W -graf aleatori per relacionar les quantitats t(H, Gn ) i t(H, W ) per a cada graf fixat H, on Gn és un W -graf aleatori d’ordre n. La prova fa servir una desigualtat de concentració per a martingales coneguda com la desigualtat d’Azuma-Hoeffding i el lema de Borel-Cantelli, que recordem a continuació. Una successió (Xn : n ∈ N) de variables aleatòries amb esperança finita sobre un espai de probabilitat és una martingala si, per a cada n > 1, l’esperança de Xn condicionada a X1 , . . . , Xn−1 és Xn−1 , és a dir, E(Xn |X1 , . . . , Xn−1 ) = Xn−1 .

Oriol Serra

Un cèlebre resultat de concentració en martingales amb valors de salt fitats és la desigualtat d’Azuma-Hoeffding (vegeu, per exemple, la monografia de Colin McDiarmid [14] sobre desigualtats de concentració). Teorema 10 (Azuma-Hoeffding). Sigui (Xn : n ∈ N) una martingala amb E(Xn ) = x0 i sigui cn una successió de nombres reals tals que Pr(|Xn − Xn−1 | ≤ cn ) = 1. Aleshores, per a cada nombre real positiu t i cada n ≥ 1 Pr(|Xn − x0 | ≥ t) ≤ e

−

t2 Pn c2 i=1 i

El lema de Borel-Cantelli és un resultat bàsic de teoria de probabilitat (i de teoria de la mesura) que es pot enunciar de la manera següent. Lema 11 (Borel-Cantelli). Sigui (An : n ∈ N) una successió d’esdeveniments en un espai de probabilitat. Si X

Pr(An ) < ∞,

n≥1

aleshores la probabilitat que se satisfaci una quantitat infinita d’esdeveniments de la successió és zero. A partir d’aquests resultats, es pot provar el teorema següent. Teorema 12. Sigui W un grafó. La successió Gn de grafs on cada Gn és un W -graf aleatori d’ordre n és convergent i el seu límit és W amb probabilitat 1. Prova. Fixem un graf H amb h = |V (H)| vèrtexs i n > h. Observem primer que, per la definició de Gn com a W -grafó i la definició de t(H, W ), la probabilitat que un subconjunt particular de h vèrtexs de Gn indueixi una còpia de H és t(H, W ). Definim ara una successió X0 , X1 , . . . , Xn de variables aleatòries, on Xi denota el nombre esperat de còpies de H en Gn quan s’han fixat i vèrtexs de Gn i les arestes del graf induït per aquests i vèrtexs en la construcció del W -graf aleaton n ri Gn . Per la linealitat de l’esperança, X0 = h t(H, W ) i Xn = h t(H, Gn ). Observem que E(Xi |Xi−1 ) = E(Xi−1 ), de manera que la successió de variables aleatòries és una martingala. D’altra banda, |Xi − Xi−1 | ≤ nh−1 per a cada i = 1, . . . , n, fitant generosament pel nombre possible d’aplicacions de [h] en [n] quan s’ha fixat almenys un punt. Fent servir la desigualtat d’AzumaHoeffding, per a cada nombre real positiu t, Pr(|Xn − X0 | ≥ t) ≤ 2e

−

t2 2n2h−1

Límits de grafs

Per a cada > 0, posant t = nh a la desigualtat anterior, s’obté 2

Pr(|Xn − X0 | ≥ nh ) ≤ 2e− n/2 . Utilitzant la fitació

n h

≥ nh /hh , obtenim finalment 2

Pr(|t(H, Gn ) − t(H, W )| ≥ hh ) ≤ 2e− n/2 . Pel lema de Borel-Cantelli, la successió t(H, Gn ) és convergent i el seu límit és t(H, W ) amb probabilitat 1. 2

El lema de regularitat

Per a concloure l’equivalència entre les nocions de convergència de successions de grafs i la convergència a un grafó, cal una darrera peça que enllaça amb la noció de distància de tall. Aquesta peça és un resultat celebrat de Szemerédi que ha tingut un impacte important en el desenvolupament de la combinatòria i la informàtica teòrica del segle xx i que forma part del reconeixement que li va valer el prestigiós Premi Abel al matemàtic hongarès Endre Szemerédi el 2012. L’anomenat lema de regularitat de Szemerédi estableix que, de qualsevol graf prou gran, se’n pot extreure una part estructurada i una part aleatòria. La manera explícita i quantitativa de descriure ambdues parts és el que dona força al teorema. Sigui G = (V , E) un graf. Per a cada parell de subconjunts disjunts X, Y ⊂ V denotem per eG (X, Y ) dG (X, Y ) = |X| · |Y | la densitat d’arestes del parell. Recordem que eG (X, Y ) denota el nombre d’arestes de G amb un vèrtex a X i un a Y , de manera que la densitat dG (X, Y ) és una mesura normalitzada del nombre d’arestes entre X i Y respecte del seu valor màxim |X| · |Y |. Si ens concentrem en el subgraf H = G[X ∪ Y ] induït per X ∪ Y , aleshores, per a cada U ⊂ X i W ⊂ Y , es pot mesurar la diferència entre dH (U , W ) i dH (X, Y ). Si les arestes de H estan ben repartides, aleshores aquesta diferència és petita, almenys si U i W són subconjunts prou grans (per a subconjunts petits no podem esperar que la diferència de densitats relatives sigui petita). Per a > 0 fixat, es diu que el parell (X, Y ) és -regular si, per a cada parell de subconjunts U ⊂ X i W ⊂ Y tals que |U | ≥ |X| i |W | ≥ |Y |, se satisfà |dH (U , W ) − dH (X, Y )| < . (1) El que expressa la desigualtat és que un parell -regular (X, Y ) té les arestes repartides de manera quasi aleatòria, en el sentit que la densitat de parells de subconjunts prou grans és pròxima al valor esperat en un graf aleatori amb bipartició {X, Y } i densitat d’arestes dH (X, Y ). Amb aquesta terminologia es

Oriol Serra

pot enunciar el lema de regularitat de Szemerédi [15]. Es diu que una partició V = V1 ∪ · · · ∪ Vr d’un conjunt V és una equipartició si totes les parts tenen aproximadament el mateix cardinal; més precisament, si ||Vi | − |Vj || ≤ 1 per a cada parell i, j. Teorema 13 (Lema de regularitat). Per a cada > 0 existeix un k = k( ) tal que qualsevol graf G = (V , E) admet una equipartició V = V1 ∪ · · · ∪ Vr amb 1/ < r < k( ) tal que tots els parells (Vi , Vj ) són -regulars llevat com a molt de r 2 parells. El lema de regularitat estableix que qualsevol graf prou gran admet una equipartició del conjunt de vèrtexs en un nombre, que depèn només de i no del graf, tal que gairebé tots els subgrafs induïts pels parells de parts són -regulars, és a dir, propers a un graf aleatori. Una partició amb aquesta propietat es diu que és una partició -regular. Per a grafs petits o grafs dispersos, es pot prendre la partició de G en vèrtexs aïllats i la descripció estructural resulta trivial (degut a la normalització en la definició de densitat d’un parell). Una de les conseqüències del lema de regularitat en termes de la distància de tall és la següent. Sigui {X, Y } un parell -regular en un graf G i denotem per GX∪Y el subgraf bipartit de G que té per conjunt de vèrtexs X ∪ Y i les arestes de G que uneixen X i Y . Anomenem G̃X∪Y el graf bipartit aleatori amb bipartició {X, Y } i densitat d’arestes dG (X, Y ). El fet que un parell sigui -regular es pot expressar en termes de la distància de tall com d2 (GX∪Y , G̃X∪Y ) < . Donada una partició P = (V1 , . . . , Vr ) del conjunt de vèrtexs V del graf G, denotem per GP el graf r -partit amb la mateixa partició tal que cada subgraf GP [Vi , Vj ] és un graf aleatori bipartit amb densitat d’arestes dG (Vi , Vj ) (cada aresta escollida independentment amb probabilitat p = dG (Vi , Vj )). El lema de regularitat implica que, per a cada > 0, hi ha una equipartició P de V en un nombre de parts que depèn només de tal que d2 (G, GP ) < 2 .

(2)

En aquesta desigualtat es té en compte que hi pot haver r 2 parells que no són -regulars, fet que queda absorbit escrivint 2 en lloc de a la fita superior. El lema de regularitat ha resultat ser una eina poderosa per a l’anàlisi de grans grafs i té múltiples aplicacions, en particular, en la prova del teorema de Szemerédi sobre l’existència de progressions aritmètiques en conjunts densos d’enters (vegeu, per exemple, [8] o l’article de Lugosi i Serra [13] en aquest mateix Butlletí ). Un dels inconvenients del lema de regularitat en les aplicacions, particularment a la teoria de límits de grafs, és la relació entre i k, ja que la fita superior 2 ··

per a k no pot ser millor que una torre exponencial 22 Gowers ([4]) va provar.

d’alçada 1/ , tal com

Límits de grafs

Alan Frieze i Ravi Kannan ([3]) van donar una versió més dèbil del lema de regularitat que recull la desigualtat (2) i que dona una relació molt més eficient entre k i . Aquesta versió és adequada per a la seva aplicació als límits de grafs. En termes de la distància de tall, la versió dèbil del lema de regularitat de Frieze i Kannan s’enuncia de la manera següent. Teorema 14 (Lema dèbil de regularitat). Per a cada enter positiu k, qualsevol graf G admet una equipartició P en k parts tal que 4 d2 (G, GP ) ≤ √ . k Frieze i Kannan van estendre el lema dèbil de regularitat també a l’espai dels grafons. Per a aquesta versió s’aproxima un grafó per un grafó esgraonat. Donada una partició P = {S1 , . . . , Sk } de [0, 1] en k conjunts mesurables, un grafó esgraonat és un grafó que és constant sobre Si × Sj per a cada i, j. Per exemple, donat un graf G, el grafó WG que s’ha definit a la secció 2 és un grafó esgraonat (que només pren valors a {0, 1}). Per a un grafó W i una partició P de [0, 1] en k conjunts mesurables de mesura no nul.la, denotem per WP el grafó esgraonat que sobre cada conjunt Si × Sj pren el valor mitjà de W sobre aquest conjunt: Z 1 WP |Si ×Sj ≡ W (x, y) dx dy, λ(Si )λ(Sj ) Si ×Sj on λ denota la mesura de Lebesgue. Teorema 15 (Lema dèbil de regularitat). Per a cada enter positiu k i qualsevol grafó W hi ha una partició P de [0, 1] en k conjunts mesurables de mesura no nul.la tal que 4 d2 (W , WP ) ≤ √ . k Una partició P de [0, 1] tal que d2 (W , WP ) < s’anomena una partició -regular de W . L’equivalència de nocions amb el cas dels grafs és clara, i l’enunciat en el cas dels grafons resulta més transparent.

Lema de regularitat i densitat d’immersions

La connexió entre les successions t(·, G) i t(·, W ), basades a comptar subgrafs en grafs o grafons, i el lema de regularitat es fonamenten en l’anomenat lema de comptatge, una de les aplicacions més notables del lema de regularitat. El lema de comptatge dona una aproximació del nombre de còpies de certs subgrafs de H en un graf G a través de particions regulars. Si P = {V1 , . . . , Vr } és una partició -regular de G, denotem per G̃P el graf aleatori r -partit que, per a cada parell de vèrtexs x, y en parts diferents Vi , Vj , conté l’aresta {x, y}

Oriol Serra

amb probabilitat d(Vi , Vj ). El nombre esperat de còpies d’un subgraf H de G/P a G̃P és aleshores r Y Y dG (Vi , Vj ) |Vr |. ij∈E(H)

i=1

La regularitat de la partició permet veure que el nombre de còpies de H en G és aproximadament aquest nombre esperat. Més precisament, el nombre ind(H, G) de còpies d’un subgraf H de G/P a G satisfà ind(H, G) −

Y ij∈E(H)

dG (Vi , Vj )

r Y i=1

|Vr | ≤ e(H)

r Y

|Vr |,

i=1

on e(H) és el nombre d’arestes de H. En termes de la densitat d’immersions, aquest lema es pot reformular de la manera següent. D’acord amb el lema dèbil de regularitat (teorema 14), per a cada > 0 hi ha una partició P de G tal que d2 (G, GP ) < amb un nombre de parts k = 1/ 2 . El següent enunciat dona, doncs, una forma en cert sentit més general del lema de comptatge. Teorema 16 (Lema de comptatge). Sigui H un graf. Per a dos grafs G, G0 se satisfà |t(H, G) − t(H, G0 )| ≤ e(H)d2 (G, G0 ). El lema de comptatge anterior s’estén de manera natural a densitat d’immersions en grafons (Lovász i Szegedy [12]). Teorema 17 (Lema de comptatge). Sigui H un graf. Per a dos grafons W , W 0 se satisfà |t(H, W ) − t(H, W 0 )| ≤ e(H)d2 (W , W 0 ). Aquest darrer resultat es pot expressar dient que, per a un graf H fixat, l’aplicació φ : W0 → [0, 1] W , t(H, W ) és de Lispschitz en l’espai mètric (W0 , d2 ). A més, es pot provar que l’aplicació és injectiva i té inversa contínua. Finalment, es pot enunciar el teorema, que és el nostre objectiu final. Teorema 18 (Lovász i Szegedy [12]). Sigui Gn una successió convergent de grafs. Existeix un grafó W tal que la successió convergeix a W . Prova. Pel teorema 7, l’espai dels grafons (W0 , d2 ) amb la distància de tall és compacte. D’altra banda, si G denota l’espai dels grafs finits, l’espai de seqüències {t(·, G) : G ∈ G} és isomorf a [0, 1]G×G , que també és compacte, pel teorema de Tijonov. L’aplicació W , (·, W ) és contínua pel teorema 17, i té inversa contínua. Si Gn és una successió convergent de grafs, aleshores la successió t(H, Gn ) és convergent per a cada H i t(H, WGn ) també ho és. Per la continuïtat de l’aplicació anterior, la successió WGn també és convergent a (W0 , d2 ). 2

Límits de grafs

Recapitulant el que s’ha exposat fins aquí, hem donat una definició de convergència de successions de grafs en termes de nombres d’immersions i hem definit una distància en l’espai dels grafs, la distància de tall, segons la qual una successió és convergent si, i només si, és de Cauchy respecte de la distància de tall. D’altra banda, hem definit la noció de convergència a un grafó i hem vist que cada grafó és el límit d’una successió de grafs i que la convergència es pot descriure en termes de la distància de tall. Finalment, hem constatat que cada grafó és el límit d’una successió de grafs. D’aquesta manera hi ha un marc sòlid per a estudiar límits de grafs densos.

Per acabar

En aquest article s’ha introduït la noció de límit d’una successió de grafs i els grafons com a objectes límit. Aquest és només l’inici d’una història molt més llarga que posa en acció aquesta noció per a obtenir resultats sobre l’anàlisi de grans xarxes. D’aquesta història se n’han escrit ja uns quants capítols, però en queden molts més per escriure. Els grafons són objectes en els quals es poden aplicar les poderoses eines de l’anàlisi matemàtica. Com passa sovint, molts problemes són més tractables en el continu que en el discret, i els resultats són sovint més compactes i transparents. D’altra banda, els grafons obren un nombre d’interrogants que segurament no es plantejarien des de la perspectiva discreta, problemes de naturalesa topològica i analítica, alguns dels quals han trobat fins ara respostes inesperades, que han enriquit l’univers dels objectes límit. Com ja hem comentat, la noció de grafó només resulta útil quan es consideren successions de grafs densos. En el cas dels grafs dispersos, amb un nombre subquadràtic d’arestes, la noció de límit s’ha de reformular d’una altra manera, en particular, per l’absència del lema de regularitat de Szemerédi per a aquesta classe de grafs. En aquest sentit, s’han proposat diverses alternatives per a la noció de convergència, en concret per a la classe de grafs en què el grau màxim dels vèrtexs és fitat. Aquesta classe no inclou, però, exemples importants de grafs, com els grafs plans o molts dels models de grans xarxes, en els quals la successió de graus dels vèrtexs segueix una llei potencial. En aquest sentit, la teoria està en plena expansió i s’aborda des d’angles molt diferents, des de la perspectiva de la probabilitat, de la lògica, de la topologia, de l’anàlisi o de l’àlgebra, cadascuna aportant eines i punts de vista substancials. Els desenvolupaments descrits en els paràgrafs anteriors estan exposats al text de Lovász [11] i alguns dels avenços més recents estan reflectits a l’article de Grzesik i Král’ [5], on el lector interessat trobarà material i referències abundants per a continuar aprofundint en aquesta apassionant aventura matemàtica. La importància científica de l’anàlisi matemàtica de grans xarxes ha estat reconeguda per l’European Research Council, que, en la seva convocatòria del 2018 en el programa «ERC Synergy Grants», finança el projecte Dynamics and Structure of Networks, liderat per Lászó Lovász, László Barabássy i Jaroslav

Oriol Serra

Nešetřil, l’únic projecte purament matemàtic en aquest programa estrella de la Unió Europea. De ben segur que en els propers anys la teoria dels límits de grafs tindrà una evolució substancial i, qui sap, es podrà fer realitat el somni de Lovász de contribuïr a entendre millor no solament les grans xarxes humanes, biològiques o tecnològiques, sino també el món que ens envolta i la seva immensa xarxa d’interaccions.

Referències [1] Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. Graph Theory. 1736–1936. 2a ed. Nova York: The Clarendon Press, Oxford University Press, 1986. [2] Diestel, R. Graph Theory. 5a ed. Berlín: Springer, 2018. (Graduate Texts in Mathematics; 173) [3] Frieze, A.; Kannan, R. «Quick approximation to matrices and applications». Combinatorica, 19 (2) (1999), 175–220. [4] Gowers, W. T. «Lower bounds of tower type for Szemerédi’s uniformity lemma». Geom. Funct. Anal., 7 (2) (1997), 322–337. [5] Grzesik, A.; Král’, D. «Analytic representations of large graphs». A: Surveys in Combinatorics 2019. Cambridge: Cambridge University Press, 2019, 57–88. (London Math. Soc. Lecture Note Ser.; 456) [6] Hell, P.; Nešetřil, J. «On the complexity of H-coloring». J. Combin. Theory Ser. B, 48 (1) (1990), 92–110. [7] Hell, P.; Nešetřil, J. Graphs and Homomorphisms. Oxford: Oxford University Press, 2004. (Oxford Lecture Series in Mathematics and its Applications; 28) [8] Komlós, J.; Shokoufandeh, A.; Simonovits, M.; Szemerédi, E. «The regularity lemma and its applications in graph theory». A: Theoretical Aspects of Computer Science. Berlín: Springer, 2002, 84–112. (Lecture Notes in Comput. Sci.; 2292) [9] Král’, D. «Graph limits and extremal graph theory». Curs a São Paulo School of Advanced Science on Algorithms, Combinatorics and Optimization (2016). [10] Lovász, L. «Operations with structures». Acta Math. Acad. Sci. Hungar., 18 (1967), 321–328. [11] Lovász, L. Large Networks and Graph Limits. Providence, RI: American Mathematical Society, 2012. (American Mathematical Society Colloquium Publications; 60) [12] Lovász, L.; Szegedy, B. «Limits of dense graph sequences». J. Combin. Theory Ser. B, 96 (6) (2006), 933–957. [13] Lugosi, G.; Serra, O. «Endre Szemerédi, Premi Abel 2012». Butlletí de la Societat Catalana de Matemàtiques, 28 (1) (2013), 87–115.

Límits de grafs

[14] McDiarmid, C. «Concentration». A: Probabilistic Methods for Algorithmic Discrete Mathematics. Berlín: Springer, 1998, 195–248. (Algorithms Combin.; 16) [15] Szemerédi, E. «Regular partitions of graphs». A: Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). París: CNRS, 1978, 399–401. (Colloq. Internat. CNRS; 260)

Departament de matemàtiques Universitat Politècnica de Catalunya 08034 Barcelona oriol.serra@upc.edu

Butlletí de la Societat Catalana de Matemàtiques Vol. 35, núm. 1, 2020. Pàg. 81–82

English summaries

Pere Ara The Banach-Tarski paradox and the type semigroup In this article we will study a key concept in relation to the well-known BanachTarski paradox. This is the concept of equidecomposability of subsets of a set X with respect to the action of a discrete group G. A subset E of X is G-paradoxical if there are two disjoint subsets E1 and E2 of E such that each of them is equidecomposable with E. The study of this relationship can be systematized by introducing a specific semigroup S(X, G), called the type semigroup of X. We will explain the use of the type semigroup S(X, G) in the proof of Tarski’s Theorem. We will also introduce some generalizations of this concept to a topological setting, and we will consider the problem of the validity of Tarski’s Theorem within this new context. In addition, we will review a recent result by Grabowski, Máthé and Pikhurko which gives a positive solution to the measurable circle squaring problem. Keywords: Banach-Tarski paradox, type semigroup, Tarski’s Theorem, topological space, circle squaring. MSC2010 Subject Classification: 43A07, 03E25, 20E05.

Júlia Moreno, Mònica Blanco and Pere Pascual Compactness, a seminal idea in the evolution of general topology (1895–1930) In this paper we analyze the evolution of the notion of compactness for topological spaces from its first appearance in a Fréchet 1904 paper generalising the Bolzano-Weierstrass property, encompassing its relationship with the Borel covering theorem for the interval [0, 1], and including the general definition based on the Heine-Borel property for arbitrary open covers in 1929. We focus our analysis on four key works: Borel’s thesis, Fréchet’s thesis, Hausdorff’s Grundzüge and Alexandroff-Urysohn’s memoire.

Keywords: complete accumulation point, open covering, compact space. MSC2010 Subject Classification: 01-02, 54-03.

Oriol Serra Graph limits The theory of graph limits was developed in the 2000s with the aim of creating a mathematical model of large networks. The need for such a model was mainly motivated by the emergence of the Internet with its huge network of interconnections, and large networks are also present in many scientific and technological areas, from biology, physics or social sciences to computer science, among others. László Lovász has been the main leader of the creative process behind this theory, and this was one of the reasons he was awarded the Hypatia European Prize in 2019 by the Barcelona Knowledge Hub of the Academia Europaea. In this paper, the basic notions and results of the theory of graph limits are presented and we offer a perspective on its main current developments. Keywords: large networks, complex networks, graph theory, extremal combinatorics. MSC2010 Subject Classification: 05C35, 05C25, 05C80, 05C82, 90B15.

Instruccions per als autors Els articles sotmesos a publicació s’han d’enviar als editors o a qualsevol membre del comitè editorial per correu electrònic, preferentment en format PDF. Els originals han de contenir la versió anglesa del títol, un resum breu en català i en anglès, paraules clau en català i en anglès i els codis de la classificació per matèries MSC2010. Les versions definitives dels articles acceptats s’han de presentar en codi TEX, preferentment en l’estil LATEX propi del Butlletí. Aquest estil es pot obtenir a les pàgines web de la Societat Catalana de Matemàtiques (SCM). Fem notar que en aquesta publicació s’utilitza preferentment el punt per a separar decimals, en lloc de la coma recomanada per l’IEC, per a poder facilitar la comprensió de les expressions matemàtiques. Per tal d’accelerar el procés de producció, es prega als autors que segueixin les indicacions contingudes en el document d’exemple. La versió en paper del Butlletí s’imprimeix en blanc i negre. Quan un article contingui figures en color i es consideri convenient, l’autor proporcionarà una versió dels gràfics substituint el color per tons de grisos i línies de gruix variable. Així mateix, modificarà els comentaris que facin referència al color de les figures. En qualsevol cas, el Butlletí publicarà l’original en color en el seu format electrònic. La propietat intel.lectual dels articles és dels respectius autors. Els autors, en el moment de lliurar els articles al Butlletí per a sol.licitar-ne la publicació, accepten els termes següents: — Els autors cedeixen a la SCM (filial de l’Institut d’Estudis Catalans) els drets de reproducció, comunicació pública i distribució dels articles presentats per a ser publicats al Butlletí. — Els autors responen davant la SCM de l’autoria i l’originalitat dels articles presentats. — És responsabilitat dels autors l’obtenció dels permisos per a la reproducció de tot el material gràfic inclòs en els articles. — La SCM està exempta de tota responsabilitat derivada de l’eventual vulneració de drets de propietat intel.lectual per part dels autors. Cada autor rebrà una còpia en PDF d’alta qualitat de la versió digital del seu article i un exemplar imprès del número del Butlletí en el qual es publiqui. La correspondència administrativa relacionada amb el Butlletí s’ha d’adreçar a la SCM. Pel que fa a la protecció de dades personals, l’Institut d’Estudis Catalans (IEC) compleix el que estableix el Reglament general de protecció de dades de la Unió Europea (Reglament 2016/679, del 27 d’abril de 2016). De conformitat amb aquesta norma, s’informa que, amb l’acceptació de les normes de publicació, els autors autoritzen que les seves dades personals (nom i cognoms, dades de contacte i dades de filiació) puguin ser publicades en el corresponent volum del Butlletí.

Aquestes dades seran incorporades a un tractament que és responsabilitat de l’IEC amb la finalitat de gestionar aquesta publicació. Únicament s’utilitzaran les dades dels autors per a gestionar la publicació del Butlletí i no seran cedides a tercers, ni es produiran transferències a tercers països o organitzacions internacionals. Un cop publicat el Butlletí, aquestes dades es conservaran com a part del registre històric d’autors. Els autors poden exercir els drets d’accés, rectificació, supressió, oposició, limitació en el tractament i portabilitat, adreçant-se per escrit a l’Institut d’Estudis Catalans (carrer del Carme, 47, 08001 Barcelona), o bé enviant un correu electrònic a l’adreça dades.personals@iec.cat, en què s’especifiqui de quina publicació es tracta.

Comitè editorial Antoni Guillamon (editor en cap) Departament de Matemàtiques Universitat Politècnica de Catalunya antoni.guillamon@upc.edu

Rosa Camps (editora adjunta) Departament de Matemàtiques Universitat Autònoma de Barcelona rcamps@mat.uab.cat

Carme Cascante Dep. de Matemàtiques i Informàtica Universitat de Barcelona cascante@ub.edu

Marc Noy Departament de Matemàtiques Universitat Politècnica de Catalunya marc.noy@upc.edu

Bartomeu Coll Dep. de Matemàtiques i Informàtica Universitat de les Illes Balears tomeu.coll@uib.cat

Francesc Planas Departament de Matemàtiques Universitat Politècnica de Catalunya francesc.planas@upc.edu

Núria Fagella Dep. de Matemàtiques i Informàtica Universitat de Barcelona fagella@maia.ub.es

Joan Saldaña Dep. d’Informàtica, Mat. Aplicada i Estadística Universitat de Girona joan.saldana@udg.edu

Armengol Gasull Departament de Matemàtiques Universitat Autònoma de Barcelona gasull@mat.uab.cat

Marta Sanz-Solé Dep. de Matemàtiques i Informàtica Universitat de Barcelona marta.sanz@ub.edu

Gábor Lugosi ICREA i Departament d’Economia Universitat Pompeu Fabra gabor.lugosi@upf.edu

Gil Solanes Departament de Matemàtiques Universitat Autònoma de Barcelona solanes@mat.uab.cat

Societat Catalana de Matemàtiques La Societat Catalana de Matemàtiques (SCM) és una societat filial de l’Institut d’Estudis Catalans, que continua les activitats de la Secció de Matemàtiques de la Societat Catalana de Ciències, que fou fundada per l’Institut l’any 1931. Les finalitats de la SCM són: el conreu de les ciències matemàtiques, l’extensió del seu coneixement en la societat catalana, el foment del seu ensenyament i de la seva investigació teòrica i aplicada, així com la publicació de tota mena de treballs que s’adeqüin a aquests objectius. La SCM desenvolupa les seves activitats en les terres de llengua i cultura catalanes. El català és, doncs, la llengua pròpia de la SCM i la que és usada normalment en tots els seus actes i publicacions. La SCM edita les publicacions periòdiques SCM/Notícies i Butlletí de la Societat Catalana de Matemàtiques. Els socis de la SCM reben, gratuïtament, aquestes dues publicacions. La SCM té convenis de reciprocitat amb diverses societats matemàtiques d’arreu del món, mitjançant els quals els socis de la SCM obtenen una reducció en la quota de soci d’aquestes societats. Així mateix, els socis de la SCM poden fer-se socis de la Societat Matemàtica Europea pagant una quota complementària. La Junta Directiva de la SCM està constituïda per les persones següents: Presidenta: Dolors Herbera i Espinal Vicepresident: Josep Vives i Santa-Eulàlia Adjunt a la vicepresidència: Abraham de la Fuente Pérez Secretària: Immaculada Baldomá i Barraca Tresorer: Albert Granados i Corsellas Vocal Empresa: Aleix Ruiz de Villa Vocal Publicacions: Montserrat Alsina i Aubach Vocals: Josep Grané i Manlleu, Mireia Lopez i Beltran, Albert Ruiz i Cirera, Manel Udina i Abelló Delegada de l’IEC: Pilar Bayer i Isant L’adreça de la SCM és carrer del Carme, 47, 08001 Barcelona. Telèfon: 933 248 583. Fax: 932 701 180. Correu electrònic: scm@iec.cat. Adreça web: http://scm.iec.cat.