certa fα. Ma allora f(xα) = fα(xα), che però non appartiene a X.
Modificando leggermente i passi della costruzione appena vista, Sierpi ´n- ski ha ottenuto diversi risultati interessanti.
Teorema 5.4.3 (Sierpi ´nski): L’insieme dei realiR contiene due sottoinsiemi densi X e Y che sono disgiunti, non isomorfi ad alcuno dei loro sottoinsiemi propri e tali che X∪Y non è isomorfo ad alcuno dei suoi sottoinsiemi propri.
Dimostrazione. La dimostrazione ripercorre fondamentalmente quella del teo- rema precedente.
5.4 teorema di laver 43
esclusa l’identità. I punti fissi di tali funzioni non possono essere densi ovunque. Di conseguenza, per ogni α < c, l’insieme {p ∈R| fα(p) 6= p}
ha cardinalità c.
Si definiscono ora induttivamente i seguenti sottoinsiemi diR.
passo base Siano x0, y0 ∈ R tali che X0 = {x0}, Y0 = {y0} e F0 =
{ f0(x0)} ∪ {f0(y0)}siano disgiunti.
passo induttivo Si supponga di aver definito, per ogni β< α, gli insiemi
Xβ = {xγ |γ≤β}, Yβ = {yγ |γ≤β} e Fβ = {fγ(xγ)|γ≤ β} ∪
{ fγ(yγ)|γ≤β}disgiunti e tali che δ6=γ =⇒ xδ 6=xγ e yδ 6=yγ.
Siccome esistono c punti tali che fα(x) 6= x, se ne possono scegliere
due xα e yα tali che Xα =
S β<αXβ∪ {xα}, Yα = S β<αYβ∪ {yα} e Fα = S
β<αFβ ∪ { fα(xα), fα(yα)} siano disgiunti e, per ogni β < α,
valga xα6=xβ e yα 6=yβ.
Allora gli insiemi X = S
α<cXα e Y =
S
α<cYα sono sottoinsiemi di R
con cardinalità continua, disgiunti, densi e non isomorfi ad alcuno dei loro sottoinsiemi propri. Inoltre anche X∪Y non è isomorfo ad alcuno dei suoi sottoinsiemi propri.
Definizione 5.4.1: Siano X e Y come nel teorema di Sierpi ´nski5.4.3. Per
ogni T ⊆Y, si definisce XT = X∪T⊆ X∪Y.
L’esistenza di catene infinite strettamente decrescenti e anticatene infinite di ordini totali di cardinalità continua, è un semplice corollario del lemma seguente.
Lemma 5.4.1: Siano X e Y come nel teorema di Sierpi ´nski5.4.3. Siano S, T ⊆Y. Se S\T6=∅, allora XS XT.
Dimostrazione. Sia per assurdo h : XS →XT un’immersione. Visto che XS ⊇
X, e dunque è denso in R, allora h può essere estesa ad un’immersione eh : R→R.
Innanzitutto, poiché S\T 6=∅, allora h non può essere l’identità, e dunque
neanche eh. Allora eh∈Ω, da cui esiste α<ctale che eh= fα. Ma xα ∈X⊆ XS
e fα(xα)∈/X∪Y⊇XT. Da cui h(xα)∈/ XT.
Corollario 5.4.2: Esistono catene infinite strettamente decrescenti e anticatene infinite di ordini totali aventi la cardinalità del continuo.
Dimostrazione. Siano X e Y come nel teorema di Sierpi ´nski5.4.3. Se si defini-
scono Y⊇ S1⊃S2⊃. . . , per il lemma precedente si ha che XS1 XS2 . . .
è una catena infinita strettamente decrescente.
Per fare una costruzione esplicita, basta prendere un sottoinsieme numera- bile {y1, y2, . . .} ⊆Y di Y e definire gli insiemi Si =Y\ {y1, . . . , yi}.
Se invece si definiscono Si =Y\ {yi}, per il lemma precedente si ha che
44 congettura di fraïssé
Dushnik e Miller dimostrarono anche che ogni ordine totale numerabile ammette un suo sottordine proprio isomorfo. Ciò spinse Fraïssé a pensare che la sua congettura potesse essere vera.
B I B L I O G R A F I A
[1] Carlos A. Di Prisco e Stevo Todorcevic. «Canonical forms of shift- invariant maps on[N]∞». In: Discrete Mathematics 306 (16 2006), pp. 1862– 1870. issn: 0012-365X. doi:10.1016/j.disc.2006.03.060.
[2] Ben Dushnik e E. W. Miller. «Concerning similarity transformations of linearly ordered sets». In: Bulletin of the American Mathematical Socie- ty 46 (4 1940), pp. 322–327. issn: 0273-0979,1088-9485. doi: 10.1090/ s0002-9904-1940-07213-1.
[3] Pál Erd˝os e Richard Rado. «Combinatorial Theorems on Classifications of Subsets of a Given Set». In: Proceedings of the London Mathematical Society s3-2 (1 1952), pp. 417–439. issn: 0024-6115,1234-5678. doi: 10 . 1112/plms/s3-2.1.417.
[4] Roland Fraïssé. «Sur la comparaison des types d’ordres». In: Comp- tes Rendus Hebdomadaires des Séances de l’Académie des Sciences. 1948, pp. 1330–1331.
[5] Fred Galvin e Karel Prikry. «Borel Sets and Ramsey’s Theorem». In: Journal of Symbolic Logic 38 (2 1973), pp. 193–198. issn: 0022-4812,1943- 5886. doi:10.2307/2272055.
[6] Felix Hausdorff. «Grundzüge einer Theorie der geordneten Mengen.» In: Mathematische Annalen 65 (1908), pp. 435–505. url: http://eudml. org/doc/158357.
[7] Thomas Jech. Set Theory. The Third Millennium Edition. Springer Mo- nographs in Mathematics. Springer-Verlag Berlin Heidelberg, 2002. isbn: 978-3-540-44085-7,978-3-540-44761-0.
[8] Richard Laver. «Better-Quasi-Orderings and a Class of Trees». In: Stu- dies in Foundations and Combinatorics. A cura di Gian-Carlo Rota. Ad- vances in mathematics : Supplementary studies. Academic Press Inc, 1979, pp. 32–48.
[9] Richard Laver. «On Fraisse’s Order Type Conjecture». In: Annals of Mathematics 93 (1 1971), pp. 89–111. issn: 0003-486X. doi: 10 . 2307 / 1970754.
[10] Richard Laver. «Well-quasi-orderings and sets of finite sequences». In: Mathematical Proceedings of the Cambridge Philosophical Society 79 (1 1976), pp. 1–10. issn: 0305-0041,1469-8064. doi:10.1017/s030500410005204x. [11] Marco Manetti. Topologia. 2aed. Vol. 78. UNITEXT - La Matematica per
il 3+2. Springer-Verlag Italia, 2014.
[12] Alberto Marcone. «Foundations of BQO Theory». In: Transactions of the American Mathematical Society 345 (2 1994), pp. 641–660. issn: 0002- 9947,1088-6850. doi:10.2307/2154991.
[13] A. R. D. Mathias. «On a generalization of Ramsey’s theorem». In: American Mathematical Society Notices 15 (1968).
46 bibliografia
[14] A.R.D. Mathias. «Happy families». In: Annals of Mathematical Logic 12 (1 1977), pp. 59–111. issn: 0003-4843. doi: 10 . 1016 / 0003 - 4843(77 ) 90006-7.
[15] C. St. J. A. Nash-Williams. «On better-quasi-ordering transfinite se- quences». In: Mathematical Proceedings of the Cambridge Philosophical So- ciety 64 (2 1968), pp. 273–290. issn: 0305-0041,1469-8064. doi:10.1017/ s030500410004281x.
[16] C. St. J. A. Nash-Williams. «On well-quasi-ordering infinite trees». In: Mathematical Proceedings of the Cambridge Philosophical Society 61 (3 1965), pp. 697–720. issn: 0305-0041,1469-8064. doi:10.1017/s0305004100039062. [17] Yann Pequignot. «Towards Better: A motivated introduction to better-
quasi-orders». In: EMS Surveys in Mathematical Sciences 4 (2 2017), pp. 185– 218. issn: 2308-2151, 2308-216X. doi:10.4171/EMSS/4-2-2.
[18] Richard Rado. «Partial well-ordering of sets of vectors». In: Mathema- tika 1 (2 1954), pp. 89–95. issn: 0025-5793,2041-7942. doi: 10 . 1112 / s0025579300000565.
[19] Joseph G. Rosenstein. Linear Orderings. Pure and applied mathematics 98. Academic Press, 1982. isbn: 9780080874142,9780125976800,0125976801. [20] Peter M. Schuster, Monika Seisenberger e Andreas Weiermann. Well-
Quasi Orders in Computation, Logic, Language and Reasoning: A Unifying Concept of Proof Theory, Automata Theory, Formal Languages and Descrip- tive Set Theory. 1st ed. 2020. Trends in Logic 53. Springer International Publishing, 2020. isbn: 978-3-030-30228-3,978-3-030-30229-0.
[21] Wacław Sierpi ´nski. «Sur les types d’ordre des ensembles linéaires». In: Fundamenta Mathematicæ 37 (1 1950), pp. 253–264. issn: 0016-2736. [22] Stephen G. Simpson. «Bqo Theory and Fraïssé Conjecture». In: Recur-
sive Aspects of Descriptive Set Theory. Oxford Logic Guides+11. The Cla- rendon Press Oxford University Press, 1985. Cap. 9. isbn: 0-19-503602- 6.
[23] Robert M. Solovay. «A Model of Set-Theory in Which Every Set of Reals is Lebesgue Measurable». In: Annals of Mathematics 92 (1 1970), pp. 1–56. issn: 0003-486X. doi:10.2307/1970696.
[24] Fons van Engelen, Arnold W. Miller e John Steel. «Rigid Borel Sets and Better Quasiorder Theory». In: Logic and Combinatorics: Proceedings. A cura di Stephen G. Simpson. Contemporary Mathematics 065. Ame- rican Mathematical Society, 1987. isbn: 0-8218-5052-0,978-0-8218-5052- 7,47-1985-511-3,31-1985-295-3,17-1974-384-3,59-1963-833-8.