기수에 대한 정리

정리1

임의의 집합이 $X$이고 임의의 순서수 $\beta$의 모든 $\alpha\in \beta$에 대해 $X_\alpha$가 정의될때

$\beta = 0$이면 $X_\beta = X$로 정의되고

$\beta = \alpha +1$인 순서수 $\alpha$가 존재하면 $X_\beta = X_\alpha \cup \{ X_\alpha\}$로 정의되고

$\beta$가 극한순서수이면 $X_\beta = \displaystyle \bigcup_{\alpha \in \beta} X_\alpha$로 정의되는 집합 $X_\beta$는 모든 순서수 $\beta$에 대해 유일하게 존재하고

$X_\beta\notin X$와 $\beta\ne \gamma$인 모든 순서수 $\gamma$에 대해 $X_\beta\ne X_\gamma$가 성립한다.

증명

초한귀납법으로 모든 $\alpha\in \beta$에 대해 $X_\alpha$가 유일하게 존재하고 $X\subseteq X_\alpha$라고 가정할때

$\beta = 0$이면 $X_\beta = X$는 유일하게 존재하고 집합 정리로 $X\subseteq X = X_\beta$이다.

$\beta = \alpha +1$인 순서수 $\alpha$가 존재하면 순서수 덧셈 정리로 $\alpha\in \alpha +1= \beta$이므로

귀납가정으로 $X_\alpha$가 유일하게 존재함에 따라 $X_\beta = X_\alpha \cup \{ X_\alpha\}$는 유일하게 존재하고

$X\subseteq X_\alpha \subseteq X_\alpha \cup \{ X_\alpha\} = X_\beta$가 되어 집합 정리로 $X\subseteq X_\beta$이다.

$\beta$가 극한순서수이면 귀납가정으로 모든 $\alpha\in \beta$에 대해 $X_\alpha$가 유일하게 존재하여 $X_\beta = \displaystyle \bigcup_{\alpha \in \beta} X_\alpha$가 유일하게 존재하고

$\beta\ne \emptyset$이므로 $\alpha\in \beta$가 존재하여 합집합의 정의로 $X\subseteq X_\alpha \subseteq X_\beta$임에 따라 집합 정리로 $X\subseteq X_\beta$이다.

따라서 모든 순서수 $\beta$에 대해 $X_\beta$가 유일하게 존재하고 $X\subseteq X_\beta$이므로 

$X_\beta\in X$라고 가정하면 $X_\beta\in X\subseteq X_\beta$가 되어 집합 정리에 모순임에 따라 $X_\beta\notin X$이다.

초한귀납법으로 임의의 순서수 $\gamma$의 모든 $\beta \in \gamma$에 대해 모든 $\alpha\in \beta$가 $X_\alpha\in X_\beta$라고 가정하면

$\gamma = 0$일때 공허하게 모든 $\alpha\in \gamma$에 대해 $X_\alpha\in X_\gamma$가 성립한다.

$\gamma = \beta+1$인 순서수 $\beta$가 존재할때

$\beta\in \gamma$이고 순서수 덧셈 정리로 모든 $\alpha\in \gamma = \beta+1 = \beta\cup \{ \beta\}$는 $\alpha\in \beta$이거나 $\alpha = \beta$이므로

$\alpha\in \beta$이면 귀납가정으로 $X_\alpha \in X_\beta \subseteq X_\beta \cup \{ X_\beta\} = X_\gamma$이고 $\alpha = \beta$이면 $X_\alpha=X_\beta \in X_\beta \cup \{ X_\beta\} = X_\gamma$이다.

$\gamma$가 극한순서수이면 $X_\gamma = \displaystyle \bigcup_{\beta\in \gamma} X_\beta$이므로 극한순서수 정리와 합집합의 정의로

모든 $\alpha\in \gamma = \displaystyle \bigcup_{\beta\in \gamma} \beta$는 $\alpha \in \beta$인 $\beta\in \gamma$가 존재하여 귀납가정으로 $X_\alpha \in X_\beta \subseteq X_\gamma$이다.

따라서 임의의 순서수 $\gamma$의 모든 $\beta \in \gamma$에 대해 $X_\beta\in X_\gamma$가 성립하여

$\beta\ne \gamma$인 모든 순서수 $\beta,\gamma$는 순서수 정리로 $\beta \in \gamma$ 또는 $\gamma\in \beta$이므로

$\beta \in \gamma$이면 $X_\beta\in X_\gamma$임에 따라 집합 정리로 $X_\beta\ne X_\gamma$이고

$\gamma\in \beta$이면 $X_\gamma \in X_\beta$임에 따라 집합 정리로 $X_\gamma\ne X_\beta$이다.

 

 

 

정리2

임의의 언어 $\mathcal{L}$에 대해 $\mathcal{L}$-일차논리의 논리식집합 $W$의 임의의 부분집합 $\Sigma \subseteq W$가 무모순이면

모든 문장 $\phi \in W$에 대해 $\phi \in \Sigma^+$ 또는 $(\neg \phi) \in \Sigma^+$중 하나만 성립하고

$\Sigma \subseteq \Sigma^+$가 성립하는 무모순인 집합 $\Sigma^+$가 존재한다.

증명

집합의 크기 정리로 모든 문장들의 집합 $S \subseteq W$의 크기 $|S| =\kappa$가 존재하여 $\kappa$는 기수이고

집합의 크기의 정의와 역함수 정리로 전단사함수 $\psi :\kappa\to S$가 존재한다.

기수는 순서수이므로 $(\kappa,\underline{\in})$는 정렬집합이 되어 $(\kappa,\underline{\in})$에 대한 초한 귀납법으로

임의의 $\lambda\in \kappa$에 대해 모든 $\eta\in \lambda$가 $\psi(\eta) \in \Sigma_\eta$ 또는 $(\neg \psi(\eta)) \in \Sigma_\eta$ 중 하나만 성립하고

$\Sigma \subseteq \Sigma_\eta$가 성립하는 무모순인 집합 $\Sigma_\eta\subseteq W$가 $\eta$에 대해 유일하게 존재한다고 가정할때

$\lambda = 0$이면 무모순 정리로 $\Sigma$에 대해 문장과의 합집합 또는 문장의 부정과의 합집합 중 하나는 무모순이므로

$\Sigma\cup \{ \psi(0) \}$이 무모순일때 $\Sigma_0 = \Sigma\cup \{ \psi(0) \}$으로 정의하고

$\Sigma \cup \{ \psi(0) \}$에 모순이 있을때 $\Sigma_0 = \Sigma \cup \{ (\neg \psi(0)) \}$으로 정의하여 $\lambda = 0$에 대해 $\Sigma_0$은 유일하게 존재한다.

$\lambda = \eta +1$인 순서수 $\eta$가 존재할때

순서수 덧셈 정리로 $\eta\in \eta +1= \lambda$이므로 귀납가정으로 $\eta$에 대해 $\Sigma_\eta$가 유일하게 존재함에 따라

$\Sigma_\eta\cup \{ \psi(\lambda)\}$가 무모순이면 $\Sigma_\lambda =\Sigma_\eta \cup \{ \psi(\lambda)\}$로 정의하고

$\Sigma_\eta\cup \{ \psi(\lambda)\}$에 모순이 있으면 $\Sigma_\lambda =\Sigma_\eta \cup \{ (\neg \psi(\lambda) )\}$로 정의하여 $\lambda$에 대해 $\Sigma_\lambda$는 유일하게 존재하고

$\psi(\lambda)\in S\subseteq W$는 문장이므로 $(\neg \psi(\lambda))$도 문장이 되어 $(\neg \psi(\lambda)) \in S\subseteq W$이고

$\Sigma \subseteq \Sigma_\eta\subseteq W$임에 따라 $\Sigma\subseteq \Sigma_\lambda\subseteq W$이고 무모순 정리로 $\Sigma_\lambda$는 무모순이다.

$\lambda$가 극한순서수일때 귀납가정으로 모든 $\eta\in \lambda$에 대해 $\Sigma\subseteq \Sigma_\eta \subseteq W$이고 무모순인 $\Sigma_\eta$가 유일하게 존재하여

$\Sigma \subseteq \displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta \subseteq W$인 $\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta$가 유일하게 존재하므로

$\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta$에 모순이 있다고 가정하면 어떤 논리식 $\theta \in W$가 존재하여 $\theta,(\neg \theta)$가 $\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta$의 정리인데

$\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta$로부터 $\theta,(\neg \theta)$의 증명은 각각 크기가 유한인 배열이므로 증명에 사용된 $\theta,(\neg \theta)$의 가정도 유한 개가 되어

어떤 $\eta_0 \in \lambda$에 대해 증명에 사용된 $\theta,(\neg \theta)$의 가정을 모두 포함하는 $\Sigma_{\eta_0} \subseteq \displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta$이 존재하므로

$\theta,(\neg \theta)$는 $\Sigma_{\eta_0}$의 정리가 되고 $\Sigma_{\eta_0}$이 무모순이라는 가정에 모순임에 따라 $\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta$는 무모순이다.

$\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta \cup \{ \psi(\lambda)\}$가 무모순이면 $\Sigma_\lambda=\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta \cup \{ \psi(\lambda)\}$로 정의하고

$\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta \cup \{ \psi(\lambda)\}$에 모순이 있으면 $\Sigma_\lambda=\displaystyle \bigcup_{\eta\in \lambda}\Sigma_\eta \cup \{ (\neg\psi(\lambda))\}$로 정의하여 $\lambda$에 대해 $\Sigma_\lambda$는 유일하게 존재한다.

따라서 모든 $\lambda\in \kappa$에 대해 $\psi(\lambda) \in \Sigma_\lambda$ 또는 $(\neg \psi(\lambda)) \in \Sigma_\lambda$ 중 하나만 성립하고

$\Sigma \subseteq \Sigma_\lambda$가 성립하는 무모순인 집합 $\Sigma_\lambda \subseteq W$가 존재하여 모든 $\eta\in \lambda$에 대해 $\Sigma \subseteq\Sigma_\eta\subseteq \Sigma_\lambda \subseteq W$이므로

$\Sigma^+=\displaystyle \bigcup_{\lambda \in \kappa}\Sigma_\lambda$로 정의하면 위와 비슷하게 $\Sigma^+$은 무모순이다.

또 $\Sigma \subseteq \Sigma^+ \subseteq W$이고 모든 문장 $\phi\in W$는 $\phi\in S$이므로 전사의 정의로 $\phi=\psi(\lambda_0)$인 $\lambda_0\in \kappa$이 존재하여

$\phi \in \Sigma_{\lambda_0} \subseteq \Sigma^+$ 또는 $(\neg \phi) \in \Sigma_{\lambda_0} \subseteq \Sigma^+$ 중 하나만 성립한다.

 

 

 

정리3

임의의 집합 $X$의 크기 $|X|$에 대해 다음이 성립한다.

1. $X$가 유한집합이기 위한 필요충분조건은 $|X|$가 유한집합인 것이다.

2. $X$가 무한집합이기 위한 필요충분조건은 $|X|$가 무한집합인 것이다.

증명

1.

기수 정리와 자연수 정리로 $X$가 유한집합이기 위한 필요충분조건은 $|X|$가 유한집합인 것이다.

2.

1번의 대우로 성립한다.

 

 

 

정리4

임의의 집합족 $\mathcal{F}$에 대해 다음이 성립한다.

1. $\mathcal{F}$의 합집합의 크기는 $\displaystyle \bigcup_{A\in \mathcal{F}}|A|$ $\underline{\in}$ $\displaystyle \left |\bigcup_{A\in \mathcal{F}} A \right|$이다.

2. 부분순서집합 $(\mathcal{F},\,$$\subseteq$$)$에서 $\mathcal{F}$의 상계 $M$이 존재하면 $\displaystyle \bigcup_{A\in \mathcal{F}} |A| = |M|=\left |\bigcup_{A\in \mathcal{F}} A \right|$이다.

증명

1.

집합의 크기 정리로 모든 $A \in\mathcal{F}$의 크기 $|A|$는 기수이므로 기수 정리로 $\displaystyle \bigcup_{A\in \mathcal{F}}|A|$는 기수이고

