[정수론] 1-1. Numbers and Sequences

$\S$ Well-Ordering Property (WOP / 정렬 원리)란?

모든 공집합이 아닌 자연수 집합 $\mathbb{N}$의 부분 집합 $S$는 최소 원소(min element)가 존재한다.
( $\forall$ $S \subset \mathbb{N}$ and $S \neq \varnothing$, $S$ has min element.)

 

정수론에서는 이를 공리로써 받아들인다.

 

이를 넓혀, 임의의 어떤 집합 $R$의 모든 공집합이 아닌 부분 집합 $S$가 항상 최소 원소를 가지고 있다면, 우리는 이 집합 $R$이 "Well-Ordered"돼있다고 이야기한다.

 

예를 들어 보자.

$\mathbb{N}$은 Well-Ordered 이다.	$\mathbb{Z}$는 not Well-Ordered 이다.
그 이유는 WOP.	그 이유는 부분 집합 $S$를 음의 정수로 잡는다면, 이 부분 집합에는 최소 원소가 없기 때문이다.

---

$\S$ WOP를 이용한 $\sqrt{2}$의 무리수 증명

 

Proof) $\bullet$ 귀류법(proof by contradiction) 사용

 

$\sqrt{2}$가 유리수라고 가정하자. 그러면 $a \in \mathbb{N}$ 이고 $b \in \mathbb{N}$인 어떤 $a,b$가 존재하여 $a/b = \sqrt{2}$를 만족시킨다.

 

WOP를 쓰기 위해서는 공집합이 아닌 $\mathbb{N}$의 부분 집합 $S$를 잡아줘야 한다.

그래서 $S$ $=$ $\{ k\sqrt{2} | k \in \mathbb{N}, k\sqrt{2} \in \mathbb{N} \}$ 이라고 해보자.

 

당연히, $\sqrt{2} = a/b$이므로, $a = b\sqrt{2}$이고, $a \in \mathbb{N}$, $b \in \mathbb{N}$이므로 $S \neq \varnothing$이다.

따라서, $S$는 최소 원소를 가지고 있다.

 

이 최소 원소를 $m$이라고 하자. 그리고, $S$의 정의에 의해, 어떤 $t \in \mathbb{N}$에 대해, $m = t\sqrt{2}$이다.

 

우리는 $m$보다 작은 원소가 $S$안에 들어 있음을 보여줌으로써, $S$가 최소 원소를 가지고 있지 않음을 보여주고자 한다.(이는 WOP와 모순이 생기는 지점이다.)

 

$m\sqrt{2} - m$을 생각해보자.

우리가 보여줄 것은 두 가지이다. 1. $(m\sqrt{2} - m) \in S$, 2.$m\sqrt{2} - m < m$

 

1. $(m\sqrt{2} - m) \in S$

먼저, $m > t$이고 $m \in \mathbb{N}$, $t \in\mathbb{N} $이므로, $(m-t) \in\mathbb{N}$이다.

따라서, $m\sqrt{2} - m$ $=$ $m\sqrt{2} - t\sqrt{2}$ $=$ $(m-t)\sqrt{2}$ $>$ $0$이고,$m\sqrt{2} - m$ $=$ $(2t - m) \in \mathbb{Z}$이므로, $(m\sqrt{2} - m) \in \mathbb{N}$이다.

따라서,$(m\sqrt{2} - m) \in S$

 

2.$m\sqrt{2} - m < m$

좌변의 $m$을 우변으로 넘기면 쉽게 확인할 수 있다.

 

 

최종적으로, $m\sqrt{2} - m$은 $m$보다 작으면서 $S$에 들어있는 원소이므로, WOP와 모순이 생긴다. $\blacksquare$

---

$\S$ Algebraic(대수적)이란?

 

어떤 수 $\alpha$가 algebraic하다는 것은 다음과 같은 말이다.

$a_n\alpha^{n} + a_{n-1}\alpha^{n-1} + \cdots + a_0 = 0$을 만족시키는 $a_0, a_1, \cdots , a_n$이 존재한다.

---

$\S$ Greatest Integer Function(최대 정수 함수)란?

어떤 수 $x$의 greatest integer(최대 정수)는 $\left \lfloor x \right \rfloor$와 같이 표시하고, 이 정수는 아래와 같은 조건을 만족시킨다.
$$\left \lfloor x \right \rfloor \leq x < \left \lfloor x \right \rfloor + 1$$

비슷한 함수로 Ceiling Function이 있으며 이는 $\left \lceil x \right \rceil$와 같이 표시하며, 아래와 같은 조건을 만족시킨다.

$$\left \lceil x \right \rceil - 1 < x \leq \left \lceil x \right \rceil$$

 

이를 이용하여 실수의 fractional part를 정의하는데, 이는 $x$에서 $\left \lfloor x \right \rfloor$를 뺀 값으로 정의한다. 또한, 이를 $\{x\}$로 표기한다.

