OrdinalAnalysis(PA) Pohlers

산술의 언어(language of arithmetic)

산술의 언어 \(\mathcal{L} (\mathsf{NT}):=\mathcal{L} (\mathscr{C} ,\mathscr{F} ,\mathscr{R} )\) 를 정의하려면 그것의 시그니처를 정의하는 것으로 충분하다. \(\mathcal{L}(\mathsf{NT})\) 의 시그니처를 같이 정의한다.

• \(\mathscr{C} := \{\underline{0}\}\)
• \(\mathscr{F} := \{f : f \text{ 는 원시 재귀 함수 항의 기호이다 }\}\) (항수 \(\#\underline{f}\) 는 원시 재귀 함수 항의 항수이다)
• \(\mathscr{R} := \{=\}\) (\(=\) 의 항수는 \(2\) 이다)

\(\mathcal{L}(\mathsf{NT})\)-항을 산술적 항(arithmetical term)이라고 한다.

\(\mathcal{L}(\mathsf{NT})\)-식 \(F\) 가 \(\operatorname{FV}_{2}(F) = \operatorname{BV}_{2}(F) = \varnothing\) 이면 산술적이라고 한다.

자연수 구조(structure of natural number)

자연수 구조 \(\N := (\N ,^{\N })\) 를 다음과 같이 정의한다. 자연수 구조 \(\N\) 은 \(\mathcal{L}(\mathsf{NT})\) 의 표준 모델이다.

• \(\underline{0}^{\N } := 0\)
• \(\underline{f}^{\N }\) 를 \(f\) 에 의하여 표현되는 함수로 정의한다. 즉, 정의 2.1.2 에 따라 \(\underline{f}^{\N }(z_1, \dots, z_n) := \operatorname{ev}(f, z_1, \dots, z_n)\) 이다.
• \(z_1 = ^{\N }z_2 : \iff z_1 = z_2\). 즉, \(= ^{\N }\) 는 자연수 위의 동등성으로 해석된다.

보조정리 5.1.2

산술적 항 \(t\) 와 \(\Phi (v) = z\) 인 \(\N\)-할당 \(\Phi\) 를 잡으면 다음이 성립한다.

보조정리 5.1.3

\(\mathcal{L}(\mathsf{NT})\)-식 \(F\) 와 \(\Phi (v) = z\) 인 \(\N\)-할당 \(\Phi\) 를 잡으면 다음이 성립한다.

정리 5.1.4 1차 논리 양화의 만족 관계의 정의

\(\mathcal{L}(\mathsf{NT})\)-식 \(F(v)\) 를 잡으면 다음이 성립한다.

\(\N \vDash (\forall x)F_v(x) [\Phi ] \iff\) 모든 \(z \in \N\) 에 대하여 \(\N \vDash F_v(\underline{z})[\Phi ]\)

\(\N \vDash (\exists x)F_v(x)[\Phi ] \iff\) 어떤 \(z \in \N\) 에 대하여 \(\N \vDash F_v(\underline{z})[\Phi ]\)

\(\mathcal{L}(\mathsf{NT})\)-정의가능한 식

다음을 만족하는 \(\mathcal{L}(\mathsf{NT})\) 식 \(F(u, v_1, \dots, v_n)\) 와 자연수 \(z_1, \dots, z_n\) 이 존재하면 부분집합 \(A \subseteq \N\) 을 \(\mathcal{L}(\mathsf{NT})\)-정의가능하다고 한다.

\(\mathcal{L}\)-식의 계층

\(\mathcal{L}\)-식에 대한 계층을 다음과 같이 구문론적으로 정의한다.

• \(\forall _{0}^{0}\)-식의 클래스는 양화사가 없는 \(\mathcal{L}\)-식으로 구성된다. \(\exists _{0}^{0}:=\forall _{0}^{0}\) 이다.
• \(G\) 가 \(\exists _{n}^{0}\)-식이면 \((\exists x)G_u(x)\) 는 \(\exists _{n}^{0}\) 이고 \((\forall x)G_u(x)\) 는 \(\forall _{n+1}^{0}\)-식이다.
• \(G\) 가 \(\forall_{n}^{0}\)-식이면 \((\forall x)G_u(x)\) 는 \(\forall _{n}^{0}\) 이고 \((\exists x)G_u(x)\) 는 \(\exists _{n+1}^{0}\)-식이다.

식이 \(\exists _{n}^{0}\)-식과 논리적으로 동등하고 \(\forall _{n}^{0}\)-식과도 논리적으로 동등하면 \(\Delta _{n}^{0}\)-식이라고 한다.

2차 논리식으로 확장된 \(\mathcal{L}\)-식의 계층

다음과 같이 계층을 2차 논리식으로 확장한다.

• \(\forall _{0}^{1}\)-식의 계층은 모든 \(\forall _{n}^{0}\) 식의 합집합으로 구성된다. \(\Delta _{0}^{1}:= \exists _{0}^{1} := \forall _{0}^{1}\) 이다.
• \(G\) 가 \(\exists _{n}^{1}\)-식이면 \((\exists x)G_u(x), (\forall x)G_u(x), (\exists X)G_U(X)\) 는 \(\exists _{n}^{1}\)-식이고 \((\forall X)G_U(X)\) 는 \(\forall _{n+1}^{1}\)-식이다.
• \(G\) 가 \(\forall _{n}^{1}\)-식이면 \((\exists x)G_u(x), (\forall x)G_u(x), (\forall X)G_U(X)\) 는 \(\forall _{n}^{1}\)-식이고 \((\exists X)G_U(X)\) 는 \(\exists _{n+1}^{1}\)-식이다.

산술 계층(arithmetical hierarchy), 산술적 집합(arithmetical set)

자연수의 정의가능한 집합의 계층의 기초는 원시 재귀적으로 정의가능한 집합을 형성한다. \(\mathcal{L}(\mathsf{NT})\) 의 표현력 덕분에 모든 원시 재귀적으로 정의가능한 집합은 이미 \(\forall _{0}^{0}\) 식에 의하여 정의가능하다. 다음과 같이 정의한다.

• \(\Pi_{0}^{0} := \Sigma_{0}^{0} := \Delta _{0}^{0} = \{A \subseteq \N :\) \(A\) 는 산술적 \(\forall _{0}^{0}\)-식에 의하여 정의가능 \(\}\)
• \(\Pi_{n}^{0}:= \{A \subseteq \N:A\) 는 산술적 \(\forall _{n}^{0}\)-식에 의하여 정의가능 \(\}\)
• \(\Sigma_{n}^{0}:= \{A \subseteq \N:A\) 는 산술적 \(\exists _{n}^{0}\)-식에 의하여 정의가능 \(\}\)
• \(\Delta _{n}^{0}:= \Sigma_{n}^{0}\cap \Pi_{n}^{0}\)

\(A \in \Delta _{n}^{0}\) 을 만족하는 \(n\) 이 존재하면 집합 \(A \subseteq \N\) 을 산술적이라고 한다.

해석 계층(analytical hierarchy)

산술 계층을 2차 논리식에 의하여 정의가능한 자연수 집합으로 구성된 해석 계층으로 확장할 수 있다. 다음과 같이 정의한다.

• \(\Sigma_{0}^{1} := \Pi_{0}^{1} := \Delta _{0}^{1}\) 는 모든 산술적 집합의 모임이다.

\(n \geq 1\) 에 대하여 다음과 같이 정의한다.

• \(\Pi_{n}^{1}\) 은 \(\forall _{n}^{1}\)-식에 의하여 정의가능한 자연수 집합의 모임이다.
• \(\Sigma_{n}^{1}\) 은 \(\exists_{n}^{1}\)-식에 의하여 정의가능한 자연수 집합의 모임이다.
• \(\Delta _{n}^{1}:= \Sigma_{n}^{1}\cap \Pi_{n}^{1}\)

정의 5.2.1 산술에 대한 타이트 언어

산술에 대한 타이트 언어의 기호를 다음과 같이 정의한다.

• 종속 숫자 변수: \(x,y,z,x_0,\dots\)
• 집합 변수: \(X,Y,X_0,\dots\)
• 논리적 기호: \(\land ,\lor ,\forall ,\exists\)
• 이항 관계 기호: \(\ein , \not \ein , = , \neq\)
• 상수 \(\underline{0}\)
• 모든 원시 재귀 함수에 대한 기호

항은 상수 \(\underline{0}\) 로부터 함수 기호를 사용하여 일반적인 항 구성 방식으로 구성된다.

원자식은 항 \(s,t\) 에 대한 등식 \(s=t\) 과 부등식 \(s \neq t\), 항 \(t\) 와 집합 변수 \(X\) 에 대한 \(t \ein X\) 과 \(t \not \ein X\) 이다.

식은 원자식으로부터 논리적 연산을 적용하여 얻는다.

\(\ssim F\) 를 다음과 같이 정의한다.

• \(\ssim (s = t) : \equiv s \neq t\)

  \(\ssim (s \neq t) : \equiv s = t\)

• \(\ssim (s \ein t) : \equiv s \not \ein t\)

  \(\ssim (s \not \ein t) : \equiv s \ein t\)

• \(\ssim (A \land B) : \equiv \ssim A \lor \ssim B\)

  \(\ssim (A \lor B) : \equiv \ssim A \land \ssim B\)

• \(\ssim (\forall x)F(x) : \equiv (\exists x)\ssim F(x)\)

  \(\ssim (\exists x)F(x) : \equiv (\forall x)\ssim F (x)\)

\(F\) 에서 나타난 집합 변수로의 \(\N\) 의 부분집합의 임의의 할당 \(\Phi\) 에 대하여 다음을 얻는다.

그러므로 \(\ssim F\) 대신 \(\lnot F\) 라고 쓸 수 있다.

관찰 5.3.1

산술적 문장은 자유 집합 변수를 갖지 않는 산술의 1차 논리 타이트 언어의 식을 말한다. \(\operatorname{Diag}(\N)\) 를 \(\N\) 의 다이어그램, 즉, 타이트 언어의 참인 원자 문장의 집합이라고 하자. 참인 산술적 문장은 다음과 같은 부류로 특징지어진다.

• \(\operatorname{Diag}(\N)\) 안의 문장들.
• 각각 어떤 \(i \in \{0,1\}\) 또는 \(k \in \omega\) 에 대하여 참인 \(F_i\) 와 \(F(\underline{k})\) 에 대한 문장 형태 \((F_0 \lor F_1)\) 와 \((\exists x)F(x)\).
• 각각 모든 \(i \in \{0,1\}\) 또는 \(k \in \omega\) 에 대하여 참인 \(F_i\) 와 \(F(\underline{k})\) 에 대한 문장 형태 \((F_0 \land F_1)\) 와 \((\forall x)F(x)\).

정의 5.3.2

정리 5.3.1 을 따라 산술적 문장을 다음의 두 타입으로 분류할 수 있다.

\(\bigandtype\) 에 속한 문장을 결합 타입(conjunctive type)이라고 하고, \(\bigortype\) 에 속한 문장을 분리 타입(disjunctive type)이라고 한다.

정의 5.3.3 특성열(characteristic sequence)

\(F\) 의 부분문장의 특성열 \(\operatorname{CS}(F)\) 을 \(\circ \in \{\land ,\lor \}\) 와 \(\mathsf{Q}\in \{\forall ,\exists \}\) 에 대하여 다음과 같이 정의한다.

문장 \(F\) 의 형태의 길이는 그것의 특성열 \(\operatorname{CS}(F)\) 의 길이이다.

관찰 5.3.4

관찰 5.3.1 과 정의 5.3.2 에 의하여 곧바로 다음을 얻는다.

\(F \in \bigandtype \implies [\N \vDash F \iff (\forall G \in \operatorname{CS}(F))(\N \vDash G)]\)

\(F \in \bigortype \implies [\N \vDash F \iff (\exists G \in \operatorname{CS}(F))(\N \vDash G)]\)

공진리(vacuous truth)

문장 \(S\) 가 공허하게 참(vacuously true)이라는 것은 \(S\) 가 \(P \implies Q\) 의 형태이고 \(P\) 가 거짓이라는 것이다. 이 공진리는 다음과 같은 보편 양화사의 형태로도 나타내어진다.

1. \(\forall x : \lnot P(x)\) 인 \(P\) 에 대하여 \(\forall x: P(x) \implies Q(x)\) 는 공진리이다.
2. 공집합 \(A\) 에 대하여 \(\forall x \in A: Q(x)\) 는 공진리이다.

정의 5.3.5 무한 검증 계산(infinitary verification calculus), 진리 복잡도(truth complexity)

무한 검증 계산 \(\svDash{\alpha }{}F\) 를 다음과 같이 귀납적으로 정의한다. \(\svDash{\alpha }{}F\) 를 \(F\) 가 \(\alpha\)-검증가능하다고 한다.

\((\land)\) \(F \in \bigandtype\) 이고 \((\forall G \in \operatorname{CS}(F))(\exists \alpha _G<\alpha )\left[ \svDash{\alpha _G}{} G\right]\) 이면 \(\svDash{\alpha }{}F\) 이다.

\((\lor)\) \(F \in \bigortype\) 이고 \((\exists G \in \operatorname{CS}(F))(\exists \alpha _G<\alpha )\left[ \svDash{\alpha _G}{} G\right]\) 이면 \(\svDash{\alpha }{}F\) 이다.

문장 \(F\) 의 진리 복잡도 \(\operatorname{tc}(F)\) 를 다음과 같이 정의한다.

정리 5.3.6

\(\svDash{\alpha }{}F\) 이면 \(\N \vDash F\) 이다.

관찰 5.3.7, 랭크(rank)

\(F\) 에서 나타난 논리적 기호의 수를 \(\operatorname{rnk}(F)\) 라고 하자. 그러면 다음이 성립한다.

1. \(\N \vDash F \implies \operatorname{tc}(F) \leq \operatorname{rnk}(F)\)

2. \(\N \vDash F \iff \operatorname{tc}(F) < \omega\)

정의 5.4.1 유사 \(\Pi_{1}^{1}\)-문장(pseudo \(\Pi_{1}^{1}\)-sentence)

자유 숫자 변수를 포함하지 않지만 자유 집합 파라미터를 포함할 수 있는 산술적 식을 유사 \(\Pi_{1}^{1}\)-문장이라고 한다. 유사 \(\Pi_{1}^{1}\)-문장 \(F(\overrightarrow{X})\) 에 대하여 다음과 같이 정의한다.

유사 \(\Pi_{1}^{1}\)-문장에 대하여 \(\bigandtype\) 과 \(\bigortype\) 의 정의를 받아들인다. 그러나 열린 원자 유사 문장, 즉, 다음의 형태의 문장은 어느 타입에도 속하지 않는다.

관찰 5.4.2

유사 \(\Pi_{1}^{1}\)-문장 \(F\) 의 자유 집합 변수에 대한 임의의 할당 \(\Phi\) 에 대하여 다음이 성립한다.

\(F \in \bigandtype \implies (\N \vDash F[\Phi ] \iff (\forall G \in \operatorname{CS}(F))[\N \vDash G[\Phi ]])\)

\(F \in \bigortype \implies (\N \vDash F[\Phi ] \iff (\exists G \in \operatorname{CS}(F))[\N \vDash G[\Phi ]])\)

정의 5.4.3

\(\Pi_{1}^{1}\)-문장의 유한 집합은 분리(disjunction)로 해석한다. 또한, \(\{F_1, \dots, F_n\}\) 은 \(F_1, \dots, F_n\) 로 표기하고, \(\Delta \cup \Gamma\) 는 \(\Delta ,\Gamma\) 로 표기하고, \(\Delta \cup \{F\}\) 는 \(\Delta ,F\) 로 표기한다.

유사 \(\Pi_{1}^{1}\)-문장의 유한 집합 \(\Delta\) 에 대하여 검증 계산(verification calculus) \(\svDash{\alpha }{}\Delta\) 를 귀납적으로 다음과 같이 정의한다.

\(\operatorname{(Ax)}\quad\) \(s ^{\N }=t ^{\N }\) 이면 모든 서수 \(\alpha\) 에 대하여 \(\svDash{\alpha }{}\Delta ,s \ein X, t \not \ein X\) 이다.

\((\land)\quad\) \(F \in (\Delta \cap \bigandtype )\) 이고 \((\forall G \in \operatorname{CS}(F))(\exists \alpha _G<\alpha )\left[ \svDash{\alpha _G}{} \Delta ,G\right]\) 이면 \(\svDash{\alpha }{}\Delta\) 이다.

\((\lor)\quad\) \(F \in (\Delta \cap \bigortype )\) 이고 \((\exists G \in \operatorname{CS}(F))(\exists \alpha _G<\alpha )\left[ \svDash{\alpha _G}{} \Delta ,G\right]\) 이면 \(\svDash{\alpha }{}\Delta\) 이다.

\(\operatorname{(Ax)}\) 의 식 \(s \ein X\) 와 \(t \not \ein X\), \((\land)\) 와 \((\lor)\) 의 식 \(F\) 를 결정식(ciritical formula)이라고 한다.

이 정의들에 의하여 검증 계산에는 다음과 같은 구조적 규칙이 성립한다.

\(\operatorname{(STR)} \quad\) \(\svDash{\alpha }{}\Delta\) 이면 모든 \(\beta \geq \alpha\) 와 모든 \(\Gamma \supseteq \Delta\) 에 대하여 \(\svDash{\beta }{}\Gamma\) 이다.

보조정리 5.4.4 건전성 정리(soundness theorem)

검증 계산 \(\svDash{\alpha }{}\Delta\) 는 유사 \(\Pi_{1}^{1}\)-문장에 대하여 건전하다. 즉, \(\Delta\) 에서 나타난 모든 자유 집합 변수가 \(\overrightarrow{X}:= (X_1, \dots, X_n)\) 중에 있다면 다음이 성립한다.

정의 5.4.5 탐색 트리(search tree)

이제 완전성을 증명할 차례이다. 순수 논리에 대한 완전성 증명처럼 탐색 트리로 증명이 이루어진다.

• \(\Delta\) 를 유사 \(\Pi_{1}^{1}\)-문장의 유한 집합이라고 하자. \(\Delta\) 의 식의 순서를 임의로 정하여 유사 \(\Pi_{1}^{1}\)-문장의 유한열 \(\left< \Delta \right>\) 를 만들자. \(\left< \Delta \right>\) 에서 \(\bigandtype\) 이거나 \(\bigortype\) 인 가장 왼쪽 식을 \(\left< \Delta \right>\) 의 레덱스 \(R(\left< \Delta \right>)\) 라고 한다. \(\left< \Delta \right>\) 에서 레덱스 \(R(\left< \Delta \right>)\) 를 제거하여 얻은 열을 \(\left< \Delta \right>^{r}\) 라고 하자.

• 다음과 같이 정의한다.

  \[ \operatorname{Ax}(\Delta ):\iff \exists s,t,X[s ^{\N } = t ^{\N } \land \{t \ein X, s \not \ein X\} \subseteq \Delta ] \]

• 두 유사 \(\Pi_{1}^{1}\)-문장이 수치적으로 동등하다(numerically equivalent)는 것은 그들이 오직 평가(evaluation)가 같은 값을 내는 항에서만 다르다는 것이다.

유사 \(\Pi_{1}^{1}\)-문장의 유한열 \(\left< \Delta \right>\) 에 대한 탐색 트리 \(S_{\left<\Delta\right>}^{\omega}\) 와 \(\Pi_{1}^{1}\)-문장의 유한열을 \(S_{\left<\Delta\right>}^{\omega}\) 의 노드에 할당하는 라벨 함수 \(\delta\) 를 귀납적으로 다음과 같이 정의한다.

• \((S _{\left< \right>})\quad\) \(\left< \right>\in S_{\left<\Delta\right>}^{\omega} \qquad \delta (\left< \right>) = \left< \Delta \right>\)

(아래의 정의에서는 \(s \in S _{\left< \Delta \right>}^{\omega }\) 이고 \(\lnot \operatorname{Ax}(\delta (s))\) 라고 가정한다.)

• \((S _{Id})\quad\) \(\delta (s)\) 가 레덱스를 갖지 않으면 다음과 같이 정의한다.

  \[s \concat \left< 0 \right> \in S_{\left<\Delta\right>}^{\omega} \qquad \delta (s \concat \left< 0 \right>) = \delta (s)\]

• \((S _{\bigand_{}^{}})\quad\) 레덱스 \(R(\delta (s))\) 가 \(\bigandtype\) 에 속하면 모든 \(F_i \in \operatorname{CS}(R(\delta (s)))\) 에 대하여 다음과 같이 정의한다.

  \[s \concat \left< i \right> \in S _{\left< \Delta \right>} \qquad \delta (s \concat \left< i \right>) = \delta (s)^{r},F_i\]

• \((S _{\bigor})\quad\) 레덱스 \(R(\delta (s))\) 가 \(\bigortype\) 에 속하면 \(\bigcup_{s_0 \subseteq s}^{}\delta (s_0)\) 에 속하는 식과 수치적으로 동등하지 않은 \(\operatorname{CS}(F)\) 의 첫번째 식 \(F_i\) 에 대하여 다음과 같이 정의한다.

  \[s \concat \left< 0 \right> \in S_{\left<\Delta\right>}^{\omega} \qquad \delta (s \concat \left< 0 \right>) = \delta (s)^{r}, F_i, R(\delta (s))\]

  그러한 식이 존재하지 않으면 다음과 같이 정의한다.

  \[\delta (s \concat \left< 0 \right>) = \delta (s)^{r}, R(\delta (s))\]

보조정리 5.4.7 구문론적 주요 보조정리(syntactical main lemma)

\(S_{\left<\Delta\right>}^{\omega}\) 가 wf 이면 유한 집합으로 볼 수 있는 \(\delta (s)\) 에 대하여 모든 \(s \in S_{\left<\Delta\right>}^{\omega}\) 에 대하여 \(\svDash{\operatorname{otyp}(s)}{}\delta (s)\) 이다.

보조정리 5.4.8 의미론적 주요 보조정리(semantical main lemma)

\(S_{\left<\Delta\right>}^{\omega}\) 가 wf 가 아니면 다음을 만족하는 \(\Delta\) 에서 나타나는 집합변수들에 대한 할당 \(S_1, \dots, S_n\) 이 존재한다.

• 모든 \(F \in \Delta\) 에 대하여 \(\N \not \vDash F[S_1, \dots, S_n]\) 이다.

정리 5.4.9 \(\omega\)-완전성 정리(\(\omega\)-completeness theorem)

\((\forall X_1)\dots (\forall X_n)F(X_1, \dots, X_n)\) 형태의 모든 \(\Pi_{1}^{1}\)-문장에 대하여 다음이 성립한다.

정의 5.4.10 진리 복잡도(truth complexity)

검증 계산이 \(\lor\)-내보내기(exportation) 성질, 즉, 다음과 같은 성질을 갖는다는 것을 \(\alpha\) 에 대한 귀납법으로 쉽게 보일 수 있다.

식 \(F\) 에 대하여 \(F ^{\nabla }\) 를 \(F\) 의 모든 분리를 내보내서 얻어진 유한집합으로, 즉, 다음과 같이 정의하자.

그러면 다음을 얻는다.

이제 \(\Pi_{1}^{1}\) 문장 \((\forall \overrightarrow{X})F(\overrightarrow{A})\) 을 잡자. \(F\) 의 진리복잡도를 다음과 같이 정의한다.

자유 집합 파라미터 \(\overrightarrow{X}\) 를 포함하는 유사 \(\Pi_{1}^{1}\)-문장 \(G(\overrightarrow{X})\) 의 진리복잡도를 다음과 같이 정의한다.

정리 5.4.11

임의의 (유사) \(\Pi_{1}^{1}\)-문장 \(F\) 에 대하여 다음이 성립한다.

정의 6.1.1 귀납적 정의(inductive definition), \(\mathscr{A}\)-닫혀있다(\(\mathscr{A}\)-closed)

• \(X\) 의 귀납적 정의는 다음과 같은 조항들의 모임 \(\mathscr{A}\) 이다. 그러므로 조항은 페어 \((A, b)\) 이다. 조항을 편의상 \(A \implies b\) 라고 표기한다.

  모든 \(a \in A\) 에 대하여 \(a \in X\) 이면, \(b \in X\) 이다.

• \(\mathscr{A}\) 를 귀납적 정의라고 하자. 집합 \(X\) 가 \(\mathscr{A}\) 를 만족한다는 것은 \((A \implies b) \in \mathscr{A}\) 이고 \(A \subseteq X\) 이면 \(b \in X\) 가 성립한다는 것이다. 이것을 집합 \(X\) 가 \(\mathscr{A}\) 의 조항에 대하여 닫혀있다, 또는 \(\mathscr{A}\)-닫혀있다고 한다.

정의 6.1.2 귀납적으로 생성된 집합(inductively generated set), 결정론적(deterministic) 귀납적 정의

• 귀납적 정의 \(\mathscr{A}\) 에 대한 집합 \(I(\mathscr{A})\) 를 \(\mathscr{A}\) 에 대하여 닫혀있는, 포함관계에 대한 최소 집합으로 정의한다. \(I(\mathscr{A})\) 를 \(\mathscr{A}\) 에 의하여 귀납적으로 생성된 집합이라고 한다.

  귀납적 정의 \(\mathscr{A}\) 의 결론 집합 \(C _{\mathscr{A} } := \{b : (A \implies b) \in \mathscr{A} \}\) 은 항상 \(\mathscr{A}\)-닫혀있다. 또한, \(\mathscr{A}\)-닫힌 집합의 교집합도 \(\mathscr{A}\)-닫혀있다. 그러므로 다음을 얻는다.

  \(I(\mathscr{A} ) = \bigcap_{}^{}\{X : X\) 는 \(\mathscr{A}\)-닫혀있다 \(\}\)

• 귀납적 정의 \(\mathscr{A}\) 가 결정론적이라는 것은 \((A \implies b) \in \mathscr{A}\) 와 \((B \implies b) \in \mathscr{A}\) 가 \(A = B\) 를 함의한다, 즉, \(b\) 가 \(I(\mathscr{A})\) 로 들어가는 길이 유일하다는 것이다.

정의 6.2.1 단조 연산자(monotone operator)

• 귀납적 정의 \(\mathscr{A}\) 에 대하여 다음을 만족하는 집합 \(X\) 를 잡자.

  모든 \((A \implies a) \in \mathscr{A}\) 에 대하여 \(A \cup \{a\} \subseteq X\) 이다.

  다음과 같은 연산자를 정의하자.

  \(\Phi _{\mathscr{A}}: \operatorname{Pow} (X) \to \operatorname{Pow} (X)\)

  \(\Phi _{\mathscr{A}}(S) := \{b \in X : (\exists (A \implies b) \in \mathscr{A})[A \subseteq S]\}\)

  그러면 \(S_0 \subseteq S_1 \subseteq X\) 에 대하여 다음이 성립하므로 연산자 \(\Phi _{\mathscr{A}}\) 는 단조(monotone)이다.

  \[ \Phi _{\mathscr{A}} (S_0) \subseteq \Phi _{\mathscr{A}}(S_1) \]

• 모든 단조 연산자 \(\Phi :\operatorname{Pow} (X) \to \operatorname{Pow} (X)\) 는 다음과 같은 귀납적 정의 \(\mathscr{A}\) 의 조항의 모임으로 볼 수 있다.

  \[\{(A \implies a) : A \subseteq X \land a \in \Phi (A)\}\]

그러므로 귀납적 정의와 단조 연산자는 본질적으로 같다.

정의 6.2.2 일반화된 귀납적 정의(generalized inductive definition)

집합 \(A\) 위에서 일반화된 귀납적 정의는 단조 연산자 \(\Phi :\operatorname{Pow} (A ^{n}) \to \operatorname{Pow} (A ^{n})\) 이다.

정의 6.2.3 \(\Phi\)-닫혀있다(\(\Phi\)-closed)

귀납적 정의 \(\Phi :\operatorname{Pow} (A ^{n}) \to \operatorname{Pow} (A ^{n})\) 를 잡자. 집합 \(S \subseteq A ^{n}\) 가 \(\Phi\)-닫혀있다는 것은 \(\Phi (S) \subseteq S\) 와 동치이다.

\(\Phi\)-닫힌 집합들의 포함 관계에 대한 최소 집합을 다음과 같이 정의한다.

관찰 6.2.4 단조 연산자의 고정점(fixed point)

\(\Phi : \operatorname{Pow} (A ^{n}) \to \operatorname{Pow} (A ^{n})\) 가 귀납적 정의이면 \(I(\Phi )\) 는 연산자 \(\Phi\) 의 최소 고정점, 즉, \(\Phi (S) = S\) 인 최소 \(S\) 이다.

\(I(\Phi )\) 를 귀납적 정의 \(\Phi\) 의 고정점이라고 정의한다.

집합론에서 집합 \(A\) 의 기수 \(\overline{\overline{A}}\) 보다 큰 첫번째 기수 \(\left( \overline{\overline{A}} \right)^{+}\) 가 정칙 기수라는 것이 알려져있다. 그러므로 기수가 \(\leq \omega\) 인 가산 집합에 대하여 첫번째 비가산 기수 \(\omega _1 := \omega ^{+}\) 은 정칙이다.

다음 동치 명제가 성립한다.

1. \(\overline{\overline{A}}\) 보다 작거나 같은 기수의 서수가 \(\left( \overline{\overline{A}} \right)^{+}\) 만큼 많이 존재한다.
2. \(\left( \overline{\overline{A}} \right)^{+}\) 보다 작은 서수가 \(\left( \overline{\overline{A}} \right)^{+}\) 만큼 많이 존재한다.

정의 6.3.1

\(\displaystyle \Phi ^{<\alpha }:= \bigcup_{\xi <\alpha }^{}\Phi ^{\xi }\) 에 대하여 초한 재귀로 다음과 같이 정의한다.

\(\displaystyle \Phi ^{\alpha } := \Phi (\Phi ^{<\alpha })\)

보조정리 6.3.2

집합 \(A\) 위의 귀납적 정의 \(\Phi\) 를 잡자. 그러면 \(\Phi ^{< \sigma } = \Phi ^{\sigma }\) 를 만족하는 서수 \(\sigma < \left( \overline{\overline{A}} \right)^{+}\) 가 존재한다.

정의 6.3.3 닫힘 서수(closure ordinal)

\(\left| \Phi \right|\) 를 다음과 같이 정의하고 귀납적 정의 \(\Phi\) 의 닫힘 서수라고 한다.

\(\left| \Phi \right|:=\min \{\xi :\Phi ^{\xi } = \Phi (\Phi ^{<\xi }) = \Phi ^{< \xi }\}\)

정리 6.3.4

귀납적 정의 \(\Phi\) 에 대하여 다음이 성립한다.

\(I(\Phi ) = \Phi ^{<|\Phi |}\)

정의 6.3.5 귀납적 노름(inductive norm)

\(\overrightarrow{n}\in I(\Phi )\) 에 대한 귀납적 노름을 다음과 같이 정의한다.

보조정리 6.3.6

귀납적 정의 \(\Phi\) 의 닫힘 서수는 다음과 같다.

정의 6.4.1 산술적으로 정의가능한 연산자(arithmetically definable)

수 파라미터 \(a_1, \dots, a_m\) 에 대하여 다음을 만족하는 수론의 1차 논리 언어에서의 식 \(F(X, \overrightarrow{x}, y_1, \dots, y_n)\) 이 존재하면 연산자 \(\Phi :\operatorname{Pow} (\N ^{n}) \to \operatorname{Pow} (\N ^{n})\) 를 산술적으로 정의가능하다고 한다.

식 \(F(X, \overrightarrow{x}, y_1, \dots, y_n)\) 와 숫자 상수 \(a_1, \dots, a_m\) 의 튜플로 유도된 연산자를 \(\Phi _F[a_1, \dots, a_m]\) 라고 표기한다. (그러나 일반적으로 추가 파라미터 \(a_1, \dots, a_m\) 에 대한 언급을 하지 않는다.)

정의 6.4.3 \(X\)-포지티브(\(X\)-positive)

산술의 언어에서의 식 \(F(X)\) 를 잡자. \(F(X)\) 를 타이트 언어로 변환한 이후에 \(t \not \ein X\) 이 \(F(X)\) 에 나타나지 않으면, \(F(X)\) 를 \(X\)-포지티브라고 한다.

보조정리 6.4.4 포지티브 연산자(positive operator, 포지티브 귀납적 정의, positive inductive definition)

\(X\)-포지티브 식 \(F(X,x)\) 에 의하여 유도된 연산자 \(\Phi _{F}\) 는 단조이다.

이때 이런 연산자를 포지티브 연산자라고 한다.

정의 6.4.5

\(X\)-포지티브 식 \(F(X, x, a_1, \dots, a_n)\) 에 의하여 정의된 귀납적 정의 \(\Phi _F\) 를 잡자.

\(I(\Phi _F[a_1, \dots, a_n])\) 를 \(I_F[a_1, \dots, a_n]\) 라고 쓴다.

\(|\Phi _F|\) 를 \(|F|\) 라고 쓴다.

\(\Phi _F[a_1, \dots, a_n]^{<\xi }\) 를 \(I_F ^{< \xi }[a_1, \dots, a_n]\) 라고 쓴다.

\(\Phi _F[a_1, \dots, a_n]^{\xi }\) 를 \(I_F ^{\xi }[a_1, \dots, a_n]\) 라고 쓴다.

(추가 파라미터 \(a_1, \dots, a_n\) 는 보통 생략한다.)

\(a\)-슬라이스(\(a\)-slice)

집합 \(S\) 와 자연수 \(a\) 에 대하여 \(a\)-슬라이스는 다음과 같은 집합이다.

정의 6.4.7 포지티브-귀납적으로 정의가능한 집합(positive-inductively definable set)

집합 \(S \subseteq \N\) 에 대하여 다음을 만족하는 추가 숫자 파라미터가 있어도 되는 \(X\)-포지티브 식 \(F(X,x)\) 와 자연수 \(a\) 가 존재하면 \(S\) 가 포지티브-귀납적으로 정의가능하다고 한다.

\(S\) 는 고정점 \(I_F\) 의 \(a\) 슬라이스이다.

보조정리 6.4.8

모든 포지티브-귀납적으로 정의가능한 집합은 \(\Pi_{1}^{1}\) 에 속한다.