모든 $B \in\mathcal{F}$에 대해 $\displaystyle B \subseteq \bigcup_{A\in \mathcal{F}} A $임에 따라 기수 정리로 $\displaystyle |B| \underline{\in} \left |\bigcup_{A\in \mathcal{F}} A \right |$이다.

따라서 기수는 순서수이므로 순서수 정리로 $\displaystyle \bigcup_{A\in \mathcal{F}}|A| \underline{\in} \left |\bigcup_{A\in \mathcal{F}} A \right |$이다.

2.

순서집합 정리로 $(\mathcal{F},\subseteq)$는 부분순서집합이다.

모든 $a\in \displaystyle \bigcup_{A\in \mathcal{F}} A$에 대해 합집합의 정의로 $a\in A$인 $A\in \mathcal{F}$가 존재하여

상계의 정의로 $a\in A\subseteq M$이므로 $\displaystyle \bigcup_{A\in \mathcal{F}} A\subseteq M$임에 따라 기수 정리로 $\displaystyle \left |\bigcup_{A\in \mathcal{F}} A \right | \underline{\in} |M|$이고

상계의 정의로 $M\in \mathcal{F}$이므로 $\displaystyle |M| \subseteq \bigcup_{A\in \mathcal{F}}| A| $이 되어 순서수 정리로 $\displaystyle |M| \underline{\in} \bigcup_{A\in \mathcal{F}} |A| $이다.

$\displaystyle \left |\bigcup_{A\in \mathcal{F}} A \right | \underline{\in} |M| \underline{\in} \bigcup_{A\in \mathcal{F}}|A|$이고 1번으로 $\displaystyle \bigcup_{A\in \mathcal{F}}|A| \underline{\in} \left |\bigcup_{A\in \mathcal{F}} A \right |$이므로 $\displaystyle \bigcup_{A\in \mathcal{F}} |A| = |M|=\left |\bigcup_{A\in \mathcal{F}} A \right|$이다.

 

 

 

정리5

무한집합인 임의의 언어 $\mathcal{L}$에 대해 $\mathcal{L}$-일차논리의 항집합이 $T$이고 논리식집합이 $W$일때 다음이 성립한다.

1. $T$의 크기는 $|T|$ $\underline{\in}$ $|\mathcal{L}|$이다.

2. $W$의 크기는 $|W|= |\mathcal{L}|$이다.

증명

함수기호집합 $\mathcal{F}$와 관계기호집합 $\mathcal{R}$과 상수기호집합 $\mathcal{C}$에 대해 $\mathcal{L} = \mathcal{F}\cup \mathcal{R}\cup \mathcal{C}$일때

집합의 크기 정리로 $\mathcal{L}$의 크기 $|\mathcal{L}|$은 기수이고 $\mathcal{L}$이 무한집합이므로 위 정리로 $|\mathcal{L}|$은 무한집합이 되어

기수 정리와 극한순서수 정리로 자연수집합 $\mathbb{N}$에 대해 $\mathbb{N}\underline{\in} |\mathcal{L}|$이다.

가부번인 변수기호집합 $\mathcal{V}$와 등호집합 $\{ = \}$과 괄호집합 $\{ (,)\}$와 쉼표집합 $\{ ,\}$과

결합자기호집합 $\{ \neg,\to\}$과 한정기호집합 $\{ \forall\}$에 대해

$\mathcal{L}$-일차논리의 기호집합은 $\mathcal{S} = \mathcal{L} \cup \mathcal{V}\cup \{=\} \cup \{ (,)\} \cup \{ ,\} \cup \{\neg,\to\}\cup \{\forall\}$이므로

무한집합 정리로 $\mathcal{S}$는 무한집합이고 위 정리로 $|\mathcal{S}|$도 무한집합이다.

일차논리의 기호의 정의로 $\mathcal{L},\mathcal{V},\{ =\},\{(,)\},\{,\},\{ \neg,\to\},\{ \forall\}$은 모두 서로소이고 $|\mathcal{L}|$은 무한집합이므로

$\{ =\},\{(,)\},\{,\},\{ \neg,\to\},\{ \forall\}$은 유한집합이고 가부번 정리로 $|\mathcal{V}| =\mathbb{N} \underline{\in} |\mathcal{L}|$임에 따라

집합의 크기 정리와 유한집합 정리와 기수 덧셈 정리로

$\begin{align*}|\mathcal{S}| &= |\mathcal{L} \cup \mathcal{V}\cup \{=\} \cup \{ (,)\} \cup \{ ,\} \cup \{\neg,\to\}\cup \{\forall\}|  \\[0.5em] & = |\mathcal{L}| \oplus |\mathcal{V}| \oplus |\{ =\}|\oplus |\{ (,)\}| \oplus |\{,\}|\oplus |\{ \neg,\to\}|\oplus |\{\forall\}|\\[0.5em]& = |\mathcal{L}| \oplus \mathbb{N} \oplus 1 \oplus 2 \oplus 1\oplus 2 \oplus 1 \\[0.5em]& = |\mathcal{L}| \oplus \mathbb{N} \\[0.5em] & = |\mathcal{L}| \text{ 이다.}\end{align*}$

$n\ge 1$인 임의의 $n\in \mathbb{N}$에 대해 순서수 정리로 $n = \{ 0,1,\cdots, n-1\}$임에 따라

$\mathcal{S}$의 원소를 사용하는 길이가 $n$인 문자열들의 집합은 $S_n = \{ s \in \mathcal{P}(n\times \mathcal{S}) : s\text{는 길이가 }n\text{인 문자열}\}$이므로

$n\ge 1$인 임의의 $n\in \mathbb{N}$에 대한 귀납법으로 $|S_n|=|\mathcal{S}|$임을 보인다.

$n=1$일때 임의의 $x\in \mathcal{S}$에 대해 $s_x(0) = x$인 함수 $s_x : 1\to \mathcal{S}$는 길이가 $1$인 문자열이고 $s_x\in S_1$이므로

$F_1(x) = s_x$로 함수 $F_1:\mathcal{S}\to S_1$을 정의하면 $F_1$이 전단사임에 따라 집합의 크기 정리로 $|S_1|=|\mathcal{S}|$이다.

$k\ge 1$인 모든 $k\in \mathbb{N}$에 대해 $|S_k|=|\mathcal{S}|$라고 가정할때 집합의 크기 정리로 전단사함수 $F_k :S_k \to \mathcal{S}$가 존재하여

임의의 $s\in S_{k+1}$는 $s:k+1\to \mathcal{S}$인 함수이므로 축소함수 $s|_k :k\to \mathcal{S}$가 $s|_k\in S_k$임에 따라

$F_{k+1}(s) = (F_k(s|_k), s(k))\in \mathcal{S}\times \mathcal{S}$인 함수 $F_{k+1}:S_{k+1}\to \mathcal{S}\times \mathcal{S}$을 정의한다.

임의의 $s,t\in S_{k+1}$에 대해 $(F_k(s|_k),s(k))=F_{k+1}(s) = F_{k+1}(t) = (F_k(t|_k),t(k))$일때

순서쌍의 상등으로 $F_k(s|_k) = F_k(t|_k)$이고 $s(k) = t(k)$이므로 단사의 정의로 $s|_k = t|_k$가 되어

모든 $i = 0,1,\cdots, k-1$에 대해 $s(i) = s|_k(i) = t|_k(i) = t(i)$임에 따라 $s=t$이고 $F|_{k+1}$은 단사이다.

임의의 $(x,y)\in \mathcal{S}\times \mathcal{S}$에 대해 전사의 정의로 $F_k(s_k) = x$인 $s_k\in S_k$가 존재하여

모든 $i = 0,1,\cdots, k-1$에 대해 $s(i) = s_k(i)$이고 $s(k) = y$인 함수 $s: k+1\to \mathcal{S}$는 $s\in S_{k+1}$이므로

$F_{k+1}(s) = (F_k(s|_k) , s(k)) = (F_k(s_k), y) = (x,y)$임에 따라 $F|_{k+1}$은 전사이다.

$F|_{k+1}$이 전단사이므로 집합의 크기 정리와 집합의 크기 정리와 기수 곱셈의 정의와 기수 곱셈 정리로

$|S_{k+1}| = |\mathcal{S}\times \mathcal{S}| = ||\mathcal{S}|\times |\mathcal{S}|| = |\mathcal{S}|\otimes |\mathcal{S}| = |\mathcal{S}|$이다.

따라서 $n\ge 1$인 모든 $n\in \mathbb{N}$에 대해 $|S_n| = |\mathcal{S}|$이므로

집합의 크기 정리와 선택 공리로 $n\ge 1$인 모든 $n\in \mathbb{N}$에 대해 전단사함수 $F_n:S_n\to \mathcal{S}$을 선택하면

모든 $s\in \displaystyle \bigcup_{n= 1}^\infty S_n$는 합집합의 정의로 $s\in S_n$이고 $n\ge 1$인 $n\in \mathbb{N}$이 존재하고 $s: n\to \mathcal{S}$인 함수임에 따라

$s\in S_n$인 $n\in \mathbb{N}$은 유일하므로 $F(s) = (n-1, F_n(s))\in \mathbb{N}\times \mathcal{S}$인 함수 $F:\displaystyle \bigcup_{n=1}^\infty S_n\to \mathbb{N}\times \mathcal{S}$를 정의한다.

임의의 $s,t\in \displaystyle \bigcup_{n= 1}^\infty S_n$가 어떤 $n,m\in \mathbb{N}$에 대해 $(n-1,F_n(s))=F(s) = F(t) = (m-1,F_m(t))$일때

순서쌍의 상등으로 $n-1 = m-1$이고 $F_n(s) = F_m(t)$이므로

$n = m$이 되어 단사의 정의로 $s= t$임에 따라 $F$는 단사이다.

임의의 $(m, x)\in \mathbb{N}\times \mathcal{S}$에 대해 전사의 정의로 $F_{m+1}(s) = x$인 $s\in S_{m+1}$가 존재하여

$F(s) = (m+1-1,F_{m+1}(s)) = (m,F_{m+1}(s)) = (m,x)$이므로 $F$가 전사임에 따라

집합의 크기 정리와 집합의 크기 정리와 기수 곱셈의 정의와 기수 곱셈 정리로

$\displaystyle \left |\bigcup_{n= 1}^\infty S_n \right | = |\mathbb{N}\times \mathcal{S}| = |\mathbb{N}\times |\mathcal{S}|| = \mathbb{N}\otimes |\mathcal{S}| = \mathbb{N} \otimes |\mathcal{L}| = |\mathcal{L}|$이다.

1.

$\mathcal{L}$-일차논리의 항집합 $T$는 $T\subseteq \displaystyle \bigcup_{n=1}^\infty S_n$이므로 집합의 크기 정리로 $\displaystyle |T|\underline{\in} \left |\bigcup_{k= 1}^\infty S_n \right | = |\mathcal{L}|$이다.

2.

$\mathcal{L}$-일차논리의 논리식집합 $W$는 $W \subseteq \displaystyle \bigcup_{n=1}^\infty S_n$이므로 집합의 크기 정리로 $\displaystyle |W|\underline{\in} \left |\bigcup_{n= 1}^\infty S_n \right | = |\mathcal{L}|$이다.

$\mathcal{L} = \mathcal{F}\cup \mathcal{R}\cup \mathcal{C}$이고 일차논리의 기호의 정의로 $\mathcal{F}\cap \mathcal{R}\cap \mathcal{C} =\emptyset$이므로

변수기호집합 $\mathcal{V} = \{ x_0,x_1,\cdots \}$에 대해 함수 $\phi :\mathcal{L}\to W$를

임의의 $f\in \mathcal{F}$가 $n_f$항함수에 대응되는 함수기호일때 $\phi(f) = (f(x_1,\cdots,x_{n_f}) = f(x_1,\cdots,x_{n_f})) \in W$로 정의하고

임의의 $R \in \mathcal{R}$이 $n_R$항관계에 대응되는 관계기호일때 $\phi(R) = R(x_1,\cdots,x_{n_R}) \in W$로 정의하고

임의의 상수기호 $c\in \mathcal{C}$에 대해 $\phi(c) = (c=c)\in W$로 정의하면

$\phi$가 단사임에 따라 집합의 크기 정리로 $|\mathcal{L}|\underline{\in} |W|$가 되어 $|W|= |\mathcal{L}|$이다.

 

 

 

정리6

