거듭제곱집합과 데카르트 곱
ZF6. 거듭제곱집합 공리; Power set axiom.
\(x\)가 집합이라고 하자. 그러면 \(x\)의 모든 부분집합만을 원소로 갖는 집합이 존재한다.
\(x\)가 집합일 때 \(x\)의 모든 부분집합만을 원소로 갖는 집합은 유일하다. 그러므로 다음과 같이 정의한다.
정의 1. \(x\)가 집합일 때, \(x\)의 모든 부분집합만을 원소로 갖는 집합을 \(x\)의 거듭제곱집합(power set) 또는 멱집합이라고 부르고, \(\mathcal{P}(x)\)로 나타낸다.
거듭제곱집합 공리 덕분에 집합의 데카르트 곱을 정의할 수 있다.
정리 2. \(X\)와 \(Y\)가 집합이라고 하자. 그러면 \(x\in X,\) \(y\in Y\)를 만족시키는 모든 순서쌍 \(\langle x,\,y \rangle\)를 원소로 갖는 집합이 존재한다.
증명
거듭제곱집합 공리에 의하여 \(P=\mathcal{P} ( \mathcal{P} ( X\cup Y ))\)는 집합이다. 이제 \(x\in X,\) \(y\in Y\)라고 하자. 그러면 \[\begin{gather} \left\{ x \right\} \in \mathcal{P} (X\cup Y), \\[5pt] \left\{ y \right\} \in \mathcal{P} (X\cup Y) \end{gather}\] 이므로 \[\langle x,\,y \rangle = \left\{\left\{ x \right\} ,\, \left\{ x,\,y \right\}\right\} \in \mathcal{P} ( \mathcal{P} ( X\cup Y )) = P\] 이다. \[Z = \left\{ z\in P \,\vert\, \exists x \exists y ( x \in X \wedge y \in Y \wedge z = \langle x,\,y \rangle )\right\}\] 라고 하면, 분류 공리꼴에 의하여 \(Z\)는 잘 정의된 집합이며 정확히 \(x\in X,\) \(y\in Y\)를 만족시키는 모든 순서쌍 \(\langle x,\,y \rangle\)를 원소로 가진다.
정리 2의 증명에서 \(X\)와 \(Y\)가 정해질 때마다 집합 \(Z\)는 하나로 정해진다.
정의 3. \(X\)와 \(Y\)가 집합이라고 하자. 이때 \(x\in X,\) \(y\in Y\)를 만족시키는 모든 순서쌍 \(\langle x,\,y\rangle\)만을 원소로 갖는 집합을 \(X\)와 \(Y\)의 데카르트 곱(Cartesian product)이라고 부르고 \(X\times Y\)로 나타낸다.
관계와 함수
정의 4. \(X\)와 \(Y\)가 집합이라고 하자. 이때 \(X\times Y\)의 부분집합 \(R\)를 ‘\(X\)와 \(Y\) 사이의 관계(relation)’라고 부른다. 특히 \(X\)와 \(X\) 사이의 관계를 간단하게 ‘\(X\) 위에서의 관계’라고 부른다. \(R\)가 \(X\)와 \(Y\) 사이의 관계일 때, \(\langle x,\,y\rangle \in R\)를 간단하게 \(xRy\)와 같이 나타낸다.
정의 5. \(R\)가 \(X\)와 \(Y\) 사이의 관계라고 하자. 만약 임의의 \(x\in X\)에 대하여 [\(\langle x,\,y\rangle \in R\)인 \(y\in Y\)가 유일하게 존재]하면, \(R\)를 \(X\)로부터 \(Y\)로의 함수(function)라고 부른다. 만약 \(f\)가 \(X\)로부터 \(Y\)로의 함수이면, \(\langle x,\,y\rangle \in f\)를 간단히 \(y=f(x)\)와 같이 나타낸다. 함수를 사상(map)이라고 부르기도 한다.
\(F\)가 \(A\)로부터 \(B\)로의 함수라는 것을 \(\mathcal{L}\)의 논리식으로 나타내면 다음과 같다. \[(F\subseteq A\times B) \wedge \forall x ( x\in A \rightarrow \exists y ((y\in B)\wedge (\langle x,\,y\rangle \in F ) \wedge \forall z (\langle x,\,z\rangle \in F \rightarrow z=y )))\] \(X\)와 \(Y\) 사이의 모든 관계의 모임은 \(\mathcal{P}(X\times Y)\)이므로 집합이다. 함수는 관계의 일종이므로, 모든 함수의 모임 또한 집합이다.
정의 6. \(X\)와 \(Y\)가 집합이라고 하자. 이때 \(X\)로부터 \(Y\)의 모든 함수만으로 이루어진 집합을 \(Y^X\)로 나타낸다.
\(f\)가 함수일 때 \(f\)의 정의역(domain)을 다음과 같이 정의한다. \[\operatorname{Dom}(f) = \left\{ x\in \bigcup \bigcup f \,\vert\, \exists y \in \bigcup \bigcup f ( \langle x,\,y\rangle \in f ) \right\}\] 또한 \(f\)의 치역(range)을 다음과 같이 정의한다. \[\operatorname{Ran}(f) = \left\{ y\in \bigcup \bigcup f \,\vert\, \exists x \in \bigcup \bigcup f ( \langle x,\,y\rangle \in f ) \right\}\] \(f\)가 \(X\)로부터 \(Y\)로의 함수일 때 \(f\)의 치역을 \(f[X]\)와 같이 나타내기도 한다.
\(X\)와 \(Y\)가 집합일 때, \(f\)가 \(X\)로부터 \(Y\)로의 함수인 것을 \(f:X\rightarrow Y\)와 같이 나타낸다. 편의상 별다른 언급이 없으면 \(f\)의 정의역이 \(X\)인 것으로 약속한다. 즉 \(\operatorname{Dom}(f) = X\)인 것으로 약속한다.
함수는 순서쌍의 모임이다. 그러므로 두 함수 \(f:X\rightarrow Y\)와 \(g:X\rightarrow Z\)가 같다는 것은 두 집합 \(f\)와 \(g\)가 같다는 것을 의미한다. 이때 두 함수의 공역 \(Y\)와 \(Z\)가 서로 일치하는지 여부는 상관없다. \(f=g\)로부터 얻는 것은 \(f[X] = g[X]\)라는 사실과 \(f[X]\)가 \(Y\cap Z\)의 부분집합이라는 사실뿐이다.
함수의 정의에 따르면 \(\varnothing\)은 \(\varnothing\)으로부터 \(\varnothing\)으로의 함수이다. 또한 \(\varnothing\)으로부터 \(\varnothing\)으로의 함수는 \(\varnothing\) 뿐이다. 그러므로 \(\varnothing ^ \varnothing = \left\{ \varnothing \right\}\)이다.
동등관계와 순서관계
동등관계와 순서관계는 함수와 더불어 수학에서 가장 많이 사용되는 관계이다.
정의 7. \(E\)가 \(X\) 위에서 정의된 관계라고 하자. 이때 다음과 같이 정의한다.
- 임의의 \(x\in X\)에 대하여 \(\langle x,\,x\rangle \in E\)가 성립하면, \(E\)를 반사적 관계(reflexive relation)라고 부른다.
- \(X\)의 임의의 원소 \(x,\) \(y\)에 대하여, \(\langle x,\,y\rangle \in E\)일 때마다 \(\langle y,\,x \rangle \in E\)가 성립하면, \(E\)를 대칭적 관계(symmetric relation)라고 부른다.
- \(X\)의 임의의 원소 \(x,\) \(y,\) \(z\)에 대하여, [\(\langle x,\,y\rangle \in E\)이고 \(\langle y,\,z\rangle \in E\)]일 때마다 \(\langle x,\,z\rangle \in E\)가 성립하면, \(E\)를 추이적 관계(transitive relation)라고 부른다.
만약 \(E\)가 위 세 조건을 모두 만족시키면, \(E\)를 \(X\) 위에서 정의된 동등관계(equivalent relation)라고 부른다. 동등관계를 동치관계라고 부르기도 한다.
정의 8. \(R\)가 \(X\) 위에서 정의된 관계라고 하자. 이때 다음과 같이 정의한다.
- \(X\)의 임의의 원소 \(x,\) \(y\)에 대하여, [\(\langle x,\,y\rangle \in R\)이고 \(\langle y,\,x\rangle \in R\)]일 때마다 \(x=y\)가 성립하면, \(R\)를 반대칭적 관계(antisymmetric relation)라고 부른다.
- \(R\)가 반사적이고 반대칭적이며 추이적인 관계일 때 \(R\)를 약한 반순서관계(weak partial order)라고 부른다.
- \(R\)가 약한 반순서관계라고 하자. 만약 \(X\)의 임의의 두 원소가 비교 가능하면, 즉 \(X\)의 임의의 원소 \(x,\) \(y\)에 대하여 \(\langle x,\,y\rangle \in R\) 또는 \(\langle y,\,x\rangle \in R\)가 성립하면, \(R\)를 약한 전순서관계(weak total order)라고 부른다.
- 임의의 \(x\in X\)에 대하여 \(\langle x,\,x\rangle \notin R\)가 성립하면, \(R\)를 반반사적 관계(irreflexive relation)라고 부른다.
- \(R\)가 반반사적이고 추이적인 관계라고 하자. 만약 \(X\)의 임의의 원소 \(x,\) \(y\)에 대하여, \(\langle x,\,y\rangle \in R \rightarrow \langle y ,\,x \rangle \notin R\)가 성립하면, \(R\)를 강한 반순서관계(strict partial order)라고 부른다.
- \(R\)가 강한 반순서관계라고 하자. 만약 \(X\)의 서로 다른 임의의 두 원소 \(x,\) \(y\)에 대하여 \(\langle x,\,y\rangle \in R\) 또는 \(\langle y,\,x\rangle \in R\)가 성립하면, \(R\)를 강한 전순서관계(strict total order)라고 부른다.
정리 9. \(S\)가 \(X\) 위에서 정의된 강한 반순서관계라고하자. 그러면 \[R = S\cup \left\{ \langle x,\,x \rangle \,\vert\, x\in X \right\}\] 는 \(X\) 위에서 정의된 약한 반순서관계이다. 여기서 만약 \(S\)가 전순서관계이면 \(R\)도 전순서관계이다.
증명
주어진 관계가 정의 8의 조건을 만족시키는지 점검해 보면 된다.
동등관계를 나타낼 때와 마찬가지로 순서관계를 나타낼 때도 \(\langle x,\,y\rangle \in R\)를 간단히 \(xRy\)와 같이 나타낸다.
동등관계를 나타낼 때 주로 기호 ‘\(\sim\)’이나 ‘\(\approx\)’를 사용한다. 강한 순서관계를 나타낼 때 주로 ‘\( < \)‘나 ‘\(\prec\)’를 사용하며, 약한 순서관계를 나타낼 때 주로 ‘\(\le\)’나 ‘\(\preceq\)’를 사용한다.
부분집합을 나타내는 기호 \(\subseteq\)는 관계가 아니다. 왜냐하면 모든 집합의 집합이 존재하지 않기 때문이다. 그러나 적당한 집합 \(X\)를 고정시키면 \(\subseteq\)는 거듭제곱집합 \(\mathcal{P}(X)\) 위에서 정의된 관계이다.