2011 Fall - KSA 논리 및 집합 중간고사

[1] (a) 다음을 정의하시오. <<$S$ is a function with domain $I$.>> [3점]

(b) $S$ 가 위와 같을 때 $\prod_{i\in I} S_i $ 가 $\prod_{i\in I} S_i =\{f|f$ is a function on $I$ and $f(i)\in S_i$ for all $i\in I \}$ 와 같이 정의됨을 기억하시오. 이 때 $\prod_{i\in I} S_i $ 가 잘 정의됨을 보이시오. [사용되는 집합론공리들을 모두 언급하시오.] [10점]

[2] (a) $P_0$ 명제논리의 모든 공리들을 소개하시오. [3점]

(b) 위에서 부정기호 $\not$ 가 들어가는 공리가 꼭 필요함을 보이시오. 즉, 그 공리 없이는 $P_0$ 명제논리가 complete하지 않음을 보이시오. [Hint. $\tau _0 : P_0 \to \{0, 1\}$를 3가지 진리함수 $\tau : P \to \{0, \frac{1}{2}, 1\}$로 어떻게 확장하면 좋을까? 공리 중 어떤 것이 3가 항진 명제인가? ] [12점]

[3] (a) 다음을 정의하시오. <<변수 $x$는 명제 $\phi$에 자유로 나타난다.>> [3점]

(b) 다음을 정의하시오. <<술어논리에서 명제 $\phi$가 타당하다.>> [3점]

  (c) 술어논리의 공리 $\forall x [\phi \to \psi]\to [\phi \to \forall x \psi]$가 타당함을 보이시오. 여기서 변수 $x$는 명제 $\phi$에 자유로 나타나지 않는다. [7점]

[4] (a) 다음을 정의하시오. <<$\alpha$ is an ordinal.>> [3점]

(b) 각 집합 $x$에 대해 명제 $\phi (x,y)$가 성립하는 집합 $y$가 유일하게 있다. 이 때 모든 ordinal $\alpha$에 대해 집합 $f\alpha$를 다음이 만족되도록 정의할 수 있음을 보이시오: $g$가 ordinal $\alpha$위에서 정의된 함수이고 각 $\beta \in \alpha$에 대해 $g_\beta =f \beta$이면 $\phi (g,f\alpha)$이다.  [Ordinal과 함수에 대한 기본 성질들은 증명 없이 이용하시오. ] [10점]

[5] (a) 다음을 정의하시오. <<$(W,\prec)$ is a well-ordered set.>> [2점]

(b) $(W,\prec)$가 well-ordered set이면 단 하나의 ordinal $\alpha$와 순서동형임을 보이시오. [Ordinal과 함수에 대한 기본 성질들은 증명 없이 이용하시오.] [12점]