임의의 언어 $\mathcal{L}$에 대해 $\mathcal{L}$-일차논리의 논리식집합이 $W$일때

임의의 $\mathcal{L}$-이론 $T\subseteq W$가 무모순이면 $T$는 $\mathcal{L}$-일차논리에서 만족가능하다.

증명

$\mathcal{L}$이 유한이면 가산이므로 가산언어 정리로 $T$는 $\mathcal{L}$-일차논리에서 만족가능하다.

$\mathcal{L}$이 무한이면 위 정리로 $|\mathcal{L}|$도 무한집합이므로 $\kappa = |\mathcal{L}|$로 둘때

기수 정리와 극한순서수 정리로 자연수집합 $\mathbb{N}$에 대해 $\mathbb{N}\underline{\in} |\mathcal{L}| = \kappa$이다.

임의의 기호는 집합이므로 $b_0 = \mathcal{L}$으로 정의하고 위 정리와 같이 모든 $\lambda\in \kappa$에 대해 $b_\lambda$를 정의하면

집합의 크기 정리와 기수 정리로 기호집합 $\{ b_\lambda : \lambda\in \kappa\}$의 크기는 $\kappa$이고 모든 $\lambda\in \kappa$에 대해 $b_\lambda \notin \mathcal{L}$이다.

언어 $\mathcal{L} = \mathcal{F} \cup \mathcal{R} \cup \mathcal{C}$의 상수기호집합 $\mathcal{C}$에 $\{ b_\lambda : \lambda\in \kappa\}$를 추가하여 $\mathcal{C}^+ = \mathcal{C} \cup \{ b_\lambda: \lambda\in \kappa\}$로 확장하고

언어 $\mathcal{L}^+ = \mathcal{L} \cup \{ b_\lambda:\lambda\in \kappa\} $를 정의하면 $\{ b_\lambda:\lambda\in \kappa\} =\mathcal{C}^+ \setminus \mathcal{C} $이고 $\mathcal{L}\cap (\mathcal{C}^+\setminus \mathcal{C}) =\emptyset$이므로

집합의 크기 정리와 기수 덧셈 정리로 $|\mathcal{L}^+| = |\mathcal{L} \cup (\mathcal{C}^+\setminus \mathcal{C})| = |\mathcal{L}| \oplus |\mathcal{C}^+\setminus \mathcal{C}| = \kappa\oplus \kappa = \kappa$이다.

위 정리로 $\mathcal{L}^+$-논리식집합 $W^+$는 $\kappa = |\mathcal{L}^+| = |W^+|$와 $W \subseteq W^+$가 성립하여

가부번인 변수기호집합이 $\{ x_0,x_1,\cdots\}$이고 하나의 자유변수를 가지는 $\mathcal{L}^+$-논리식들의 집합이 $A \subseteq W^+$일때

집합의 크기 정리로 $|A| \underline{\in} |W^+| = \kappa$이고 모든 $\lambda\in \kappa$에 대해 $(x_0 = b_\lambda) \in A$가 되어 $\kappa \underline{\in} |A|$임에 따라 $|A| = \kappa$이다.

집합의 크기의 정의와 역함수 정리로 $\kappa$에서 $A$로의 전단사함수가 존재하므로 $A = \{ \alpha_\lambda: \lambda\in \kappa\}$일때

기수는 순서수이므로 $(\kappa,\underline{\in})$가 정렬집합임에 따라 $(\kappa,\underline{\in})$에 대한 초한 귀납법으로

임의의 $\lambda\in \kappa$의 모든 $\sigma \in \lambda$에 대해 $\alpha_\sigma\in A$에 포함되지 않는 $c_\sigma\in \mathcal{C}^+\setminus \mathcal{C}$가 유일하게 존재하여

모든 $\eta\in \sigma$에 대해 $c_\sigma$는 $\alpha_\eta\in A$에 포함되지 않고 $c_\eta \in \mathcal{C}^+\setminus \mathcal{C}$에 대해 $c_\eta\ne c_\sigma$라고 가정하면

순서수 정리와 기수 정리로 $|\{ c_\sigma : \sigma\in \lambda \}| = |\lambda|\underline{\in} \lambda \in \kappa = |\kappa| = |\mathcal{C}^+\setminus \mathcal{C}|$이므로 

모든 $\sigma \in \lambda$에 대해 $c_\sigma \ne b_\mu$인 $b_\mu \in \mathcal{C}^+\setminus \mathcal{C}$가 존재하여 $b_\mu \in (\mathcal{C}^+\setminus \mathcal{C}) \setminus \{ c_\sigma:\sigma\in \lambda\}$이다.

모든 $b \in (\mathcal{C}^+\setminus \mathcal{C}) \setminus \{ c_\sigma:\sigma\in \lambda\}$가 $\alpha_\lambda\in A$ 또는 어떤 $\sigma\in \lambda$에 대해 $\alpha_\sigma\in A$에 포함된다고 가정하면

모든 논리식은 길이가 유한인 문자열임에 따라 어떤 $i\in \mathbb{N}$에 대해 $\alpha_\lambda(i) = b$ 또는 $\alpha_\sigma(i) = b$이므로

$(\mathcal{C}^+\setminus \mathcal{C}) \setminus \{ c_\sigma:\sigma\in \lambda\} \subseteq \{ \alpha_\lambda(i) : i=0,1,\cdots, k_\lambda-1\}\cup \displaystyle \bigcup_{\sigma\in \lambda} \{ \alpha_{\sigma}(i) : i = 0,1,\cdots, k_\sigma -1\}$인데

$\lambda$가 유한집합이면 집합 정리로 $(\mathcal{C}^+\setminus \mathcal{C}) \setminus \{ c_\sigma:\sigma\in \lambda\}$는 무한집합이고

집합 정리로 $\{ \alpha_\lambda(i) : i=0,1,\cdots, k_\lambda-1\}\cup \displaystyle \bigcup_{\sigma\in \lambda} \{ \alpha_{\sigma}(i) : i = 0,1,\cdots, k_\sigma -1\}$는 유한집합이므로

집합 정리에 모순이다.

$\lambda$가 무한집합이면 위 정리로 $|\lambda|$도 무한집합이 되어 기수 정리와 극한순서수 정리로 $\mathbb{N}\underline{\in} |\lambda|$이므로

집합의 크기 정리와 집합의 크기 정리와 자연수집합 정리와 기수 곱셈의 정의와 기수 정리로

$\begin{align*} |(\mathcal{C}^+\setminus \mathcal{C}) \setminus \{ c_\sigma :\sigma \in \lambda \}|& \underline{\in} \left |\{ \alpha_\lambda(i) : i=0,1,\cdots, k_\lambda-1\}\cup \bigcup_{\sigma\in \lambda} \{ \alpha_{\sigma}(i) : i = 0,1,\cdots, k_\sigma -1\} \right | \\[0.5em] & \underline{\in} \left | (\{\lambda \} \times \{ \alpha_\lambda(i) : i=0,1,\cdots, k_\lambda-1\})\cup \bigcup_{\sigma\in \lambda} (\{\sigma\} \times \{ \alpha_{\sigma}(i) : i = 0,1,\cdots, k_\sigma -1\}) \right | \\[0.5em] & \underline{\in} \left | (\{\lambda \} \times k_\lambda)\cup \bigcup_{\sigma\in \lambda} (\{\sigma\} \times k_\sigma ) \right | \\[0.5em] & \underline{\in} \left | (\{\lambda \} \times \mathbb{N})\cup \bigcup_{\sigma\in \lambda} (\{\sigma\} \times \mathbb{N}) \right | \\[0.5em] & \qquad = \left | (\{\lambda \} \times \mathbb{N})\cup (\lambda \times \mathbb{N}) \right | \\[0.5em] & \qquad = | \{\lambda \} \times \mathbb{N} |\oplus |\lambda \times \mathbb{N}| \\[0.5em] & \qquad = | \{\lambda \} \times \mathbb{N} |\oplus ||\lambda| \times \mathbb{N}| \\[0.5em] & \qquad = |\mathbb{N}| \oplus (|\lambda|\otimes \mathbb{N}) \\[0.5em] & \qquad = \mathbb{N} \oplus (|\lambda|\otimes \mathbb{N}) \\[0.5em] & \qquad = \mathbb{N} \oplus |\lambda| \\[0.5em] & \qquad = |\lambda| \text{ 이고} \end{align*}$

집합의 크기 정리와 기수 정리와 기수 정리와 순서수 정리로

$\begin{align*} \kappa & = |\mathcal{C}^+\setminus \mathcal{C}| \\[0.5em]& = | ((\mathcal{C}^+\setminus \mathcal{C}) \setminus \{ c_\sigma :\sigma \in \lambda \}) \cup \{ c_\sigma :\sigma \in \lambda \} | \\[0.5em]& = | (\mathcal{C}^+\setminus \mathcal{C}) \setminus \{ c_\sigma :\sigma \in \lambda \}| \oplus | \{ c_\sigma :\sigma \in \lambda \} | \\[0.5em]& \underline{\in} |\lambda| \oplus |\lambda| = |\lambda| \\[0.5em]& \underline{\in} \lambda \\[0.5em]&\in \kappa \text{ 가 되어 모순임에 따라} \end{align*}$

모든 $\sigma \in \lambda$에 대해 $\alpha_\lambda\in A$와 $\alpha_\sigma\in A$에 포함되지 않고 $c_\sigma \ne b_\mu$인 $b_\mu \in \mathcal{C}^+\setminus \mathcal{C}$가 존재하므로

정렬집합의 정의로 $b_\mu$의 첨수 $\mu \in \kappa$가 최소라고 가정할때 $\lambda$에 대해 $c_\lambda= b_\mu$가 유일하게 존재한다.

모든 $\lambda\in \kappa$에 대해 $\alpha_\lambda \in A$에 포함되는 유일한 자유변수 $x_{i_\lambda}$의 첨수가 $i_\lambda\in \mathbb{N}$일때

초한 귀납적으로 정의된 $c_\lambda\in \mathcal{C}^+\setminus \mathcal{C}$에 대해

$\mathcal{L}^+$-논리식 $\theta_\lambda = (( \neg (\forall x_{i_\lambda}) \alpha_\lambda) \to (\neg $$\alpha_\lambda[c_\lambda / x_{i_\lambda}]$$))$를 정의하면 $\theta_\lambda$는 문장이다.

 

$T\subseteq W\subseteq W^+$이고 모든 $\lambda\in \kappa$에 대해 $\theta_\lambda \in W^+$이므로 $T_\lambda = T\cup \{ \theta_\sigma : \sigma\in \lambda\} \subseteq W^+$로 정의할때

$(\kappa,\underline{\in})$에 대한 초한 귀납법으로 모든 $\lambda\in \kappa$에 대해 $T_\lambda$가 $\mathcal{L}^+$-일차논리에서 무모순임을 보인다.

모든 $\lambda\in \kappa$의 모든 $\sigma \in \lambda$에 대해 $T_\sigma\subseteq W^+$가 $\mathcal{L}^+$-일차논리에서 무모순이라고 가정하면

$\lambda = 0$일때

$\mathcal{L}$-일차논리에서 $T_0  = T$는 무모순이고 $T$의 모든 논리식은 $\mathcal{C}^+\setminus \mathcal{C}$의 상수들을 항으로 갖지 않으므로

$\mathcal{L}^+$-일차논리에서 $T$에 모순이 있으면 어떤 $\psi^+ \in W^+$에 대해 $\psi^+ , (\neg \psi^+)$가 $T$의 정리인데

$T$로부터 $\psi^+ , (\neg \psi^+)$의 증명에서 나온 $\mathcal{C}^+\setminus \mathcal{C}$의 상수들은 유한 개이고 변수집합은 무한이므로

증명에서 나오지 않는 변수들을 $\mathcal{C}^+\setminus \mathcal{C}$의 상수들에 대응시켜 치환하면

어떤 $\psi \in  W$에 대해 $\psi , (\neg \psi)$가 $T$의 정리이고 $\mathcal{L}$-일차논리에서 $T$가 무모순이라는 가정에 모순이므로 

$\mathcal{L}^+$-일차논리에서 $T_0 = T$는 무모순이다.

$\lambda =\sigma +1$인 순서수 $\sigma$가 존재할때 순서수 덧셈 정리로 $\sigma \in \sigma +1 = \lambda$이므로 귀납가정으로 $T_\sigma$는 무모순이 되어

