원시재귀 집합함수

Primitive recursive set function

수학에서 원시 재귀 집합함수 또는 원시 재귀 순서함수는 원시 재귀함수의 아날로그로, 자연수가 아닌 세트나 서수에 대해 정의된다.그것들은 옌센과 카프(1971)에 의해 소개되었다.

정의

원시재귀 집합함수는 다음과 같은 치환 및 재귀 규칙을 반복적으로 적용함으로써 다음과 같은 기본함수로부터 얻을 수 있는 집합에서 집합까지의 함수다.

기본 기능은 다음과 같다.

  • 투영: Pn,m (x1, ..., xn) = 0 ≤ m ≤ n에 대한m x
  • 0: F(x) = 0
  • 요소를 집합에 연결: F(x, y) = x ∪ {y}
  • 시험 멤버십: C(x, y, u, v) = u ∈ v인 경우 x, C(x, y, u, v) = otherwise.

대체에 의한 새로운 기능의 생성에 관한 것이다.

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

여기서 x와 y는 변수의 유한 시퀀스다.

재귀에 의해 새로운 기능을 생성하는 규칙은

  • F(z, x) = G(u ∈ zf(u, x), z, x)

초기 함수 F(x, y) = x ∪ {y}이(가) F(x) = x ∪ {x}(x의 후속)으로 대체되는 것을 제외하고 원시 재귀 서수함수는 동일한 방법으로 정의된다.원시 재귀 서수함수는 서수를 서수에 매핑하는 원시 재귀 집합 함수와 동일하다.

또한 더 큰 종류의 함수를 얻기 위해 더 많은 초기 함수를 추가할 수 있다.예를 들어, 순서 함수 Ω은α 원시 재귀가 아니다. 왜냐하면 값 Ω(또는 다른 무한 세트)이 있는 상수 함수는 원시 재귀가 아니기 때문에 이 상수 함수를 초기 함수에 추가하기를 원할 수 있기 때문이다.

참조

  • Jensen, Ronald B.; Karp, Carol (1971), "Primitive recursive set functions", Axiomatic Set Theory, Proc. Sympos. Pure Math., vol. XIII, Part I, Providence, R.I.: Amer. Math. Soc., pp. 143–176, ISBN 9780821802458, MR 0281602