집합론의 언어
집합론의 언어 \(\mathcal{L}\)이란 일차술어논리(FOPC; first order predicate calculus)에 이항관계기호 ‘∈’이 추가된 것이다. 여기서 이항관계기호 ‘∈’는 집합(set)이라고 불리는 두 대상 \(x\)와 \(X\) 사이의 ‘원소 관계’ \(x\in X\)를 나타낸다. 이로써 언어 \(\mathcal{L}\)은 다음과 같은 기호로 구성된 언어이다.
- 논리외적기호 ‘∈’
- 논리기호 ‘∧’, ‘∨’, ‘￢’, ‘→’, ‘∀’, ‘∃’, ‘＝’
- 괄호 ‘(’, ‘)’
- 가산 개의 변수 기호
여기서 한정기호 ‘∀’과 ‘∃’는 각각 “모든 …에 대하여”, “적당한 …에 대하여”를 나타내며, 모든 집합을 그 범위로 취한다.
\(\mathcal{L}\)에서 유의미하게 결합된 문자열을 논리식(formula)이라고 부른다. 즉 논리식이란 다음과 같이 귀납적으로 정의된다.
- 변수 \(x,\) \(y\)에 대하여 두 식 \((x\in y)\)와 \((x=y)\)를 아톰논리식(atom formula)이라고 부른다. 아톰논리식은 논리식이다.
- \(\phi\)가 논리식이면 \((\neg\phi)\)는 논리식이다.
- \(\phi\)와 \(\psi\)가 논리식이면 \((\phi\wedge\psi),\) \((\phi\vee\psi),\) \((\phi\rightarrow\psi)\)는 모두 논리식이다.
- \(\phi\)가 논리식이고 \(x\)가 \(\phi\)의 변수이면 \(\forall x \phi\)와 \(\exists x \phi \)는 논리식이다.
- 논리식은 여기서 나열한 과정을 하나 이상 적용하여 얻어지는 것뿐이다.
논리식에 포함된 변수가 한정기호에 의하여 제한될 때, 그 변수를 종속변수(bounded variable)라고 부른다. 종속변수가 아닌 변수를 자율변수(free variable)라고 부른다.
논리식 \((\phi\rightarrow\psi)\)와 논리식 \(((\neg \phi)\vee\psi)\)가 논리적으로 동치인 것으로 정의한다. 즉 논리식 \((\phi\rightarrow\psi)\)은 “\(\phi\)가 참이고 \(\psi\)가 거짓인 경우”가 존재하지 않는 한 참이다. 편의상 \((\phi\rightarrow\psi)\)와 \((\psi\leftarrow\phi)\)가 논리적 동치인 것으로 정의한다. 또한 \[((\phi\rightarrow\psi)\wedge(\psi\rightarrow\phi))\] 를 간단히 \((\phi\leftrightarrow\psi)\)로 나타낸다.
집합론에서 다루는 대부분의 진술은 \(\mathcal{L}\)을 사용하여 형식적으로(formally) 표현할 수 있다. 하지만 모든 진술을 \(\mathcal{L}\)만을 사용하여 표현하는 것은 지루하므로, 특별히 필요하지 않는 한 집합론에서 명제를 진술할 때 일상적인 수학의 표현을 사용한다. 형식언어는 모순을 피하기 위하여 집합론의 공리를 정확하게 진술할 때 사용된다.
부분집합
편의를 위하여 다음과 같은 부분집합 기호를 도입한다. 즉 \(y\)와 \(z\)가 \(\mathcal{L}\)의 변수일 때, \[\forall x ( x\in y \rightarrow x\in z)\] 를 “\(y\subseteq z\)”로 나타낸다. 이 논리식은 “\(y\)가 \(z\)의 부분집합(subset)이다”라고 읽는다.
집합의 상등
이제 집합론에서 사용할 기본 개념을 정의하기 위한 공리를 살펴 보자.
ZF1. 외연 공리; The axiom of extensionality.
두 집합이 서로 같기 위한 필요충분조건은 두 집합이 서로 같은 원소를 갖는 것이다.
외연 공리를 논리식으로 나타내면 다음과 같다. \[\forall x \forall y ((x=y)\leftrightarrow \forall z ( z\in x \leftrightarrow z\in y))\]
공집합
ZF2. 공집합 공리; Null set axiom.
원소를 갖지 않는 집합이 존재한다.
공집합 공리를 논리식으로 나타내면 다음과 같다. \[\exists x \forall y (\neg (y\in x))\] 편의상 \((\neg(y\in x))\)를 \((y\notin x)\)로 나타내자. 그러면 위 식은 다음과 같이 쓸 수 있다. \[\exists x \forall y (y\notin x)\]
정리 1. 원소를 갖지 않는 집합이 유일하게 존재한다.
정리 1을 논리식으로 나타내면 다음과 같다. \[\begin{gather} [\forall x \forall y ((x=y) \leftrightarrow \forall z ( z \in x \leftrightarrow z \in y )) \wedge \exists x \exists y (\neg (y \in x ))] \\[6pt] \rightarrow \exists x ( \forall t \neg (t\in x) \wedge \forall y (\forall w ( w\notin y) \rightarrow y=x )). \end{gather}\] 이 논리식은 FOPC에서 형식적인 방법으로 증명된다. 하지만 여기서는 통상적인 증명을 살펴보자.
정리 1의 증명. ZF2에 의하여 원소를 갖지 않는 집합 \(x\)가 존재한다. \(y\) 또한 원소를 갖지 않는 집합이라고 가정하자. 그러면 임의의 \(z\)에 대하여, \(z\in x\)와 \(z\in y\)가 모두 거짓이므로, \[(z\in x) \leftrightarrow (z\in y)\] 가 참이다. 그러므로 ZF1에 의하여 \(x=y\)이다.
원소를 갖지 않는 집합이 유일하므로, 그것에 이름을 붙이고 기호로 나타낼 수 있다.
정의 2. 원소를 갖지 않는 집합을 공집합(empty set)이라고 부르고, \(\varnothing\)으로 나타낸다.
공집합을 나타내는 기호가 \(\mathcal{L}\)의 기호가 아니지만 \(\mathcal{L}\)에 공집합 기호를 추가해도 \(\mathcal{L}\)은 본질적으로 변하지 않는다. 왜냐하면 공집합 기호가 사용된 논리식은 항상 공집합 기호가 사용되지 않은 동치인 논리식으로 표현할 수 있기 때문이다.
쌍 공리
지금까지의 공리와 기호를 통해 존재성이 확보된 집합은 공집합 뿐이다. 이제 다른 집합을 다루기 위한 공리와 정의를 살펴 보자.
ZF3. 쌍 공리; Unordered pairs.
\(x\)와 \(y\)가 집합일 때, 정확히 \(x\)와 \(y\)만을 원소로 갖는 집합이 존재한다.
쌍 공리를 논리식으로 나타내면 다음과 같다. \[\forall x \forall y \exists z ( x \in z \wedge y \in z \wedge \forall w ( w \in z \rightarrow [ w = x \vee w = y ])\] \(x,\) \(y\)가 정해질 때마다 위 논리식이 참이 되도록 하는 \(z\)가 유일하게 존재한다. 그러한 집합 \(z\)를 \[\left\{ x,\,y\right\}\] 로 나타낸다. 즉 중괄호 ‘{’, ‘}’와 쉼표 ‘,’를 \(\mathcal{L}\)에 추가하여 사용한다. 공집합 기호와 마찬가지로 쌍 공리를 표현하기 위한 기호를 집합론 언어에 추가하여도 집합론 언어는 본질적으로 변하지 않는다.
\(x\)가 집합일 때 ZF3에 의하여 \(\left\{ x \right\} = \left\{ x,\,x \right\}\)이다. 또한 논리합의 교환법칙에 의하여 \[\left\{ x,\,y\right\} = \left\{ y,\,x\right\}\] 이다. 즉 쌍 공리에서 집합 \(\left\{ x ,\,y\right\}\)의 원소 \(x,\) \(y\)의 순서는 이 집합의 속성이 아니다.
순서쌍
수학에서는 두 대상을 나타내는 순서가 하나의 속성이 되는 쌍, 즉 순서쌍을 자주 사용한다. 순서쌍을 다음과 같이 정의한다.
정의 3. \(x,\) \(y\)가 집합이라고 하자. 집합 \(\left\{\left\{ x \right\} ,\, \left\{ x,\,y \right\}\right\}\)을 \(x\)와 \(y\)의 순서쌍(ordered pair)이라고 부르고 \(\langle x ,\,y \rangle\)로 나타낸다. 여기서 \(x\)를 \(\langle x ,\,y \rangle\)의 첫째 좌표, \(y\)를 \(\langle x ,\,y \rangle\)의 둘째 좌표라고 부른다.
책에 따라서는 순서쌍 \(\langle x ,\,y \rangle\)를 \((x,\,y)\)로 나타낸다.
다음 정리는 위와 같이 정의한 순서쌍이 우리가 수학에서 사용하는 순서쌍의 성질을 그대로 가지고 있다는 사실을 설명한다.
정리 4. \(x,\) \(y,\) \(u,\) \(v\)가 집합이라고 하자. 만약 \(\langle x,\,y \rangle = \langle u,\,v \rangle\)이면, \(x=u\)이고 \(y=v\)이다.
증명
\(\langle x,\,y \rangle = \langle u,\,v \rangle\)를 집합으로 나타내면 다음과 같다. \[\left\{\left\{ x \right\} ,\, \left\{ x,\,y \right\}\right\} = \left\{\left\{ u \right\} ,\, \left\{ u,\,v \right\}\right\}\] 여기서 집합 \(\left\{\left\{ x \right\} ,\, \left\{ x,\,y \right\}\right\}\)를 LHS라고 부르고, \(\left\{\left\{ u \right\} ,\, \left\{ u,\,v \right\}\right\}\)를 RHS라고 부르자. (left-hand side, right-hand side.)
먼저 \(x=y\)인 경우를 생각하자. 이 경우 \(\left\{ x,\,y\right\} = \left\{ x \right\}\)이므로 \[\left\{ \left\{ x \right\} ,\, \left\{ x,\,y\right\}\right\} = \left\{ \left\{ x \right\} ,\, \left\{ x,\,x\right\}\right\} = \left\{ \left\{ x \right\}\right\}\] 이다. 즉 LHS는 원소가 \(x\) 뿐인 집합이다. ZF1에 의하여 RHS의 각 원소는 LHS의 원소이므로 \[\left\{ u \right\} = \left\{ x\right\} ,\quad \left\{ u ,\,v \right\} = \left\{ x \right\}\] 이다. 그러므로 \(\left\{ u,\,v\right\} = \left\{ u \right\}\)이며, \(u=v\)이고 \(u=x\)이다. 즉 \(y=x=u=v\)이다.
\(u=v\)인 경우에도 \(x=y\)인 경우와 마찬가지로 \(y=x=u=v\)를 얻는다.
이제 \(x\ne y\)이고 \(u\ne v\)인 경우를 살펴보자. \(\left\{ x \right\}\)가 LHS의 원소이므로 \(\left\{ x \right\}\)는 RHS의 원소이다. RHS의 원소가 두 개이므로, \(\left\{ x \right\}\)는 \(\left\{ u,\,v\right\}\)와 같거나 \(\left\{u\right\}\)와 같다.
만약 \(\left\{ x \right\} = \left\{u ,\,v\right\}\)라면, \(u=x\)이고 \(v=x\)이므로, \(u=v\)라는 결과를 얻는다. 이것은 모순이다.
만약 \(\left\{ x \right\} = \left\{ u \right\}\)라면, \(x=u\)이다.
다음으로 \(\left\{ x,\,y\right\}\)가 LHS의 원소이므로 \(\left\{ x,\,y\right\}\)는 RHS의 원소이다. 그러므로 \(\left\{ x,\,y\right\}\)는 \(\left\{ u \right\}\)와 같거나 \(\left\{ u,\,v\right\}\)와 같다.
만약 \(\left\{ x,\,y\right\} = \left\{ u \right\}\)라면, 앞에서 살펴본 결과와 비슷하게 \(x=y\)라는 모순이 발생한다. 그러므로 \(\left\{ x,\,y\right\} = \left\{ u,\,v\right\}\)일 수밖에 없다. 여기서 다시 \(x\)가 \(u\)와 같거나 \(y\)가 \(u\)와 같은데, 만약 \(y=u\)라면 이 등식을 앞에서 얻은 \(x=u\)와 결합하여 \(x=y\)를 얻는다. 이것은 모순이므로 \(y\)는 \(u\)와 같을 수 없다. 그러므로 \(y=v\)이다.
위 정리의 증명 과정을 통해 다음과 같은 따름정리를 얻는다.
따름정리. 만약 \(x\ne y\)이면, \(\langle x,\,y \rangle \ne \langle y,\,x\rangle\)이다.
합집합
ZF4. 합집합 공리; Unions.
\(x\)가 집합일 때, \(x\)의 모든 원소의 모든 원소를 원소로 취하는 집합이 존재한다.
합집합 공리를 논리식으로 나타내면 다음과 같다. \[\forall x \exists y \forall z ( z \in y \leftrightarrow \exists w ( z \in w \wedge w \in x ))\] \(x\)의 모든 원소의 모든 원소를 원소로 취하는 집합을 \(\bigcup x\)로 나타낸다. 직관적 집합론에서는 \[\bigcup x = \left\{ z \,\vert\, \exists w\in x : z \in w \right\}\] 로 정의한다.
정리 5. \(x\)와 \(y\)가 집합이면 \(\left\{ x,\,y\right\}\)도 집합이다.
증명.
쌍 공리에 의하여 \(z=\left\{ x,\,y\right\}\)는 집합이다. 합집합 공리에 의하여 \(\bigcup\left\{ x,\,y\right\}\)도 집합이다.
\(x\)와 \(y\)가 집합일 때, \(\bigcup\left\{ x,\,y\right\}\)를 \(x\cup y\)로 나타낸다.
교집합과 차집합
ZF5. 분류 공리꼴; Comprehension scheme.
\(\phi ( z,\,w_1 ,\,w_2 ,\, \cdots ,\,w_k )\)가 \(\mathcal{L}\)의 논리식이고 자율변수 \(z,\) \(w_1 ,\) \(W_2 ,\) \(\cdots ,\) \(w_k\)를 가지며, \(x\)가 집합이라고 하자. 그러면 임의의 집합 \(w_1 ,\) \(W_2 ,\) \(\cdots ,\) \(w_k\)에 대하여, \(x\)의 원소 중에서 \(\phi (z,\,w_1 ,\,w_2 ,\, \cdots ,\,w_k )\)를 만족시키는 \(z\)를 원소로 갖는 집합 \(y\)가 존재한다.
분류 공리꼴을 부분집합 공리꼴(subset axiom scheme) 또는 Seperation scheme이라고 부르기도 한다.
만약 \(\phi(z,\,w_1 ,\,w_2 ,\, \cdots ,\,w_k )\)가 \(\mathcal{L}\)의 논리식이고 \(z,\) \(w_1 ,\) \(w_2 ,\) \(\cdots ,\) \(w_k\)가 \(\phi\)의 자율변수이면 ZF5에 의하여 다음이 성립한다. \[\forall x \forall w_1 \forall w_2 \cdots \forall w_k \exists y \forall z [ z\in y \leftrightarrow ( z \in x \wedge \phi ( z,\,w_1 ,\, w_2 ,\, \cdots ,\,w_k ))]\] 여기서 \(w_i\)들은 매개변수이다. 위외 같은 조건을 만족시키는 집합 \(y\)를 다음과 같이 나타낸다. \[\left\{ z\in x \,\vert\, \phi ( z ,\, w_1 ,\, w_2 ,\, \cdots ,\, w_k ) \right\}\] ZF5는 하나의 공리가 아니라 공리꼴(axiom scheme)이다. 왜냐하면 각 논리식 \(\phi\)에 대하여 공리가 하나씩 대응되기 때문이다.
직관적 집합론에서는 분류공리꼴에 의하여 존재성이 보장되는 집합을 다음과 같이 나타내기도 한다. \[\left\{ z \,\vert\, \phi( z,\,w_1 ,\,w_2 ,\, \cdots ,\,w_k )\right\}\] 이와 같은 표현의 문제점은 존재성이 보장되지 않은 집합 \(z\)까지 위 집합의 원소의 대상이 되어 Russell의 역설을 야기한다는 점이다.
분류 공리꼴을 사용하여 교집합과 차집합을 정의할 수 있다.
\(x,\) \(y\)가 집합이라고 하자. 이때 \(x\)와 \(y\)의 교집합을 \[x\cap y = \left\{ z\in x \,\vert\, z\in w \right\}\] 로 정의하며, \(x\)에 대한 \(y\)의 차집합을 \[x\setminus y = \left\{ z\in x \,\vert\, z\notin w \right\}\] 로 정의한다.
정리 6. \(x\)와 \(y\)가 집합일 때, \(x\cap y\)와 \(x\setminus y\)도 집합이다.
증명.
\(\phi (z,\,w) = (z\in w)\)라고 하고 \(\varphi ( z,\,w) = (\neg (z\in w))\)라고 하면 \[\begin{align} x\cap y &= \left\{ z\in x \,\vert\, \phi(x,\,y)\right\}\\[6pt] x\setminus y &= \left\{ z\in x \,\vert\, \varphi (z,\,y) \right\} \end{align}\] 이다. 그러므로 분류 공리꼴에 의하여 \(x\cap y\)와 \(x\setminus y\)도 집합이다.
임의 개수의 집합의 합집합을 정의한 것처럼 임의 개수의 집합의 교집합을 정의할 수 있다.
정리 7. \(x\)가 공집합이 아닌 집합이라고 하자. 그러면 \(x\)의 모든 원소의 교집합은 집합이다. 이 집합을 \(\bigcap x\)로 나타낸다.
증명.
합집합 공리에 의하여 \(\bigcup x\)는 집합이다. 또한 \[\bigcap x = \left\{ z\in \bigcup x \,\vert\, \forall y ((y\in x) \rightarrow (z\in y))\right\}\] 이므로 분류 공리꼴에 의하여 \(\bigcap x\)도 집합이다.
위 정리에서 만약 \(x\)가 공집합이라면 \(\bigcap \varnothing\)이 모든 집합의 집합이 되어 모순이다. 그 이유는 다음과 같다.
정리 8. 모든 집합의 집합은 존재하지 않는다.
증명.
모든 집합의 집합이 존재한다고 가정하자. 그리고 \(x\)가 모든 집합의 집합이라고 하자. 그러면 분류 공리꼴에 의하여 \[y = \left\{ z\in x \,\vert\, z\notin z\right\}\] 또한 집합이다. 이 집합의 정의에 의하여 \[y\in y \,\leftrightarrow\, y\notin y\] 를 얻는다. 이것은 모순이다.
차집합에 대해서도 마찬가지 경우를 생각할 수 있다.
따름정리 9. \(x\)가 집합이라고 하자. 이때 \(x\)에 속하지 않는 집합을 모두 모은 집합은 존재하지 않는다.
즉 위 정리는 절대적인 차집합이 존재하지 않으며, 바탕이 되는 집합이 주어졌을 때 상대적인 차집합만 다룰 수 있다는 뜻이다.
클래스
정리 8에서 모든 집합의 집합이 존재하지 않는다는 사실을 밝혔다. 그러나 모든 집합의 ‘모임’을 집합이 아닌 것으로 간주하면, 그러한 모임을 다룰 수 있다.
정의 10. \(\phi\)가 \(\mathcal{L}\)의 논리식이고 \(x\)의 범위가 모든 집합일 때 \[\mathbf{X} = \left\{ x\,\vert\,\phi (x)\right\}\] 의 꼴로 표현되는 모임을 클래스(class)라고 부른다.
클래스는 집합보다 더 넓은 범위의 개체이므로 \(\mathcal{L}\)에서 변수의 범위가 모든 클래스에 이르지는 않는다.
정의 10에서 \(\phi\)는 \(x\) 외의 변수를 가질 수 있다. 이때 \(\mathbf{X}\)는 자율변수를 가진 클래스가 된다.
클래스라는 개념을 도입하면 \[\mathbf{U} = \left\{ x\,\vert\, x=x\right\}\]와 같은 클래스도 다룰 수 있다. 이 클래스는 모든 집합의 모임, 즉 직관적 집합론에서 전체 집합이라고 부르는 모임이다. 물론 이 클래스는 집합이 아니다.
클래스 중에서 다른 클래스에 속할 수 없는 것을 고유 클래스(proper class)라고 부른다. 모든 집합의 모임 \(\mathbf{U}\)는 대표적인 고유 클래스이다. 한편 고유 클래스의 개념을 사용하면 \[\mathbf{R} = \left\{ x\,\vert\, x\notin x\right\}\] 와 같은 모임을 다루어도 Russell의 역설이 발생하지 않는다. 왜냐하면 \(\mathbf{R}\)를 고유 클래스로 분류하면 되기 때문이다.