$T_\lambda =T_{\sigma +1} = T\cup \{ \theta_\eta:\eta\in \sigma +1\} = T\cup \{ \theta_\eta: \eta\in \sigma \cup \{ \sigma\}\}= T_\sigma \cup \{ \theta_\sigma \}$에 모순있다고 가정하면

어떤 $\psi \in W^+$에 대해 $\psi , (\neg \psi)$가 $T_\sigma \cup \{ \theta_\sigma\}$의 정리이고 형식계 정리로 $T_\sigma \cup \{ \theta_\sigma\} \cup \{ (\neg (\neg \theta_\sigma))\}$의 정리이므로

$\theta_\sigma$가 문장임에 따라 일차논리 정리로 $(\neg \theta_\sigma)$는 $T_\sigma \cup \{ \theta_\sigma\}$의 정리이고 $(\theta_\sigma \to (\neg \theta_\sigma))$는 $T_\sigma$의 정리이다.

또 일차논리 정리와 명제논리 정리로 $((\theta_\sigma \to (\neg \theta_\sigma)) \to (\neg \theta_\sigma))$는 일차논리의 정리이므로

형식계 정리로 $T_\sigma$의 정리가 되어 전건긍정으로 $(\neg \theta_\sigma) = (\neg (( \neg (\forall x_{i_\sigma}) \alpha_\sigma) \to (\neg \alpha_k[c_\sigma/x_{i_\sigma}])) )$는 $T_\sigma$의 정리이고

일차논리 정리와 명제논리 정리로

$((\neg (( \neg (\forall x_{i_\sigma}) \alpha_\sigma) \to (\neg \alpha_\sigma[c_\sigma/x_{i_\sigma}])) ) \to (\neg (\forall x_{i_\sigma}) \alpha_\sigma))$와 $((\neg (( \neg (\forall x_{i_\sigma}) \alpha_\sigma) \to (\neg \alpha_\sigma[c_\sigma/x_{i_\sigma}])) ) \to \alpha_\sigma[c_\sigma/x_{i_\sigma}])$가

일차논리의 정리이므로 형식계 정리와 전건긍정으로 $(\neg (\forall x_{i_\sigma}) \alpha_\sigma)$와 $\alpha_\sigma[c_\sigma/x_{i_\sigma}]$는 $T_\sigma$의 정리이다.

$c_\sigma$의 정의로 $c_\sigma \in \mathcal{C}^+ \setminus \mathcal{C}$는 $T_\sigma = T \cup \{ \theta_\eta : \eta\in \sigma\}$의 모든 논리식에 포함되지 않으므로

$T_\sigma$로부터 $\alpha_\sigma[c_\sigma/x_{i_\sigma}]$의 증명에서 나온 $c_\sigma$를 포함하는 논리식은 $T_\sigma$의 원소가 아니고 공리나 추론규칙으로 유도되어

$c_\sigma$를 증명에 나오지 않은 변수기호 $y$로 치환가능하고 증명에 나온 모든 $c_\sigma$를 $y$로 치환하면

$\alpha_\sigma[y/x_{i_\sigma}]$는 $T_\sigma$의 정리이므로 일반화로 $(\forall y)\alpha_\sigma[y/x_{i_\sigma}]$는 $T_\sigma$의 정리이고

일차논리 정리와 형식계 정리로 $((\forall y)\alpha_\sigma[y/x_{i_\sigma}] \to (\forall x_{i_\sigma}) \alpha_\sigma)$가 $T_\sigma$의 정리이므로

전건긍정으로 $(\forall x_{i_\sigma}) \alpha_\sigma$가 $T_\sigma$의 정리이고 $T_\sigma$에 모순 $(\forall x_{i_\sigma}) \alpha_\sigma,$ $(\neg (\forall x_{i_\sigma}) \alpha_\sigma)$가 있게 되어

귀납가정인 $T_{\sigma}$가 무모순임에 모순이므로 $T_\lambda=T_{\sigma +1} = T_\sigma \cup \{ \theta_\sigma\}$는 무모순이다.

$\lambda$가 극한순서수일때 

$T_\lambda = T\cup \{ \theta_\sigma:\sigma \in \lambda\} = \displaystyle \bigcup_{\sigma \in \lambda} T_\sigma$이고 $\displaystyle \bigcup_{\sigma \in \lambda}T_\sigma$으로부터 논리식의 증명은 크기가 유한인 배열이므로

귀납가정으로 모든 $\sigma \in \lambda$에 대해 $T_\sigma = T\cup \{ \theta_\eta:\eta\in \sigma\}$가 무모순임에 따라 $\displaystyle T_\lambda=\bigcup_{\sigma \in \lambda}T_\sigma$도 무모순이다.

따라서 모든 $\lambda\in \kappa$에 대해 $T_\lambda = T\cup \{ \theta_\sigma :\sigma\in \lambda\}$는 무모순이므로 

$\displaystyle \bigcup_{\lambda\in \kappa}T_\lambda$도 무모순이 되어 위 정리로 $\displaystyle T\cup \{ \theta_\lambda : \lambda\in \kappa \} = \bigcup_{\lambda\in \kappa}T_\lambda \subseteq T^+$이고

모든 문장 $\phi \in W^+$에 대해 $\phi \in T^+$ 또는 $(\neg \phi) \in T^+$중 하나만 성립하는 무모순인 집합 $T^+$가 존재한다.

 

$\mathcal{L}^+$-항집합이 $X$일때 $V \subseteq X$가 변수기호를 갖지 않는 모든 항들의 집합이면

$\{ b_\lambda : \lambda\in \kappa \}\subseteq V$이므로 $V \ne \emptyset$이고 집합의 크기 정리와 위 정리로 $|V|\underline{\in} |X| \underline{\in} |\mathcal{L}^+| = \kappa = |\mathcal{L}|$이다.

임의의 $t,u \in V$에 대해

$E(t,u)$이기 위한 필요충분조건이 $T^+ \vdash (t = u)$인 이항관계 $E$는 일차논리 정리로 $V$의 동치관계이므로

$T^+$가 만족가능한 $\mathcal{L}^+$-구조 $\mathcal{M} = (M,f_\mathcal{M},R_\mathcal{M},c_\mathcal{M})$과 $\mathcal{M}$에 대한 항의 해석 $s : X \to M$를 다음과 같이 정의한다.

1. $\mathcal{M}$의 전체 $M$은 $E$에 대한 $V$의 몫집합 $M = V/E$로 정의한다.

2. 변수기호집합은 가부번이므로 추가된 상수기호집합 $\mathcal{C}^+\setminus \mathcal{C} = \{ b_\lambda :\lambda\in \kappa \}$에 대해

항의 해석 $s$는 변수기호 $x_i$의 첨수가 $i\in \mathbb{N}\underline{\in} \kappa$임에 따라 $E$에 대한 상수 $b_i$의 동치류 $s(x_i) = [b_i]_E$로 정의한다.

3. 상수기호 $c \in \mathcal{L}^+$에 대응되는 $\mathcal{M}$의 상수 $c_\mathcal{M}\in M$은 $E$에 대한 $c$의 동치류 $c_\mathcal{M} = [c]_E$로 정의한다.

4. 함수기호 $f \in \mathcal{L}$에 대응되는 $\mathcal{M}$의 $n_f$항함수 $f_\mathcal{M}$은

임의의 $[t_1]_E,\cdots, [t_{n_f}]_E \in M$에 대해 $f_\mathcal{M}([t_1]_E,\cdots,[t_{n_f}]_E) = \displaystyle \bigcup_{u_1 \in [t_1]_E}\cdots \bigcup_{u_{n_f}\in [t_{n_f}]_E} [f(u_1,\cdots,u_{n_f})]_E$로 정의한다.

5. 관계기호 $R \in \mathcal{L}$에 대응되는 $\mathcal{M}$의 $n_R$항관계 $R_\mathcal{M}$은

임의의 $[t_1]_E,\cdots, [t_{n_R}]_E \in M$에 대해 $R_\mathcal{M}([t_1]_E,\cdots,[t_{n_R}]_E)$이기 위한 필요충분조건이

모든 $u_1 \in [t_1]_E ,\cdots, u_{n_R}\in [t_{n_R}]_E$에 대해 $T^+ \vdash R(u_1,\cdots,u_{n_R})$인 것이다.

 

항집합의 구성인 집합열이 $X_0,X_1,\cdots \subseteq X$일때 모든 $n \in \mathbb{N}$에 대해

임의의 항 $t \in \displaystyle \bigcup_{i = 0}^nX_i$가 $t \in V$이면 $\mathcal{M}$에 대한 항의 해석 $s$에 대해 $s(t) = [t]_E$임을 귀납법으로 보인다.

$n=0$일때 $t \in X_0$가 $t \in V$이면 $t = c$인 상수기호이므로 

항의 해석 정의로 $c \in \mathcal{L}^+$에 대응되는 상수 $c_\mathcal{M} \in M$에 대해 $s(c) = c_\mathcal{M} = [c]_E $이다.

모든 $k \in \mathbb{N}$에 대해 $t \in \displaystyle \bigcup_{i = 0}^kX_i$가 $t \in V$이면 $s(t) = [t]_E$일때

 $t \in \displaystyle \bigcup_{i = 0}^{k+1}X_i$는 $t \in \displaystyle \bigcup_{i = 0}^{k}X_i$이거나 $t \in X_{k+1}$이므로 $t \in \displaystyle \bigcup_{i = 0}^{k}X_i$이면 귀납가정으로 $t \in V$일때 $s(t) = [t]_E$이고

$t \in X_{k+1}$가 $t \in V$이면 어떤 함수기호 $f \in \mathcal{L}$와 어떤 $t_1,\cdots,t_{n_f}\in \displaystyle \bigcup_{i = 0}^kX_i$에 대해

$t = f(t_1,\cdots,t_{n_f})$이고 $t$는 변수기호를 갖지 않으므로 $t_1,\cdots,t_{n_f}\in V$가 되어

$f $에 대응되는 $n_f$항함수 $f_\mathcal{M}$에 대해 일차논리 정리로 $t_1 \in [t_1]_E ,\cdots, t_{n_f} \in [t_{n_f}]_E$이고

$s(\,f(t_1,\cdots,t_{n_f})\,)=f_\mathcal{M}([t_1]_E,\cdots,[t_{n_f}]_E) = \displaystyle \bigcup_{u_1 \in [t_1]_E}\cdots \bigcup_{u_{n_f}\in [t_{n_f}]_E} [f(u_1,\cdots,u_{n_f})]_E = [f(t_1,\cdots,t_{n_f})]_E$이다.

따라서 모든 $n \in \mathbb{N}$에 대해 가정이 성립하고 $X = \displaystyle \bigcup_{i = 0}^\infty X_i$이므로 모든 $t \in X$에 대해 $t \in V$이면 $s(t) = [t]_E$이다.

 

논리식집합의 구성인 집합열이 $W_0^+,W_1^+,\cdots \subseteq W^+$이고 $s$에 대한 값매김이 $v_s : W^+ \to \{\mathbf{F},\mathbf{T}\}$일때

모든 $n \in \mathbb{N}$에 대해 $\phi\in \displaystyle \bigcup_{i = 0}^nW^+_i$가 문장이면 $ T^+$ $\vdash$ $\phi$이기 위한 필요충분조건이 $v_s(\phi) = \mathbf{T}$임을 귀납법으로 보인다.

$n = 0$일때 $\phi \in W^+_0$는 원자논리식이므로 $\phi$가 문장이면 $\phi$에 포함되는 항들은 모두 $V$에 속하여

$\phi \in W^+_0$가 어떤 관계기호 $R \in \mathcal{L}$와 어떤 $t_1,\cdots,t_{n_R}\in V$에 대해 $\phi = R(t_1,\cdots,t_{n_R})$이면

$T^+ \vdash R(t_1,\cdots,t_{n_R})$일때 일차논리 정리로 모든 $u_1 \in [t_1]_E ,\cdots, u_{n_R}\in [t_{n_R}]_E$에 대해 $T^+ \vdash R(u_1,\cdots,u_{n_R})$이므로

$R$에 대응되는 $n_R$항관계 $R_\mathcal{M}$에 대해 $R_\mathcal{M}([t_1]_E,\cdots,[t_{n_R}]_E)$이고

