어릴때 썼던거라.. 다소 과한 표현이 많을 것 같습니다.. 부디 귀엽게 봐주셔요..
1. The Real Line and Euclidean Space
1-3 Least Upper Bound $\def \d#1{\mathbb{#1}}$
1-3절에서는 최소값과 최대값 역할을 하는 supremum과 infimum에 대해서 배운다. 머신러닝에서는 Cost Function을 최소화 하거나 Reward Function을 최대화하는 일을 많이 하기 때문에 중요한 개념이라고 말 할 수 있다.
우선 앞서 정의했던 Bound 개념을 다시 보자.
$S \subset \d R$에 대해
-
$S$ is Bounded
iff $\exists M \in N$ s.t $\mid x \mid \leq M , \forall x \in S$
-
$\exists m,M$ s.t $m \leq x \leq M , \forall x \in S$일시
$m$ is called Lower Bound,$M$ is called Upper Bound
이에 대해서 Least Upper Bound는 다음과 같이 정의된다.
Least Upper Bound
For $S \subset \d R $ , $b$ is called Least Upper Bound if following propositios hold
- $b$ is Upper Bound of $S$
- If $b’$ is upper bound of $S$, then $b \leq b’$
다음의 표현은 모두 Equivalent 하다
- $b$ is smallest upper bound of $S$
- $b$ is least upper bound of $S$
- $b$ is supremum of $S$
- $b = sup S$
+$sup \ \phi = -\infty$
이에 대해서 수학적으로 표현하면 다음과 같다.
$b = sup \ S$
iff $\forall \epsilon >0 , \ \exists x \in S$ s.t $\ b-\epsilon \leq x$
이를 역으로 정의하면 Greatest Lower Bound를 정의할 수 있다.
Greatest Lower Bound
For $S \subset \d R$, $a$ is called Greatest Lower Bound of $S$ if following propositions hold
- $a$ is lower bound of $S$
- If $a’$ is lower bound, then $a \leq a’$
다음의 표현은 모두 Equivalent 하다
- $a$ is greatest lower bound of $S$
- $a$ is greatest lower bound of $S$
- $a$ is infimum of $S$
- $a = inf \ S $
+$inf \ \phi = \infty$
이들에 대해 다음과 같은 Proposition이 성립한다.
For $A \subset B \subset \d R $, $inf \ B \leq inf \ A \leq sup \ A \leq sup \ B$
Least Upper Bound Property
For field $\d F$, If “$\forall S \subset \d F , S \neq \phi$ and $S$ is upper bounded, then $S$ has least upper bound in $\d F$” holds, then $\d F$ has Least Upper Bound Property
이 같은 property는 Monotnone Sequence Property 와 동치 관계에 있다. 즉, 다음이 성립한다
$\d F$ is complete
$\d F$ has Monotone Seaquence Property
$\d F$ has Least Upper Bound Property
1-4 Cauchy Sequence
Cauchy Sequence는 다음과 같이 정의된다.
Cauchy Sequence
$\forall \epsilon>0, \exists N$ such that $\mid x_n - x_m \mid < \epsilon , \forall n,m \geq N$
convergence의 정의가 하나의 상수로의 완전한 접근을 의미한다면, 코시 수열의 경우 수열 끼리의 접근을 의미한다.
교수님이 말씀하시길, convergence나 complete는 수렴의 존재성에 관한 이야기인 반면, 코시 수열은 수렴의 상태에 관한 의미라고 한다.
그러나 $\d F$가 Complete하다면 수렴의 상태성이 곧 존재를 의미한다고 한다. 이에 대한 증명은 다음과 같다.
pf) 1.$x_n$이 코시 시퀀스 이면 Convergence하다
1.1 ${x_n}$이 코시 시퀀스 하면 ${x_n}$은 bounded하다.
$\epsilon = 1 > 0 \Rightarrow \exists N \in \d N \ s.t. \mid x_n - x_N \mid < \epsilon = 1 \ \forall n \geq N$
$\mid x_n \mid - \mid x_N \mid \leq \mid x_n - x_N \mid < 1 \Rightarrow \mid x_n \mid \leq \mid x_N \mid +1$
$M := max(\mid x_1 \mid ,\mid x_2 \mid ,…,\mid x_N \mid, \mid x_N \mid +1)$ 일시
$\mid x_n \mid \leq M \Rightarrow$ ${x_n}$는 Bounded하다.
1.2 ${x_n}$이 Cauchy Sequence 일시 그의 subsequence는 수렴한다.
$\exists {x_{n_k}} \subset {x_n} , \exists x \in \d R \ s.t \ x_{n_k} \rightarrow x$
$ \mid x_n\mid \in (-M,M) $이므로
$[-M,0],[0,M]$ 중 한 곳에는 inifinitely many한 점들이 존재한다.
그 지점을 $[a_1,b_1]$로 삼자
$[a_1,b_1] \ni x_{n_1}$인 $x_{n_1}$을 따오자
다음으로
$[a_1,\frac{a_1+b_1}{2}],[\frac{a_1+b_1}{2},b_1]$ 중 한 곳에는 inifinitely many한 점들이 존재한다.
그 지점을 $[a_2,b_2]$로 삼자
$[a_2,b_2] \ni x_{n_2}$인 $x_{n_2}$을 따오자.
이와 같이 반복함으로써 $[a_k,b_k]$와 그 안에 있는 $x_{n_k}$을 따오자.
이렇게 반복하면 $[a_{k+1},b_{k+1}] \subset [a_k,b_k] $ 이므로 $a_{k} \leq a_{k+1}$, $a_k \leq M$ 이므로 $a_k \rightarrow a$로 수렴한다. 마찬가지로 $b_k \rightarrow b$라고 하자.
$b_k-a_k = \frac{b_{k-1}-a_{k-1}}{2} = \frac{M}{2^{k-1}}$이므로 ${b_k - a_k} \rightarrow 0 , a=b$이다.
$a_k \leq x_{n_k} \leq b_k , a_k \rightarrow a , b_k \rightarrow a$ 이므로 $x_{n_k} \rightarrow a$로 수렴한다.
1.3 $X_n$이 코시 시퀀스 이면 Convergence하다
이미 알고 있는 정리는 다음과 같다.
$\forall \epsilon >0 , \exists N_0 \in \d N \ s.t \ \mid x_m - x_n \mid < \epsilon \ \forall n,m \geq N_0$
$\forall \epsilon >0 ,\exists K_0 \in \d N \ s.t \ \mid x_{n_k} -a \mid < \epsilon ,\forall k \geq K_0$
이를 이용해서 다음과 같이 논리를 이어가자
$N := max(N_0,K_0)$
$\forall n \geq N , \mid x_n - x \mid \leq \mid x_n - x_{n_{K_0}} \mid + \mid x_{n_{K_0}} - x \mid < \epsilon + \epsilon = 2\epsilon$
따라서 $x_n \rightarrow x$로 수렴한다.
pf) 2.${x_n}$이 Convergence하면 코시 시퀀스이다
이는 사실 trivial하다.
$\forall \epsilon_1 > \epsilon_2 >0 , \exists N \in \d N \ s.t \mid x_n-x\mid <\epsilon_1$ and $\mid x_m - x \mid < \epsilon_2 \ \forall n,m \geq N$
$\epsilon_0 := \epsilon_1 - \epsilon_2 >0$
$\forall \epsilon_0 >0, \exists N \in \d N \ s.t \mid x_n-x \mid - \mid x_m -x \mid \leq \mid x_n - x_m \mid < \epsilon_1- \epsilon_2 = \epsilon_0 \ \forall n,m \geq N$
따라서 ${X_n}$이 수렴하면 코시 시퀀스의 정의도 만족한다.
코시 시퀀스의 성질은 다음과 같다.
a. If ${x_n} \rightarrow x$ ,then ${x_n}$ is cauchy sequence
b. Every Cauchy Sequence is bounded
c. If ${x_n}$ is cauchy sequence and its subsequence converges to x, then $x_n \rightarrow x$
d.If ${x_n} $ is bounded ,then $\exists {x_{n_k}} \subset {x_n}$ such that $x_{n_k} \rightarrow x $
b의 증명은 위의 1.1에서, d의 증명은 위의 1.2에서 진행하였다.
이것이 함의하는 바는 적어도 Complete함이 알려진 $\d R$에서는 수렴의 상태성만 보임으로써 수렴을 한다는 것을 말할 수 있음을 의미한다.
1-5 Cluster Point , lim sup , lim inf
A. Cluster Point
단순 수렴은 너무나도 강한 제약을 가진 정의라고 한다. 따라서 Cluster Point라고 하는, 수렴의 정의보다는 좀 더 약한 개념이 정의되어 있다. 그는 다음과 같다.
x is called Cluster point of ${x_n}$ if below proposition holds
$\forall \epsilon >0 , \exists$ infinitely many $X_n$ such that $\mid x_n -X \mid <\epsilon$
$\forall \epsilon >0 , \forall N \in \d N , \exists n \geq N\ s.t. \mid x_n - x \mid < \epsilon$
좀 더 개념적으로 설명하면, 수열이 수렴을 할 때는, 수렴점 근처의 일정 구역 내에서는 infinitely many한 포인트들이 존재하고, 일정 이상 벗어난 구간에서는 finitely many한 포인트가 존재한다는 개념이다.
반면 수열이 클러스터 포인트를 가진다는 것은, 클러스터 포인트 근처의 일정구역 내에서는 여전히 infinitely many한 포인트들이 존재하지만, 나머지 구간에서 어떻게 되던지에 대한 제약은 존재하지 않는 다고 한다.
이러한 직관은 증명이나 적용을 할 때 유용하게 쓰일 수 있을것 같다.
Cluster Point 의 속성은 다음과 같다.
a. x is Cluster Point of $X_n$ iff $\forall \epsilon >0 , \forall N \in \d N , \exists n \geq N \ s.t. \mid x_n - x \mid <\epsilon$
b. $x$ is a cluster point of ${x_n }$ iff $\exists {x_{n_k}} \subset {x_n}$ such that $x_{n_k} \rightarrow x$
c. $x_n \rightarrow x$ iff $\forall {x_{n_k}} \subset {x_n} ,x_{n_k} \rightarrow x$
d.$x_n \rightarrow x$ iff ${x_n}$ is bounded and x is cluster point of ${x_n}$
e. $x_n \rightarrow x$ , iff $\forall {x_{n_k}} \subset x_n , \exists {x_{n_{k_l}}} \subset {x_{n_k}}$ such that ${x_{n_{k_l}}} \rightarrow x$
이에 대해서 하나하나 모두 증명해보자
Proof of Cluster point Property
a. x is Cluster Point of $X_n$ iff $\forall \epsilon >0 , \forall N \in \d N , \exists n \geq N \ s.t. \mid x_n - x \mid <\epsilon$
pf) 1. If x is Cluster Point of $X_n$ ,then $\forall \epsilon >0 , \forall N \in \d N , \exists n \geq N \ s.t. \mid x_n - x \mid <\epsilon$
If x is cluster point, then $\forall \epsilon >0 ,$there is infinitely many n such that $\mid x_n - x \mid < \epsilon$
then we can call $T_\epsilon = {n \in \d N ; \mid x_n- x \mid < \epsilon}$ is infinite set.
So we can draw n for every N such that n > N and it could be rewrite as
$\exists n \in T_\epsilon$ with n>N s.t $\mid x_n -x \mid < \epsilon$
pf)2. If $\forall \epsilon >0 , \forall N \in \d N, \exists n \geq N \ s.t. \mid x_n - x \mid < \epsilon$ , then x is cluster point of $X_n$
we can draw $n_1$ that holds proposition. And then draw $n_2$ that holds proposition and is bigger than $n_1$. Keeping it, we can infinitely many $n_k$ near x. And it means x is cluster point of $X_n$
b. $x$ is a cluster point of ${x_n }$ iff $\exists {x_{n_k}} \subset {x_n}$ such that $x_{n_k} \rightarrow x$
pf) 1. If $x$ is cluster point of ${x_n}$, then $\exists {x_{n_k}} \subset {x_n}$ such that $x_{n_k} \rightarrow x $
By proposition (a), we can draw $x_{n_1} \ s.t. \ ,\mid x_{n_1}-x \mid < 1$, and we can draw again $x_{n_2}$ such that $\mid x_{n_2} -x \mid < 1/2 , n_2 > n_1$, and by keeping it on, we can draw $x_{n_k}$ s.t. $\mid x_{n_k} -x \mid < \frac{1}{2^{k-1}}$
As a result, we can make $x_{n_k} \in {x_n}$ such that $\forall \epsilon >0 ,\exists K \in \d N \ s.t. \mid x_{n_k}-x\mid <\epsilon ,\forall k > K$
pf)2. If $\exists {x_{n_k}} \subset {x_{n_k}}$ such that $x_{n_k} \rightarrow x$ ,then $x$ is cluster point of ${x_n} $
So trivial. We can draw infinitely many points $x_{n’}$ through assumption, so there is infinitely many point near x
c. $x_n \rightarrow x$ iff $\forall {x_{n_k}} \subset {x_n} ,x_{n_k} \rightarrow x$
pf)1. If $x_n \rightarrow x$, then $\forall {x_{n_k}} \subset {x_n}, x_{n_k} \rightarrow x$
By a definition of convergence, $\forall \epsilon>0, \exists N \in \d N$ such that $\mid x_n - x \mid < \epsilon , \forall n >N$. In other words, There is no $n$ such that $\mid x_n -x \mid > \epsilon$ ,$n> N$. And it means that $x’$ is not cluster point if $x \neq x’$. Using contrapposition of (b), If x’ is not a cluster point of ${x_n}$,then $\forall {x_{n_k}} \subset {x_n} ,x_{n_k} \nrightarrow x’$.
Because $x$ is the only cluster point of ${x_n}$ and there is no convergence point which is not cluster point, every subsequence of ${x_n}$ converges to $x$.
pf)2. If $\forall {x_{n_k}} \subset {x_n}, x_{n_k} \rightarrow x$, then $x_n \rightarrow x$
Suppose $x_n \nrightarrow x$, then $\forall N \in \d N,\exists \epsilon_0 >0$ and $\exists n \geq N$such that $ \mid x_{n} - x \mid \geq \epsilon$
It means that we can draw $n_1$ such that $n_1 \geq N=1 , \mid x_n -x \mid \geq \epsilon$, and we can draw $n_2$ such that $n_2 \geq N+n_1 , \mid x_n - x \mid \geq \epsilon$. By keeping it, we can draw $n_k$ such that $n_k \geq N+ n_{k-1} , \mid x_{n_k}-x \mid \geq \epsilon$ and it means there exists ${x_{n_k}} \subset {x_n}$ such that $x_{n_k} \nrightarrow x$ and it is contradiction with assumption
d.$x_n \rightarrow x$ iff ${x_n}$ is bounded and x is cluster point of ${x_n}$
pf)1. If $x_n \rightarrow x$,then ${x_n}$ is bounded and x is the ony cluster point of ${x_n}$
$x_n$이 bounded 하다는 것은 trivial하다. $x_n$이 수렴할시 코시 시퀀스 이고, 코시 시퀀스는 bounded하다는 것을 생각하자. $x_n$이 수렴할 시 수렴점이 유일한 cluster point라는 것은 c의 증명에서 같이 했다. 따라서 넘어가자.
pf)2. If ${x_n}$ is bounded and x is the only cluster point of ${x}$,then $x_n \rightarrow x$
If ${x_n}$ is bounded, there exists subsequence ${x_{n_k}} \rightarrow y$ and by (b), y is cluster point of ${x_n}$. By assumption, x=y and if $x_n \nrightarrow x$, if means there is finitely many points in near x, but x is cluster so there is infinitely many points near x. There is contradiction if $x_n \nrightarrow x$, so $x_n \rightarrow x $
e. $x_n \rightarrow x$ , iff $\forall {x_{n_k}} \subset x_n , \exists {x_{n_{k_l}}} \subset {x_{n_k}}$ such that ${x_{n_{k_l}}} \rightarrow x$
이는 c를 이용함으로써 trivial하게 증명할 수 있다.
B. lim sup , lim inf
lim sup 혹은 lim inf라는 개념이 새로이 등장한다. 아무도 그런말은 안했지만 내가 이해하기로는 기존의 supremum,infimum이 수열 전체가 가질 수 있었던 최대값, 최소값의 개념이라면, limit supremum, limit infimum은 수열이 충분히 많이 진행했을 때(lim) 가지게 되는 값들의 집합(S) 중의 최대값, 최소값 이라고 이해된다.
정확한 수리적인 정의는 다음과 같다.
For Sequence ${x_n}$ , $S := {s \in \d R;s $ is cluster point of $ {x_n} }$,
$\limsup \ x_n := Sup \ S $
$\liminf \ x_n := inf \ S $
이 lim sup에 대해서는 다음과 같은 property가 존재한다.
${x_n}$ is bounded above and $b = \limsup x_n$ ,iff
- $\forall \epsilon >0 , \exists N \in \d N$ such that $ b-\epsilon<x_n $ $\forall n \geq N$ and
- $\forall \epsilon >0 ,\forall N \in \d N, \exists n$ such that $x_n < b+ \epsilon , n \geq N$
이는 $(b-\epsilon,\infty)$의 구간에는 무한개의 점이 존재하고 $(b+ \epsilon, \infty)$의 구간에는 유한개의 점이 존재하는 것을 함의한다.
1.6 Other
$\d R^n = {(x_1,x_2,…x_n) \mid x_i \in \d R , i =1,2,…n}$ (Vector Space)
$\parallel x \parallel = \sqrt{x_1^2+x_2^2+…+x_n^2}$ (Norm)
$\parallel x \parallel_1 = \mid x_1 \mid + \mid x_2 \mid + … + \mid x_n \mid $
$\parallel x \parallel_{\infty} = max(\mid x_1 \mid ,\mid x_2 \mid, …,\mid x_n \mid)$
$\d C = {x+iy \mid x,y \in \d R , i^2 =-1}$ : Complex Number
이는 addition axiom과 multiplication axiom은 만족하지만, order axiom은 만족하지 않는다.
$\d R \subset \d C$