Funkce primitivní rekurzivní množiny - Primitive recursive set function

v matematika, primitivní rekurzivní množinové funkce nebo primitivní rekurzivní řadové funkce jsou analogy primitivní rekurzivní funkce, definované pro sady nebo řadové spíše než přirozená čísla. Byly představeny Jensen & Karp (1971).

Definice

Funkce primitivní rekurzivní množiny je a funkce ze sad do sad, které lze získat z následujících základních funkcí opakovaným použitím následujících pravidel substituce a rekurze:

Základní funkce jsou:

• Projekce: P_n,m(X₁, ..., X_n) = X_m pro 0 ≤m ≤ n
• Nula: F(X) = 0
• Sloučení prvku s množinou: F(X, y) = X ∪ {y}
• Testování členství: C(X, y, u, proti) = X -li u ∈ proti, a C(X, y, u, proti) = y v opačném případě.

Pravidla pro generování nových funkcí substitucí jsou

• F(X, y) = G(X, H(X), y)
• F(X, y) = G(H(X), y)

kde X a y jsou konečné posloupnosti proměnných.

Pravidlo pro generování nových funkcí rekurzí je

• F(z, X) = G(∪_u ∈ z F(u, X), z, X)

Primitivní rekurzivní pořadová funkce je definována stejným způsobem, s výjimkou počáteční funkce F(X, y) = X ∪ {y} je nahrazen F(X) = X ∪ {X} ( nástupce z X). Primitivní rekurzivní ordinální funkce jsou stejné jako primitivní rekurzivní sady funkcí, které mapují ordinály na ordinály.

Lze také přidat více počátečních funkcí a získat větší třída funkcí. Například pořadová funkce ω^α není primitivní rekurzivní, protože konstantní funkce s hodnotou ω (nebo jakoukoli jinou nekonečná sada ) není primitivní rekurzivní, takže je možné přidat tuto konstantní funkci k původním funkcím.

Reference

• Jensen, Ronald B .; Karp, Carol (1971), „Primitivní rekurzivní množinové funkce“, Teorie axiomatických množin, Proc. Symposy. Pure Math., XIII, Part I, Providence, R.I .: Amer. Matematika. Soc., S. 143–176, ISBN  9780821802458, PAN  0281602