위에서 보인 것으로 $s(t_1) = [t_1]_E, \cdots, s(t_{n_R}) = [t_{n_R}]_E$이므로 $R_\mathcal{M}(s(t_1),\cdots,s(t_{n_R}))$이 되어

$v_s(\,R(t_1,\cdots,t_{n_R})\,) = \mathbf{T}$이다.

역으로 $v_s(\,R(t_1,\cdots,t_{n_R})\,) = \mathbf{T}$이면 모든 $u_1 \in [t_1]_E ,\cdots, u_{n_R}\in [t_{n_R}]_E$에 대해 $T^+ \vdash R(u_1,\cdots,u_{n_R})$이므로

일차논리 정리로 $t_1 \in [t_1]_E ,\cdots, t_{n_R}\in [t_{n_R}]_E$임에 따라 $T^+ \vdash R(t_1,\cdots,t_{n_R})$이다.

$\phi \in W^+_0$가 어떤 $t_1,t_{2}\in V$에 대해 $\phi = (t_1 = t_2)$이면

$T^+ \vdash (t_1 = t_2)$일때 $E(t_1,t_2)$이므로 동치류 정리와 위에서 보인 것으로 $s(t_1) =[t_1]_E =[t_2]_E = s(t_2)$가 되어

$v_s(\,(t_1=t_{2})\,) = \mathbf{T}$이다.

역으로 $v_s(\,(t_1=t_{2})\,) = \mathbf{T}$이면 $[t_1]_E = s(t_1) = s(t_2) =[t_2]_E $이므로 동치류 정리로 $T^+ \vdash (t_1 = t_2)$이다.

모든 $k \in \mathbb{N}$에 대해 문장 $\phi\in \displaystyle \bigcup_{i = 0}^kW^+_i$가 $T^+ \vdash \phi$이기 위한 필요충분조건이 $v_s(\phi) = \mathbf{T}$일때

문장 $\phi\in \displaystyle \bigcup_{i = 0}^{k+1}W^+_i$가 $\phi\in \displaystyle \bigcup_{i = 0}^{k}W^+_i$이면 귀납가정으로 $T^+ \vdash \phi$와 $v_s(\phi) = \mathbf{T}$가 동치이다.

문장 $\phi\in \displaystyle \bigcup_{i = 0}^{k+1}W^+_i$가 $\phi \in W^+_{k+1}$이면

어떤 $\psi,\theta\in \displaystyle \bigcup_{i = 0}^{k}W^+_i$와 어떤 변수기호 $x$에 대해 $\phi = (\neg \psi)$ 또는 $\phi = (\psi \to \theta)$ 또는 $\phi = (\forall x)\psi$이므로

$\phi = (\neg \psi)$일때 

$T^+ \vdash (\neg \psi)$이면 $T^+$가 무모순임에 따라 $\psi$는 $T^+$의 정리가 아니므로

귀납가정으로 $v_s(\psi) = \mathbf{F}$가 되어 값매김 정리와 불 대수 정리로 $v_s(\,(\neg \psi)\,) = \neg v_s(\psi) = \neg \mathbf{F} = \mathbf{T}$이다.

역으로 $v_s(\,(\neg \psi)\,) = \mathbf{T}$이면

값매김 정리와 불 대수 정리로 $v_s(\psi) = \neg (\neg v_s(\psi)) = \neg v_s(\,(\neg \psi)\,) = \neg \mathbf{T} = \mathbf{F}$가 되어

귀납가정으로 $\psi$는 $T^+$의 정리가 아니고 $T^+$의 정의로 $\psi \in T^+$ 또는 $(\neg \psi) \in T^+$인데

$\psi \in T^+$이면 모순이므로 $(\neg \psi) \in T^+$가 되어 $T^+ \vdash (\neg \psi)$이다.

$\phi = (\psi \to \theta)$일때

$T^+ \vdash (\psi\to \theta)$이고 $v_s(\,(\psi \to \theta)\,) = \mathbf{F}$라고 가정하면

값매김 정리와 불 대수 정의로 $\mathbf{F}= v_s(\,(\psi \to \theta)\,)= v_s(\psi) \to v_s(\theta) = \neg v_s(\psi) \lor v_s(\theta)$가 되어

$v_s(\psi) = \mathbf{T}$이고 $v_s( \theta) = \mathbf{F}$이므로 귀납가정으로 $\psi$는 $T^+$의 정리이고 $\theta$는 $T^+$의 정리가 아니다.

$T^+$의 정의에 모순이 되지 않도록 $(\neg \theta )\in T^+$가 되어 $\psi,(\neg \theta)$는 $T^+$의 정리이고

일차논리 정리와 명제논리 정리와 형식계 정리로 $(\psi \to ((\neg \theta) \to (\neg (\psi \to \theta))))$도 $T^+$의 정리이므로

전건긍정으로 $(\neg (\psi \to \theta))$는 $T^+$의 정리인데 $T^+ \vdash (\psi\to \theta)$를 가정하였으므로 $T^+$의 정의에 모순이 되어

$T^+ \vdash (\psi\to \theta)$이면 $v_s(\,(\psi \to \theta)\,) = \mathbf{T}$이다.

역으로 $v_s(\,(\psi \to \theta)\,) = \mathbf{T}$일때 $(\psi \to \theta)$가 $T^+$의 정리가 아니라고 가정하면

$T^+$의 정의에 모순이 되지 않도록 $(\neg (\psi \to \theta))\in T^+$가 되어 $(\neg (\psi \to \theta))$는 $T^+$의 정리이고

일차논리 정리와 명제논리 정리와 형식계 정리로 $((\neg (\psi \to \theta))\to \psi)$와 $((\neg (\psi \to \theta))\to (\neg \theta))$가 $T^+$의 정리가 되어

전건긍정으로 $\psi,(\neg \theta)$가 $T^+$의 정리이므로 귀납가정으로 $v_s(\psi) = \mathbf{T}$이고 $v_s(\theta) = \mathbf{F}$인데

값매김 정리와 불 대수 정의와 불 대수 정리로 $\mathbf{T}=v_s(\,(\psi \to \theta)\,) = v_s(\psi) \to v_s(\theta) = \neg \mathbf{T} \lor \mathbf{F} = \mathbf{F}$인 모순이 되어

$v_s(\,(\psi \to \theta)\,) = \mathbf{T}$이면 $T^+ \vdash (\psi \to \theta)$이다.

$x$가 $\psi$의 자유변수가 아니고 $\phi = (\forall x)\psi$일때

$T^+ \vdash (\forall x) \psi$이면 공리4와 전건긍정으로 $T^+\vdash \psi$이고 $x$가 $\psi$의 자유변수가 아니므로 $\psi$는 문장이 되어

귀납가정과 값매김 정리로 모든 $r \in M$에 대해 $v_{s[r/x]}(\psi) =v_s(\psi) = \mathbf{T}$이고 $v_s(\,(\forall x) \psi\,) = \mathbf{T}$이다.

역으로 $v_s(\,(\forall x) \psi\,) = \mathbf{T}$이면

값매김 정리로 $v_s(\psi) = \mathbf{T}$이고 $\psi$는 문장이므로 귀납가정으로 $T^+\vdash \psi$가 되어 일반화로 $T^+ \vdash (\forall x) \psi$이다.

$x$가 $\psi$의 자유변수이고 $\phi = (\forall x)\psi$일때

$\psi$는 하나의 자유변수만 갖는 논리식이므로 $x = x_{i_\lambda}$이고 $\psi = \alpha_\lambda\in A$인 $\lambda\in \kappa$가 존재하여

$v_s(\, (\forall x_{i_\lambda})\alpha_\lambda\,)  = v_s(\,(\forall x)\psi\,)= \mathbf{T}$이면 상수기호 $c_\lambda \in \mathcal{C}^+\setminus \mathcal{C}$에 대해 공리5의 $((\forall x_{i_\lambda}) \alpha_{\lambda} \to \alpha_\lambda[c_\lambda/x_{i_\lambda}])$는

일차논리 정리로 일차논리의 논리적 귀결이므로 $v_s(\, ((\forall x_{i_\lambda}) \alpha_{\lambda} \to \alpha_\lambda[c_\lambda/x_{i_\lambda}]) \,) = \mathbf{T}$가 되어

값매김 정리로 $v_s(\,(\forall x_{i_\lambda})\alpha_\lambda\,) \to v_s(\alpha_\lambda[c_\lambda/x_{i_\lambda}]) = v_s(\, ((\forall x_{i_\lambda}) \alpha_{\lambda} \to \alpha_\lambda[c_\lambda/x_{i_\lambda}]) \,) = \mathbf{T}$이므로

불 대수 정리로 $v_s(\alpha_\lambda[c_\lambda/x_{i_\lambda}]) = \mathbf{T}$이고 $\alpha_\lambda[c_\lambda/x_{i_\lambda}]$이 문장임에 따라 귀납가정으로 $T^+ \vdash \alpha_\lambda[c_\lambda/x_{i_\lambda}]$이다.

문장 $(\forall x)\psi$가 $T^+$의 정리가 아니라고 가정하면 $ (\neg (\forall x)\psi)\in T^+$이므로 $T^+ \vdash (\neg (\forall x)\psi)$이고

위에서 보인 것으로 $\theta_\lambda= ((\neg (\forall x_{i_\lambda})\alpha_\lambda) \to (\neg \alpha_\lambda[c_\lambda/x_{i_\lambda}]))$는

$ ((\neg (\forall x_{i_\lambda})\alpha_\lambda) \to (\neg \alpha_\lambda[c_\lambda/x_{i_\lambda}])) \in T^+$이므로 $T^+ \vdash ((\neg (\forall x_{i_\lambda})\alpha_\lambda) \to (\neg \alpha_\lambda[c_\lambda/x_{i_\lambda}]))$가 되어

$(\neg(\forall x)\psi )=  (\neg (\forall x_{i_\lambda}) \alpha_\lambda)$로 $T^+ \vdash (\neg (\forall x_{i_\lambda})\alpha_\lambda)$에 대해 전건긍정으로 $T^+ \vdash (\neg \alpha_\lambda[c_\lambda/x_{i_\lambda}])$인데

$\alpha_\lambda[c_\lambda/x_{i_\lambda}], (\neg \alpha_\lambda[c_\lambda/x_{i_\lambda}])$가 $T^+$의 정리이므로 $T^+$가 무모순임에 모순이 되어 $T^+ \vdash (\forall x)\psi$이다.

역으로 $T^+ \vdash (\forall x)\psi$일때 $v_s(\,(\forall x) \psi\,) = \mathbf{F}$라고 가정하면

$(\forall x)\psi = (\forall x_{i_\lambda}) \alpha_\lambda$로 $v_s(\, (\forall x_{i_\lambda}) \alpha_\lambda\,) = \mathbf{F}$이므로 값매김 정리로 $v_{s[r/x_{i_\lambda}]}(\alpha_\lambda) = \mathbf{F}$인 $r \in M = V/E$이 존재하고

$r$은 $E$에 대한 동치류이므로 $r = [t]_E$인 $t \in V$가 존재하여 위에서 보인 것처럼 $s(t) = [t]_E =r$이다.

$t\in V$는 변수기호를 갖지 않으므로 $\alpha_\lambda$에서 $x_{i_\lambda}$을 $t$로 치환가능하여 $\alpha_\lambda[t/x_{i_\lambda}]$은 문장이고

논리식집합의 구성은 $\neg , \to ,\forall$에 따라 구성되어 $\alpha_\lambda = \psi \in \displaystyle \bigcup_{i = 0}^{k}W^+_i$에 대해 $\alpha_\lambda[t/x_{i_\lambda}]\in \displaystyle \bigcup_{i = 0}^{k}W^+_i$이므로

값매김 정리로 $\mathbf{F} =v_{s[s(t)/x_{i_\lambda}]}(\alpha_\lambda) = v_s(\alpha_\lambda[t/x_{i_\lambda}])$에 대해

귀납가정으로 $\alpha_\lambda[t/x_{i_\lambda}]$은 $T^+$의 정리가 아니고 $(\neg \alpha_\lambda[t/x_{i_\lambda}]) \in T^+$이므로 $T^+ \vdash (\neg \alpha_\lambda[t/x_{i_\lambda}])$이다.

