Funkce Veblen - Veblen function

v matematika, Veblen funkce jsou hierarchií normální funkce (kontinuální přísně se zvyšuje funkce z řadové pořadovým řádům), který zavedl Oswald Veblen v Veblen (1908). Pokud φ₀ je libovolná normální funkce, pak pro jakoukoli nenulovou ordinální α, φ_α je funkce výčtu společné pevné body φ_β pro β <α. Všechny tyto funkce jsou normální.

Veblenova hierarchie

Ve zvláštním případě, když φ₀(α) = ω^αtato rodina funkcí je známá jako Veblenova hierarchie. Funkce φ₁ je stejný jako ε funkce: φ₁(α) = ε_α. Li ${displaystyle alpha$ pak ${displaystyle varphi _ {alpha} (varphi _ {eta} (gamma)) = varphi _ {eta} (gamma) ,.}$ Z toho a ze skutečnosti, že φ_β se přísně zvyšuje, dostáváme objednání: ${displaystyle varphi _ {alpha} (eta)$ jen a jen pokud buď (${displaystyle alpha = gamma}$ a ${displaystyle eta$) nebo (${displaystyle alpha$ a ${displaystyle eta$) nebo (${displaystyle alpha> gamma}$ a ${displaystyle varphi _ {alpha} (eta)$).

Základní sekvence pro hierarchii Veblen

Základní posloupnost ordinálu s spolufinancování ω je rozlišovací přísně rostoucí ω-sekvence, která má jako limit ordinál. Pokud má někdo základní posloupnosti pro α a všechny menší limitní ordinály, může vytvořit explicitní konstruktivní bijekci mezi ω a α (tj. Nepoužívat axiom výběru). Zde popíšeme základní posloupnosti pro Veblenovu hierarchii ordinálů. Obrázek uživatele n pod základní posloupností pro α bude označeno α [n].

Varianta Cantor normální forma použitý v souvislosti s Veblenovou hierarchií je - každé nenulové pořadové číslo α lze jednoznačně zapsat jako ${displaystyle alpha = varphi _ {eta _ {1}} (gamma _ {1}) + varphi _ {eta _ {2}} (gamma _ {2}) + cdots + varphi _ {eta _ {k}} ( gamma _ {k})}$, kde k> 0 je přirozené číslo a každý člen za prvním je menší nebo roven předchozímu členu, ${displaystyle varphi _ {eta _ {m}} (gama _ {m}) geq varphi _ {eta _ {m + 1}} (gama _ {m + 1}) ,,}$ a každý ${displaystyle gamma _ {m}$ Pokud lze pro poslední člen zadat základní posloupnost, lze tento člen nahradit takovou posloupností ${displaystyle alpha [n] = varphi _ {eta _ {1}} (gamma _ {1}) + cdots + varphi _ {eta _ {k-1}} (gamma _ {k-1}) + (varphi _ {eta _ {k}} (gama _ {k}) [n]) ,.}$

Pro libovolné β, pokud γ je limit s ${displaystyle gamma$ pak nech ${displaystyle varphi _ {eta} (gama) [n] = varphi _ {eta} (gama [n]) ,.}$

Nelze zajistit žádnou takovou sekvenci ${displaystyle varphi _ {0} (0)}$ = ω⁰ = 1, protože nemá společnou definici ω.

Pro ${displaystyle varphi _ {0} (gamma +1) = omega ^ {gamma +1} = omega ^ {gamma} cdot omega ,,}$ vybíráme si ${displaystyle varphi _ {0} (gama +1) [n] = varphi _ {0} (gama) cdot n = omega ^ {gamma} cdot n ,.}$

Pro ${displaystyle varphi _ {eta +1} (0) ,,}$ používáme ${displaystyle varphi _ {eta +1} (0) [0] = 0}$ a ${displaystyle varphi _ {eta +1} (0) [n + 1] = varphi _ {eta} (varphi _ {eta +1} (0) [n]) ,,}$ tj. 0, ${displaystyle varphi _ {eta} (0)}$, ${displaystyle varphi _ {eta} (varphi _ {eta} (0))}$, atd..

Pro ${displaystyle varphi _ {eta +1} (gama +1)}$, používáme ${displaystyle varphi _ {eta +1} (gama +1) [0] = varphi _ {eta +1} (gama) +1}$ a ${displaystyle varphi _ {eta +1} (gama +1) [n + 1] = varphi _ {eta} (varphi _ {eta +1} (gama +1) [n]) ,.}$

Nyní předpokládejme, že β je limit:

Li ${displaystyle eta$, pak nechte ${displaystyle varphi _ {eta} (0) [n] = varphi _ {eta [n]} (0),}}$

Pro ${displaystyle varphi _ {eta} (gama +1)}$, použijte ${displaystyle varphi _ {eta} (gama +1) [n] = varphi _ {eta [n]} (varphi _ {eta} (gama) +1) ,.}$

Jinak nelze řadový řadit pomocí menších řadových řádků ${displaystyle varphi}$ a toto schéma se na něj nevztahuje.

Funkce Γ

Funkce Γ vyjmenuje ordinály α tak, že φ_α(0) = α. Γ₀ je Feferman – Schütte pořadové číslo, tj. je to nejmenší α takové, že φ_α(0) = α.

Pro Γ₀, lze zvolit základní posloupnost ${displaystyle Gamma _ {0} [0] = 0}$ a ${displaystyle Gamma _ {0} [n + 1] = varphi _ {Gamma _ {0} [n]} (0),}}$

Pro Γ_{β + 1}, nechť ${displaystyle Gamma _ {eta +1} [0] = Gamma _ {eta} +1}$ a ${displaystyle Gamma _ {eta +1} [n + 1] = varphi _ {Gamma _ {eta +1} [n]} (0),}}$

Pro Γ_β kde ${displaystyle eta$ je limit, pojďme ${displaystyle Gamma _ {eta} [n] = Gamma _ {eta [n]} ,.}$

Zobecnění

Konečně mnoho proměnných

Chcete-li vytvořit funkci Veblen z konečného počtu argumentů (finitární funkce Veblen), nechte binární funkci ${displaystyle varphi (alfa, gama)}$ být ${displaystyle varphi _ {alpha} (gama)}$ jak je definováno výše.

Nechat ${displaystyle z}$ být prázdný řetězec nebo řetězec skládající se z jedné nebo více nul oddělených čárkami ${displaystyle 0,0, ..., 0}$ a ${displaystyle s}$ být prázdný řetězec nebo řetězec skládající se z jednoho nebo více řadových znaků oddělených čárkami ${displaystyle alpha _ {1}, alpha _ {2}, ..., alpha _ {n}}$ s ${displaystyle alpha _ {1}> 0}$. Binární funkce ${displaystyle varphi (eta, gamma)}$ lze psát jako ${displaystyle varphi (s, eta, z, gamma)}$ kde oba ${displaystyle s}$ a ${displaystyle z}$ jsou prázdné řetězce. Finitární funkce Veblen jsou definovány takto:

• ${displaystyle varphi (gamma) = omega ^ {gamma}}$
• ${displaystyle varphi (z, s, gama) = varphi (s, gama)}$
• -li ${displaystyle eta> 0}$, pak ${displaystyle varphi (s, eta, z, gama)}$ označuje ${displaystyle (1 + gamma)}$-tý společný pevný bod funkcí ${displaystyle xi mapsto varphi (s, delta, xi, z)}$ pro každého ${displaystyle delta$

Například, ${displaystyle varphi (1,0, gama)}$ je ${displaystyle (1 + gamma)}$-tý pevný bod funkcí ${displaystyle xi mapsto varphi (xi, 0)}$, jmenovitě ${displaystyle Gamma _ {gamma}}$; pak ${displaystyle varphi (1,1, gama)}$ výčet pevných bodů této funkce, tj ${displaystyle xi mapsto Gamma _ {xi}}$ funkce; a ${displaystyle varphi (2,0, gama)}$ vyjmenuje pevné body všech ${displaystyle xi mapsto varphi (1, xi, 0)}$. Každá instance zobecněných funkcí Veblen je v poslední nenulové proměnná (tj. pokud se má proměnná měnit a všechny pozdější proměnné se udržují neustále rovné nule).

Řadový ${displaystyle varphi (1,0,0,0)}$ je někdy známý jako Ackermann pořadový. Hranice ${displaystyle varphi (1,0, ..., 0)}$ kde počet nul se pohybuje nad ω, je někdy známý jako „Malý“ Veblen pořadový.

Každý nenulový ordinál ${displaystyle alpha}$ méně než malý Veblenův ordinál (SVO) lze jednoznačně napsat v normální formě pro finitární funkci Veblen:

${displaystyle alpha = varphi (s_ {1}) + varphi (s_ {2}) + cdots + varphi (s_ {k})}$

kde

• ${displaystyle k}$ je kladné celé číslo
• ${displaystyle varphi (s_ {1}) geq varphi (s_ {2}) geq cdots geq varphi (s_ {k})}$
• ${displaystyle s_ {m}}$ je řetězec skládající se z jednoho nebo více řadových znaků oddělených čárkami ${displaystyle alpha _ {m, 1}, alpha _ {m, 2}, ..., alpha _ {m, n_ {m}}}$ kde ${displaystyle alpha _ {m, 1}> 0}$ a každý ${displaystyle alpha _ {m, i}$

Základní posloupnosti pro limitní ordinály finitární Veblenovy funkce

Pro limitní ordinály ${displaystyle alpha$, napsaný v normální formě pro finitární funkci Veblen:

• ${displaystyle (varphi (s_ {1}) + varphi (s_ {2}) + cdots + varphi (s_ {k})) [n] = varphi (s_ {1}) + varphi (s_ {2}) + cdots + varphi (s_ {k}) [n]}$,
• ${displaystyle varphi (gamma) [n] = left {{egin {array} {lcr} nquad {ext {if}} quad gamma = 1 varphi (gamma -1) cdot nquad {ext {if}} quad gamma quad { ext {je pořadovým pořadím}} varphi (gamma [n]) quad {ext {if}} quad gamma quad {ext {je limitní pořadové číslo}} end {pole}} ight.}$,
• ${displaystyle varphi (s, eta, z, gama) [0] = 0}$ a ${displaystyle varphi (s, eta, z, gama) [n + 1] = varphi (s, eta -1, varphi (s, eta, z, gama) [n], z)}$ -li ${displaystyle gamma = 0}$ a ${displaystyle eta}$ je pořadovým nástupcem,
• ${displaystyle varphi (s, eta, z, gama) [0] = varphi (s, eta, z, gama -1) +1}$ a ${displaystyle varphi (s, eta, z, gama) [n + 1] = varphi (s, eta -1, varphi (s, eta, z, gama) [n], z)}$ -li ${displaystyle gamma}$ a ${displaystyle eta}$ jsou pořadovými řády nástupce,
• ${displaystyle varphi (s, eta, z, gama) [n] = varphi (s, eta, z, gama [n])}$ -li ${displaystyle gamma}$ je limitní pořadové číslo,
• ${displaystyle varphi (s, eta, z, gama) [n] = varphi (s, eta [n], z, gama)}$ -li ${displaystyle gamma = 0}$ a ${displaystyle eta}$ je limitní pořadové číslo,
• ${displaystyle varphi (s, eta, z, gama) [n] = varphi (s, eta [n], varphi (s, eta, z, gama -1) + 1, z)}$ -li ${displaystyle gamma}$ je nástupcem pořadového čísla a ${displaystyle eta}$ je limitní pořadové číslo.

Transfinitivně mnoho proměnných

Obecněji Veblen ukázal, že φ lze definovat i pro transfinitní posloupnost ordinálů α_β, za předpokladu, že všechny kromě konečného počtu jsou nulové. Všimněte si, že pokud je taková posloupnost řadových čísel vybrána z těch méně než nespočetných řádný kardinál κ, pak může být sekvence kódována jako jeden ordinál menší než κ^κ. Jeden tedy definuje funkci φ z κ^κ do κ.

Definici lze uvést následovně: let α být transfinitní posloupností řadových čísel (tj. řadová funkce s konečnou podporou) která končí nulou (tj. takové, že α₀ = 0), a nechat α[0↦γ] označuje stejnou funkci, kde konečná 0 byla nahrazena γ. Pak γ↦φ (α[0↦γ]) je definována jako funkce vyjmenující společné pevné body všech funkcí ξ↦φ (β) kde β rozsahy přes všechny sekvence, které jsou získány snížením nejmenší nenulové hodnoty nenulové hodnoty α a nahrazení nějaké menší indexované hodnoty neurčitým ξ (tj. β=α[ι₀↦ζ, ι↦ξ] znamená, že pro nejmenší index ι₀ takový, že α_ι₀ je nenulová, druhá byla nahrazena nějakou hodnotou ζ <α_ι₀ a že pro nějaký menší index ι <ι₀ je hodnota α_ι= 0 byl nahrazen ξ).

Například pokud α= (ω↦1) označuje transfinitní posloupnost s hodnotou 1 na ω a 0 všude jinde, pak φ (ω↦1) je nejmenší pevný bod ze všech funkcí ξ↦φ (ξ, 0,…, 0) s konečně mnoho konečných nul (to je také limit φ (1,0,…, 0) s konečně mnoha nulami, malá Veblenova ordinální část).

Nejmenší pořadové α, takže α je větší než φ, aplikované na jakoukoli funkci s podporou v α (tj. Které nelze dosáhnout „zdola“ pomocí Veblenovy funkce transfinitivně mnoha proměnných) je někdy známé jako „Velký“ Veblen pořadový.

Reference

• Hilbert Levitz, Transfinitní ordinálové a jejich notace: Pro nezasvěcené, výkladový článek (8 stran, v PostScript )
• Pohlers, Wolfram (1989), Teorie důkazůPřednášky z matematiky, 1407, Berlín: Springer-Verlag, doi:10.1007/978-3-540-46825-7, ISBN  978-3-540-51842-6, PAN  1026933
• Schütte, Kurt (1977), Teorie důkazůGrundlehren der Mathematischen Wissenschaften, 225, Berlín-New York: Springer-Verlag, str. Xii + 299, ISBN  978-3-540-07911-8, PAN  0505313
• Takeuti, Gaisi (1987), Teorie důkazů„Studium logiky a základy matematiky, 81 (Second ed.), Amsterdam: North-Holland Publishing Co., ISBN  978-0-444-87943-1, PAN  0882549
• Smorynski, C. (1982), „Odrůdy stromové zkušenosti“, Matematika. Vyzvědač, 4 (4): 182–189, doi:10.1007 / BF03023553 obsahuje neformální popis hierarchie Veblen.
• Veblen, Oswald (1908), „Neustálé zvyšování funkcí konečných a transfinitních ordinálů“, Transakce Americké matematické společnosti, 9 (3): 280–292, doi:10.2307/1988605, JSTOR  1988605
• Miller, Larry W. (1976), „Normální funkce a konstruktivní řadové notace“, The Journal of Symbolic Logic, 41 (2): 439–459, doi:10.2307/2272243, JSTOR  2272243