이차논리

(Second-order logic)

계산가능성과 논리 : George S. Boolos   Richard C. Jeffrey 저, 김영정.최훈.강진호 옮김, 문예출판사 (393-5681), 1996 (원서 : Computability and Logic, 3rd ed, Cambridge Univ. Press, 1989), page 247~259

우리가 15 장에서 배운 바에 따르면, 표준 해석 에서 참인 L 의 문장들의 집합은 효율적으로 결정가능한 L 의 문장들의 어떤 집합의 귀결들의 집합이 아니며, 따라서 L 의 어떤 단일한 문장 (또는 문장들의 유한한 집합) 의 귀결들의 집합은 더욱 아니었다. 17 장에서는 에서 참인 L 의 문장들의 집합의 비동형적인 모형이, 더 정확히 말해, 비동형적인 열거가능한 모형이, 적어도 두 개 있다는 것을 알았다.

우리는 이제 언어의 문장 개념을 어떤 방식으로 넓히면, 그리고 이에 따라 문장이 해석에서 참이 되는 조건에 대한 우리의 설명을 확장하면, 그런 결과들이 더 이상 생기지 않는다는 것을 알아보려고 한다. 우리는 이차 (second-order) 문장을 도입할 것이다. 일차 문장과 이차 문장을 참이 되게 하는 조건에 대한 연구를 이차 논리학이라 한다.

이차 논리학 (표준적인, 즉 '진짜' 이차 논리학을 말한다. 우리가 여기서 다루지 않을 비표준적인 이차 논리학에서는 해석의 정의가 바뀌어 함수와 술어 변항에 대해 별도의 논의 영역이 필요하다. 이 장 말고 이차 문장과 식을 논의하는 곳은 19장의 처음 절반과 23장의 한 문단뿐이다.) 은 우리가 지금까지 연구해 오고 앞으로도 계속 연구할 일차 (또는 기초) 논리학과는 판이하게 다르다. 뚜렷한 차이점 여섯가지를 말해 보면 이렇다.

(1) 이차 문장들의 타당성에 대한 효율적이고 긍정적인 검사는 없다.
(2) 어떤 문장들의 집합이 있는데, 그 집합은 열거가능하면서도 만족불가능하지만 그 집합의 모든 유한한 부분집합은 만족가능하다. 그 집합에 있는 문장들 가운데 하나가 이차 문장이다. (따라서 조밀성 정리는 이차 논리학에서 성립하지 않는다.)
(3) 논의 영역이 열거가능하지 않은 해석들 모두가 그리고 오로지 그 해석들만이 모형인 어떤 이차 문장이 하나 있다. (스콜렘-뢰벤하임 정리는 성립하지 않는다.)
(4) 에서 참인 L 의 문장들 모두를 그리고 오로지 그것들만을 (일차와 이차) 귀결로 갖는 어떤 한 이차 문장이 있다.
(4) L 에 대한 해석이 과 동형적이 될 경우 그리고 오직 그 경우에만 그 해석이 어떤 이차 문장의 모형이 될 그러한 어떤 한 이차 문장이 있다.
(6) 에서 참인 일차 문장들의 괴델수들 모두에 그리고 오로지 그것들에 대해서만 에서 참인 이차 식이 있다.

이 장에서 (1) 부터 (5) 까지를 증명하겠다. (6) 은 다음 장을 위해 아껴놓겠다. 먼저 (3) 을 증명하고, 그 다음에 (5) 를 증명한다. (1), (2), (4) 는 (5) 에서 직접 따라나온다.

우선 이차 논리학에서 언어 의 정의와 해석 의 정의를 바꾸지 않는다는 점을 강조해야겠다. 언어는 여전히 비논리적 기호들의 열거가능한 집합이고, 해석은 여전히 내내 써오던 것과 똑같은 것이다 (9 장 참조). 식 과 문장 에는 변화가 있다. 즉, 더 많은 표현들이 식과 문장으로 허용된다. 그리고 문장이 참이 되는 해석상의 조건들에 관한 9 장의 기술도 새로운 종류의 문장들까지 포괄할 수 있도록 확장된다.

