A korábbiak után már könnyû a számosság operációt leírni.

Definíció: Egy H halmaz számossága az a legkisebb J jó halmaz, amely párbaállítható H-val.

A fenti definíció jogossága nem nyilvánvaló. Az szükséges hozzá, hogy minden halmaz párbaállítható egy jó halmazzal. Ez könnyen láthatóan ekvivalens azzal, hogy minden halmazon definiálható olyan rendezés, amellyel jólrendezett halmaz lesz, azaz röviden minden halmaz jólrendezhetõ. Ez az állítás Hilbert elsõ problémájában is benne foglaltatott. Elsõ bizonyítása Zermelo nevéhez fûzõdik (Zermelo jólrendezési tétele). A tétel nemtrivialitása abban is megmutatkozik, hogy Kõnig Gyula ezen álítás cáfolatát adta elõ Berstein egy hibásan leírt tételére alapozva.

Tétel: (Zermelo) Minden halmaz jólrendezhetõ.

Megjegyzés: A tétel bizonyítása egy jó halmazelméleti szemlélelt kialakulása után nem ördöngõs. nehézsége igazán abból ered, hogy bizonyításunkat formálisan le kell írni. Az ötlet a következõ: ``Haladjunk'' a rendszámok ``sorozatán'' és minden rendszámnál vegyünk ki a jólrendezendõ halmaznak egy eddig nem érintett elemét. Amikor a halmaz kifogy, akkor definiáltunk egy bijektív függvényt a kiinduló halmaz és egy rendszám között. Ennek a bizonyítási tervnek formalizálása azonban további elõkészületeket igényel.

Tétel: (Transzfinit indukció) Legyen A(a) egy rendszámokon értelmezett állítás. Ha tudjuk, hogy ``abból, hogy minden a-nál kisebb rendszámhoz rendelt állítás igaz, következik, hogy A(b) is igaz'' akkor azt is tudjuk, hogy minden a rendszámra A(a) igaz.

Bizonyítás: Tegyük fel, hogy van olyan a rendszám amalyre A(a) nem igaz. Ekkor minimális ilyen a(0) rendszám is van, ami ellentmond feltételünknek.

Tétel: (Transzfinit rekurzió tétele) Legyen U a rendszámokon értelmezett függvények osztálya. Legyen O egy operáció U-n. Ekkor pontosan egy olyan F rendszámokon értelmezett operáció van, amely a rendszámon felvett értéke megegyezik az a elõtt felvett értékeibõl összeálló (a-n értelmezett) függvényhez az O operáció által hozzárendelt értékkel.

Bizonyítás: Unicitás: Tegyük fel, hogy F és F' két operáció, amely eleget tesz a tételbeli elvárásoknak. Transzfinit indukcióval belátjuk, hogy minden a rendszámra F(a)=F'(a).

A tételbeli elvárásokat megszoríthatjuk egy rendszám elemeire: Legyen U a rendszámokon értelmezett függvények osztálya. Legyen O egy operáció U-n. Ekkor pontosan egy olyan F a rendszámon értelmezett függvény van, amely az a rendszám bármely b elemén felvett értéke megegyezik a b elõtt felvett értékeibõl összeálló (b-n értelmezett) függvényhez az O operáció által hozzárendelt értékkel. Egy ilyen F függvény unicitása is adódik a fenti gondolatmenetbõl. Ezek után, amennyiben létezik a megfelelõ a-n értelmezett függvény F(a)-val jelöljük.

Egzisztencia:

Ha F(a) létezik, akkor F(a+1) is létezik: b < a esetén F(a+1)(b) legyen F(a)(b), továbbá F(a+1)(a) legyen O(F(a)).

Ha a < b és F(a), illetve F(b) létezik, akkor F(a)=F(b)|a. Könnyen ellenõrizhetõ, hogy F(b)|a egy a-n értelmezett az elvárásoknak megfelelõ függvény, azaz az unicitás eredményünkból adódik az állítás.

Ha F(a(i)) létezik minden I-beli i-re, akkor F(sup{a(i)}) is létezik. Legyen b sup{a(i)} egy tetszõleges eleme. Ekkor valamely i-re b a(i)-nek is eleme. Legyen F(sup{a(i)})(b)=F(a(i))(b). Ez a fentiekbõl követekzõen jól definiált és könnyen láthatóan eleget tesz a kívánalmaknak.

F(a) minden rendszámra létezik: Transzfinit indukcióval belátható. Ha F(b) létezik b ( < a)-ra, akkor létezik supp{a: b < a}-ra és supp{a: b < a}+1-re is, ami bizonyítja a transzfinit indukcióhoz szükséges állítást.

Ezekután a ``globális'' F is létezik: F(a) legyen F(a+1)(a) egy jó definíció.

Ezzel a transzfinit rekurzió tételét beláttuk.

A bevezetõ ötletben említett gondolatmenet formalizálásához egy transzfinit rekurzióval definiálandó függvényt definiálunk. A függvény ``amíg tud'' rendszámokhoz újabb és újabb elemet rendel H-ból, amikor pedig kimerítette H-t egy H-ban nem benne lévõ elemet rendel minden további rendszámhoz.

A rekurzióval történõ definícióhoz le kell írnunk, hogyan ``folytassuk a definiációt, ha egy a-nál kisebb rendszámokig a hozzárendeleás már megtörtént. Ehhez szükséges lesz egy kiválasztási függvény H nem üres részhalmazain. Legyen ez k. Legyen k' az a függvény,a mley H össze részhalmazához hozzárendel egy halmazt: ha a halmaz nem üres, akkor a k által hozzárendelt érteket rendeli k' is, az üres halmazhoz viszont egy nem H-beli * értéket rendel (ez könnyen megtehetõ, hiszen H egyhalmaz és az összes halmaz nem alkot halmazt). Ezek után, ha az a-nál kisebb rendszámokon már értelmeztünk egy f függvényt, akkor O(f) legyen k'(H-{f(b):b < a}).

Transzfinit rekurzió tétele alapján létezik F operáció ehhez a rekurzióhoz. Errõl könnyen ellenõrizhetõ, hogy

• Injektív ott, ahol nem * értéket vesz fel.
• Felveszi a * értéket is: Ha nem venné fel, akkor legyen H' azon elmei H-nak, amelyek elõállnak F-beli értékként (H' halmaz). F injektivitása miatt értelmezhetõ egy inverz függvény H'-n, ami az összes rendszámot felveszi értékként. Ekkor viszont az összes rendszám halmazt alkotna, amirõl tudjuk, hogy nem igaz.

Legyen r egy olyan rendszám, amelyhez F a *-t rendeli. Azon rendszámok, amelyhez F nem a *-t rendeli r-nél kisebbek lesznek és így egy halmazt alkotnak. Ez a halmaz r egy kezdõszelete, így egy a rendszám lesz. F-et a-ra megszorítva kapunk egy függvényt, ami H és egy rendszám közti bijekció. Ezzel a jólrendezési tételt beláttuk.

Következmény: Számosságoperáció létezik.