Pořadové číslo - Ordinal number

Reprezentace pořadových čísel do ω ^ω . Každé otočení spirály představuje jednu mocninu ω.

V teorii množin , což je pořadové číslo nebo pořadové číslo , je jedním zobecnění pojmu přirozené číslo , které se používá k popisu způsob, jak uspořádat (možná nekonečná) kolekci objektů v pořádku, jeden po druhém.

Jakoukoli konečnou sbírku předmětů lze dát do pořádku pouhým procesem počítání: označení objektů odlišnými přirozenými čísly. Základní myšlenkou řadových čísel je zobecnit tento proces na případně nekonečné kolekce a poskytnout „označení“ pro každý krok v tomto procesu. Pořadová čísla jsou tedy „štítky“ potřebné k uspořádání sbírek předmětů v pořadí.

Pořadové číslo se používá k popisu typu příkazu o spořádané sady (i když to není práce pro spořádané správném třídě ). Dobře uspořádaná množina je množina se vztahem <takovým, že:

• ( Trichotomii ) pro jakékoli části x a y , právě jeden z těchto tvrzení je pravdivé:
  • x < y
  • y < x
  • x = y
• ( Transitivita ) Pro všechny prvky x , y , z , pokud x < y a y < z , pak x < z.
• ( Odůvodněnost ) Každá neprázdná podmnožina má nejmenší prvek, to znamená, že má prvek x takový, že v podmnožině, kde y < x , není žádný jiný prvek y .

Dvě dobře uspořádané množiny mají stejný typ pořadí, právě tehdy, když existuje bijekce z jedné sady do druhé, která převádí vztah v první sadě, na relaci ve druhé sadě.

Zatímco řadové číslovky jsou užitečné pro uspořádání objektů v kolekci, liší se od základních čísel , která jsou užitečná pro kvantifikaci počtu objektů v kolekci. Ačkoli rozdíl mezi řadovými a kardinálními čísly není v konečných sadách vždy zřejmý (lze přecházet od jednoho k druhému pouhým počítáním štítků), stejnému kardinálovi mohou odpovídat různé nekonečné pořadové čísla. Kromě toho mohou existovat sady, které nelze dobře uspořádat, a jejich základní čísla neodpovídají pořadovým číslům. (Například existence takových množin vyplývá z teorie množin Zermelo-Fraenkel s negací zvoleného axiomu.) Stejně jako ostatní druhy čísel lze řadit pořadové číslo , násobit ho a umocňovat , ačkoli žádná z těchto operací není komutativní.

Řadovky představil Georg Cantor v roce 1883, aby se přizpůsobily nekonečným sekvencím a klasifikovaly odvozené sady , které předtím zavedl v roce 1872 - při studiu jedinečnosti trigonometrických řad .

Řadovky rozšiřují přirozená čísla

Přirozené číslo (které jsou v tomto kontextu zahrnuje číslo 0 ), lze použít pro dva účely: popisovat velikost o souboru , nebo popisovat pozici elementu v sekvenci. Když jsou omezeny na konečné množiny, tyto dva pojmy se shodují a existuje pouze jeden způsob, jak dát konečnou množinu do lineární posloupnosti ( až do izomorfismu ). Při práci s nekonečnými množinami je však třeba rozlišovat mezi pojmem velikosti, který vede ke světovým číslům , a pojmem pozice, který vede k zde popsaným pořadovým číslům. Důvodem je, že zatímco každá sada má pouze jednu velikost (její mohutnost ), existuje mnoho neizomorfních uspořádání řádků jakékoli nekonečné množiny, jak je vysvětleno níže.

Zatímco pojem základní číslo je spojen se sadou, na které není žádná konkrétní struktura, pořadové číslo je úzce spojeno se zvláštním druhem množin, které se nazývají dobře uspořádané (ve skutečnosti tak úzce propojené, že někteří matematici mezi nimi nerozlišují) dva pojmy). Dobře uspořádaná množina je zcela uspořádaná množina (vzhledem k jakýmkoli dvěma prvkům jeden soudržným způsobem definuje menší a větší), ve které každá neprázdná podmnožina množiny má nejmenší prvek. Zejména neexistuje žádná nekonečná klesající sekvence. (Může však existovat nekonečné zvyšující se posloupnosti.) K označení prvků libovolné dané dobře uspořádané množiny lze použít pořadové číslo (nejmenší prvek je označen 0, jeden za tím 1, další 2, „atd.“ ) a změřit „délku“ celé sady nejmenším pořadovým číslem, které není popiskem prvku sady. Tato „délka“ se nazývá typ objednávky sady.

Libovolné pořadové číslo je definováno sadou pořadových čísel, které mu předcházejí. Ve skutečnosti nejběžnější definice ordinals identifikuje každý ordinal jako soubor ordinals, který mu předchází. Například ordinální číslo 42 je typem pořadí ordinálů menší než to, tj. Pořadové číslo od 0 (nejmenší ze všech pořadových čísel) do 41 (bezprostřední předchůdce 42) a obecně je identifikováno jako množina { 0,1,2,…, 41}. Naopak každá množina S ordinálů, která je uzavřena směrem dolů-což znamená, že pro jakoukoli ordinální α v S a jakoukoli ordinální β <α, β je také v S -je (nebo ji lze identifikovat s) ordinální.

