Ordinaali

Ordinaali eli ordinaaliluku on joukko-opissa käytetty luonnollisen luvun käsitteen yleistys, jolla kuvataan tapoja sijoittaa johonkin kokoelmaan kuuluvat kohteet peräkkäiseen järjestykseen, yksi toisensa jälkeen. Jokainen äärellinen määrä kohteita voidaan asettaa järjestykseen yksinkertaisesti laskemalla ne: tällöin jokainen kohde saa järjestys­luvukseen jonkin kokonaisluvun. Käytännössä ordinaaliluvut voidaan ajatella vaikkapa numerolapuiksi, joiden avulla kohteet voidaan asettaa määrättyyn järjestykseen. 
Äärellisten kokoelmien tapauksessa ordinaali­luvut vastaavat täysin luonnollisia lukuja eli positiivisia kokonaislukuja. Sen sijaan äärettömille kokoelmille on olemassa useampiakin "järjestyksen" käsitteitä. Sitä niistä, joka lähinnä voidaan katsoa yleistykseksi äärellisen joukon järjestyksestä "yksi toisensa jälkeen", sanotaan hyvin­järjestykseksi. hyvin­järjestyksen voidaan ajatella merkitsevän sitä, että kohteet merkitään nimi- tai numerolapuilla "yksi toisensa jälkeen", mutta sallitaan, että jotkin nimilaput tulevat vasta äärettömän monen edeltäjän jälkeen. Esimerkiksi luonnollisten lukujen joukon {0,1,2,...} jälkeen voidaan jonon loppuun lisätä symboli ω, joka on pienin ääretön ordinaali. Näin joukko {0,1,2,...,ω) jatkuu ylös äärettömään. Jotkin ordinaalit ovat jonkin edeltäjänsä välitön seuraaja, seuraajaordinaali', kuten on laita luonnollisten lukujen {1,2,...}, mutta toiset ordinaalit kuten ω eivät ole minkään toisen ordinaalin välittömiä seuraajia, ja sellaisia sanotaan rajaordinaaleiksi.
Ordinaalit on erotettava kardinaali­luvuista, joiden avulla voidaan ilmoittaa, kuinka monta kohdetta jossakin kokoelmassa on.  Äärellisten lukujen tapauksessa kardinaali- ja ordinaali­luvut vastaavat kääntäen yksi­käsitteisesti toisiaan; esimerkiksi ordinaali­luvusta voidaan siirtyä vastaavaan kardinaali­lukuun laskemalla nimilaput. Sitä vastoin kaksi tai useampikin eri ääretöntä ordinaalia voi vastata samaa kardinaalia (katso Hilbertin hotelli). Muiden lukujen tapaan ordinaalejakin voidaan laskea yhteen, kertoa tai korottaa potenssiin, mutta äärettömien ordinaalien tapauksessa yhteen- ja kertolasku eivät ole kommutatiivisia.
Ordinaalit otti käyttöön Georg Cantor vuonna 1883 käsitelläkseen äärettömiä jonoja ja luokitellakseen johdetut joukot, jotka hän oli vuonna 1872 ottanut käyttöön tutkiessaan trigono­metristen sarjojen yksi­käsitteisyyttä.

Hyvinjärjestetyt joukot

