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, $I$ tetszőleges indexhalmaz, $m_i$ és $n_i$ számosságok minden $i \in I$ értékre, amire $m_i < n_i \!$ teljesül minden $i \in I$ esetén, akkor

$\sum_{i\in I}m_i<\prod_{i\in I}n_i.$

ahol a bal oldalon az $m_i$ számosságok összege, a jobb oldalon az $n_i$ számosságok szorzata áll.

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

Bizonyítása

Legyen $\langle X_i\mid i\in I\rangle$, $\langle Y_i\mid i\in I\rangle$ két, páronként diszjunkt halmazok sorozata, amire $\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 $\Phi:\bigcup_{i\in I} X_i\to\{f:I\to\cup_{i\in I}Y_i\mid\forall i\in I f(i)\in Y_i\}$

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

Adva legyen most egy $\Phi$, és defniáljuk $f(i)$-t minden $i\in I$-re $Y_i\setminus\{\Phi(x)(i)\vert x\in X_i\}$ elemeként. Ekkor $f$ az $i$ helyen különbözik $\Phi$ $X_i$-beli képétől. Mivel ez minden $i\in I$-re teljesül, $\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.