하지만 $T^+ \vdash (\forall x_{i_\lambda}) \alpha_\lambda$이고 공리5와 전건긍정으로 $T^+ \vdash \alpha_\lambda[t/x_{i_\lambda}]$이므로 $T^+$가 무모순임에 모순이 되어

$T^+ \vdash (\forall x)\psi$이면 $v_s(\,(\forall x) \psi\,) = \mathbf{T}$이다.

따라서 모든 $n \in \mathbb{N}$에 대해 가정이 성립하고 $W^+ = \displaystyle \bigcup_{i = 0}^\infty W^+_i$이므로

임의의 $\phi\in W^+$가 문장이면 $T^+$ $\vdash$ $\phi$이기 위한 필요충분조건은 $v_s(\phi) = \mathbf{T}$가 되어

$\mathcal{L} \subseteq \mathcal{L}^+$인 $\mathcal{L}^+$-구조 $\mathcal{M}$의 전체 $M$은 그대로 두고 상수기호에 대한 해석만 제한하여 $\mathcal{M}$을 $\mathcal{L}$-구조로 정의할때

$s$에 대한 값매김 $v_s$에 대해 모든 문장 $\phi \in T \subseteq T^+$는 $T^+ \vdash \phi$이므로 $v_s(\phi) = \mathbf{T}$가 되어

무모순인 $\mathcal{L}$-이론 $T$는 언어가 $\mathcal{L}$인 일차논리에서 만족가능하다.

 

 

 

정리7(일차논리의 완전성[completeness])

임의의 언어 $\mathcal{L}$에 대해 $\mathcal{L}$-일차논리의 논리식집합 $W$와 임의의 $\mathcal{L}$-이론 $T\subseteq W$에 대해

임의의 문장 $\phi \in W$가 $T \models \phi$이면 $T \vdash \phi$이다.

증명

임의의 문장 $\phi \in W$에 대해 $T \models \phi$이면 형식계 정리로 $T \cup \{ (\neg \phi) \} \models \phi$이므로

모든 $\sigma \in T \cup \{ (\neg \phi) \}$에 대해 $v(\sigma) =\mathbf{T}$인 모든 값매김 $v$가 $v(\phi) = \mathbf{T}$인데

값매김 정리와 불 대수 정리로 $ \mathbf{T} = v(\,(\neg \phi)\,) = \neg v(\phi) = \neg \mathbf{T} = \mathbf{F}$가 되어

불 대수 정의에 모순이므로 $T \cup \{ (\neg \phi) \}$는 $\mathcal{L}$-일차논리에서 만족가능하지 않다.

따라서 위 정리의 대우로 $T \cup \{ (\neg \phi) \}$에는 모순이 있어

어떤 논리식 $\psi \in W$에 대해 $\psi ,(\neg \psi)$가 $T \cup \{ (\neg \phi) \}$의 정리이고 $\phi$가 문장이므로

일차논리 정리로 $((\neg \phi) \to \psi), ((\neg \phi) \to (\neg \psi))$는 $T$의 정리이고

일차논리 정리와 명제논리 정리와 형식계 정리로

$T\vdash (((\neg \phi) \to \psi) \to (((\neg \phi) \to (\neg \psi)) \to \phi))$가 되어 전건긍정으로 $T \vdash \phi$이다.

 

 

 

정리8

임의의 언어 $\mathcal{L}$에 대해 $\mathcal{L}$-일차논리의 논리식집합이 $W$일때

임의의 논리식 $\phi \in W$가 $\mathcal{L}$-일차논리의 논리적 귀결이기 위한 필요충분조건은 $\phi$가 $\mathcal{L}$-일차논리의 정리인 것이다.

증명

$\vdash \phi$일때 $\models \phi$임은 건전성으로 성립한다.

역으로 $\phi$가 $\models \phi$일때 $\phi$가 문장이면 완전성으로 $\vdash \phi$이다.

$\models \phi$인 $\phi$가 문장이 아닐때 자유변수 $x_1,x_2,\cdots,x_n$을 가지면 모든 $\mathcal{L}$-구조 $\mathcal{M}$에 대해 $\mathcal{M} \models \phi$이고

일차논리 정리로 $\mathcal{M} \models (\forall x_1)(\forall x_2)\cdots (\forall x_n)\phi$이므로 $\models (\forall x_1)(\forall x_2)\cdots (\forall x_n)\phi$이다.

$\theta = (\forall x_1)(\forall x_2)\cdots (\forall x_n)\phi$로 둘때 $\models \theta$이므로 형식계 정리로 $\{(\neg \theta)\}\models \theta$가 되어

$v(\, (\neg \theta)\,) =\mathbf{T}$인 모든 값매김 $v$가 $v(\theta) = \mathbf{T}$인데

값매김 정리와 불 대수 정리로 $ \mathbf{T} = v(\,(\neg \theta)\,) = \neg v(\theta) = \neg \mathbf{T} = \mathbf{F}$가 되어

불 대수 정의에 모순이므로 $ \{ (\neg \theta) \}$는 $\mathcal{L}$-일차논리에서 만족가능하지 않다.

따라서 위 정리의 대우로 $\{ (\neg \theta) \}$에는 모순이 있어

어떤 논리식 $\psi \in W$에 대해 $\psi ,(\neg \psi)$가 $ \{ (\neg \theta) \}$의 정리이고 $\theta$가 문장이므로

일차논리 정리로 $((\neg \theta) \to \psi), ((\neg \theta) \to (\neg \psi))$는 $\mathcal{L}$-일차논리의 정리이고

일차논리 정리와 명제논리 정리로 $\vdash (((\neg \theta) \to \psi) \to (((\neg \theta) \to (\neg \psi)) \to \theta))$가 되어

전건긍정으로 $ \vdash \theta$이므로 $\vdash (\forall x_1)(\forall x_2)\cdots (\forall x_n)\phi$이고 일차논리 정리로 $\vdash \phi$이다.

 

 

 

정리9(일차논리의 콤팩트성[compactness])

임의의 언어 $\mathcal{L}$에 대해 $\mathcal{L}$-일차논리의 논리식집합 $W$와 임의의 $\mathcal{L}$-이론 $T \subseteq W$에 대해 

$T$의 유한인 모든 부분집합이 $\mathcal{L}$-일차논리에서 만족가능하면 $T$도 $\mathcal{L}$-일차논리에서 만족가능하다.

증명

$T$의 유한인 모든 부분집합은 $\mathcal{L}$-일차논리에서 만족가능하므로 일차논리 정리로 무모순이다.

귀류법으로 $T$가 만족가능하지 않다고 가정하면

위 정리의 대우로 $T$에는 모순이 있어 어떤 $\psi \in W$에 대해 $\psi ,(\neg \psi)$가 $T$의 정리인데

$T$로부터 $\psi, (\neg \psi)$의 증명은 각각 크기가 유한인 배열이므로 증명에 사용된 $\psi,(\neg \psi)$의 가정도 유한 개가 되어

증명에 사용된 $\psi,(\neg \psi)$의 가정을 모두 포함하는 유한인 부분집합 $\Gamma \subseteq T$가 존재하므로

$\psi, (\neg \psi)$는 $\Gamma$의 정리가 되고 $\Gamma$가 무모순이라는 가정에 모순이므로 $T$는 무모순이다.

 

 

 

정리10

임의의 집합 $S$의 동치관계 $\mathcal{R}$에 대한 몫집합 $S/\mathcal{R}$의 크기는 $|S/\mathcal{R}|$ $\underline{\in}$ $|S|$이다.

증명

임의의 $A\in S/\mathcal{R}$는 동치관계 정리와 분할의 정의로 $A\subseteq S$이고 $A\ne \emptyset$이므로 어떤 $a \in A$가 존재하여

선택정리로 $f(A) = a\in A\subseteq S$인 함수 $f:S/\mathcal{R}\to S$가 존재한다.

$A\ne B$인 임의의 $A,B\in S/\mathcal{R}$에 대해 $f(A)\in A$이고 $f(B)\in B$이므로

동치관계 정리와 분할의 정의로 $A\cap B= \emptyset$임에 따라 $f(A) \ne f(B)$가 되어 단사 정리로 $f$는 단사이다.

따라서 집합의 크기 정리로 $|S/\mathcal{R}|\underline{\in} |S|$이다.

 

 

 

정리11(뢰벤하임-스콜렘[Löwenheim-Skolem] 정리)

임의의 언어 $\mathcal{L}$에 대해 $\mathcal{L}$-일차논리의 논리식집합 $W$와 임의의 $\mathcal{L}$-이론 $T \subseteq W$에 대해 

$\mathcal{N} $ $\models$ $T$인 $\mathcal{L}$-구조 $\mathcal{N}$이 존재하면 $\mathcal{M} \models T$가 되는 $\mathcal{L}$-구조 $\mathcal{M} = (M,f_\mathcal{M},R_\mathcal{M},c_\mathcal{M})$이 존재한다.

이때 $\mathcal{M}$의 전체 $M$에 대해 $\mathcal{L}$이 유한이면 $M$은 가산이고 $\mathcal{L}$이 무한이면 $M$의 크기는 $|M|$ $\underline{\in}$ $|\mathcal{L}|$이다.

증명

$\mathcal{L}$이 유한이면 $\mathcal{L}$은 가산이므로 가산 뢰베하임-스콜렘 정리로 정리가 성립한다.

$\mathcal{L}$이 무한일때

$\mathcal{N} \models T$이면 $\mathcal{N}$의 모든 값매김 $v_\mathcal{N}$에 대해 모든 $\phi \in T$가 $v_\mathcal{N}(\phi) = \mathbf{T}$이므로

$T$는 $\mathcal{L}$-일차논리에서 만족가능하여 일차논리 정리로 $T$는 무모순이다.

위 정리에 나온 $\mathcal{L}$-구조 $\mathcal{M} = (M,f_\mathcal{M},R_\mathcal{M},c_\mathcal{M})$과 $\mathcal{M}$에 대한 항의 해석 $s$와 $s$에 대한 값매김 $v_s$에 대해

모든 $\phi \in T$가 $v_s(\phi) = \mathbf{T}$이고 $\phi$는 문장이므로

값매김 정리로 $\mathcal{M}$의 모든 값매김 $v_\mathcal{M}$에 대해 $v_\mathcal{M}(\phi) = v_s(\phi)= \mathbf{T}$가 되어 $\mathcal{M} \models T$이고

$\mathcal{M}$의 전체 $M$의 정의와 위 정리로 $|M| \underline{\in} |\mathcal{L}|$이다.

 

 

 

정리12

체 $(F,+_{F},\cdot_{F},0_F,1_F)$위의 벡터공간 $(V,+_V,\cdot,\vec{0})$가 $V\ne \{\vec{0}\}$일때

임의의 $\beta\subseteq V$에 대해 $\beta $가 $(V,+_V,\cdot,\vec{0})$의 기저이기 위한 필요충분조건은

모든 $v \in V\setminus \{ \vec{0}\}$에 대해 양의 정수 $n_v\in \mathbb{Z}^+$가 유일하게 존재하여 $v = a_{1}\cdot u_1 +_V \cdots +_V a_{n_v} \cdot u_{n_v}$인

$a_{1},\cdots,a_{n_v} \in F\setminus \{ 0_F\}$와 서로 다른 $u_1,\cdots,u_{n_v}\in \beta$가 유일하게 존재하는 것이다.

증명

$\beta $가 $(V,+_V,\cdot,\vec{0})$의 기저이면

기저의 정의로 $\underset{(V,+_V,\cdot,\vec{0})}{\operatorname{span}(\beta)} = V$이므로 모든 $v \in V\setminus \{ \vec{0}\} \subseteq V = \underset{(V,+_V,\cdot,\vec{0})}{\operatorname{span}(\beta)}$에 대해

생성집합의 정의와 벡터공간의 정의로 어떤 $n\in \mathbb{Z}^+$이 존재하여

$v = a_{1}\cdot u_1 +_V \cdots +_V a_{n} \cdot u_{n}$인 $a_{1},\cdots,a_{n} \in F\setminus \{ 0_F\}$와 서로 다른 $u_1,\cdots,u_{n}\in \beta$이 존재한다.

어떤 $m \in \mathbb{Z}^+$과 $b_{1},\cdots,b_{m} \in F\setminus \{ 0_F\}$와 서로 다른 $w_1,\cdots,w_{m}\in \beta$에 대해