Hyvin­järjestetyssä joukossa jokaisella ei-tyhjällä osajoukolla on pienin alkio. Valinta-aksiooman mukaan tämä on yhtäpitävää sen kanssa, että joukko on täydellisesti järjestetty ja että siinä ei ole ääretöntä laskevaa jonoa, mikä on ehkä helpommin hahmotettavissa. hyvin­järjestyksen käytännössä tärkein merkitys on siinä, että se mahdollistaa transfinittisen induktion: jos siitä, että jokin ominaisuus on jonkin alkion kaikilla edeltäjillä, seuraa, että se on myös kyseisellä alkiolla, silloin tämä ominaisuus on koko joukon kaikilla alkioilla, edellyttäen, että joukko on hyvin­järjestetty. Tällä on merkitystä myös tieto­tekniikassa: jos jokin laskenta­menetelmä voidaan hyvin­järjestää siten, että jokaista askelta seuraa "alempi" askel, laskenta ei jatku loppumattomiin.
Kahta hyvin­järjestettyä joukkoa A ja B sanotaan järjestys­isomorfisiksi, jos jokaista joukon A alkiota vastaamaan voidaan asettaa jokin joukon B alkio siten, että jos joukon A alkio x on pienempi kuin joukon A'  alkio y, on myös alkiota x vastaava alkio joukossa B pienempi kuin alkiota y vastaava alkio joukossa B ja päinvastoin. Tällaista eri joukkojen alkioiden vastaavuutta sanotaan järjestysisomorfismiksi. Järjestys­isomorfiset joukot ovat järjestyksen kannalta saman­laisia, ja niistä voidaankin sanoa, että niiden alkiot on vain "nimetty eri tavoin.".  Joukkojen järjestys­isomorfisuus on selvästikin ekvivalenssirelaatio. Mikäli kahden hyvin­järjestetyn joukon välillä on järjestys­isomorfismi, sellaisia on vain yksi: tämä seikka osaltaan oikeuttaakin pitämään näitä joukkoja oleellisesti samoina ja etsiä isomorfismi­tyypille (luokalle) "kanonista" edustajaa. Ordinaalit ovatkin juuri sellaisia isomorfismi­tyyppien "kanonisia" edustajia, ja niitä voidaankin käyttää jokaisen hyvin­järjestetyn joukon merkitsemis­tapoina.
Muodollisesti jos osittainen järjestys < on määritelty joukossa S ja osittainen järjestys <' joukossa S' , osittain järjestetyt joukot (S,<) ja (S' ,<') ovat järjestys­isomorfismia, jos niiden välillä on olemassa bijektio f, joka säilyttää järjestyksen eli f(a) < f(b), jos ja vain jos a < b. Jokainen hyvin­järjestetty joukko (S,<) on järjestys­isomorfinen niiden ordinaalien joukon kanssa, jotka ovat pienempi kuin se ordinaaliluku, joka ilmaisee joukon (S,<) järjestystyypin. 
Alkujaan ordinaalit käsitettiin hyvin­järjestettyjen joukkojen isomorfia­luokiksi, toisin sanoen järjestys­isomorfisuutta merkitsevän ekvivalenssirelaatioon liittyviksi ekvivalenssi­luokiksi. Tähän liittyy kuitenkin se tekninen ongelma, että tämä ekvivalenssi­luokka on liian laaja, jotta sitä voitaisiin käsitellä joukkona joukko-opin tavan­omaisessa Zermelon–Frankelin aksioomiin perustuvassa muotoilussa. Tämä vaikeus on kuitenkin voitettavissa. Ordinaaleja voidaan sanoa joukkojen järjestys­tyypeiksi.

Ordinaalin määritelmä ekvivalenssiluokkana

Ordinaaliluvun alku­peräisessä määritelmässä, joka löytyy esimerkiksi teoksesta Principia Mathematica, hyvin­järjestetyn joukon järjestys­tyyppi määritellään kaikkien niiden hyvin­järjestysten joukkona, jotka ovat tämän kanssa järjestys­isomorfisia; toisin sanoen ordinaaliluvut ovat hyvin­järjestettyjen joukkojen muodostamia ekvivalenssi­luokkia. Tämä määritelmä joudutaan kuitenkin hylkäämään Zermelon–Fraenkelin esittämässä ja sitä muistuttavissa joukko-opin aksiomatisoinneissa, koska nämä ekvivalenssi­luokat ovat liian laajoja ollakseen joukkoja. Määritelmää kuitenkin voidaan kuitenkin yhä käyttää tyyppiteoriassa sekä Quinen aksiomaattisessa joukko-opissa (New Foundation) ja sitä muistuttavissa muotoiluissa (joissa se myös tarjoaa sangen yllättävän vaihtoehtoisen ratkaisun suurinta ordinaalia koskevalle Buralin–Fortin paradoksille).

Transfiittinen jono

Jos α on rajaordinaali ja X joukko, kuvausta α:sta X:ään voidaan sanoa myös α:lla indeksoiduksi X:n alkioiden jonoksi. Tämä käsite, transfiniittinen jono eli ordinaali-indeksoitu jono on jonon käsitteen yleistys. Tavallinen jono vastaa tapausta, jossa  α = ω.