Existují také nekonečné pořadové čísla : nejmenší nekonečný řadový je , což je typ řádu přirozených čísel (konečných pořadových čísel), a který lze dokonce ztotožnit se sadou přirozených čísel. Ve skutečnosti je množina přirozených čísel dobře uspořádaná-stejně jako každá řada řadových řad-a protože je směrem dolů uzavřená, lze ji ztotožnit s řadou s ní spojenou (což je přesně definováno). ${\ displaystyle \ omega}$${\ displaystyle \ omega}$

Grafické znázornění řadové ω² „zápalkou“. Každá páčka odpovídá ordinálu tvaru ω · m + n, kde m a n jsou přirozená čísla.

Jasnější intuici řadových řad lze možná vytvořit prozkoumáním několika prvních z nich: jak bylo uvedeno výše, začínají přirozenými čísly, 0, 1, 2, 3, 4, 5, ... Po všech přirozených číslech přichází první nekonečný pořadový list , ω, a poté přijdou ω+1, ω+2, ω+3 atd. (Přesně to, co znamená sčítání, bude definováno později: považujte je pouze za jména.) Poté, co přijde toto ω · 2 (což je ω+ω), ω · 2+1, ω · 2+2 atd., poté ω · 3 a později ω · 4. Nyní takto vytvořená množina řadových řad (ω · m + n , kde m a n jsou přirozená čísla) musí mít sama k sobě přiřazenou pořadovou hodnotu: a to je ω ² . Dále bude ω ³ , pak ω ⁴ atd. A ω ^ω , pak ω ^{ω ω} , později ω ^{ω ω ω} a ještě později ε ₀ ( epsilon nic ) (abychom uvedli několik příkladů relativně malé - počitatelné - pořadové číslo). To může pokračovat donekonečna (jako pokaždé, když člověk řekne „a tak dále“ při výčtu pořadových čísel, definuje to větší pořadové číslo). Nejmenší nespočitatelná řadovka je množina všech počitatelných řadovek, vyjádřená jako ω ₁ nebo . ${\ displaystyle \ Omega}$

Definice

Dobře seřazené sady

V dobře uspořádané sadě obsahuje každá neprázdná podmnožina zřetelně nejmenší prvek. Vzhledem k axiomu závislé volby je toto ekvivalentní tomu, když řekneme, že množina je zcela uspořádaná a neexistuje žádná nekonečná klesající sekvence (ta druhá je snadněji vizualizovatelná). V praxi je důležitost řádného uspořádání odůvodněna možností aplikace transfinitní indukce , která v podstatě říká, že jakákoli vlastnost, která přechází z předchůdců prvku na samotný prvek, musí platit pro všechny prvky (daného dobře uspořádaná sada). Pokud lze stavy výpočtu (počítačový program nebo hra) dobře uspořádat-takovým způsobem, že po každém kroku následuje krok „nižší“-, pak výpočet skončí.

Není vhodné rozlišovat mezi dvěma dobře uspořádanými množinami, pokud se liší pouze v „označení svých prvků“, nebo formálněji: pokud lze prvky první sady spárovat s prvky druhé sady tak, že pokud jedna prvek je menší než jiný v první sadě, pak partner prvního prvku je menší než partner druhého prvku v druhé sadě a naopak. Taková korespondence jeden na jednoho se nazývá řádový izomorfismus a dvě dobře uspořádané množiny jsou údajně izomorfní nebo podobné (s tím, že se jedná o vztah ekvivalence ).

Formálně, pokud je částečné uspořádání ≤ je definována na množině S , a při parciálním pořadí ≤ ‚je definován na množině S‘ , pak Posets ( S , ≤) a ( S ‚≤‘), tak , aby izomorfní v případě, že je bijection f který zachovává uspořádání. To znamená, že f ( a ) ≤ ' f ( b ) právě tehdy, když a ≤ b . Za předpokladu, že existuje řádový izomorfismus mezi dvěma dobře uspořádanými množinami, je řádový izomorfismus jedinečný: to činí celkem ospravedlnitelným považovat tyto dvě sady za v podstatě identické a hledat „kanonického“ zástupce typu (třídy) izomorfismu. To je přesně to, co ordinály poskytují, a také poskytuje kanonické označování prvků jakékoli dobře uspořádané sady. Každá dobře uspořádaná množina ( S , <) je izomorfní k množině pořadových čísel menší než jedno konkrétní pořadové číslo podle jejich přirozeného uspořádání. Tato kanonická sada je typem objednávky ( S , <).

V zásadě je ordinál určen k definování jako třída izomorfismu dobře uspořádaných množin: to znamená jako třída ekvivalence pro vztah ekvivalence „být řádově izomorfní“. Existuje však technický problém ve skutečnosti, že třída ekvivalence je příliš velká na to, aby mohla být množinou v obvyklé formalizaci teorie množin Zermelo – Fraenkel (ZF). Ale to není vážná obtíž. O ordinále lze říci, že je typem objednávky jakékoli sady ve třídě.

Definice ordinálu jako třídy ekvivalence

