* [PUBLISHER] upload files #175 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-19-symmetric-key-encryption.md * [PUBLISHER] upload files #177 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-19-symmetric-key-encryptio.md * [PUBLISHER] upload files #178 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * [PUBLISHER] upload files #179 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * [PUBLISHER] upload files #180 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * [PUBLISHER] upload files #181 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * [PUBLISHER] upload files #182 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * [PUBLISHER] upload files #183 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * [PUBLISHER] upload files #184 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * [PUBLISHER] upload files #185 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * [PUBLISHER] upload files #186 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * [PUBLISHER] upload files #187 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 14. Secure Multiparty Computation.md * DELETE FILE : _posts/Lecture Notes/Modern Cryptography/2023-09-19-symmetric-key-encryption.md * DELETE FILE : _posts/lecture-notes/modern-cryptography/2023-09-18-symmetric-key-cryptography-2.md * [PUBLISHER] upload files #188 * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH NOTE : 14. Secure Multiparty Computation.md * DELETE FILE : _posts/Lecture Notes/Modern Cryptography/2023-09-19-symmetric-key-encryption.md * chore: remove files * [PUBLISHER] upload files #197 * PUSH NOTE : 수학 공부에 대한 고찰.md * PUSH NOTE : 09. Lp Functions.md * PUSH ATTACHMENT : mt-09.png * PUSH NOTE : 08. Comparison with the Riemann Integral.md * PUSH ATTACHMENT : mt-08.png * PUSH NOTE : 04. Measurable Functions.md * PUSH ATTACHMENT : mt-04.png * PUSH NOTE : 06. Convergence Theorems.md * PUSH ATTACHMENT : mt-06.png * PUSH NOTE : 07. Dominated Convergence Theorem.md * PUSH ATTACHMENT : mt-07.png * PUSH NOTE : 05. Lebesgue Integration.md * PUSH ATTACHMENT : mt-05.png * PUSH NOTE : 03. Measure Spaces.md * PUSH ATTACHMENT : mt-03.png * PUSH NOTE : 02. Construction of Measure.md * PUSH ATTACHMENT : mt-02.png * PUSH NOTE : 01. Algebra of Sets and Set Functions.md * PUSH ATTACHMENT : mt-01.png * PUSH NOTE : Rules of Inference with Coq.md * PUSH NOTE : 블로그 이주 이야기.md * PUSH NOTE : Secure IAM on AWS with Multi-Account Strategy.md * PUSH ATTACHMENT : separation-by-product.png * PUSH NOTE : You and Your Research, Richard Hamming.md * PUSH NOTE : 10. Digital Signatures.md * PUSH ATTACHMENT : mc-10-dsig-security.png * PUSH ATTACHMENT : mc-10-schnorr-identification.png * PUSH NOTE : 9. Public Key Encryption.md * PUSH ATTACHMENT : mc-09-ss-pke.png * PUSH NOTE : 8. Number Theory.md * PUSH NOTE : 7. Key Exchange.md * PUSH ATTACHMENT : mc-07-dhke.png * PUSH ATTACHMENT : mc-07-dhke-mitm.png * PUSH ATTACHMENT : mc-07-merkle-puzzles.png * PUSH NOTE : 6. Hash Functions.md * PUSH ATTACHMENT : mc-06-merkle-damgard.png * PUSH ATTACHMENT : mc-06-davies-meyer.png * PUSH ATTACHMENT : mc-06-hmac.png * PUSH NOTE : 5. CCA-Security and Authenticated Encryption.md * PUSH ATTACHMENT : mc-05-ci.png * PUSH ATTACHMENT : mc-05-etm-mte.png * PUSH NOTE : 1. OTP, Stream Ciphers and PRGs.md * PUSH ATTACHMENT : mc-01-prg-game.png * PUSH ATTACHMENT : mc-01-ss.png * PUSH NOTE : 4. Message Authentication Codes.md * PUSH ATTACHMENT : mc-04-mac.png * PUSH ATTACHMENT : mc-04-mac-security.png * PUSH ATTACHMENT : mc-04-cbc-mac.png * PUSH ATTACHMENT : mc-04-ecbc-mac.png * PUSH NOTE : 3. Symmetric Key Encryption.md * PUSH ATTACHMENT : is-03-ecb-encryption.png * PUSH ATTACHMENT : is-03-cbc-encryption.png * PUSH ATTACHMENT : is-03-ctr-encryption.png * PUSH NOTE : 2. PRFs, PRPs and Block Ciphers.md * PUSH ATTACHMENT : mc-02-block-cipher.png * PUSH ATTACHMENT : mc-02-feistel-network.png * PUSH ATTACHMENT : mc-02-des-round.png * PUSH ATTACHMENT : mc-02-DES.png * PUSH ATTACHMENT : mc-02-aes-128.png * PUSH ATTACHMENT : mc-02-2des-mitm.png * PUSH NOTE : 18. Bootstrapping & CKKS.md * PUSH NOTE : 17. BGV Scheme.md * PUSH NOTE : 16. The GMW Protocol.md * PUSH ATTACHMENT : mc-16-beaver-triple.png * PUSH NOTE : 15. Garbled Circuits.md * PUSH NOTE : 14. Secure Multiparty Computation.md * PUSH NOTE : 13. Sigma Protocols.md * PUSH ATTACHMENT : mc-13-sigma-protocol.png * PUSH ATTACHMENT : mc-13-okamoto.png * PUSH ATTACHMENT : mc-13-chaum-pedersen.png * PUSH ATTACHMENT : mc-13-gq-protocol.png * PUSH NOTE : 12. Zero-Knowledge Proofs (Introduction).md * PUSH ATTACHMENT : mc-12-id-protocol.png * PUSH NOTE : 11. Advanced Topics.md * PUSH NOTE : 0. Introduction.md * PUSH NOTE : 02. Symmetric Key Cryptography (1).md * PUSH NOTE : 09. Transport Layer Security.md * PUSH ATTACHMENT : is-09-tls-handshake.png * PUSH NOTE : 08. Public Key Infrastructure.md * PUSH ATTACHMENT : is-08-certificate-validation.png * PUSH NOTE : 07. Public Key Cryptography.md * PUSH NOTE : 06. RSA and ElGamal Encryption.md * PUSH NOTE : 05. Modular Arithmetic (2).md * PUSH NOTE : 03. Symmetric Key Cryptography (2).md * PUSH ATTACHMENT : is-03-feistel-function.png * PUSH ATTACHMENT : is-03-cfb-encryption.png * PUSH ATTACHMENT : is-03-ofb-encryption.png * PUSH NOTE : 04. Modular Arithmetic (1).md * PUSH NOTE : 01. Security Introduction.md * PUSH ATTACHMENT : is-01-cryptosystem.png * PUSH NOTE : Search Time in Hash Tables.md * PUSH NOTE : 랜덤 PS일지 (1).md * chore: rearrange articles * feat: fix paths * feat: fix all broken links * feat: title font to palatino
9.0 KiB
share, toc, math, categories, path, tags, title, date, github_title, image, attachment
| share | toc | math | categories | path | tags | title | date | github_title | image | attachment | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| true | true | true |
|
_posts/mathematics/measure-theory |
|
03. Measure Spaces | 2023-01-24 | 2023-01-24-measure-spaces |
|
|
Remarks on Construction of Measure
Construction of measure 증명에서 추가로 참고할 내용입니다.
명제. $A$가 열린집합이면 A \in \mathfrak{M}(\mu) 이다. 또한 A^C \in \mathfrak{M}(\mu) 이므로, $F$가 닫힌집합이면 F \in \mathfrak{M}(\mu) 이다.
증명. 중심이 x\in \mathbb{R}^p 이고 반지름이 $r$인 열린 box를 $I(x, r)$이라 두자. $I(x, r)$은 명백히 $\mathfrak{M} _ F(\mu)$의 원소이다. 이제
A = \bigcup _ {\substack{x \in \mathbb{Q}^p, \; r \in \mathbb{Q}\\ I(x, r)\subseteq A}} I(x, r)
로 적을 수 있으므로 $A$는 $\mathfrak{M} _ F(\mu)$의 원소들의 countable union이 되어 A \in \mathfrak{M}(\mu) 이다. 이제 $\mathfrak{M}(\mu)$가 $\sigma$-algebra이므로 A^C\in \mathfrak{M}(\mu) 이고, 이로부터 임의의 닫힌집합 $F$도 $\mathfrak{M}(\mu)$의 원소임을 알 수 있다.
명제. A \in \mathfrak{M}(\mu) 이면 임의의 \epsilon > 0 에 대하여
F \subseteq A \subseteq G, \quad \mu\left( G \setminus A \right) < \epsilon, \quad \mu\left( A \setminus F \right) < \epsilon
를 만족하는 열린집합 $G$와 닫힌집합 $F$가 존재한다.
이는 곧 정의역을 $\mathfrak{M}(\mu)$로 줄였음에도 $\mu$가 여전히 \mathfrak{M}(\mu) 위에서 regular라는 뜻입니다.
증명. A = \bigcup _ {n=1}^\infty A _ n (A _ n \in \mathfrak{M} _ F(\mu)) 로 두고 \epsilon > 0 을 고정하자. 각 n \in \mathbb{N} 에 대하여 열린집합 B _ {n, k} \in \Sigma 를 잡아 A _ n \subseteq\bigcup _ {k=1}^\infty B _ {n, k} 와
\mu\left( \bigcup _ {k=1}^{\infty} B _ {n, k} \right) \leq \sum _ {k=1}^{\infty} \mu\left( B _ {n, k} \right) < \mu\left( A _ n \right) + 2^{-n}\epsilon
을 만족하도록 할 수 있다.1
이제 열린집합을 잡아보자. G _ n = \bigcup _ {k=1}^{\infty} B _ {n, k} 으로 두고 G = \bigcup _ {n=1}^{\infty} G _ n 로 잡는다. A _ n \in \mathfrak{M} _ F(\mu) 이므로 \mu\left( A _ n \right) < \infty 이고, 다음이 성립한다.
\begin{aligned} \mu\left( G \setminus A \right) & = \mu\left( \bigcup _ {n=1}^{\infty} G _ n \setminus\bigcup _ {n=1}^{\infty} A _ n \right) \leq \mu\left( \bigcup _ {n=1}^{\infty} G _ n \setminus A _ n \right) \\ &\leq \sum _ {n=1}^{\infty} \mu\left( G _ n \setminus A _ n \right) \leq \sum _ {n=1}^{\infty} 2^{-n}\epsilon = \epsilon. \end{aligned}
닫힌집합의 존재성을 보이기 위해 위 과정을 $A^C$에 대해 반복하면 A^C \subseteq F^C, \mu\left( F^C \setminus A^C \right) < \epsilon 가 되도록 열린집합 $F^C$를 잡을 수 있다. $F$가 닫힌집합이고 F^C \setminus A^C = F^C \cap A = A\setminus F 이므로 \mu\left( A \setminus F \right) < \epsilon 이고 F\subseteq A 이다.
정의. (Borel $\sigma$-algebra) $\mathbb{R}^p$의 모든 열린집합과 닫힌집합을 포함하는 $\sigma$-algebra를 \mathfrak{B} = \mathfrak{B}(\mathbb{R}^p) 라 적고 Borel $\sigma$-algebra라 한다. 또한 $\mathfrak{B}$의 원소 $E$를 Borel set이라 한다.
Borel $\sigma$-algebra는 $\mathbb{R}^p$의 열린집합을 포함하는 가장 작은 $\sigma$-algebra로 정의할 수도 있습니다. $O$가 $\mathbb{R}^p$의 열린집합의 모임이라 하면
\mathfrak{B} = \bigcap _ {O \subseteq G,\;G:\, \sigma\text{-algebra}} G
로 정의합니다. 여기서 '가장 작은'의 의미는 집합의 관점에서 가장 작다는 의미로, 위 조건을 만족하는 임의의 집합 $X$를 가져오더라도 X \subseteq\mathfrak{B} 라는 뜻입니다. 그래서 교집합을 택하게 됩니다. 위 정의에 의해 \mathfrak{B} \subseteq\mathfrak{M}(\mu) 임도 알 수 있습니다.
$\mu$-measure Zero Sets
정의. ($\mu$-measure zero set) A \in \mathfrak{M}(\mu) 에 대하여 \mu(A) = 0 인 $A$를 $\mu$-measure zero set이라 한다.
명제. A \in \mathfrak{M}(\mu) 이면 F \subseteq A \subseteq G 인 Borel set F, $G$가 존재한다. 추가로, $A$는 Borel set과 $\mu$-measure zero set의 합집합으로 표현할 수 있으며, $A$와 적당한 $\mu$-measure zero set을 합집합하여 Borel set이 되게 할 수 있다.
증명. $\mathfrak{M}(\mu)$의 regularity를 이용하여 다음을 만족하는 열린집합 G _ n \in \Sigma, 닫힌집합 F _ n \in \Sigma 를 잡는다.
F _ n \subseteq A \subseteq G _ n, \quad \mu\left( G _ n \setminus A \right) < \frac{1}{n}, \quad \mu\left( A \setminus F _ n \right) < \frac{1}{n}.
이제 F = \bigcup _ {n=1}^{\infty} F _ n, G = \bigcap _ {n=1}^{\infty} G _ n 로 정의하면 F, G \in \mathfrak{B} 이고 F \subseteq A \subseteq G 이다.
한편, A = F \cup (A \setminus F), G = A \cup (G \setminus A) 로 적을 수 있다. 그런데 n \rightarrow\infty 일 때
\left.\begin{array}{r}\mu\left( G \setminus A \right)\leq \mu\left( G _ n \setminus A \right) < \frac{1}{n} \\ \mu\left( A \setminus F \right) \leq \mu\left( A \setminus F _ n \right) < \frac{1}{n}\end{array}\right\rbrace \rightarrow 0
이므로 A \in \mathfrak{M}(\mu) 는 Borel set 과 $\mu$-measure zero set의 합집합이다. 그리고 A \in \mathfrak{M}(\mu) 에 적당한 $\mu$-measure zero set을 합집합하여 Borel set이 되게 할 수 있다.
명제. 임의의 measure $\mu$에 대하여 $\mu$-measure zero set의 모임은 $\sigma$-ring이다.
증명. Countable subadditivity를 확인하면 나머지는 자명하다. 모든 n\in \mathbb{N} 에 대하여 \mu\left( A _ n \right) = 0 이라 하면
\mu\left( \bigcup _ {n=1}^{\infty} A _ n \right) \leq \sum _ {n=1}^{\infty} \mu\left( A _ n \right) = 0
이다.
명제. $A$가 countable set이면 m(A) = 0 이다. 그러나 m(A) = 0 이지만 uncountable set인 $A$가 존재하기 때문에 역은 성립하지 않는다.
증명. $A$가 countable set이라 하자. 그러면 $A$는 점들의 countable union이고, 점은 measure가 0인 $\mathbb{R}^p$의 닫힌집합이므로 $A$는 measurable이면서 (닫힌집합의 합집합) m(A) = 0 이 된다.
Uncountable인 경우에는 Cantor set $P$를 생각한다. $E _ n$을 다음과 같이 정의한다.
-
E _ 0 = [0, 1]. -
E _ 1 = \left[0, \frac{1}{3}\right] \cup \left[\frac{2}{3}, 1\right], $E _ 0$의 구간을 3등분하여 가운데를 제외한 것이다. -
E _ 2 = \left[0, \frac{1}{9}\right] \cup \left[\frac{2}{9}, \frac{3}{9}\right] \cup \left[\frac{6}{9}, \frac{7}{9}\right] \cup \left[\frac{8}{9}, 1\right], 마찬가지로 $E _ 1$의 구간을 3등분하여 가운데를 제외한 것이다.
위 과정을 반복하여 $E _ n$을 얻고, Cantor set은 P = \bigcap _ {n=1}^{\infty} E _ n 로 정의한다. 여기서 m(E _ n) = \left( \frac{2}{3} \right)^n 임을 알 수 있고, P \subseteq E _ n 이므로 m(P)\leq m(E _ n) 가 성립한다. 이제 n \rightarrow\infty 로 두면 m(P) = 0 이다.
참고. \mathfrak{M}(m) \subsetneq \mathcal{P}(\mathbb{R}^p). $\mathbb{R}^p$의 부분집합 중 measurable하지 않은 집합이 존재한다.2
Measure Space
이제 본격적으로 measure와 Lebesgue integral을 다룰 공간을 정의하겠습니다.
정의. (Measure Space) 집합 $X$에 대하여 $\sigma$-algebra/$\sigma$-ring \mathfrak{M} on $X$와 \mathfrak{M} 위의 measure $\mu$가 존재하면 $X$를 measure space라 한다. 그리고 X = (X, \mathfrak{M}, \mu) 로 표기한다.
정의. (Measurable Space) 집합 $X$에 대하여 $\mathfrak{M}$이 $\sigma$-algebra on $X$이면 $X$를 measurable space라 한다. 그리고 X = (X, \mathfrak{M}) 으로 표기한다.
두 정의를 비교하면 measure $\mu$가 주어진 $(X, \mathfrak{M}, \mu)$는 measure space이고, $\mu$가 주어지지 않은 $(X, \mathfrak{M})$은 잴 수 있다는 의미에서 measurable space입니다.
예제.
-
$(\mathbb{R}^p, \mathfrak{M}(m), m)$를 Lebesgue measure space라 한다.
-
원소의 개수를 세는 counting measure
\mu(E) = \lvert E \rvert(E \in \mathcal{P}(\mathbb{N})) 에 대하여 $(\mathbb{N}, \mathcal{P}(\mathbb{N}), \mu)$는 measure space가 된다.
정의. (Complete Measure Space) Measure space $(X, \mathfrak{M}, \mu)$의 임의의 $\mu$-measure zero set $B$에 대하여 $B$의 임의의 부분집합 또한 $\mu$-measurable이면, $(X, \mathfrak{M}, \mu)$를 complete measure space라 한다. 즉,
A \subseteq B \subseteq X일 때,B \in \mathfrak{M}이고\mu(B) = 0이면A \in \mathfrak{M}이다.
-
첫 번째 부등식은 countable subadditivity, 두 번째 부등식은 $\mu^\ast$의 정의에서 나온다. ↩︎
-
Vitali set 참고. ↩︎