이차 문장이란 무엇인가? 지금까지 '변항' 이라고 한 것은 개체변항 (individual variable) 이라고 부르자. 이제 새로운 종류의 변항들을 들여오겠다. 즉, 함수변항, 문장변항, 술어변항이 그런 변항들이다. 일항, 이항, 삼항, 그리고 그 이상의 함수 기호와 술어문자가 있었던 것처럼 일항, 이항, 삼항, 그리고 그 이상의 함수변항과 술어변항이 있다. 우리는 어떠한 한 종류의 기호도 다른 종류의 기호로 쓰이지 않는다고 가정하겠다. 지금까지 식에서 함수기호, 문장문자, 술어문자만 (각각!) 나타날 수 있었던 자리에 함수변항, 문장변항, 술어변항이 오는 것을 허용하고, 또 양화사 '∃' 과 '∀' 다음에 새로운 종류의 변항이 오는 것도 허용해서 식의 정의를 확장하겠다. 새로운 종류의 변항에 대한 '자유로운 나타남' 과 '속박된 나타남' 의 정의는 개체변항에 대한 정의와 똑같다. 언제나처럼 문장은 어떠한 변항 (개체, 함수, 문장, 술어) 도 자유롭게 나타나지 않은 식이다. 그러면 이차 식은 함수변항, 문장변항 또는 술어변항이 적어도 한 번 나타나는 식이고, 이차 문장은 문장인 이차 식이다. 한 언어의 식이나 문장은 일차든 이차든 간에 예전처럼 그것의 비논리적 기호가 모두 그 언어에 속하는 것이다. 문장변항은 별로 중요한 것이 아니지만 주로 대칭성 (symmetry) 을 유지하기 위해 포함시켰다는 것을 말해 두겠다 (그러나 23 장을 보라).

우리는 일차 논리학에서 어떤 특정 함수를 항등 함수라고 말할 수 있었다. 즉, ∀xf(x)=x 가 그 함수이다. 그러나 이차 논리학에서는 항등 함수의 존재를 주장할 수 있다. 즉 ∃u∀xu(x)=x 라고 말이다. 마찬가지로 우리는 일차 논리학에서 특정한 두 개체가 어떤 성질을 공유한다고 주장할 수 있었는데 (Pa&Pb), 이차 논리학에서는 모든 두 개체가 어떤 성질을 공유한다고 주장할 수 있다 (∀x∀y∃X(Xx&Xy)).

마지막으로 우리는 일차 논리학에서 만약 두 특정 개체가 동일하다면 그 개체들은 특정 성질을 양자 모두 갖든가 양자 모두 안 갖든가 해야 한다고 주장할 수 있었다. 즉, a=b→(Pa↔Pb) 이다.

그러나 이차 논리학에서는 동일성을 라이프니츠의 식별불가능한 것들의 동일성 원리를 가지고 정의 할 수 있다. 즉, a=b↔∀X(Xa↔Xb) 이다.

(보기에서 u 는 일항 함수변항으로 쓰였고 X 는 일항 술어변항으로 쓰였다.) 우리가 위에서 제시한 세 이차 문장은 모두 타당하다. 다시 말해서, 그 이차 문장들 각각은 모든 해석들에서 참이다.

이차 문장 S 는 언제 해석 에서 참인가? 우리는 9 장의 (S) 의 정의에 여섯가지 경우를 덧붙여서 이 문제에 대답하겠다. 앞으로 계속해서 F 는 함수변항 u〔 문장변항 p, 술어변항 X 〕가 자유롭게 나타날 수 있는 식이고, f〔P, R 〕는 F 에 나타나지 않는 함수기호〔 문장문자, 술어문자 〕일 것이다. f〔 R 〕는  u〔 X 〕와 같은 개수의 항을 갖는다고 생각된다. 〔 ,  〕는 f 에 함수 를 〔 P 에 진리값 i(=0, 1) 를, R 에 특징함수 Φ 를 〕할당한다는 점에서만 와 다른 해석 (만약 다른 점이 있다면) 일 것이다. 그리고 F_uf〔 F_pP, F_xR 〕는 F 에서 자유롭게 나타난 모든 u〔 p, X 〕를 f〔 R, R 〕로 치환해서 F 로부터 얻은 문장일 것이다.

타당성, 만족가능성, 함축의 정의는 이차 문장들에 대해서도 변하지 않는다. 일차 문장이든 이차 문장이든 임의의 문장은 모든 해석에서 참일 경우 그리고 오직 그 경우에만 타당하고, 적어도 한 해석에서 참일 경우 그리고 오직 그 경우에만 만족가능하다. 문장들의 집합 Δ 는 Δ 에 있는 모든 문장들을 참이게 하나 S 를 거짓이게 하는 해석이 전혀 없을 경우 그리고 오직 그 경우에만 문장 S 를 함축한다.