Původní definice pořadových čísel, nacházející se například v Principia Mathematica , definuje typ řádu dobře uspořádaného jako množinu všech řádných uspořádání podobných (řádově izomorfních) tomuto dobře uspořádanému: jinými slovy, ordinální číslo je skutečně třídou ekvivalence dobře uspořádaných sad. Tuto definici je třeba v ZF a souvisejících systémech axiomatické teorie množin opustit, protože tyto třídy ekvivalence jsou příliš velké na to, aby vytvořily množinu. Tuto definici však stále lze použít v teorii typů a v Quineově teorii axiomatických množin Nové základy a související systémy (kde poskytuje poměrně překvapivé alternativní řešení Burali-Fortiho paradoxu největšího ordinálu).

Von Neumannova definice ordinálů

Spíše než definovat ordinál jako třídu ekvivalence dobře uspořádaných množin, bude definován jako konkrétní dobře uspořádaná množina, která (kanonicky) představuje třídu. Pořadové číslo tedy bude dobře uspořádaná množina; a každá dobře uspořádaná množina bude izomorfní přesně na jedno pořadové číslo.

Pro každý dobře uspořádané soustavě , definuje pořadí izomorfismus mezi a množinu všech podskupin , které mají tvar nařízené začlenění. To motivuje standardní definici, navrženou Johnem von Neumannem , nyní nazývanou definice von Neumannových řadovek : „každý pořadník je uspořádanou sadou všech menších řadovek.“ V symbolech, . Formálně: ${\ displaystyle T}$${\ displaystyle a \ mapsto T _ {<a}}$${\ displaystyle T}$${\ displaystyle T}$${\ Displaystyle T _ {<a}: = \ {x \ in T \ mid x <a \}}$${\ Displaystyle \ lambda = [0, \ lambda)}$

Množina S je pořadové číslo tehdy a jen tehdy, jestliže S je přísně spořádaný s ohledem na nastavenou členství a každý prvek S je podmnožina S .

Přirozená čísla jsou tedy podle této definice řadová. Například 2 je prvek 4 = {0, 1, 2, 3} a 2 se rovná {0, 1}, a je tedy podmnožinou {0, 1, 2, 3}.

Transfinitovou indukcí lze ukázat, že každá dobře uspořádaná množina je řádově izomorfní přesně k jednomu z těchto pořadových čísel, to znamená, že mezi nimi existuje řád zachovávající bijektivní funkci .

Kromě toho prvky každého pořadového čísla jsou samotné řadové. Vzhledem k tomu, dva řadové S a T , S je prvek T v případě, a pouze v případě, S je vlastní podmnožina z T . Navíc buď S je prvek T , nebo T je prvek S , nebo jsou si rovny. Každá sada pořadových čísel je tedy zcela uspořádaná . Kromě toho je každá řada pořadových řádků dobře uspořádaná. To zobecňuje skutečnost, že každá sada přirozených čísel je dobře uspořádaná.

V důsledku toho každý pořadové S je množina obsahující jako prvky přesně řadové menší než S . Například každá sada řadových řad má nadřazenost , pořadová hodnota získaná spojením všech řadových čísel v sadě. Toto sjednocení existuje bez ohledu na velikost sady podle axiomu sjednocení .

Třída všech pořadových čísel není sada. Pokud by to byla množina, dalo by se ukázat, že je to ordinál, a tedy člen sám sebe, což by odporovalo jejímu přísnému uspořádání členstvím. To je paradox Burali-Forti . Třída všech pořadových čísel se různě nazývá „ord“, „ON“ nebo „∞“.

Pořadové číslo je konečné tehdy a jen tehdy, je-li dobře uspořádáno i opačné pořadí, což je případ, kdy a pouze pokud má každá jeho neprázdná podmnožina maximum .

Jiné definice

Existují i ​​další moderní formulace definice ordinální. Například za předpokladu axiomu pravidelnosti jsou následující pro sadu x ekvivalentní :

• x je (von Neumann) pořadové číslo,
• x je tranzitivní množina a nastavené členství je trichotomické na x ,
• x je tranzitivní sada zcela seřazená podle zahrnutí sady,
• x je tranzitivní sada tranzitivních množin.

Tyto definice nelze použít v nepodložených teoriích množin . V množinových teoriích s urelementy je třeba dále zajistit, aby definice vylučovala urelementy z ordinals.

Transfinitní sekvence

Pokud α je jakýkoli pořadové a X je nastaveno, α-indexovaný sekvence prvků X je funkce, z a do X . Tento koncept, transfinitní sekvence (je-li α nekonečná) nebo pořadová indexovaná sekvence , je zobecněním pojmu sekvence . Běžná posloupnost odpovídá případu α ​​= ω, zatímco konečná α odpovídá n -tici , neboli řetězci .

Transfinitní indukce

Transfinitní indukce platí v každé dobře uspořádané sadě, ale je ve vztahu k pořadovým číslům tak důležitá, že zde stojí za to ji zopakovat.

Jakákoli vlastnost, která přechází z množiny řadových čísel menších než daná pořadová hodnota α na samotnou α, platí pro všechny pořadové čísla.

To znamená, že pokud P (α) platí, kdykoli P (β) platí pro všechna β <α , pak P (α) platí pro všechna α. Nebo praktičtěji: za účelem prokázání vlastnosti P pro všechny pořadové čísla α lze předpokládat, že je již známa pro všechna menší β <α .

Transfinitní rekurze

