Infinitär kombinatorik

Inom matematiken är infinitär kombinatorik , eller kombinatorisk mängdteori , en förlängning av idéer i kombinatorik till oändliga mängder . Några av de saker som studeras inkluderar kontinuerliga grafer och träd , förlängningar av Ramseys teorem och Martins axiom . Den senaste utvecklingen rör kombinatorik av kontinuumet och kombinatorik på efterföljare till singulära kardinaler.

Ramsey teori för oändliga mängder

Skriv κ, λ för ordningstal, m för ett kardinaltal och n för ett naturligt tal. Erdős & Rado (1956) introducerade notationen

$\kappa \rightarrow (\lambda )_{m}^{n}$

som ett stenografiskt sätt att säga att varje partition av mängden [κ] ⁿ av n -elementdelmängder av $\kappa }$ displaystyle i m bitar har en homogen uppsättning av ordningstyp λ. En homogen mängd är i detta fall en delmängd av κ så att varje n -element delmängd är i samma element i partitionen. När m är 2 utelämnas det ofta.

Om man antar valets axiom , finns det inga ordtal κ ​​med κ→(ω) ^ω , så n tas vanligtvis för att vara ändlig. En förlängning där n nästan får vara oändlig är notationen

$\kappa \rightarrow (\lambda )_{m}^{<\omega }$

vilket är ett förkortat sätt att säga att varje partition av mängden ändliga delmängder av κ i m bitar har en delmängd av ordningstyp λ så att för varje ändlig n är alla delmängder av storlek n i samma element i partitionen. När m är 2 utelämnas det ofta.

En annan variant är notationen

$\kappa \rightarrow (\lambda ,\mu )^{n}$

vilket är ett kortfattat sätt att säga att varje färgning av mängden [κ] ⁿ av n -elementdelmängder av κ med 2 färger har en delmängd av ordningstyp λ så att alla element i [λ] n ^har den första färgen, eller en delmängd av ordningstyp μ så att alla element i [μ] ⁿ har den andra färgen.

Några egenskaper hos detta inkluderar: (i det följande är $\kappa$ en kardinal)

$\aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}$ för alla ändliga n och k ( Ramseys sats ).

$\beth _{n}^{+}\högerpil (\aleph _{1})_{\aleph _{0}}^{n+1}$ ( Erdős–Rado-satsen .)

$2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}$ (Sierpiński-satsen)

$2^{\kappa }\not \rightarrow (3)_{\kappa }^{2}$

$\kappa \rightarrow (\kappa ,\ aleph _{0})^{2}$ ( Erdős–Dushnik–Miller-satsen ).

I valfria universum kan partitionsegenskaper med oändliga exponenter gälla, och en del av dem erhålls som konsekvenser av determinationsaxiomet ( AD) . Till exempel, Donald A. Martin bevisade att AD innebär

$\aleph _{1}\högerpil (\aleph _{1})_{2}^{\aleph _{1}}$

Stora kardinaler

Flera stora kardinalegenskaper kan definieras med denna notation. Särskilt:

• Svagt kompakta kardinaler κ är de som uppfyller κ→(κ) ²
• α- Erdős kardinaler κ är de minsta som uppfyller κ→(α) ^<ω
• Ramsey-kardinaler κ är de som uppfyller κ→(κ) ^<ω

Anteckningar

•     Dushnik, Ben; Miller, EW (1941), "Partially ordered sets", American Journal of Mathematics , 63 (3): 600–610, doi : 10.2307/2371374 , hdl : 10338.dmlcz/100377 , ISSN 32002 , ISSN 32002 32002 , ISSN 32002 7 0004862
•   Erdős, Paul ; Hajnal, András (1971), "Unsolved problems in set theory", Axiomatic Set Theory (Univ. California, Los Angeles, Calif., 1967), Proc. Sympos. Pure Math, vol. XIII del I, Providence, RI: Amer. Matematik. Soc., s. 17–48, MR 0280381
•    Erdős, Paul ; Hajnal, András ; Máté, Attila; Rado, Richard (1984), Combinatorial set theory: partition relations for cardinals , Studies in Logic and the Foundations of Mathematics, vol. 106, Amsterdam: North-Holland Publishing Co., ISBN 0-444-86157-2 , MR 0795592
•   Erdős, P. ; Rado, R. (1956), "A partition calculus in set theory" , Bull. Amer. Matematik. Soc. , 62 (5): 427–489, doi : 10.1090/S0002-9904-1956-10036-0 , MR 0081864
•   Kanamori, Akihiro (2000). The Higher Infinite (andra upplagan). Springer. ISBN 3-540-00384-3 .
•   Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs , Amsterdam: North-Holland, ISBN 978-0-444-85401-8