$a_{1}\cdot u_1 +_V \cdots +_V a_{n} \cdot u_{n} = v = b_1\cdot w_1 +_V \cdots +_V b_m\cdot w_m$이라고 가정할때 $\{u_1,\cdots,u_{n} \}\ne \{ w_1,\cdots, w_m\}$이면 

기저의 정의로 $\beta $는 $(V,+_V,\cdot,\vec{0})$에서 일차독립이므로

일차독립 정리로 $\{u_1,\cdots,u_{n} \}\cup \{ w_1,\cdots, w_m\} \subseteq \beta$은 $(V,+_V,\cdot,\vec{0})$에서 일차독립이고

$a_{1}\cdot u_1 +_V \cdots +_V a_{n} \cdot u_{n}  - b_1\cdot w_1 - \cdots - b_m\cdot w_m = \vec{0}$인데

일차독립 정리로 $a_i = 0_F$인 $i = 1,2,\cdots, n$가 존재하거나 $b_j = 0_F$인 $j= 1,2,\cdots, m$가 존재하여 모순이므로

$\{u_1,\cdots,u_{n} \} = \{ w_1,\cdots, w_m\}$이고 $n = m$이다.

또 $a_{1}\cdot u_1 +_V \cdots +_V a_{n} \cdot u_{n} = v = b_1\cdot u_1 +_V\cdot +_V b_n\cdot u_n$이라고 가정하면

$(a_{1}-b_1)\cdot u_1 +_V \cdots +_V (a_{n}-b_n) \cdot u_{n} = \vec{0}$이므로 $\beta$가 $(V,+_V,\cdot,\vec{0})$에서 일차독립임에 따라

일차독립 정리로 $a_1 - b_1 = \cdots = a_n - b_n = 0_F$가 되어 모든 $i=1,2,\cdots,n$에 대해 $a_i = b_i$이다.

역으로 모든 $v \in V\setminus \{ \vec{0}\}$에 대해 $n_v\in \mathbb{Z}^+$가 유일하게 존재하여

$v = a_{1}\cdot u_1 +_V \cdots +_V a_{n_v} \cdot u_{n_v}$인 $a_{1},\cdots,a_{n_v} \in F\setminus \{ 0_F\}$와 서로 다른 $u_1,\cdots,u_{n_v}\in \beta$가 유일하게 존재하면

생성집합의 정의로 $V \setminus \{ \vec{0}\}\subseteq \underset{(V,+_V,\cdot,\vec{0})}{\operatorname{span}(\beta)}$이고 생성공간 정리로 $ \vec{0} \in \underset{(V,+_V,\cdot,\vec{0})}{\operatorname{span}(\beta)}\subseteq V$이므로

$V \subseteq \underset{(V,+_V,\cdot,\vec{0})}{\operatorname{span}(\beta)}$임에 따라 집합 정리로 $V = \underset{(V,+_V,\cdot,\vec{0})}{\operatorname{span}(\beta)}$이고

$V\ne \{\vec{0}\}$이므로 $v \in V\setminus \{ \vec{0}\}$가 존재하여 $v = a_{1}\cdot u_1 +_V \cdots +_V a_{n_v} \cdot u_{n_v}$이다.

귀납법으로 모든 $n\in \mathbb{Z}^+$에 대해 $\vec{0} = b_1\cdot w_1 +_V \cdots +_V b_n \cdot w_n$인

$b_1,\cdots,b_n\in F$과 서로 다른 $w_1,\cdots,w_n\in \beta$이 존재하면 $b_1 = \cdots = b_n = 0_F$임을 보인다.

$n = 1$일때 $\vec{0} = b_1\cdot w_1$인 $b_1\in F$와 $w_1\in \beta$에 대해 $v = v +_V\vec{0} = a_1\cdot u_1 +_V \cdots +_V a_{n_v}\cdot u_{n_v} +_V b_1\cdot w_1$이므로

$w_1 = u_j$인 $j= 1,2,\cdots,n_v$가 존재하면 $v  = a_1\cdot u_1 +_V \cdots +_V (a_j +_F b_1)\cdot u_j +_V \cdots +_V a_{n_v}\cdot u_{n_v}$인데

$a_j +_F b_1 = 0_F$라고 가정할때

$n_v = 1$이면 $j=1$이므로 $\vec{0} \ne v = (a_j +_F b_1)\cdot u_j = 0_F \cdot u_j = \vec{0}$이 되어 모순이고

$n_v > 1$이면 $n_v -1 \in \mathbb{Z}^+$이고 $v  = a_1\cdot u_1 +_V \cdots +_Va_{j-1}\cdot u_{j-1} +_V a_{j+1}\cdot u_{j+1} +_V \cdots +_V a_{n_v}\cdot u_{n_v}$이므로

$n_v\in \mathbb{Z}^+$가 유일하다는 가정에 모순이다.

$a_j +_F b_1 \ne 0_F$라고 가정할때 $a_j+_F b_1\in F\setminus \{ 0_F\}$이므로 $a_j +_F b_1 = a_j $가 되어 $b_1 = a_j - a_j = 0_F$이다.

모든 $j= 1,2,\cdots,n_v$에 대해 $w_1 \ne u_j$이면 $w_1 = \vec{0}$일때 $0_F\ne 1_F$이므로 $1_F\cdot w_1 = 1_F \cdot \vec{0} = \vec{0}$이 되어

$v = a_1\cdot u_1 +_V \cdots +_V a_{n_v}\cdot u_{n_v} +_V 1_F\cdot w_1$임에 따라 $n_v\in \mathbb{Z}^+$가 유일하다는 가정에 모순이다.

$w_1 \ne \vec{0}$일때 $b_1 \cdot w_1 = \vec{0}$인데

$b_1 \ne 0_F$이면 $\vec{0} \ne w_1=b_1^{-1}\cdot (b_1 \cdot w_1) = b_1^{-1}\cdot \vec{0} = \vec{0}$이 되어 모순임에 따라 $b_1 = 0_F$이다.

모든 $k\in \mathbb{Z}^+$에 대해 가정이 성립하고 $\vec{0} = b_1\cdot w_1 +_V \cdots +_V b_k \cdot w_k +_V b_{k+1}\cdot w_{k+1}$인

$b_1,\cdots,b_k,b_{k+1}\in F$과 서로 다른 $w_1,\cdots,w_k,w_{k+1}\in \beta$이 존재할때

$v = v +_V\vec{0} = a_1\cdot u_1 +_V \cdots +_V a_{n_v}\cdot u_{n_v} +_V b_1\cdot w_1 +_V\cdots +_Vb_k\cdot w_k +_V b_{k+1}\cdot w_{k+1}$이므로

$\vec{0} = b_1\cdot w_1 +_V \cdots +_V b_k \cdot w_k$이면 $\vec{0} = b_1\cdot w_1 +_V \cdots +_V b_k \cdot w_k +_V b_{k+1}\cdot w_{k+1} = b_{k+1}\cdot w_{k+1}$이 되어

$n= 1$일때처럼 $b_{k+1} = 0_F$이고 귀납가정으로 $b_1 = \cdots = b_k = 0_F$이다.

$\vec{0} \ne b_1\cdot w_1 +_V \cdots +_V b_k \cdot w_k$일때 $b_j = 0_F$인 $j = 1,2,\cdots, k$가 존재하면

$\begin{align*}\vec{0} & = b_1\cdot w_1 +_V \cdots +_V b_k\cdot w_k +_V b_{k+1}\cdot w_{k+1}= b_1\cdot w_1 +_V \cdots +_Vb_{j-1}\cdot w_{j-1} +_V b_{j+1}\cdot w_{j+1} +_V \cdots +_V b_{k}\cdot w_{k} +_V b_{k+1}\cdot w_{k+1} \text{ 이므로}\end{align*}$

귀납가정으로 $b_1=\cdots = b_{j-1} = b_{j+1} = \cdots =b_k =b_{k+1} = 0_F$가 되어

$\vec{0} \ne b_1\cdot w_1 +_V \cdots +_V b_k \cdot w_k = \vec{0}$임에 따라 모순이다.

모든 $j =1,2,\cdots, k$에 대해 $b_j \ne 0_F$이면 $\vec{0} \ne b_1\cdot w_1 +_V \cdots +_V b_k \cdot w_k = -b_{k+1}\cdot w_{k+1}$이 되어

$b_{k+1}\ne 0_F$임에 따라 $k = 1$과 $b_1 = -b_{k+1}$과 $w_1 = w_{k+1}$이 성립하는데 $w_1\ne w_{k+1}$이므로 모순이다.

따라서 모든 $n\in \mathbb{Z}^+$에 대해 $\vec{0} = b_1\cdot w_1 +_V \cdots +_V b_n \cdot w_n$인

$b_1,\cdots,b_n\in F$과 서로 다른 $w_1,\cdots,w_n\in \beta$이 존재하면 $b_1 = \cdots = b_n = 0_F$이므로

일차독립 정리로 $\beta$는 $(V,+_V,\cdot,\vec{0})$에서 일차독립이 되어 $\beta $는 $(V,+_V,\cdot,\vec{0})$의 기저이다.

 

 

 

정리13

체 $(F,+_{F},\cdot_{F},0_F,1_F)$위의 벡터공간 $(V,+,\cdot,\vec{0})$의 임의의 $S\subseteq T\subseteq V$에 대해

$S$가 $(V,+,\cdot,\vec{0})$에서 일차독립이고 $\underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(T)$ $ =V$이면 $S\subseteq \beta \subseteq T$인 $(V,+,\cdot,\vec{0})$의 기저 $\beta$가 존재한다.

증명

$V$의 멱집합 $\mathcal{P}(V)$에 대해

$\displaystyle \bigcap_{n = 1}^\infty \{ B \in \mathcal{P}(V) :  S\subseteq B \subseteq T \text{이고 } a_1\cdot u_1+\cdots + a_n\cdot u_n = \vec{0} \text{인 }  a_1,\cdots,a_n \in F \text{과 서로 다른 }u_1,\cdots,u_n \in B \text{이 존재하면 } a_1 = \cdots =a_n = 0_F\}$

위와 같은 $S$를 포함하고 $T$에 포함되는 $(V,+,\cdot,\vec{0})$에서 일차독립인 집합들의 집합족을 $\mathcal{F}$로 둘때

$S\subseteq T$이고 $S$는 $(V,+,\cdot,\vec{0})$에서 일차독립이므로 벡터공간 정리로 $S \in \mathcal{F}$가 되어 $\mathcal{F}$는 공집합이 아니다.

$\mathcal{F}$의 멱집합 $\mathcal{P}(\mathcal{F})$에 대해 $\mathbf{A} = \{ \mathcal{C} \in \mathcal{P}(\mathcal{F}) : \mathcal{C} \ne \emptyset \text{이고 부분순서집합 } (\mathcal{C},\subseteq)\text{가 전순서이다.}\}$를 정의하면

순서집합 정리로 $(\{ S\},\subseteq)$는 부분순서집합이고 전순서이므로 $\{ S\} \in \mathbf{A}$가 되어 $\mathbf{A}$는 공집합이 아니다.

임의의 $\mathcal{C} \in \mathbf{A}$에 대해 $(\mathcal{P}(V),\subseteq)$에서 $\mathcal{C}$의 상한은 순서집합 정리로 $\displaystyle \underset{(\mathcal{P}(V),\subseteq)}{\sup} \mathcal{C} = \bigcup \mathcal{C}= \bigcup_{B \in \mathcal{C}} B$이고

모든 $B \in \mathcal{C} \subseteq \mathcal{F}$는 $\mathcal{F}$의 정의로 $(V,+,\cdot,\vec{0})$에서 일차독립이고 $S \subseteq B \subseteq T$이므로 $S \subseteq \displaystyle \bigcup_{B \in \mathcal{C}}B \subseteq T $이다.

또 $ a_1\cdot u_1+\cdots + a_n\cdot u_n = \vec{0}$인 $n \in \mathbb{Z}^+$개의 $a_1,\cdots,a_n \in F$과 서로 다른 $u_1,\cdots,u_n \in \displaystyle \bigcup_{B \in \mathcal{C}}B$이 존재하면

모든 $i =1,2,\cdots, n $에 대해 $u_i \in B_i$인 $B_i \in \mathcal{C}$가 존재하고