Transfinitní indukci lze použít nejen k prokázání věcí, ale také k jejich definování. Taková definice se obvykle říká transfinitní rekurzí -důkazem toho, že výsledek je dobře definovaný, je transfinitní indukce. Nechť F označuje funkci (třídy) F, která má být definována na pořadových číslech. Myšlenka nyní spočívá v tom, že při definování F (α) pro nespecifikovanou ordinální α lze předpokládat, že F (β) je již definována pro všechna β <α, a tedy poskytnout vzorec pro F (α) ve smyslu těchto F ( β). Transfinitovou indukcí pak vyplývá, že existuje jedna a pouze jedna funkce splňující rekurzivní vzorec až do α včetně.

Zde je příklad definice transfinitní rekurzí na řadových řadách (více bude uvedeno později): definujte funkci F tak, že necháte F (α) nejmenší pořadovou číslici, která není v sadě { F (β) | β <α} , tj. množina skládající se ze všech F (β) pro β <α . Tato definice předpokládá F (β) známý v samotném procesu definování F ; tento zjevný začarovaný kruh je přesně to, co definice transfinitní rekurze umožňuje. Ve skutečnosti má F (0) smysl, protože neexistuje pořadové β <0 a množina { F (β) | β <0} je prázdné. Takže F (0) se rovná 0 (nejmenší pořadové číslo ze všech). Nyní, F (0) je známo, definice aplikován na F (1) dává smysl (to je nejmenší tý není v sadě ojedinělým { F (0)} = {0} ), a tak dále (dále a tak dále je přesně transfinitní indukce). Ukazuje se, že tento příklad není příliš vzrušující, protože prokazatelně F (α) = α pro všechny pořadové řádky α, což lze přesně ukázat transfinitní indukcí.

Nástupce a mezní pořadové číslo

Libovolné nenulové pořadové číslo má minimální prvek, nulu. Může, ale nemusí mít maximální prvek. Například 42 má maximum 41 a ω+6 má maximální ω+5. Na druhou stranu ω nemá maximum, protože neexistuje žádné největší přirozené číslo. Pokud má pořadové číslo maximum α, pak je to další pořadové číslo za α a nazývá se následným pořadovým číslem , konkrétně nástupcem α, zapsaného α+1. Ve von Neumannově definici pořadových čísel je nástupcem α, protože jeho prvky jsou prvky α a α samotného. ${\ Displaystyle \ alpha \ cup \ {\ alpha \}}$

Nenulové pořadové číslo, které není nástupcem, se nazývá mezní pořadové číslo . Jedním zdůvodněním tohoto výrazu je, že mezní řadovka je mez v topologickém smyslu všech menších řadových řad (pod topologií řádu ).

Kdy je pořadová indexovaná sekvence, indexovaná limitou γ a sekvence se zvyšuje , tj. Kdykoli je její limit definován jako nejmenší horní hranice množiny , tj. Nejmenší pořadová hodnota (vždy existuje) větší než jakýkoli člen sekvence. V tomto smyslu je limitní řadovka limitem všech menších řadových řad (indexovaných sama). Řečeno příměji, je to supremum množiny menších pořadových čísel. ${\ Displaystyle \ langle \ alpha _ {\ iota} | \ iota <\ gamma \ rangle}$${\ Displaystyle \ alpha _ {\ iota} <\ alpha _ {\ rho}}$${\ Displaystyle \ iota <\ rho,}$${\ Displaystyle \ {\ alpha _ {\ iota} | \ iota <\ gamma \},}$

Dalším způsobem, jak definovat mezní pořadovou hodnotu, je říci, že α je mezní řadová hodnota právě tehdy, když:

Existuje pořadové číslo menší než α a kdykoli ζ je pořadové číslo menší než α, pak existuje pořadové číslo ξ takové, že ζ <ξ <α.

Takže v následujícím pořadí:

0, 1, 2,…, ω, ω+1

ω je mezní řadovka, protože pro jakoukoli menší řadovku (v tomto případě přirozené číslo) existuje další řadovka (přirozené číslo) větší než je, ale stále menší než ω.

Každý pořadový znak je tedy buď nula, nebo nástupce (přesně definovaného předchůdce), nebo limit. Toto rozlišení je důležité, protože na něm závisí mnoho definic pomocí transfinitní rekurze. Velmi často při definování funkce F transfinitní rekurzí na všech pořadových číslech definujeme F (0) a F (α+1) za předpokladu, že je definován F (α), a pak pro mezní pořadové číslo δ definujeme F (δ) jako mez F (β) pro všechny β <δ (buď ve smyslu řadových mezí, jak již bylo vysvětleno dříve, nebo pro nějaký jiný pojem limitu, pokud F nebere pořadové hodnoty). Zajímavým krokem v definici je tedy krok nástupce, nikoli mezní pořadové číslo. Takové funkce (zejména pro F nesnižující a přijímající pořadové hodnoty) se nazývají spojité. Řadové sčítání, násobení a umocňování jsou spojité jako funkce jejich druhého argumentu (ale mohou být definovány nerekurzivně).

Indexování tříd ordinálů

