Kőnig-egyenlőtlenség

Ez a szócikk a halmazelméleti tételről szól. A gráfelméletiről a Kőnig-tétel (gráfelmélet) szócikkben olvashatsz.

A Kőnig-egyenlőtlenség a halmazelmélet egyik tétele, amely Kőnig Gyula matematikustól származik. A tétel szerint ha a kiválasztási axióma igaz, ${\displaystyle I}$ tetszőleges indexhalmaz, ${\displaystyle m_{i}}$ és ${\displaystyle n_{i}}$ számosságok minden ${\displaystyle i\in I}$ értékre, amire ${\displaystyle m_{i}<n_{i}\!}$ teljesül minden ${\displaystyle i\in I}$ esetén, akkor

${\displaystyle \sum _{i\in I}m_{i}<\prod _{i\in I}n_{i}.}$

ahol a bal oldalon az ${\displaystyle m_{i}}$ számosságok összege, a jobb oldalon az ${\displaystyle n_{i}}$ számosságok szorzata áll.

E tétel következménye, hogy ${\displaystyle \kappa ^{{\mathrm {c} f}(\kappa )}>\kappa }$ teljesül minden végtelen ${\displaystyle }$ számosságra. Innen ${\displaystyle {\mathrm {c} f}(\lambda ^{\kappa })>\kappa }$ adódik minden ${\displaystyle \kappa \geq \aleph _{0}}$, ${\displaystyle \lambda \geq 2}$ számosságra, speciálisan ${\displaystyle {\mathrm {c} f}(2^{\kappa })>\kappa }$.

Bizonyítása

Legyen ${\displaystyle \langle X_{i}\mid i\in I\rangle }$, ${\displaystyle \langle Y_{i}\mid i\in I\rangle }$ két, páronként diszjunkt halmazok sorozata, amire ${\displaystyle \vert X_{i}\vert =\kappa _{i}<\lambda _{i}=\vert Y_{i}\vert }$. Elég belátni, hogy van egy injektív, de nem bijektív ${\displaystyle \Phi :\bigcup _{i\in I}X_{i}\to \{f:I\to \cup _{i\in I}Y_{i}\mid \forall i\in If(i)\in Y_{i}\}}$

Legyen ${\displaystyle \alpha _{i}}$ elem ${\displaystyle Y_{i}\setminus X_{i}}$-ből ${\displaystyle i\in I}$-re. Legyen továbbá ${\displaystyle x\in \bigcup _{i\in I}X_{i}}$. Ekkor egyértelműen van egy ${\displaystyle j\in I}$, hogy ${\displaystyle x\in X_{j}}$. Legyen ${\displaystyle f:=\Phi (x)}$ az a függvény, amire ${\displaystyle f(i)={\begin{cases}x,&i=j\\\alpha _{i},&i\neq j\end{cases}}}$. Ekkor ${\displaystyle \Phi }$ injektív.

Adva legyen most egy ${\displaystyle \Phi }$, és definiáljuk ${\displaystyle f(i)}$-t minden ${\displaystyle i\in I}$-re ${\displaystyle Y_{i}\setminus \{\Phi (x)(i)\vert x\in X_{i}\}}$ elemeként. Ekkor ${\displaystyle f}$ az ${\displaystyle i}$ helyen különbözik ${\displaystyle \Phi }$ ${\displaystyle X_{i}}$-beli képétől. Mivel ez minden ${\displaystyle i\in I}$-re teljesül, ${\displaystyle \Phi }$ nem szürjektív, és így nem bijektív.

Források

• Jech, Thomas: Set Theory, Springer-Verlag Berlin Heidelberg (2006), ISBN 3-540-44085-2.
• Kőnig Gyula: Zum Kontinuumsproblem, Mathematische Annalen 60 (1905), 177-180.

Fordítás

Ez a szócikk részben vagy egészben a Satz von König (Mengenlehre) című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.