2011 Fall - KSA 논리 및 집합 기말고사

[1] (a) <선택공리>와 <Zorn's lemma>를 기술하시오. [5점]

(b) <선택공리>로부터 <Zorn's lemma>를 유도하시오. [10점]

[2] Bernstein 정리를 기술하고 증명하시오. [10점]

[3](AC) 각 $\alpha \in \omega _1$에 대해 $P({\alpha})=0$을 만족하는 확률 $P$를 $\omega _1$의 모든 부분집합에 정의할 수는 없음을 보이시오. [15점] [이 때 다음 사실은 증명 없이 이용하시오 : 각 $i\in I$에 대응하여 $\alpha _i \geq 0$가 있어 모든 유한 부분집합 $J \subseteq I$에 대해 $\sum_{i\in J}a_i \leq 1$을 만족하면, countable 부분집합 $I_0 \subseteq I$가 있어 모든 $i\notin I_0$에 대해 $a_i =0$이다.]

[4] 술어논리의 완비성을 증명하는데 있어 Henkin's lemma가 결정적인 역할을 하였다. 다음 형태의 Henkin's lemma를 증명하시오 : 술어기호로 두 자리 술어기호 $\in$ 하나만 있고 상수를 없는 술어논리(집합론의 언어)에서 무모순인 닫힌 명제의 집합 $H$가 있다. 이 때 countable set $C$와 술어논리 $L(\{\in \}, C)$에서의 닫힌 명제의 집합 $G$가 있어 (i) $H\subseteq G$, (ii) $G$는 무모순이고, (iii) $L(\{\in \}, C)$에서의 임의의 닫힌 명제 $\phi$에 대해 $\phi \in G$이거나 $\not \phi \in G$이고, (iv) $x$만 자유인 명제 $\phi$에 대해 각 $c\in C$에 대해 $\phi (c)\in G$일 때마다 $\forall x \phi \in G$이다. [15점]

[5] (a) RA의 약한 완비성원리를 기술하시오.

(b) RA에서 증명가능한 모든 명제의 Godel 수의 집합이 recursive하지 않음을 보이시오. [10점]

[Hint. 해당되는 함수상수를 $\pmb{p}$라 하면, 각 항 $\pmb{t}$에 대해 명제 $\pmb{p}(\pmb{t})=\hat{1}$이 $\mathbb{N}$에서 참일 필요충분조건이 $v(\pmb{t})$가 증명가능한 어떤 명제의 Godel 수가 되는 것이다. 이제 Godel의 제1불완비성원리의 증명에서와 같이 <<이 명제는 증명할 수 없다>> 라는 뜻을 가진 닫힌 명제 $\mu$를 만들 수 있을 것이다. 여기서 세 자리 함수 $sub$가 recurtive함을 이용하시오. 이제 $\mu$가 RA에서 증명가능한 경우와 아닌 경우로 나누어 각각 모순임을 보이시오.]

[6] (a) 크기수 $\kappa$가 strongly inaccessible 하다는 뜻은? [5점]

(b) 크기수 $\kappa$가 strongly inaccessible 할 때 $V_\kappa$가 <선택공리>의 standard 모델임을 증명하시오.