Každá dobře uspořádaná množina je podobná (řádově izomorfní) jedinečnému pořadovému číslu ; jinými slovy, jeho prvky mohou být indexovány rostoucím způsobem o pořadové číslo menší než . To platí zejména pro libovolnou sadu řadových čísel: jakákoli řada řadových čísel je přirozeně indexována řadovými řadami méně než některé . Totéž platí, s mírnou úpravou, pro třídy řadových řad (sbírka řadových čísel, možná příliš velká na to, aby vytvořila množinu, definovanou nějakou vlastností): libovolnou třídu řadových řad lze indexovat pořadovými čísly (a pokud je třída neomezená ve třídě všech řadových slov to znamená zařazení do třídy s třídou všech pořadových čísel). O -th elementu ve třídě (s konvencí, že „0-tý“ je nejmenší, „1-tý“ je další nejmenší atd.) Lze volně hovořit. Formálně je definice transfinitní indukcí: definován je -tý prvek třídy (za předpokladu, že již byl definován pro všechny ), jako nejmenší prvek větší než -tý prvek pro všechny . ${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$${\ displaystyle \ gamma}$${\ displaystyle \ gamma}$${\ displaystyle \ beta <\ gamma}$${\ displaystyle \ beta}$${\ displaystyle \ beta <\ gamma}$

To lze použít například na třídu limitních řadových čísel: -tý řadový, což je buď limit, nebo nula (viz řadová aritmetika pro definici násobení pořadových čísel). Podobně lze uvažovat aditivně nerozložitelné pořadové číslo (což znamená nenulový pořadový list, který není součtem dvou přísně menších pořadových čísel): -th aditivně nerozložitelný pořadový list je indexován jako . Technika indexování tříd řadových čísel je často užitečná v kontextu pevných bodů: například -tého ordinálu , který je zapsán . Říká se jim „ čísla epsilon “. ${\ displaystyle \ gamma}$${\ displaystyle \ omega \ cdot \ gamma}$${\ displaystyle \ gamma}$${\ displaystyle \ omega ^{\ gamma}}$${\ displaystyle \ gamma}$${\ Displaystyle \ alpha}$${\ Displaystyle \ omega ^{\ alpha} = \ alpha}$${\ displaystyle \ varepsilon _ {\ gamma}}$

Uzavřené neomezené sady a třídy

Třída z řadové se říká, že neomezená , nebo cofinal , pokud je podáván jakoukoliv řadové , je v takové, že (pak musí být třída správné třídy, tedy nemůže být soubor). Říká se, že je uzavřen, když je limit posloupnosti řadových čísel ve třídě opět ve třídě: nebo, ekvivalentně, když je funkce indexování (třídy -) spojitá v tom smyslu, že pro mezní pořadovou hodnotu ( - pořadové číslo ve třídě) je limit všech pro ; to je také totéž, co když je v topologickém smyslu uzavřeno pro topologii řádu (aby se zabránilo mluvit o topologii o správných třídách, je možné požadovat, aby byla průsečík třídy s jakýmkoli daným pořadovým číslem uzavřen pro topologii řádu na tomto pořadovém čísle , to je opět ekvivalentní). ${\ displaystyle C}$${\ Displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle C}$${\ displaystyle \ alpha <\ beta}$${\ displaystyle F}$${\ Displaystyle \ delta}$${\ Displaystyle F (\ delta)}$${\ Displaystyle \ delta}$${\ displaystyle F (\ gamma)}$${\ Displaystyle \ gamma <\ delta}$

Obzvláště důležité jsou ty třídy ordinálů, které jsou uzavřené a neomezené , někdy se jim říká kluby . Například třída všech mezních řadových čísel je uzavřená a neomezená: to překládá skutečnost, že vždy existuje mezní pořadová hodnota větší než daná řadová hodnota, a že mezní hodnota mezních pořadových čísel je mezní řadová hodnota (šťastná skutečnost, pokud je terminologie aby to vůbec dávalo smysl!). Třída aditivně nerozložitelných ordinálů, nebo třída ordinálů nebo třída kardinálů , jsou všechny uzavřeny bez omezení; množina pravidelných kardinálů je však neomezená, ale není uzavřena, a jakákoli konečná řada řadových čísel je uzavřená, ale není neomezená. ${\ displaystyle \ varepsilon _ {\ cdot}}$

Třída je nehybná, pokud má neprázdný průnik s každou uzavřenou neomezenou třídou. Všechny nadtřídy uzavřených neomezených tříd jsou stacionární a stacionární třídy jsou neomezené, ale existují stacionární třídy, které nejsou uzavřené, a stacionární třídy, které nemají žádnou uzavřenou neomezenou podtřídu (například třída všech limitních řadových řad s počitatelnou kofinalitou). Protože je průsečík dvou uzavřených neomezených tříd uzavřený a neomezený, je průnik stacionární třídy a uzavřené neomezené třídy stacionární. Ale průnik dvou stacionárních tříd může být prázdný, např. Třída pořadových čísel s kofinalitou ω s třídou řadových čísel s nepočítatelnou kofinalitou.

Spíše než formulovat tyto definice pro (řádné) třídy řadových řad je možné je formulovat pro množiny řadových řad pod daným pořadovým číslem : O podmnožině mezní pořadové hodnoty se říká, že je neomezená (nebo koncová) za předpokladu, že jakákoli pořadová hodnota menší než je menší než nějaké pořadové číslo v sadě. Obecněji lze nazvat podmnožinu jakéhokoli pořadového čísla za předpokladu, že každé pořadové číslo je menší než nebo stejné jako nějaké pořadové číslo v sadě. Podskupina se říká, že je uzavřena za předpokladu, že je uzavřena pro topologii řádu v , tj. Limit řadových čísel v sadě je buď v sadě, nebo se rovná sobě. ${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$ ${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$

Aritmetika řadových čísel

Existují tři obvyklé operace s pořadovými čísly: sčítání, násobení a (řadové) umocňování. Každý může být definován v zásadě dvěma různými způsoby: buď vytvořením explicitní dobře uspořádané sady, která představuje operaci, nebo pomocí transfinitní rekurze. Cantor normální forma poskytuje standardizovaný způsob psaní ordinals. Jedinečně představuje každý pořadový znak jako konečný součet řadových sil ω. To však nemůže tvořit základ univerzálního pořadového zápisu kvůli takovým sebereferenčním reprezentacím jako ε ₀ = ω ^{ε ₀} . Takzvané „přirozené“ aritmetické operace si zachovávají komutativitu na úkor kontinuity.

Vysvětlovány jako nimbers , ordinals také podléhají nimber aritmetickým operacím.

Ordinály a kardinálové

Počáteční pořadové číslo kardinála

Každý ordinál se spojuje s jedním kardinálem , svou mohutností. Existuje -li bijekce mezi dvěma pořadovými čísly (např. Ω = 1 + ω a ω + 1> ω ), spojí se se stejným kardinálem. Každá dobře uspořádaná množina, která má jako pořadový typ pořadové číslo, má stejnou mohutnost jako tento řadový. Nejmenší pořadová hodnota spojená s daným kardinálem se nazývá počáteční řadová hodnota tohoto kardinála. Každé konečné pořadové číslo (přirozené číslo) je počáteční a žádný jiný řadový pořadač s jeho kardinálem není spojen. Ale většina nekonečných pořadových čísel není počáteční, protože mnoho nekonečných pořadových čísel se spojuje se stejným kardinálem. Axiom výběru je ekvivalentní k prohlášení, že každý soubor může být spořádané, tedy že každý kardinál má počáteční pořadové číslo. V teoriích s axiomem volby má kardinální číslo jakékoli sady počáteční pořadové číslo a jako kardinální reprezentaci lze použít kardinální přiřazení Von Neumanna . (Musíme si však dát pozor na rozlišení mezi základní aritmetikou a řadovou aritmetikou.) V teoriích množin bez axiomu volby může být kardinál reprezentován množinou množin, jejichž kardinalita má minimální hodnost (viz Scottův trik ).

Jedním problémem Scotova triku je, že identifikuje základní číslo s , což je v některých formulacích pořadové číslo . Může být jasnější použít kardinální přiřazení Von Neumanna na konečné případy a použít Scottův trik pro sady, které jsou nekonečné nebo nepřijímají dobře uspořádané. Všimněte si, že základní a řadová aritmetika souhlasí s konečnými čísly. ${\ displaystyle 0}$${\ displaystyle \ {\ emptyset \}}$${\ displaystyle 1}$

Α-tý nekonečný počáteční ordinál je zapsán , je to vždy limitní ordinál. Jeho mohutnost je napsána . Například mohutnost ω ₀ = ω je , což je také mohutnost ω ² nebo ε ₀ (všechny jsou počitatelné pořadové číslo). Lze tedy ztotožnit ω s tím , že zápis se používá při psaní kardinálů a ω při psaní pořadových čísel (to je důležité, protože například = vzhledem k tomu ). Rovněž je nejmenší nespočetný pořadový znak (aby bylo vidět, že existuje, zvažte množinu tříd ekvivalence řádových uspořádání přirozených čísel: každé takové řádné uspořádání definuje počitatelné pořadové číslo a je typem pořadí dané množiny), je nejmenší ordinál, jejíž mohutnost je větší než atd., a je hranicí přirozených čísel n (jakýkoli limit kardinálů je kardinál, takže tato hranice je skutečně prvním kardinálem ). ${\ displaystyle \ omega _ {\ alpha}}$${\ Displaystyle \ aleph _ {\ alpha}}$${\ displaystyle \ aleph _ {0}}$${\ displaystyle \ aleph _ {0}}$${\ displaystyle \ aleph _ {0}}$${\ Displaystyle \ aleph _ {0}^{2}}$${\ displaystyle \ aleph _ {0}}$${\ displaystyle \ omega ^{2}> \ omega}$${\ displaystyle \ omega _ {1}}$${\ displaystyle \ omega _ {1}}$${\ displaystyle \ omega _ {2}}$${\ displaystyle \ aleph _ {1}}$${\ displaystyle \ omega _ {\ omega}}$${\ displaystyle \ omega _ {n}}$${\ displaystyle \ omega _ {n}}$

Součinnost

Kofinál z pořadové číslo je nejmenší řadová , že je typ pořadí z cofinal podmnožiny . Všimněte si, že řada autorů definuje kofinalitu nebo ji používá pouze pro limitní pořadové číslo. Kofinalita množiny pořadových čísel nebo jakékoli jiné dobře uspořádané množiny je kofinalitou typu objednávky dané sady. ${\ Displaystyle \ alpha}$${\ Displaystyle \ delta}$${\ Displaystyle \ alpha}$

Takže pro limitní ordinál existuje -indexovaná přísně rostoucí sekvence s limitem . Například cofinalita ω ² je ω, protože posloupnost ω · m (kde m se pohybuje nad přirozenými čísly) má tendenci k ω ² ; ale obecněji má jakákoli spočítatelná mezní hodnota cofinality ω. Nespočitatelná mezní hodnota může mít buď součinnost ω stejně, nebo nepočítatelnou součinnost. ${\ Displaystyle \ delta}$${\ Displaystyle \ alpha}$${\ displaystyle \ omega _ {\ omega}}$

Kofinalita 0 je 0. A cofinalita jakéhokoli následného pořadového čísla je 1. Kofinalita jakéhokoli limitního pořadového čísla je minimálně . ${\ displaystyle \ omega}$

Pořadové číslo, které se rovná jeho cofinalitě, se nazývá pravidelné a je vždy počátečním pořadovým číslem. Jakýkoli limit pravidelných pořadových čísel je limitem počátečních řadových čísel, a je tedy také počáteční, i když není pravidelný, což obvykle není. Pokud je axiom volby, pak je pravidelný pro každé α. V tomto případě, řadové 0, 1, , , a jsou pravidelné, vzhledem k tomu, 2, 3, a omega _{omega · 2} jsou počáteční řadové, které nejsou pravidelné. ${\ displaystyle \ omega _ {\ alpha +1}}$${\ displaystyle \ omega}$${\ displaystyle \ omega _ {1}}$${\ displaystyle \ omega _ {2}}$${\ displaystyle \ omega _ {\ omega}}$

Kofinalita libovolné ordinální α je regulární ordinální, tj. Kofinalita kofinality α je stejná jako kofinalita α . Operace kofinality je tedy idempotentní .

Nějaké „velké“ spočitatelné ordinály

Jak je uvedeno výše (viz Cantor normální forma ), pořadové ε ₀ je nejmenší splňující rovnici , takže je limit sekvence 0, 1, , , , atd Mnoho řadové mohou být definovány takovým způsobem, jako pevné body určitých ordinálních funkcí ( -th ordinal, který se nazývá , pak by se dalo pokračovat ve snaze najít -th ordinal tak, že „a tak dále“, ale veškerá jemnost spočívá v „a tak dále“). Dalo by se to zkusit udělat systematicky, ale bez ohledu na to, jaký systém se používá k definování a konstrukci pořadových čísel, vždy existuje pořadové číslo, které leží těsně nad všemi pořadovými čísly vytvořenými systémem. Snad nejdůležitější pořadové číslo, které omezuje systému konstrukce tímto způsobem je Church-Kleene pořadové číslo , (i přes jméno, toto pořadové je spočetná), což je nejmenší řadové, které nemohou být v žádném případě reprezentovanou počítačově funkcí (to může být samozřejmě přísné). Níže však lze definovat značně velké pořadové číslo , které měří „důkazně teoretickou sílu“ určitých formálních systémů (například měří sílu Peanovy aritmetiky ). Nad ordinálem Church-Kleene lze také definovat velké počitatelné ordinály, jako jsou počitatelné přípustné ordinály , které jsou zajímavé v různých částech logiky. ${\ Displaystyle \ omega ^{\ alpha} = \ alpha}$${\ displaystyle \ omega}$${\ displaystyle \ omega ^{\ omega}}$${\ displaystyle \ omega ^{\ omega ^{\ omega}}}$${\ Displaystyle \ iota}$${\ Displaystyle \ omega ^{\ alpha} = \ alpha}$${\ displaystyle \ varepsilon _ {\ iota}}$${\ Displaystyle \ iota}$${\ Displaystyle \ varepsilon _ {\ alpha} = \ alpha}$${\ displaystyle \ omega _ {1}^{\ mathrm {CK}}}$${\ displaystyle \ omega _ {1}}$${\ displaystyle \ omega _ {1}^{\ mathrm {CK}}}$${\ displaystyle \ varepsilon _ {0}}$

Topologie a pořadové číslo

Libovolné pořadové číslo může být převedeno do topologického prostoru tím, že je vybaveno topologií řádu ; tato topologie je diskrétní tehdy a jen tehdy, je -li ordinál počitatelným kardinálem, tj. nanejvýš ω. Podmnožina ω + 1 je v topologii řádu otevřená právě tehdy, pokud je buď cofinitová, nebo neobsahuje ω jako prvek.

Viz část Topologie a pořadové číslo v článku „Topologie objednávky“.

Dolů uzavřené sady řadových řad

Sada je uzavřena směrem dolů, pokud je v sadě také něco menšího než prvek sady. Pokud je řada řadových čísel uzavřena směrem dolů, pak je tato množina řadová - nejmenší pořadová hodnota, která v sadě není.

Příklady:

• Množina pořadových čísel menší než 3 je 3 = {0, 1, 2}, nejmenší pořadová hodnota ne menší než 3.
• Množina konečných pořadových čísel je nekonečná, nejmenší nekonečná pořadová hodnota: ω.
• Množina počitatelných pořadových čísel je nepočitatelná, nejmenší nespočitatelná pořadová hodnota: ω ₁ .

Dějiny

Transfinitní pořadová čísla, která se poprvé objevila v roce 1883, vznikla v Cantorově práci s odvozenými množinami . Jestliže P je množina reálných čísel, odvozená množina P‘ je množina koncových bodů z P . V roce 1872, Cantor generované množiny P ^{( n )} za použití odvozené nastavenou operaci n krát k P . V roce 1880 poukázal na to, že tyto sady tvoří posloupnost P '  ⊇ ··· ⊇  P ^{( n )}  ⊇  P ^{( n  + 1)}  ⊇ ··· a pokračoval v procesu odvozování definováním P ^(∞) jako průsečíku těchto sad. Poté iteroval odvozenou množinovou operaci a křižovatky, aby rozšířil svou posloupnost množin do nekonečna: P ^(∞)  ⊇  P ^{(∞ + 1)}  ⊇  P ^{(∞ + 2)}  ⊇ ··· ⊇  P ^(2∞)  ⊇ ·· · ⊇  P ^{(∞ 2 )}  ⊇ ···. Horní indexy obsahující ∞ jsou pouze indexy definované procesem derivace.

Cantor použil tyto věty ve větách: (1) Pokud P ^(α)  = ∅ pro nějaký index α, pak P ' je spočitatelné; (2) Naopak, pokud je P ' spočitatelné, pak existuje index α takový, že P ^(α)  = ∅. Tyto věty jsou dokázány rozdělením P ' do párových disjunktních množin: P'  = ( P '  ∖  P ⁽²⁾ ) ∪ ( P ⁽²⁾  ∖  P ⁽³⁾ ) ∪ ··· ∪ ( P ^(∞)  ∖  P ^{( ∞ + 1)} ) ∪ ··· ∪  P ^(α) . Pro β <α: protože P ^{(β + 1)} obsahuje mezní body P ^(β) , sady P ^(β)  ∖  P ^{(β + 1)} nemají žádné mezní body. Jsou to tedy diskrétní sady , takže je lze spočítat. Důkaz první věty: Pokud P ^(α)  = ∅ pro nějaký index α, pak P ' je spočitatelné spojení počitatelných množin. Proto je P ' počitatelné.

Druhá věta vyžaduje dokázat existenci α tak, aby P ^(α)  = ∅. Aby to dokázal, Cantor považoval množinu všech α za spočítatelně mnoho předchůdců. Aby definoval tuto množinu, definoval transfinitní pořadová čísla a transformoval nekonečné indexy na pořadové čísla nahrazením ∞ ω, prvním transfinitálním pořadovým číslem. Cantor nazval množinu konečných pořadových čísel první číselnou třídou . Druhá číselná třída je množina řadových řad, jejichž předchůdci tvoří spočitatelně nekonečnou množinu. Množina všech α mající spočítatelně mnoho předchůdců - tj. Množina počitatelných pořadových čísel - je sjednocením těchto dvou číselných tříd. Cantor dokázal, že mohutnost druhé číselné třídy je první nespočetnou mohutností.

Druhá Cantorova věta se stává: Je -li P ' spočitatelné, pak existuje počitatelné pořadové číslo α takové, že P ^(α)  = ∅. Jeho důkaz používá důkaz rozporem . Nechť P ' je počitatelné a předpokládejme, že takové α neexistuje. Tento předpoklad vytváří dva případy.

V obou případech je P ' nepočitatelné, což je v rozporu s tím, že P' je počitatelné. Proto existuje počitatelná pořadová hodnota α taková, že P ^(α)  = ∅. Cantorova práce s odvozenými množinami a pořadovými čísly vedla k Cantorově-Bendixsonově větě .

Pomocí nástupců, limitů a mohutnosti vygeneroval Cantor neomezenou posloupnost řadových čísel a číselných tříd. (Α + 1) -tá číselná třída je množina pořadových čísel, jejichž předchůdci tvoří množinu stejné mohutnosti jako α-ta číselná třída. Mohutnost (α + 1) -té číselné třídy je mohutnost bezprostředně následující po α-té číselné třídě. Pro limitní ordinální α je α-tá číselná třída sjednocením β-tých číselných tříd pro β <α. Jeho mohutnost je limitem kardinalit těchto číselných tříd.

Je -li n konečné, má n -tá číselná třída mohutnost . Pokud α ≥ ω, α-tá číselná třída má mohutnost . Kardinality číselných tříd proto odpovídají jedna k jedné s alefskými čísly . Třída α-tého čísla se také skládá z řadových čísel odlišných od těch v předchozích číslových třídách právě tehdy, když α je nelimitní pořadová hodnota. Neomezené číselné třídy proto rozdělí řadové číslice do párových disjunktních sad. ${\ Displaystyle \ aleph _ {n-1}}$${\ Displaystyle \ aleph _ {\ alpha}}$

Viz také

• Počítací
• Sudé a liché pořadové číslo
• První nespočetný řadový
• Pořadový prostor
• Neskutečné číslo , zobecnění pořadových čísel , které zahrnuje negativy

Poznámky

Reference

externí odkazy

• „Pořadové číslo“ , encyklopedie matematiky , EMS Press , 2001 [1994]
• Ordinals ve společnosti ProvenMath
• Pořadová kalkulačka Bezplatný software GPL pro výpočet s pořadovými čísly a pořadovými čísly
• Kapitola 4 přednášek Dona Monka o teorii množin je úvodem do řadových slov.