$(\mathcal{C},\subseteq)$는 전순서이므로 순서집합 정리로 모든 $i =1,2,\cdots, n $에 대해 $B_i \subseteq B_k$인 $B_k \in \mathcal{C}$가 존재하여

$u_1,\cdots,u_n \in B_k \in \mathcal{F}$이므로 $\mathcal{F}$의 정의로 $a_1=\cdots = a_n = 0_F$가 되어 $\displaystyle \bigcup_{B \in \mathcal{C}}B$는 $(V,+,\cdot,\vec{0})$에서 일차독립이다.

따라서 모든 $\mathcal{C} \in \mathbf{A}$에 대해 $(\mathcal{F},\subseteq)$에서 $\mathcal{C}$의 상한은 $\displaystyle \underset{(\mathcal{F},\subseteq)}{\sup} \mathcal{C} = \bigcup_{B \in \mathcal{C}} B \in \mathcal{F}$이므로

순서집합 정리로 $(\mathcal{F},\subseteq)$에서 $\mathcal{F}$의 극대원소 $\beta \in \mathcal{F}$가 존재하여 $S \subseteq \beta \subseteq T$이고

$(V,+,\cdot,\vec{0})$에서 일차독립인 임의의 $B\subseteq T$가 $\beta \subseteq B$이면 $S\subseteq \beta \subseteq B \subseteq T$임에 따라

$B\in \mathcal{F}$가 되어 극대원소의 정의로 $\beta = B$이므로 $\beta$는 $(V,+,\cdot,\vec{0})$에서 일차독립인 $T$의 극대 부분집합이고

$\underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(T) = V$임에 따라 벡터공간 정리로 $\beta$는 $(V,+,\cdot,\vec{0})$의 기저이다.

 

 

 

정리14

체 $(F,+_{F},\cdot_{F},0_F,1_F)$위의 벡터공간 $(V,+,\cdot,\vec{0})$의 임의의 기저 $\beta$와

$(V,+,\cdot,\vec{0})$에서 일차독립인 임의의 $S\subseteq V$에 대해 어떤 $\beta_0 \subseteq \beta$이 존재하여 $S\cup \beta_0$은 $(V,+,\cdot,\vec{0})$의 기저이다.

증명

$\beta$의 멱집합 $\mathcal{P}(\beta)$에 대해 집합 $\mathcal{F} = \{ B\in \mathcal{P}(\beta) : S\cup B \text{ 가 }(V,+,\cdot,\vec{0})\text{에서 일차독립} \}$는

$\emptyset \subseteq \beta$이고 $S \cup \emptyset = S$가 $(V,+,\cdot,\vec{0})$에서 일차독립임에 따라 $\emptyset\in \mathcal{F}$이므로 $\mathcal{F}$는 공집합이 아니다.

$\mathcal{F}$의 멱집합 $\mathcal{P}(\mathcal{F})$에 대해 $\mathbf{A} = \{ \mathcal{C} \in \mathcal{P}(\mathcal{F}) : \mathcal{C} \ne \emptyset \text{이고 부분순서집합 } (\mathcal{C},\subseteq)\text{가 전순서이다.}\}$를 정의하면

순서집합 정리로 $(\{ \emptyset\},\subseteq)$는 부분순서집합이고 전순서이므로 $\{ \emptyset\} \in \mathbf{A}$가 되어 $\mathbf{A}$는 공집합이 아니다.

임의의 $\mathcal{C} \in \mathbf{A}$에 대해 $(\mathcal{P}(\beta),\subseteq)$에서 $\mathcal{C}$의 상한은 순서집합 정리로 $\displaystyle \underset{(\mathcal{P}(\beta),\subseteq)}{\sup} \mathcal{C} = \bigcup \mathcal{C}= \bigcup_{B \in \mathcal{C}} B$이고

모든 $B \in \mathcal{C} \subseteq \mathcal{F}$에 대해 $\mathcal{F}$의 정의로 $S\cup B$는 $(V,+,\cdot,\vec{0})$에서 일차독립이고 $B\subseteq \beta$이므로 $\displaystyle  \bigcup_{B \in \mathcal{C}} B\subseteq \beta$이다.

$ a_1\cdot u_1+\cdots + a_n\cdot u_n = \vec{0}$인 $n \in \mathbb{Z}^+$개의 $a_1,\cdots,a_n \in F$과 서로 다른 $u_1,\cdots,u_n \in \displaystyle S\cup \bigcup_{B \in \mathcal{C}}B$이 존재하면

$\mathcal{C}\ne \emptyset$이고 $\displaystyle S\cup \bigcup_{B \in \mathcal{C}}B = \bigcup_{B\in \mathcal{C}}(S\cup B)$임에 따라 모든 $i =1,2,\cdots, n $에 대해 $u_i \in S\cup B_i$인 $B_i \in \mathcal{C}$가 존재하고

$(\mathcal{C},\subseteq)$는 전순서이므로 순서집합 정리로 모든 $i =1,2,\cdots, n $에 대해 $B_i \subseteq B_k$인 $B_k \in \mathcal{C} \subseteq \mathcal{F}$가 존재하여

$u_1,\cdots,u_n \in S\cup B_k$임에 따라 $\mathcal{F}$의 정의와 일차독립 정리로 $a_1=\cdots = a_n = 0_F$이므로

$\displaystyle S\cup \bigcup_{B \in \mathcal{C}}B$는 $(V,+,\cdot,\vec{0})$에서 일차독립이다.

모든 $\mathcal{C} \in \mathbf{A}$에 대해 $(\mathcal{F},\subseteq)$에서 $\mathcal{C}$의 상한은 $\displaystyle \underset{(\mathcal{F},\subseteq)}{\sup} \mathcal{C} = \bigcup_{B \in \mathcal{C}} B \in \mathcal{F}$이므로

순서집합 정리로 $(\mathcal{F},\subseteq)$에서 $\mathcal{F}$의 극대원소 $\beta_0 \in \mathcal{F}$이 존재하여

$\beta_0\subseteq \beta$이고 $S \cup \beta_0$은 $(V,+,\cdot,\vec{0})$에서 일차독립이다.

$\underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(S\cup \beta_0) \ne V$라고 가정할때 생성공간 정리로 $\underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(S\cup \beta_0) \subset V$이므로

기저의 정의로 $v\notin \underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(S\cup \beta_0)$인 $v\in V = \underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(\beta) $가 존재하여 생성집합의 정의로 

어떤 $n\in \mathbb{Z}^+$에 대해 $v = a_1\cdot u_1 +\cdots + a_n\cdot u_n$인 $a_1,\cdots,a_n\in F$과 $u_1,\cdots,u_n\in \beta$이 존재하고

모든 $j = 1,2,\cdots,n$에 대해 $u_j\in \underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(S\cup \beta_0)$이면 생성공간 정리로 $v\in \underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(S\cup \beta_0)$임에 따라 모순이므로

$u_j\notin \underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(S\cup \beta_0)$인 $j= 1,2,\cdots, n$가 존재하여 $u_j\notin S\cup \beta_0$이고 $u_j \notin \beta_0$인데

일차독립 정리로 $S\cup \beta_0\cup \{u_j \}$가 $(V,+,\cdot,\vec{0})$에서 일차독립이고 $\beta_0 \cup \{ u_j\}\subseteq \beta$이므로

$\beta_0\cup \{u_j\}\in \mathcal{F}$가 되어 $\beta_0\subseteq \beta_0\cup \{ u_j\}$임에 따라 극대원소의 정의로 $u_j\in \beta_0\cup \{ u_j\} = \beta_0$이므로 모순이다.

따라서 $\underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(S\cup \beta_0) = V$이고 $S\cup \beta_0$은 $(V,+,\cdot,\vec{0})$에서 일차독립이므로 $S\cup \beta_0$은 $(V,+,\cdot,\vec{0})$의 기저이다.

 

 

 

정리15

체 $(F,+_{F},\cdot_{F},0_F,1_F)$위의 벡터공간 $(V,+,\cdot,\vec{0})$의 모든 기저 $\beta,\gamma$의 크기는 $|\beta| = |\gamma|$이다.

증명

$\beta$ 또는 $\gamma$가 유한집합이면 집합의 크기 정리와 벡터공간 정리로 $|\beta| = |\gamma|$이다.

$\beta,\gamma$가 무한집합이면 위 정리로 $|\beta|, |\gamma|$은 무한집합이고 

기수 정리와 극한순서수 정리로 자연수집합 $\mathbb{N}$에 대해 $\mathbb{N}\underline{\in} |\beta|$와 $\mathbb{N}\underline{\in} |\gamma|$가 성립한다.

$\gamma$의 멱집합 $\mathcal{P}(\gamma)$와 임의의 $v\in V\setminus \{ \vec{0}\}$에 대해

$\displaystyle \bigcup \left (\bigcup_{n=1}^\infty\{ S \in \mathcal{P}(\gamma) : \text{ 어떤 전단사함수 }f:\{ 1,\cdots,n\}\to S\text{와 어떤 } (a_1,\cdots, a_n)\in (F\setminus \{0_F\})^n\text{에 대해 } v = a_1\cdot f(1) +\cdots+ a_n\cdot f(n) \} \right )$

위와 같이 정의되는 집합 $S_\gamma(v)$는 $\gamma \subseteq V$이고 $\gamma$가 무한집합임에 따라 $V\ne \{ \vec{0}\}$이므로

위 정리로 어떤 유일한 $n_v\in \mathbb{Z}^+$가 존재하여 $S_\gamma(v) = \{ u_1,\cdots, u_{n_v}\}\subseteq \gamma$인 $n_v$개의 원소를 같는 유한집합이다.

기저의 정의로 $\gamma$는 $(V,+,\cdot,\vec{0})$에서 일차독립이고 일차독립 정리로 $\gamma \subseteq V\setminus \{ \vec{0}\}$이므로

위 정리로 모든 $w \in \gamma$에 대해 어떤 유일한 $m_w\in \mathbb{Z}^+$가 존재하여

$w = b_1\cdot v_1 + \cdots +b_{m_w}\cdot v_{m_w}$인 $b_1,\cdots,b_{m_w}\in F\setminus \{ 0_F\}$와 $v_1,\cdots,v_{m_w}\in \beta$가 존재하는데

$w\notin S_\gamma(v_1)\cup \cdots \cup S_\gamma(v_{m_w})$라고 가정할때 $w \in \underset{(V,+,\cdot,\vec{0})}{\operatorname{span}}(S_\gamma(v_1)\cup \cdots \cup S_\gamma(v_{m_w}))$이므로

일차종속 정리로 $S_\gamma(v_1)\cup \cdots \cup S_\gamma(v_{m_w})\cup \{ w\}\subseteq \gamma$가 $(V,+,\cdot,\vec{0})$에서 일차종속이 되어 일차독립 정리에 모순이다.

따라서 $w\in S_\gamma(v_1)\cup \cdots \cup S_\gamma(v_{m_w}) \subseteq \displaystyle \bigcup_{v\in \beta}S_\gamma(v)$이므로 $\gamma \subseteq \displaystyle \bigcup_{v\in \beta}S_\gamma(v)$가 되어 

집합의 크기 정리와 집합의 크기 정리와 자연수집합 정리와 기수 곱셈의 정의와 기수 정리로

$\begin{align*}|\gamma| & \underline{\in}\left |\bigcup_{v\in \beta}S_\gamma(v)\right | \underline{\in} \left| \bigcup_{v\in \beta} (\{ v\}\times S_\gamma(v))\right| = \left | \bigcup_{v\in \beta} (\{ v\}\times n_v)\right | \underline{\in} \left | \bigcup_{v\in \beta} (\{v\}\times \mathbb{N})\right | = |\beta \times \mathbb{N}| = ||\beta|\times \mathbb{N}| = |\beta|\otimes \mathbb{N} = |\beta| \text{ 이고}\end{align*}$

비슷하게 $|\beta|\underline{\in}|\gamma|$이므로 $(V,+,\cdot,\vec{0})$의 모든 기저 $\beta,\gamma$는 $|\beta| = |\gamma|$이다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/106#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/106#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

Peter J. Cameron - Sets, Logics and Categories - 9791196120375

A. G. Hamilton - Logic for Mathematicians - 9780521368650

Herbert B. Enderton - A Mathematical Introduction to Logic - 9780122384523

Stephen H. Friedberg - Linear Algebra - 9780134860244