Válcování - Cylindrification

v teorie vypočítatelnosti A válcování je konstrukce, která sdružuje a válcové číslování ke každému číslování. Koncept byl poprvé představen Yuri L. Ershov v roce 1973.

Definice

Vzhledem k číslování ${ displaystyle nu}$ the válcování ${ displaystyle c ( nu)}$ je definován jako

${ displaystyle mathrm {doména} (c ( nu)): = { langle n, k rangle | n in mathrm {doména} ( nu) }}$

${ displaystyle c ( nu) langle n, k rangle: = nu (i)}$

kde ${ displaystyle langle n, k rangle}$ je Funkce párování Cantor. Operace cylindrifikace bere vztah jako vstup arity k a vydává relaci arity k + 1 následovně: Vzhledem k relaci R arity K je její cylindrifikace označená c (R) následující množinou {(a1 ,. .., ak, a) | (a1, ..., ak) patří R a a patří A}. Všimněte si, že operace válcování zvyšuje arititu vstupu o 1.

Vlastnosti

• Vzhledem k dvěma číslováním ${ displaystyle nu}$ a ${ displaystyle mu}$ pak ${ displaystyle nu leq mu levá šipka c ( nu) leq _ {1} c ( mu)}$
• ${ displaystyle nu leq _ {1} c ( nu)}$

Reference

• Yu. L. Ershov, „Theorie der Numerierungen I.“ Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).