보기 18.1. 동일성의 정리

화이트헤드와 러셀이 지적한 것처럼 (Principia Mathematica, 1권, 57쪽) 앞에서 말했던 라이프니츠의 동일성 정의는 단순화할 수 있다. 문장

가 타당하기 때문이다. 오른쪽의 쌍조건문은 필요가 없다!

증명. 왼쪽에서 오른쪽으로 가는 것은 사소하다. 만약 (a=b)=1 이면, (a)=(b) 이고, 그러면 어떠한 (일항) Φ 에 대해서도 (Ra→Rb)=1 이고 따라서 (∀X(Xa→Xb))=1 이다. 오른쪽에서 왼쪽으로 가는 것은 이렇다. 만약 (∀X(Xa→Xb))=1 이면, (a) 에 그리고 오직 (a) 에만 산출값 1을 할당하는 특정한 Φ 에 대해 (Ra→Rb)=1 이다. (Ra)=1 이므로 (Rb)=1 이다. 따라서 (b)=(a) 이고, 그러므로 (a=b)=1 이다. 그러므로 는 (1) 의 좌변에 1을 할당할 경우 그리고 오직 그 경우에만 우변에 1을 할당하고, 증명은 완성된다. ((1) 이 타당한 까닭을 직관적으로 말하면 다음과 같다. a 의 성질들 가운데 a 와 동일하다는 성질이 있다. 그러면 만약 b 가 a 의 모든 성질들을 가진다면, b 는 특별히 그 성질도 틀림없이 갖는다.)

보기 18.2 열거가능성 '공리'

문장

∃z∃u∀X(Xz&∀x(Xx→Xu(x))→∀xXx)

를 Ax En 이라고 하자.

어떤 해석의 논의 영역이 열거가능할 경우 그리고 오직 그 경우에만 Ax En 은 그 해석에서 참인 문장이다.

증명. 를 어떤 해석이라고 하고 D 를 의 논의 영역이라고 하자.

(Ax En)=1 이라고 가정하자. 그러면 D 의 어떤 a 에 대해서 그리고 투입값 영역이 D 이고 산출값 범위가 D 의 부분집합인 어떤 함수 에 대하여

(∀X(Xo&∀x(Xx→Xs(x))→∀xXx)) = 1

이다. A={a, (a), ((a)), (((a))), ...} 라고 하자. A 는 a 를 포함하고, 또 b 를 포함할 때마다 (b) 도 포함하는 열거가능한 D 의 부분집합이다. Φ 를 A 의 특징함수라고 하자. 그러면

(No&∀x(Nx→Ns(x))→∀xNx) = 1

이다. a 는 A 속에 있기 때문에   (No) = 1 이다. A 는 (D 에 있는 임의의 b 에 대하여) b 를 포함할 때마다 (b) 를 포함하므로

(∀x(Nx→Ns(x))) = 1

이다. 그러므로 (∀xNx) = 1 읻. 그러므로 D 의 모든 b 에 대해서 b 는 A 속에 있다. 그러므로 D 는 A 와 같은 원소를 가지며 따라서 열거가능하다.

반대로, D 가 열거가능하다고 하자. D 는 의 논의 영역이기 때문에 D 는 공집합이 아니다. a₀, a₁, ... 이 D 의 모든 원소를 반복하지 않고 열거한 것이라고 하자. (어떤 n 에 대해, a₀, a₁, ... = a₀, a₁, ..., a_n 일 수도 있다.) a=a₀ 이라고 놓는다. 투입값 영역이 D 이고 산출값 범위가 D 의 부분집합인 함수 를 다음과 같이 정의하자. 즉, 만약 a₀, a₁, ... 이 무한하다면, 어떤 i 에 대해 x=a_i 이고 y=a_i+1 일 경우 그리고 오직 그 경우에만 (x)=y 라고 놓는다. 그러나 만약 어떤 n 에 대해서 a₀, a₁, ...=a₀, a₁, ..., a_n 이면, 어떤 i<n 에 대해 x=a_i 와 y=a_i+1 또는 x=a_n과 y=a_n 일 경우 그리고 오직 그 경우에만 (x)=y 라고 놓는다. 양 경우에 만약 A 가 a 를 포함하고 또 b 를 포함할 때마다 (b) 를 포함하는 D 의 부분집합이라면, D 의 모든 원소는 A 속에 있다.