Transfiniittinen rekursio

Transfinittisella induktiolla voidaan, paitsi todistaa teoreemoja, myös määritellä käsitteitä. Sellaista määritelmää sanotaan tavallisesti transinittiseksi rekursioksi. Todistus, että näin saatu käsite on hyvin määritelty, perustuu trans­finiittiseen induktioon. Olkoon jokin F ordinaaleille määriteltävä luokkafunktio. Ideana on, että määriteltäessä F(α) mille tahansa ordinaalille α voidaan jo olettaa, että F(β) on jo määritelty kaikille ordinaaleille β < α, ja täten F(α):lle voidaan esittää lauseke funktion arvojen F(β) avulla. Tästä seuraa trans­finiittisellä induktiolla, että on yksi ja vain yksi funktio, joka toteuttaa rekursio­kaavan kaikilla ordinaaleilla α:aan saakka ja se mukaan luettuna.
Esimerkkinä voidaan tarkastella funktiota F, joka määritellään siten, että F(α) on pienin ordinaali, joka ei kuulu joukkoon {F(β) }, toisin sanoen joukko, johon kuuluvat kaikki arvot F(β), kun β < α. Määritelmässä oletetaan, että F(β):n tekee tunnetuksi juuri tämä prosessi F:n määrittelemiseksi vaiheittain. Tämä saattaa vaikuttaa kehämääritelmältä, mutta juuri tämän transfiniittinen rekursio sallii. Itse asiassa F(0) on sekin hyvin määritelty, koska ei ole sellaista ordinaalia, että  β < 0, ja joukko {F(β) } on tyhjä. Näin ollen F(0) on 0, kaikkein pienin ordinaali. Nyt kun F(0) on tunnettu, voidaan todeta, että F(1) on pienin ordinaali, joka ei kuulu joukkoon {F(0)} = {0}, ja niin edelleen. Tämä esimerkki tosin on melko triviaali, sillä juuri trans­finiittisen induktion avulla osoittautuu, että F(α) = α kaikilla ordinaaleilla α.

Ordinaaliluokkien indeksointi

Jokainen hyvin­järjestetty joukko on järjestys­isomorfinen yhden ja vain yhden ordinaalin  kanssa. Toisin sanoen sen alkiot voidaan indeksoida niillä ordinaaleilla, jotka ovat pienempiä kuin . Tämä koskee erityisesti myös jokaista ordinaalien joukkoa: mikä tahansa ordinaalien joukko voidaan indeksoida ordinaaleilla, jotka ovat pienempiä kuin jokin . Hieman muunnetussa muodossa sama pätee myös ordinaalien luokille toisin sanoen sellaisille kokoelmille ordinaaleja, jotka ovat tietyssä mielessä liian laajoja ollakseen joukkoja: jokainen ordinaalien luokka voidaan indeksoida ordinaaleilla (ja jos luokka on rajoittamaton kaikkien ordinaalien luokassa, tällä tavoin muodostuu luokkabijektio kaikkien ordinaalien luokan kanssa.) Niinpä voidaan puhua luokan :nnestä alkiosta (kun sovitaan, että pienin niistä on 0:s, seuraava 1:nen jne). Muodollisesti se määritellään trans­finiittisella induktiolla: luokan :s alkio määritellään pienimmäksi alkioksi, joka on suurempi kuin :s alkio kaikilla  (tämä luonnollisesti edellyttää, että asia on jo määritelty kaikilla arvoilla ).
Tätä voitaisiin soveltaa esimerkiksi rajaordinaalien luokkaan: :s ordinaali, joka on joko rajaorbitaali tai nolla, on .  Samaan tapaan voidaan käsitellä additiivisesti jakautumattomia ordinaaleja eli sellaisia nollasta poikkeavia ordinaaleja, jotka eivät ole kahden itseään aidosti pienemmän ordinaalien summia: :nnen additiivisesti jakautumattoman ordinaalin indeksi on . Ordinaali­luokkien indeksointi­tekniikka on usein hyödyllinen käsiteltäessä kiinteitä pisteitä: esimerkiksi :nnelle ordinaalille , jolle , käytetään merkintää . Näitä sanotaan epsilonluvuiksi.

