Kőnig-egyenlőtlenség

A Wikipédiából, a szabad enciklopédiából
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[szerkesztés | forrásszöveg szerkesztése]

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 definiá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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

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.