다음이 따라나온다. 특징함수 Φ를 갖는 D 의 모든 부분집합 A 에 대해

(No&∀x(Nx→Ns(x))→∀xNx) = 1,

따라서

(∀X(Xo&∀x(Xx→Xs(x))→∀xXx)) = 1,

따라서

(∃z∃u∀X(Xz&∀x(Xx→Xu(x))→∀xXx)) = 1

즉  (Ax En)=1 이다.

그러므로 어떤 해석의 논의 영역이 열거가능할 경우 그리고 오직 그 경우에만 Ax En 은 그 해석에서 참이다.

우리는 이제 스콜렘-뢰벤하임 정리가 이차 논리학에서는 성립하지 않는다는 것을 보일 수 있다: -Ax En 은 열거가능하지 않게 무한한 논의 영역을 갖는 모든 해석에서 참이지만 (그리고 그런 해석들은 있으므로 -Ax En 은 만족가능하다 !), 열거가능한 논의 영역을 갖는 어떠한 해석에서도 참이지 않다. 그러므로 주장 (3) 은 성립하다.

이제 주장 (5) 의 증명을 하겠다. Ind 를 문장

∀X([Xo&∀x(Xx→Xx')]→∀xXx)

라고 하자. Ind 는  에서 해석될 때 수학적 귀납의 원리를 형식화하는 L 의 이차 문장이다. 그러므로 Ind 는 에서 참이다. 16 장에 나오는 열거가능하게 많은 귀납 공리들은 모두 이차 문장 Ind 한 개의 논리적 귀결이다. 우리는 16 장에서 Q 의 세번째 공리인 Q3 이 귀납 공리로부터 도출된다는 것을 지적했다. 따라서 Q3 은 Ind 로부터 도출된다. PA 를 Q 의 다른  여섯 공리들과 Ind 의 연언이라고 하자. PA 는 에서 참이다.

정리

은 PA 의 모형이 되는 L 의 어떠한 해석과도 동형적이다.

증명. 가 PA 의 모형이 되는 L 의 해석이라고 가정하자. D 의 의 논의 영역이라고 하고, 가 0, ', +, • 에 각각 e, s, p, t 를 할당하였다고 하자.

Q1, Q2, Ind, Q4, Q5, Q6, Q7 이 모두 에서 참이므로 D 의 어떠한 a, b 에 대해서도 그리고 D 의 어떠한 부분집합 A 에 대해서도 다음이 따라나온다.

(i) 만약 s(a)=s(b) 이면, a=b 이다.
(ii) e≠s(a).
(iii) e 가 A 속에 있고 (D 속의 모든 c 에 대해) c 가 A 속에 있을 때마다 s(c) 가 A 속에 있으면 A=D 이다.
(iv) p(a, e)=a.
(v) p(a, s(b))=s(p(a, b)).
(vi) t(a, e)=e.
(vii) t(a, s(b))=p(t(a, b), a).

h를 다음과 같이 귀납적을 정의하자. h(0)=e, h(n')=s(h(n)).

우리는 h가 모든 자연수들의 집합이 투입값 영역이고 D 가 산출값 범위이며, 모든 자연수 m, n 에 대해

h(m+n)=p(h(m), h(n)) 그리고 h(m• n)=t(h(m), h(n))

이라는 성질을 갖는 일대일 함수라는 것을 보여야만 한다. 이것은 지루한 작업이긴 하지만 직접적으로 나온다. 그것을 보이겠다.

e 는 D 의 원소이고 s 는 D 가 투입값 영역이고 D 의 부분집합이 산출값 범위인 함수이므로, h 는 모든 자연수들의 집합을 투입값 영역으로 하고 D 의 부분집합을 산출값 범위로 하는 함수이다.

h 는 일대일이다. 그 까닭은 이렇다. 만약 아니라고 한다면, m 을 어떤 k>m 에 대해 h(m)=h(k) 를 만족하는 가장 작은 자연수라고 하고, n 은 >m 이고 h(m)=h(n) 을 만족한다고 하자. m<n 이므로 어떤 j 에 대해 n=j' 이다. h(n)=h(j')=s(h(j)) 이고 만약 m=0 이면 h(m)=h(0)=e 이다. 그러나 (ii) 에 의해 e≠s(h(j)) 이다. 따라서 m≠0 이다. 따라서 어떤 i 에 대해 m=i' 이고, 그러면 i'<j' 이고, 따라서 i<j 이며, 여기서 i<m 이므로 m 이 가장 작다는 성질에 의해 h(i)≠h(j) 이고, 따라서 (i) 에 의해 s(h(i))≠s(h(j)) 이다. 따라서

h(m)=h(i')=s(h(i))≠s(h(j))=h(j')=h(n)

이고 이것은 모순이다.

더 나아가 e 는 h 의 산출값 범위 속에 있고, 만약 c 가 산출값 범위 속에 있으면 어떤 n 에 대해 c=h(n) 이고, 여기서 h(n')=s(c) 가 나오며 따라서 s(c) 는 산출값 범위 속에 있다. (iii) 으로부터 h 의 산출값 범위 =D 라는 결론이 따라나온다.

어떠한 m, n 에 대해서도, h(m+n)=p(h(m), h(n)) 이다. 그 까닭은 이렇다. h(m+0)=h(m) 이고, 이것은 (iv) 에 의해 =p(h(m), e)=p(h(m), h(0)) 이다. 그리고

h(m+n')=h((m+n)')=s(h(m+n))

이고, 이것은 귀납 가설에 의해 s(p(h(m), h(n))) 이고, 이것은 (v) 에 의해 =p(h(m), s(h(n)))=p(h(m), h(n')) 이다.

그리고 어떠한 m, n 에 대해서도 h(m• n)=t(h(m), h(n)) 이다. 그 까닭은 이렇다. h(m 0)=h(0)=e 이고 이것은 (vi) 에 의해 =t(h(m, e)=t(h(m), h(0)) 이다. 그리고 h(m• n')=h(m• n+m) 이고 이것은 앞서 말한 것에 의해 =p(h(m• n), h(m)) 이고, 이것은 귀납 가설에 의해 =p(t(h(m), h(n)), h(m)) 이고, 이것은 (vii) 에 의해

=t(h(m), s(h(n)))=t(h(m), h(n'))

이다.

따름정리 1

A 를 L 의 (일차 또는 이차) 문장이라고 가정하자. 그러면 A 가 에서 참일 경우 그리고 오직 그 경우에만 PAA 이다.

증명. PAA 라고 가정하자. 그러면 A 는 PA 의 모든 모형들에서 참이다. 그런데 은 PA 의 모형이다. 따라서 A 는 에서 참이다. 거꾸로 A 가 에서 참이라고 가정하자. 그러면 만약 가 PA 의 모형인 L 의 해석이라면 정리에 의해서 은 와 동형적이고 따라서 A 는 에서 참이다. 따라서 PAA 이다.

그러므로 주장 (4) 는 성립한다.

따름정리 1의 의미를 과대 평가해서는 안된다. 왜냐하면 비록 (L의) 임의의 문장이 단일한 문장 PA 의 귀결일 경우 그리고 오직 그 경우에만 그 문장은 에서 참이지만, 그렇다고 해서 산수 ( 에서의 일차 진리들의 집합) 가 진정으로 결정가능하다고 결론지을 수 없기 때문이다. 그런 어떤 것을 결론지을 수 있으려면 이차 타당성이나 귀결에 대한 효율적인 긍정적 검사가 있다는 것을 알아야 할 것이다. 그러나 따름정리 1과 산수의 결정불가능성이 함해져서 그런 긍적적인 검사가 없다는 증명을 제공한다.

따름정리 2

이차 문장들의 타당성에 대한 효율적인 긍정적 검사는 없다.

증명. A 가  L 의 (일차) 문장이라고 하자. 그러면 (PA→A) 가 타당한 꼭 그 경우에 PAA 이고, 또 (따름정리 1에 의해) 꼭 그 경우에 A 가 에서 참이고, 또 꼭 그 경우에 -A 가 에서 참이 아니고, 또 (다시 따름정리 1에 의해서) 꼭 그 경우에 PA-A 이고, 또 꼭 그 경우에 (PA→-A) 는 타당하지 않다. 만약 이차 타당성에 대한 효율적인 긍정적 검사가 존재한다면 에서의 참에 대한 결정 절차도 존재할 것이다. 즉 A 의 참을 검사하기 위해서 (PA→A) 와 (PA→-A) 모두의 타당성에 대한 긍정적 검사를 해보아라. 그 둘 가운데 정확히 하나가 타당하므로, (PA→A) 와 (PA→-A) 둘 가운데 어느 것이든지 하나가 타당하다는 것을 검사가 확인해 줄 것이다. 그러면 A 가 에서 참일 경우 그리고 오직 그 경우에만 그 검사는 (PA→A) 가 타당하다고 확인해 줄 것이다. 에서의 참에 대한 결정 절차가 없으므로 이차 타당성에 대한 효율적인 긍정적 검사도 없다.

이런 결과는 때때로 '이차 논리는 불완전하다'고 다소 오도되게 말해진다. 똑같은 말을 덜 오도되게 말해 보면 이렇다. '이차 논리의 어떠한 건전한 형식화도 완전하지 않다.' (논리가 불완전한 것은 아니다. 우리가 시도하는 형식화들이 불완전한 것이다.)

그러므로 주장 (1) 은 성립한다. (2) 도 성립한다는 것, 곧 조밀성 정리가 이차 논리학에서는 성립하지 않는다는 것을 보이는 일이 남았다.

따름정리 3

U={PA, a≠0, a≠1, a≠2, ...} 이라고 하자. 그러면 U 는 만족불가능하지만 U 의 모든 유한한 부분집합은 만족가능하다.

증명. U₀ 이 U 의 유한 부분집합이라고 한다면 어떤 n 에 대해서 문장 a≠n 은 U₀에 있지 않고 따라서 이름 a 에 n 을 할당한다는 점만 빼고는 과 똑같은 해석이 U₀ 의 모형이다. (17 장의 정리 참조)

가 U 의 모형이라고 가정하자. 와 논의 영역이 똑같고 0, ', +, • 에 가 할당하는 것과 똑같은 것을 할당하는 (그러나 a 에는 아무 것도 할당하지 않는) L 의 해석을 라고 하자.

따름정리 1에 의해서 의 참인 문장들은 모두 PA 의 귀결절들이고, 따라서 에서 성립한다. a≠0, a≠1, a≠2, ... 모두는 에서도 참이므로 17 장 정리의 증명이 보여주는 것처럼 는 와 동형적일 수 없다. 그러나 (PA)=1 이므로 (PA)=1 이고 따라서 는 과 동형적임에 틀림없다. 이것은 모순이다. 그러므로 U 는 어떠한 모형도 갖지 않는다.

그렇다면 따름정리 2 와 3 그리고 보기 18.2 가 말하는 것처럼 이차 논리는 '형식화 가능하지 않고', 조밀성이 성립하지 않고, '스콜렘-뢰벤하임적이지 않다'. 더 있다. 괴델수를 어떤 합당한 방식으로 이차 문장들에 할당했다고 가정하자. 그러면 타당한 이차 문장들의 괴델수들의 집합은 산수에서 정의가능하지(조차) 않다. 그 까닭은 이렇다. V(y) 가 이 집합을 정의한다고 가정하자. f 는, 만약 n 이 A 의 괴델수라고 한다면 f(n) 은 (PA→A) 의 괴델수라는 성질을 만족하는, 어떤 회귀 함수라고 하자. B(x, y) 는 산수에서 f 를 표시한다고 하고, F(x) 는 산수에서 L 의 문장들의 괴델수들의 (회귀) 집합을 정의한다고 하자. 그러면

F(x)&∃y(B(x, y)&V(y))

는 산수에서 산수의 정리들의 괴델수들의 집합을 정의하게 되고, 이것은 타르스키의 정의불가능성 정리에 모순된다. 같은 맥락에서 더 강한 결과들이 알려져 있다. 연습문제 18.4 를 보라.

연습문제

18.1 ∃xFx&∃x-Fx 가 만족가능하다는 사실에서 ∃X[∃xXx&∃x-Xx] 가 타당하다는 게 따라 나오는가?

18.2

'∀X([Xa&∀x∀y(Xx&xRy→Xy)]→Xb)'

를 줄여서 'aR_*b' 라고 정의하자. 다음 (a), (b), (c) 가 타당함을 보여라.

(a) aR_*a,
(b) aRb→aR_*b,
(c) aR_*b&bR_*c→aR_*c.

a 가 b 의 자녀인 경우 그리고 오직 그 경우에만 aRb 라고 가정하자. 어떤 조건에서 aR_*a 가 성립하는가?

18.3 투입값 영역이 A 이고 산출값 영역이 A 의 진부분 집합인 일대일 함수가 있으면 집합 A 는 데데킨트 무한 (Dedekind infinite) 하다고 말한다. Ax D Inf 가 문장

∃z∃u(∀xz≠u(x)&∀x∀y(x≠y→u(x)≠u(y)))

라고 하자. Ax D Inf 는 한 해석의 논의 영역이 데데킨트 무한한 경우 그리고 오직 그 경우에만 그 해석에서 참인 문장임을 보여라. 집합론에 대해서 약간 아는 사람을 위해 더 말하겠다. 만약 집합이 데데킨트 무한하면 그 집합은 무한하다. (의존) 선택 공리는 그 역, 즉 만약 집합이 무한하면 그 집합은 데데킨트 무한하다는 것을 함축한다. A 는 열거가능하게 무한한 부분집합이 있는 경우 그리고 오직 그 경우에만 A 는 데데킨트 무한하다는 것과, A 가 열거가능하고 데데킨트 무한한 경우 그리고 오직 그 경우에만 A 는 열거가능하게 무한하다는 것과, A 가 열거가능하지만 데데킨트 무한하지는 않은 경우 그리고 오직 그 경우에만 A 는 유한하다는 것을 (선택 원리들을 전혀 쓰지 말고) 보여라. 논의 영역이 유한한 해석들에서만 참인 이차 문장을 만들어 보아라. 마찬가지로 논의 영역이 열거가능하게 무한한 해석들에서만 참인 이차 문장을 만들어 보아라.

18.4 B(x) 가 일차 또는 이차 식인 경우, B(x) 는 임의의 자연수 k 에 대하여 B(k) 가 에서 참인 꼭 그 경우 k∈θ 이면 이차 산수 에서 집합 θ 를 정의한다 고 말한다. 그 때 θ 는 이차 산수에서 정의가능하다고 말한다. 우리의 괴델수 부여를 확장하여 이차 문장들에 괴델수를 부여할 수 있게 된다고 가정하자. L 의 참인 이차 문장들의 괴델수들의 집합도, 또 타당한 이차 문장들의 괴델수들의 집합도 모두 이차 산수에서 정의가능하지 않음을 보여라.

18.5 (헨킨 ) {Q1, Q2, Ind}, {Q1, Q2, -Ind}, ..., {-Q1, -Q2, -Ind} 의 여덞 조합 가운데 어느 것이 만족가능한가? Q1 과 Q2 는 200 쪽에서 정의하였고 Ind 는 253 쪽에서 정의하였다.

18.6 ∀x∀y∀z(xRy&yRz→xRz) 가

∀X∀z[∀y(yRz→[∀x(xRy→Xx)→Xy])→∀y(yRz→Xy)]

에서 따라 나옴을 보여라.

18.7 (프레게, 『개념기호법』(Begriffsschrift) 133 쪽)

∀x∀y∀z(Rxy&Rxz→y=z)&∃x(xR_*a&xR_*b)→(aR_*b∨a=b∨bR_*a)

가 타당함을 보여라. (18.2 참조.)

18.8 ◇ (R) 이 ∀x∀y(∃w(Rwx&Rwy)→∃z(Rxz&Ryz)) 를 뜻한다고 하자. ◇(R)→◇(R_*) 이 타당함을 보여라.

18.9 ∃X-∃x∀y(Xx↔Rxy) 가 타당함을 보여라.

18.10 일차 논리 문장들과 동치인 이차 논리 문장들의 괴델수 집합이 이차 산수에서 정의가능하지 않음을 보여라. (힌트 : L 의 임의의 이차 문장 S 에 대해, S 가 참일 꼭 그 경우에 PA 는 S 를 함축하고, PA 가 S 를 함축할 꼭 그 경우에 (PA&S) 는 PA 와 동치인데, PA 는 어떠한 1차 문장과도 동치가 아니다. 또한 PA 가 -S 를 함축할 꼭 그 경우에 (PA&S) 는 일차 문장 0≠0 과 동치이다.)