Suljetut rajoittamattomat joukot ja luokat

Ordinaalien luokkaa  sanotaan rajoittamattomaksi eli kofinaaliseksi, jos jokaista ordinaalia  kohti on olemassa sellainen C:hen kuuluva ordinaali , että . Tällöin luokan on oltava aito luokka, sillä se ei voi olla joukko. Luokkaa sanotaan suljetuksi, jos luokkaan kuuluvien ordinaalien jonon raja-arvo on luokka itse, tai yhtäpitävästi, jos indeksoiva luokkafunktio  on jatkuva siinä mielessä, että kun  on rajaordinaali,  eli luokan :s ordinaali on funktion arvojen  raja-arvo, kun . Tämä merkitsee myös samaa kuin että luokka on topologisessa mielessä suljettu, kun topologana käytetään järjestystopologiaa. Jotta vältettäisiin puhumasta topologiasta aitojen luokkien tapauksessa, asia voidaan yhtäpitävästi ilmaista myös niin, että luokan ja minkä tahansa ordinaalin leikkaus on suljettu tämän ordinaalin järjestys­topologiassa.
Erityisen tärkeitä ovat ne ordinaalien luokkia, jotka ovat sekä suljettuja että rajoittamattomia ja joita toisinaan sanotaan klubeisi. Esimerkiksi kaikkien raja­ordinaalien luokka on suljettu ja rajoittamaton, sillä jokaista ordinaalia kohti on aina olemassa sitä suurempi raja­ordinaali ja raja­ordinaalien raja-arvo on aina rajaordinaali. Myös addiitiivisesti jakautumattomien ordinaalien luokka on suljettu ja rajoittamaton, samoin  -ordinaalien luokka ja kaikkien kardinaalien luokka, sitä vastoin kofinaalisten kardinaalien joukko on rajoittamaton, mutta ei suljettu, kun taas jokainen äärellinen ordinaalien joukko on suljettu mutta ei rajoitettu.
Luokka on stationaarinen, jos sen leikkaus minkä tahansa suljetun rajoittamattoman luokan kanssa on ei-tyhjä. Kaikki luokat, jotka sisältävät osaluokkanaan jonkin suljetun rajoitetun luokan, ovat stationaarisia ja kaikki stationaariset luokat ovat rajoittamattomia, mutta on myös stationaarisia luokkia, jotka eivät ole suljettuja tai joilla ei ole suljettua rajoittamatonta osaluokkaa; sellainen on esimerkiksi kaikkien sellaisten raja­ordinaalien luokka, joilla on numeroituva kofinaalisuus. Koska kahden suljetun rajoittamattoman luokan leikkaus on suljettu ja rajoittamaton, statio­naarisen luokan ja suljetun rajoittamattoman luokan leikkaus on stationaarinen. Kahden statio­naarisen luokan leikkaus voi kuitenkin olla myös tyhjä; näin on laita esimerkiksi, kun muodostetaan leikkaus kaikkien niiden ordinaalien luokasta, joiden kofinaalisuus on ω, sekä kaikkien niiden ordinaalien luokasta, joiden kofinaalisuus on ylinumeroituva.
Sen sijaan että nämä määritelmät muotoiltaisiin ordinaalien (aidoille) luokille, ne voidaan muotoilla myös niiden ordinaalien luokille, jotka ovat pienempiä kuin jokin annettu ordinaali .  Rajaordinaalin   osajoukkoa sanotaan rajoitta­matto­maksi (eli kofinaaliseksi) joukossa , jos jokainen :aa pienempi ordinaali on pienempi kuin jokin kyseisen joukon ordinaali. Yleisemmin minkä tahansa ordinaalin  osajoukkoja voidaan sanoa kofinaaliseksi :ssa, jos jokainen ordinaali, joa on pienempi kuin , on pienempi tai yhtä suuri kuin jokin tähän joukkoon kuuluva ordinaali. Osajoukkoa sanotaan suljetuksi :ssa , jos se on suljettu :n järjestys­topologiassa, toisin sanoen jos joukkoon kuuluvien ordinaalien raja-arvo joko sisältyy tähän joukkoon tai on  itse.

