Бесконечна комбинаторика

Бесконечна комбинаторика или Комбинаторна теорија на множества — проширување на идеите за поврзување на комбинаториката со бесконечните множества. Работите коишто се проучуваат во рамки на бесконечната комбинаторика вклучуваат: континуелни графови и дрвја, проширувања на Ремзиевата теорема и Мартиновата аксиома. Скорешните проширувања се однесуваат на комбинаториката на континуум и комбинаториката на кардинални броеви.

Ремзиева теорија за бесконечни множества

Ако претпоставиме дека κ, λ се редни броеви, m е кардинален број и n е природен број, тогаш записот:

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

претставува скратен облик на објаснувањето дека секоја поделба на множеството [κ]ⁿ од подмножества со n елементи од $\kappa$ на m делови има хомогено множество од ред λ. Хомогеното множество во овој случај е подмножество од κ, така што секое подмножество со n елементи е во истиот елемент на поделбата. Кога m е 2, тоа обично се избегнува.

Под претпоставка дека важи аксиомата на избор, тогаш нема редни броеви κ со κ→(ω)^ω, па така n обично се јавува како конечен број. Проширувањето во коешто n се јавува како бесконечен број може да се прикаже со записот:

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

што претставува скратен облик на објаснувањето дека секоја поделба на множеството на конечни подмножества од κ на m делови има подмножество од ред λ, така што за секој конечен n, сите подмножества со големина n се во истиот елемент на поделба. Кога m е 2, тоа обично се избегнува.

Друга варијанта е записот:

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

што е скратен облик на објаснувањето дека секое обојување на множеството [κ]ⁿ од подмножества со n елементи од κ со 2 бои има подмножество од ред λ, така што сите елементи од [λ]ⁿ се обоени со првата боја или подмножество од ред μ, така што сите елементи од [μ]ⁿ се обоени со втората боја.

Некои особини на теоријата, од каде што произлегува дека $\kappa$ е кардинален број, се следните:

$\aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}$ за сите конечни n и k (Ремзиева теорема);

$\beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}$ (Ердеш-Радоева теорема);

$2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}$ (Сјерпинскиева теорема);

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

$\kappa \rightarrow (\kappa ,\aleph _{0})^{2}$ (Ердеш-Душник-Милерова теорема).

Во случаите без избор, особините на поделбата со бесконечни експоненти може да биде веродостојна и некои од нив се добиени како последица на аксиомата на одредување. Доналд Мартин докажал дека аксиомата на одредување укажува дека важи:

$\aleph _{1}\rightarrow (\aleph _{1})_{2}^{\aleph _{1}}$.

Големи кардинални броеви

Како големи кардинални броеви и нивните особини може да се издвојат следните:

• слаби компактни кардинални броеви κ коишто го задоволуваат условот κ→(κ)²;
• α-Ердешови кардинални броеви κ коишто се најмалите броеви што го задоволуваат условот κ→(α)^<ω; и
• Ремзиеви кардинални броеви κ коишто го задоволуваат условот κ→(κ)^<ω.

Поврзано

• Комбинаторина
• Теорија на множества
• Кардинален број

Литература

• Dushnik, Ben; Miller, E. W. (1941), „Partially ordered sets“, American Journal of Mathematics, 63 (3): 600–610, doi:10.2307/2371374, ISSN 0002-9327, JSTOR 2371374, MR 0004862
• Erdős, Paul; Hajnal, András (1971), Axiomatic Set Theory ( Univ. California, Los Angeles, Calif., 1967), Unsolved problems in set theory, Proc. Sympos. Pure Math, XIII Part I, Providence, R.I.: Amer. Math. Soc., стр. 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, 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. Math. Soc., 62 (5): 427–489, doi:10.1090/S0002-9904-1956-10036-0, MR 0081864
• Kanamori, Akihiro (2000). The Higher Infinite, second edition. 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