$$\{x\} = x - \left \lfloor x \right \rfloor$$

 

greatest integer의 정의에 의하여, $0 \leq \{x\} < 1$이 항상 성립한다.

---

$\S$ Pigeonhole Principle(비둘기집 원리)란?

$k+1$개 이상의 대상이 $k$개의 구역에 담길 때, 적어도 한 구역은 2개 이상의 대상을 포함하고 있다.

Proof) $\bullet$ 귀류법(proof by contradiction) 사용

 

만약 모든 구역이 하나의 대상 또는 그 이하만을 포함하고 있다고 해보자. 그렇다면, 대상의 개수는 최대 $k$개가 된다.

이는 대상의 개수와 모순이다.

---

$\S$ Dirichlet's Approximation Theorem

 

Diophantine Approximation의 주된 관심은 임의의 실수를 유리수로 잘 근사하는 것이다.

 

근데 어떻게 하면 임의의 실수에 대한 유리수 근사를 "잘"할 수 있다는 것을 보장할 수 있을까?

 

이를 설명해주는 것이 Dirichlet's Approximation Theorem이다.

어떤 실수 $\alpha$에 대해, $\alpha$의 $1,2,\cdots,n$배수들 중에서 무조건 하나는, 가까운 정수와의 거리가 $1/n$보다 작다.
($\forall \alpha \in \mathbb{R}$ and $n \in \mathbb{N}$, $\exists a, b \in \mathbb{Z}$ with $1 \leq a \leq n$ s.t. $|a\alpha - b| < 1/n$.)

 

Proof) $\bullet$ Pigeonhole Principle(비둘기집 원리) 이용

 

$n+1$개의 숫자 $0, \{ \alpha \}, \{ 2 \alpha \}, \cdots, \{ n \alpha \}$를 생각해보자.

 

이 숫자들은 모두 $j \alpha$ ($0 \leq j \leq n$)의 fractional part이므로, $0 \leq j \leq n, j \in \mathbb{Z}$에 대해 $0 \leq \{ j\alpha \} < 1$라는 사실을 알 수 있다.

 

이때, 구간 $[0, 1)$을 모든 $0 \leq k < n, k \in \mathbb{Z}$에 대해 $[k/n, (k+1)/n)$이 되도록 $n$개의 구간으로 균등하게 나눠보자.

 

Pigeonhole Principle에 의해, 이러한 구간들 중 적어도 하나는 두 개의 숫자를 포함하고 있다.

 

이 말은 곧, 어떤 $0 \leq a_0 < a_1 \leq n$에 대해 $a_0, a_1 \in \mathbb{Z}$가 존재해서, $\{ a_0 \alpha \}$와 $\{ a_1 \alpha \}$가 길이가 $1/n$인 구간에 같이 속해있다는 말이다.

 

따라서, $| \{ a_1 \alpha \} - \{ a_0 \alpha \}| < 1/n$이 성립된다.

 

$|\{ a_1 \alpha \} - \{ a_0 \alpha \}|$ $=$ $| (a_1 \alpha - \left \lfloor a_1 \alpha \right \rfloor) - (a_0 \alpha - \left \lfloor a_0 \alpha \right \rfloor)|$ $=$ $| (a_1 - a_0) \alpha - (\left \lfloor a_1 \alpha \right \rfloor - \left \lfloor a_0 \alpha \right \rfloor)|$ $=$ $|a \alpha - b| < 1/n$. $\blacksquare$

---

$\S$ Countable과 Uncountable

$\bullet$ Countable이란?
$\mathbb{N}$과 1-1 Correspondence(일대일 대응)가 가능하면, 그 집합을 Countable하다고 한다.
다시 말해, 어떤 집합이 Sequence로 표현이 된다면, Sequence $a_i$는 Domain(정의역)이 $\mathbb{N}$인 함수이므로, 1-1 Correspondence가 가능하다.
$\bullet$ Uncountable이란?
Countable하지 않은 집합을 Uncountable이라고 한다.

 

$\bullet$ $\mathbb{Z}$ is Countable.

Proof) $a_1 = 0, a_{2n} = n, a_{2n+1} = -n$이라고 정의하면 1-1 Correspondence가 가능하므로 가능하다.

 

$\bullet$ $\mathbb{Q}$ is Countable.

Proof)

다음과 같이 2d-array로 숫자를 배열한 뒤, 대각선 방향을 따라가면 1-1 Correspondence를 만들어 낼 수 있으므로 Countable이다.

---

$\S$생각해 볼 만한 내용들

 

$\bullet$ WOP를 사용한 $\sqrt{3}$의 무리수 증명

$\bullet$ Dirichlet's Approximation Theorem의 강화버전($1/n$대신 $1/(n+1)$이 들어간 버전) 증명