Kardinaalien initiaaliset ordinaalit

Jokaiseen ordinaaliin liittyy tietty kardinaaliluku, sen kardinaliteetti. Jos kahden ordinaalin välillä on bijektio (esimerkiksi ω=1+ω ja ω+1>ω), niihin liittyy sama kardinaali. Jokaisella hyvin­järjestetyllä ordinaalilla, jolla on järjestys­tyyppinään jokin ordinaali, on sama kardinaliteetti kuin tällä ordinaalilla. Pienintä annettuun kardinaaliin liittyvää ordinaalia sanotaan tämän kardinaalin initiaaliseksi ordinaaliksi.  Jokainen äärellinen ordinaali eli luonnollinen luku on initiaalinen, eikä millään muulla ordinaalilla ole samaa kardinaliteettia. Mutta useimmat äärettömät ordinaalit eivät ole initaalisia, sillä moniin äärettömiin ordinaalehin liittyy sama kardinaliteetti. Valinta-aksiooma on yhtäpitävä sen kanssa, että jokainen joukko voidaan hyvin­järjestää, toisin sanoen jokaisella kardinaalilla on initiaalinen ordinaali. Teorioissa, joihin sisältyy valinta-aksiooma, jokaisen joukon kardinaaliluvulla on initiaalinen ordinaali. Kardinaalit voidaankin käsittää ordinaalien erikois­tapauksiksi samastamalla ne initiaalisten ordinaaliensa kanssa, sillä jokainen joukko on yhtä mahtava jonkin (Neumannin mukaan määritellyn) orbitaalin kanssa. Täten ordinaali on kardinaali, jos ja vain jos se ei ole yhtä mahtava minkään itseään pienemmän ordinaalin kanssa.
Yleensä α:nnelle äärettömälle ordinaalille käytetään merkintää .  Sen kardinaliteettia merkitään .  Esimerkiksi ω₀:n eli ω:n kardinaliteetti on  , joka on myös ω²:n ja ε₀:n kardinaliteetti, sillä nämäkin ovat numeroituvia ordinaaleja. Niinpä jos valinta-aksiooma hyväksytään, ω voidaan samastaa , paitsi että merkintää  käytetään, kun on kysymys kardinaaleista ja merkintää ω, kun on kysymys ordinaaleista. (Eri merkintöjä käytetään, koska esimerkiksi   =  kardinaalina, mutta  ordinaalina).  Samoin  on pienin ylinumeroituva ordinaali (sen osoittamiseksi, että sellainen on olemassa, voidaan tarkastella luonnollisten lukujen hyvinjärjestysten ekvivalenssiluokkia: jokainen sellainen määrittelee numeroituvan ordinaalin, ja  on tämän joukon järjestystyyppi),  on pienin ordinaali, jonka kardinaliteetti on suurempi kuin  ja niin edelleen, ja  on ordinaalien  raja-arvo, kun arvot n ovat luonnollisia lukuja (jokainen kardinaalien raja-arvo on kardinaali, ja niin ollen tämä raja-arvo on itse asiassa ensimmäinen kardinaali, joka on suurempi kuin ).
Cantor käytti kardinaliteettia ordinaalien luokitteluun. Hän nimitti luonnollisia lukuja ensimmäiseksi lukuluokaksi, ordinaaleja, joiden kardinaliteetti on  eli numeroituvasti äärettömiä ordinaaleja toiseksi lukuluokaksi ja yleensä ordinaaleja, joiden kardinaliteetti on cardinality , n:nneksi lukuluokaksi.

Kofinaalisuus

Ordinaalin  kofinaalisuus on pienin ordinaali , joka on jonkin  kofinaalisen osajoukon järjestystyyppi. Joissakin teoksissa kofinaalisuuden käsite määritellään tai sitä käytetään vain rajaordinaaleille. Ordinaalien joukon tai minkä tahansa muun hyvinjärjestetyn joukon kofinaalisuus on tämän joukon järjestystyypin kofinaalisuus.
Niinpä jokaiselle rajaordinaalille  on olemassa -indeksoitu aidosti kasvava jono, jonka raja-arvo on . Esimerkiksi ω²:n kofinaalisuus on ω, koska jonon ω·m raja-arvo, missä m:n arvoina ovat kaikki luonnolliset luvut, on ω, ja yleensäkin jokaisen numeroituvan rajaordinaalin kofinaalisuus on ω.  Myös ylinumeroituvan rajaordinaalin kofinaalisuus voi olla ω, esimerkiksi ordinaalilla , mutta sellaisella voi olla myös ylinumeroituva kofinaalisuus. 
Ordinaalin 0 kofinaalisuus on 0, Jokaisen seuraajaordinaalin kofinaalisuus on 1. Jokaisen rajaordinaalin kofinaalisuus on vähintään .
Ordinaalia, jonka kofinaalisuus on yhtä suuri kuin ordinaali itse, sanotaan säännölliseksi, ja kaikki sellaiset ovat initiaalisia ordinaaleja. Säännölisten ordinaalien raja-arvo on initiaalisten ordinaalien raja-arvo ja sellaisena aian initiaalinen, joskaan ei välttämättä eikä yleenä säännöllinen. Jos valinta-aksiooma hyväksytään, siitä seuraa, että  kaikilla α, ja edelleen että ordinaalit 0, 1, ,  ja  ovat säännöllisiä, kun taas, 2, 3,  ja ωω·2 ovat esimerkkejä initiaalisista orbitaaleista, jotka eivät ole säännöllisiä.
Jokaisen ordinaalin α kofinaalisuus on säännöllinen ordinaali, toisin sanoen α:n kofinaalisuuden kofinaalisuus on sama kuin α:n kofinaalisuus. Toisin sanoen kofinaalisuusoperaatio on idempotentti.

Joitakin "suuria" numeroituvia ordinaaleja

Esimerkkinä "hyvin suuresta" äärettömästä, mutta vielä numeroituvasta ordinaalista voidaan mainita ε₀. Se on pienin ordinaali, joka toteuttaa yhtälön , ja samalla jonon 0, 1, , ,  jne. raja-arvo. Monet ordinaalit voidaan määritellä samaan tapaan jonkin ordinaalifunktion kiintopisteinä. Niinpä :tta sellaista ordinaalia, jolle pätee , merkitään , ja samaan tapaan voitaisiin yrittää löytää :s sellainen ordinaali, jolle  ja niin edelleen. Tätä voitaisiin yrittää järjestelmällisesti, mutta miten tahasa ordinaalit määritellään ja konstruoidaankin, aina on olemassa ordinaali, joka on juuri kaikkien tällä tavoin konstruoitujen ordinaalien yläpuolella Ehkä tärkein ordinaali, joka tähän tapaan rajoittaa konstruointijärjestelmää, on Churchin–Kleenen ordinaali  (joka on numeroituva siitä huolimatta, että sen nimessä esiintyy ). Se on pienin ordinaali, jota tietyssä mielessä ei mitenkään voi esittää laskettavissa olevana funktiona. Myös :n alapuolella voidaan kuitenkin määritellä huomattavan laajoja ordinaaleja, jotka mittaavat eräiden formaalisten systeemien "todistus­teoreettista vahvuutta"; niinpä esimerkiksi  mittaa Peanon aksioomeihin perustuvan aritmetiikan vahvutta. Voidaan myös määritellä ordinaaleja, jotka ovat suurempia kuin Churchin–Kleenen ordinaali ja joilla niilläkin on merkitystä useilla logiikan aloilla.

Topologia ja ordinaalit

Jokainen ordinaaliluku voidaan muodostaa topologiseksi avaruudeksi varustamalla se järjestystopologialla. Tämä topologia on diskreetti, jos ja vain jos ordinaali on numeroituva kardinaali, toisin sanoen enintään ω. Joukon ω + 1 osajoukko on avoin järjestystopologiassa, jos ja vain jos se joko on kofiniittinen (eli sen komplementti on äärellinen joukko) tai ω ei sisälly siihen alkiona.