5회 실험 · 최소상계#
이 실험
짝 서술 |
|
확인하는 것 |
상계는 무수히 많고 최소상계는 하나이며, 유리수 안에서는 그 하나가 없다 |
서술 파트에서 상계(upper bound)와 최소상계(least upper bound)를 정의하고 완비성 공리(completeness axiom)를 서술하였다. 그리고 유리수 전체의 집합이 그 공리를 만족하지 않는다는 것을 정리 16로 보였다.
여기서는 그 논증을 숫자로 되짚는다. 특히 정리 16의 증명에 나오는 식 (5.3)은 유리수 상계를 하나 받아 더 작은 유리수 상계를 만들어 내는 장치이다. 이 장치를 그대로 함수로 옮겨 돌려 보면, 상계가 계속 작아지는데도 멈출 곳이 없다는 사정이 눈에 보인다.
완비성 공리는 계산으로 확인할 수 있는 종류의 명제가 아니다. 유한 번의 계산은 “아직 최소상계를 못 찾았다”까지만 말한다. 그래서 이 실험에서 하는 일은 증명을 대신하는 것이 아니라, 증명이 무엇을 하고 있는지 각 단계를 숫자로 따라가 보는 것이다.
서술 파트의 내용 |
여기서 확인하는 방법 |
|---|---|
정의 7 의 두 조건 |
상계 후보를 여럿 놓고 조건 1과 조건 2를 따로 시험한다 |
정리 14 조건 3 |
\(\epsilon\) 을 줄여 가며 \(b-\epsilon\) 을 넘는 원소를 실제로 찾는다 |
|
|
상계를 개선하는 사상을 직접 만들어 돌리고, 두 항등식을 sympy 로 확인한다 |
|
실수 범위에서는 최소상계가 나오고 그 값이 유리수가 아님을 확인한다 |
|
\(1/n < \epsilon\) 인 가장 작은 \(n\) 을 직접 찾고 1회의 논증에 대입한다 |
0. 준비#
이 회차에서 쓸 것만 불러온다. 색은 회차마다 뜻이 고정되어 있다.
1. 상계는 무수히 많고 최소상계는 하나이다#
다음 집합을 본다.
원소가 무한히 많다. 모든 원소가 \(1\)보다 작고, \(1\)보다 작은 수는 어느 것도 상계가 될 수 없다. 따라서 \(\sup S = 1\)이고 \(1 \notin S\)이다.
컴퓨터로는 무한집합을 통째로 다룰 수 없으므로 앞의 열두 개만 잡아 시험한다. 그러면 정의 7의 조건 1은 이 유한한 표본에 대해서만 확인되는 셈이다. 이 점은 뒤에서 다시 짚는다.
# Section 1: the set S = { 1 - 2 ** (-k) : k = 1, 2, 3, ... } and candidate upper bounds
K_SHOWN = 12
k_values = np.arange(1, K_SHOWN + 1, dtype=float)
elements = 1.0 - 2.0 ** (-k_values)
def is_upper_bound(c, sample):
"""True when every entry of sample is less than or equal to c."""
return bool(np.all(sample <= c))
print(f"largest element shown : {elements.max():.12f}")
print(f"number shown : {len(elements)}")
print()
print(f"{'candidate c':>12} {'upper bound of the sample':>28}")
for c in [0.9, 0.99, 1.0, 1.2, 1.5]:
print(f"{c:>12.4f} {str(is_upper_bound(c, elements)):>28}")
largest element shown : 0.999755859375
number shown : 12
candidate c upper bound of the sample
0.9000 False
0.9900 False
1.0000 True
1.2000 True
1.5000 True
\(0.9\)와 \(0.99\)는 조건 1에서 이미 걸린다. 표본 안에 그보다 큰 원소가 있기 때문이다. 나머지 셋은 모두 상계이고, 그중 가장 작은 것이 \(1\)이다. 상계 후보를 아무리 많이 나열해도 조건 2가 지목하는 것은 언제나 하나뿐이며, 이 유일성은 정리 15가 보장한다.
# Section 1: elements below the axis, some upper bounds above it
upper_samples = np.linspace(1.0, 1.6, 13)
fig, ax = plt.subplots(figsize=(9, 2.6))
ax.scatter(upper_samples, np.full_like(upper_samples, 0.05), s=30,
color=C_UPPER, label="some upper bounds", zorder=3)
ax.scatter(elements, np.zeros_like(elements), s=45,
color=C_LOWER, label="elements of S", zorder=4)
ax.axvline(1.0, color=C_DIFF, lw=1.5, label="sup S = 1")
ax.set_yticks([])
ax.set_xlim(0.3, 1.7)
ax.set_ylim(-0.04, 0.11)
ax.set_xlabel("x")
ax.set_title("elements and upper bounds on the line")
ax.grid(True, axis="x")
ax.legend(loc="upper left")
plt.tight_layout()
plt.show()
파란 점이 오른쪽으로 몰리지만 빨간 선을 넘지 않는다. 주황 점은 빨간 선과 겹치거나 그 오른쪽에 있다. 맨 왼쪽 주황 점이 빨간 선과 정확히 겹치는 것은 \(1\) 자신도 상계이기 때문이다. 최소상계는 상계 중 가장 작은 것이지 상계에서 빠지는 값이 아니다. 그리고 빨간 선 자리의 값 \(1\)은 파란 점이 아니다. 최댓값(maximum)은 집합에 속해야 하므로 \(S\)에는 최댓값이 없고, 그래도 최소상계는 있다.
2. \(\epsilon\) 서술을 직접 시험한다#
정리 14의 조건 3은 “\(\epsilon > 0\)이 무엇이든 \(b - \epsilon < x\)인 \(x \in S\)가 있다”이다. \(b = 1\)로 두고 \(\epsilon\)을 줄여 가며 그런 원소를 실제로 찾아본다. \(1 - 2^{-k} > 1 - \epsilon\)은 \(2^{-k} < \epsilon\)과 같으므로, \(k\)를 \(1\)부터 올려 가며 처음 걸리는 것을 취하면 된다.
# Section 2: condition 3 of thm-5-eps, tested at b = 1
def first_element_above(threshold, k_limit=200):
"""Smallest k with 1 - 2 ** (-k) > threshold. Returns (k, element)."""
for k in range(1, k_limit + 1):
value = 1.0 - 2.0 ** (-k)
if value > threshold:
return k, value
raise ValueError("no element found below the given limit")
b = 1.0
print(f"{'eps':>10} {'b - eps':>18} {'k':>4} {'element':>18} {'above b - eps':>14}")
for eps in [0.5, 0.1, 0.01, 1e-4, 1e-8]:
k, value = first_element_above(b - eps)
print(f"{eps:>10.0e} {b - eps:>18.12f} {k:>4} {value:>18.12f}"
f" {str(value > b - eps):>14}")
eps b - eps k element above b - eps
5e-01 0.500000000000 2 0.750000000000 True
1e-01 0.900000000000 4 0.937500000000 True
1e-02 0.990000000000 7 0.992187500000 True
1e-04 0.999900000000 14 0.999938964844 True
1e-08 0.999999990000 27 0.999999992549 True
\(\epsilon\)을 \(10^{8}\)분의 \(1\)까지 줄여도 걸리는 원소가 있다. \(k\)가 늘어나는 속도도 눈여겨볼 만하다. \(\epsilon\)이 \(10^8\)배 작아지는 동안 \(k\)는 \(2\)에서 \(27\)로 늘었을 뿐이다. \(2^{-k} < \epsilon\)을 \(k\)에 대하여 풀면 \(k\)가 \(\log_2(1/\epsilon)\) 언저리이므로, \(\epsilon\)을 반으로 줄일 때마다 \(k\)는 하나씩만 늘어난다. 이것이 조건 3이 말하는 상황이다.
여기서 정리 14의 전제를 빠뜨리면 안 된다. 정리는 “\(b\)가 \(S\)의 상계라 하자”로 시작한다. 이 전제를 떼면 조건 3만으로는 최소상계를 가려내지 못한다.
# Section 2: condition 3 alone does not identify the supremum
b_bad = 0.99
eps = 0.005
k, value = first_element_above(b_bad - eps)
print(f"b = {b_bad}, eps = {eps}")
print(f" element found : {value:.12f}")
print(f" b - eps : {b_bad - eps:.12f}")
print(f" condition 3 holds here : {value > b_bad - eps}")
print(f" but is b an upper bound : {is_upper_bound(b_bad, elements)}")
b = 0.99, eps = 0.005
element found : 0.992187500000
b - eps : 0.985000000000
condition 3 holds here : True
but is b an upper bound : False
\(0.99\)는 조건 3을 만족하지만 상계가 아니다. 상계가 아닌 수는 애초에 최소상계 후보가 아니다. 정리 14가 세 조건을 동치라고 말할 수 있는 것은 \(b\)가 상계라는 전제 아래에서이다.
3. 유리수 안에서 상계를 줄인다#
이제 정리 16의 집합으로 옮긴다.
구간 \([1, 2]\)를 반씩 자른다. 가운데 값의 제곱이 \(2\)보다 작으면 그 값은 \(S\)의 원소이므로 왼쪽 끝으로 삼고, \(2\)보다 크면 상계이므로 오른쪽 끝으로 삼는다. Fraction으로 계산하므로 모든 값이 오차 없는 유리수이다.
# Section 3: bisection inside the rationals
left, right = Fraction(1), Fraction(2)
STEPS = 12
print(f"{'step':>4} {'left (in S)':>22} {'right (upper bound)':>22}"
f" {'right ** 2':>20} {'== 2':>6}")
for step in range(1, STEPS + 1):
middle = (left + right) / 2
if middle * middle < 2:
left = middle
else:
right = middle
is_exact = (right * right == 2)
print(f"{step:>4} {str(left):>22} {str(right):>22}"
f" {float(right * right):>20.15f} {str(is_exact):>6}")
step left (in S) right (upper bound) right ** 2 == 2
1 1 3/2 2.250000000000000 False
2 5/4 3/2 2.250000000000000 False
3 11/8 3/2 2.250000000000000 False
4 11/8 23/16 2.066406250000000 False
5 45/32 23/16 2.066406250000000 False
6 45/32 91/64 2.021728515625000 False
7 181/128 91/64 2.021728515625000 False
8 181/128 363/256 2.010635375976562 False
9 181/128 725/512 2.005100250244141 False
10 181/128 1449/1024 2.002335548400879 False
11 181/128 2897/2048 2.000953912734985 False
12 181/128 5793/4096 2.000263273715973 False
오른쪽 값은 줄어들거나 그대로이고, 왼쪽 끝과 오른쪽 끝 사이의 간격은 단계마다 반이 된다. 그런데도 어느 단계에서도 멈추지 않는다. == 2 열에 True가 나오는 단계가 없다. 3회 정리 8에 의하여 제곱이 정확히 \(2\)인 유리수가 없기 때문이다.
왼쪽 값이 7단계 이후로 \(181/128\)에 머무는 것도 눈여겨볼 만하다. 8단계부터는 가운데 값의 제곱이 매번 \(2\)보다 커서 오른쪽 끝만 갈아 치우고 있다는 뜻이다. 그래도 왼쪽 끝은 여전히 \(S\)의 원소이고 오른쪽 끝은 여전히 상계이다.
이 표는 유리수 안에 최소상계가 없다는 것을 증명하지 못한다. 열두 단계를 보였을 뿐이고, 백 단계를 더 해도 사정은 같다. 증명은 다음 절이 다루는 (5.3)이 한다.
4. 상계를 개선하는 사상 (5.3)#
정리 16의 증명은 유리수 상계 \(b\)에서 다음 값을 만든다.
\(b\)가 유리수이면 \(b'\)도 유리수이다. 증명이 쓰는 사실은 두 개이다. (5.4)에 의하여 \(b' - b\)의 부호가 \(2 - b^2\)의 부호와 같고, (5.5)에 의하여 \(b'^2 - 2\)의 부호가 \(b^2 - 2\)의 부호와 같다는 것이다.
이 사상을 함수로 옮겨 두 곳에서 출발시킨다. \(b = 2\)는 \(b^2 > 2\)인 상계이고, \(b = 1\)은 \(b^2 < 2\)인 \(S\)의 원소이다.
# Section 4: the map of equation (5.3) applied repeatedly to rationals
def improve(b):
"""The map (5.3). Sends a rational to a rational."""
return (2 * b + 2) / (b + 2)
def iterate_map(start, steps):
"""Apply improve repeatedly and collect every term."""
terms = [start]
for _ in range(steps):
terms.append(improve(terms[-1]))
return terms
def print_track(title, terms):
"""Print one track of the iteration as a table."""
print(title)
print(f"{'step':>4} {'b':>22} {'b ** 2':>20} {'b ** 2 > 2':>12}")
for step, b in enumerate(terms):
print(f"{step:>4} {str(b):>22} {float(b * b):>20.15f}"
f" {str(b * b > 2):>12}")
print()
STEPS = 8
upper_terms = iterate_map(Fraction(2), STEPS)
lower_terms = iterate_map(Fraction(1), STEPS)
print_track("start at b = 2, where b ** 2 > 2", upper_terms)
print_track("start at b = 1, where b ** 2 < 2", lower_terms)
start at b = 2, where b ** 2 > 2
step b b ** 2 b ** 2 > 2
0 2 4.000000000000000 True
1 3/2 2.250000000000000 True
2 10/7 2.040816326530612 True
3 17/12 2.006944444444445 True
4 58/41 2.001189767995241 True
5 99/70 2.000204081632653 True
6 338/239 2.000035013392623 True
7 577/408 2.000006007304883 True
8 1970/1393 2.000001030689289 True
start at b = 1, where b ** 2 < 2
step b b ** 2 b ** 2 > 2
0 1 1.000000000000000 False
1 4/3 1.777777777777778 False
2 7/5 1.960000000000000 False
3 24/17 1.993079584775086 False
4 41/29 1.998810939357907 False
5 140/99 1.999795939189879 False
6 239/169 1.999964987220335 False
7 816/577 1.999993992713161 False
8 1393/985 1.999998969311242 False
위쪽 표에서 b ** 2 > 2 열은 계속 True이고 \(b\)는 계속 작아진다. 상계를 받아 더 작은 상계를 돌려준 것이므로, 어떤 유리수 상계를 가져와도 최소가 아니다. 아래쪽 표에서는 b ** 2 > 2 열이 계속 False이고 \(b\)는 계속 커진다. \(S\)의 원소를 받아 더 큰 원소를 돌려주었으므로, \(b^2 < 2\)인 양의 유리수는 상계가 아니다.
두 경우를 합치면 양의 유리수 상계는 하나도 최소상계가 아니다. 이것이 정리 16의 논증이다.
# Section 4: the distance to sqrt(2) keeps shrinking but never reaches zero
root_two = float(np.sqrt(2.0))
steps_axis = np.arange(len(upper_terms))
upper_gap = np.array([abs(float(b) - root_two) for b in upper_terms])
lower_gap = np.array([abs(float(b) - root_two) for b in lower_terms])
fig, ax = plt.subplots(figsize=(7.5, 4.2))
ax.semilogy(steps_axis, upper_gap, "o-", color=C_UPPER,
label="start b = 2 (upper bounds)")
ax.semilogy(steps_axis, lower_gap, "o-", color=C_LOWER,
label="start b = 1 (elements of S)")
ax.set_xlabel("step")
ax.set_ylabel("distance to sqrt(2)")
ax.set_title("the map (2b + 2) / (b + 2) on rationals")
ax.legend()
plt.tight_layout()
plt.show()
두 곡선이 아래로 곧게 내려간다. 세로축이 로그 눈금이므로, 어느 단계에서도 거리가 \(0\)이 되지 않는다는 뜻이다. 거리가 \(0\)이 되려면 제곱이 정확히 \(2\)인 유리수가 있어야 한다.
5. 실수 범위에서는 최소상계가 있다#
공리 1는 위로 유계인 공집합 아닌 집합에 최소상계가 있다고 말한다. 3절과 똑같은 두 조건 \(x > 0\)과 \(x^2 < 2\)를 걸되 바탕을 유리수에서 실수로 바꾸어 sympy 에 넘겨 본다. 달라지는 것은 바탕 집합 하나뿐이다.
# Section 5: the least upper bound of { x > 0 : x ** 2 < 2 } over the reals
x = sp.Symbol("x", real=True)
positive_reals = sp.Interval.open(0, sp.oo)
solution_set = sp.solveset(x ** 2 < 2, x, domain=positive_reals)
print("solution set of x > 0 and x ** 2 < 2 over the reals")
sp.pprint(solution_set)
supremum = solution_set.sup
print()
print(f"least upper bound : {supremum}")
print(f"as a decimal : {float(supremum):.15f}")
print(f"belongs to the set : {supremum in solution_set}")
print(f"is rational : {supremum.is_rational}")
solution set of x > 0 and x ** 2 < 2 over the reals
(0, √2)
least upper bound : sqrt(2)
as a decimal : 1.414213562373095
belongs to the set : False
is rational : False
출력의 세 대목이 각각 서술 쪽의 세 가지에 대응한다. 최소상계가 나온 것은 공리 1 때문이고, 그것이 집합에 속하지 않는 것은 최댓값과 최소상계의 차이이며, 그것이 유리수가 아닌 것은 3회 정리 8이다.
증명에 쓰인 두 항등식 (5.4)와 (5.5)도 기호로 확인할 수 있다. 두 식의 양변 차이가 \(0\)으로 정리되면 항등식이 맞는 것이다.
# Section 5: the identities (5.4) and (5.5) checked symbolically
b_sym = sp.Symbol("b", positive=True)
b_next = (2 * b_sym + 2) / (b_sym + 2)
residual_54 = sp.simplify(b_next - b_sym - (2 - b_sym ** 2) / (b_sym + 2))
residual_55 = sp.simplify(b_next ** 2 - 2
- 2 * (b_sym ** 2 - 2) / (b_sym + 2) ** 2)
print(f"residual of (5.4) : {residual_54}")
print(f"residual of (5.5) : {residual_55}")
fixed_points = sp.solve(sp.Eq(b_next, b_sym), b_sym)
print(f"fixed points of the map : {fixed_points}")
residual of (5.4) : 0
residual of (5.5) : 0
fixed points of the map : [sqrt(2)]
두 잔차가 모두 \(0\)이다. 마지막 줄은 이 사상을 움직이지 않는 값이 \(\sqrt{2}\)뿐이라는 것을 말한다. 4절의 반복이 어디로 다가가고 있었는지가 여기서 드러난다. 그 값이 유리수가 아니므로 유리수 안에서는 도달할 곳이 없다.
6. 아르키메데스 성질과 1회의 빈틈#
따름정리 4은 \(\epsilon > 0\)이 무엇이든 \(1/n < \epsilon\)인 자연수 \(n\)이 있다는 것이다. 그런 \(n\) 중 가장 작은 것을 직접 찾아본다. \(n\)을 두 배씩 키워 조건을 만족하는 구간을 먼저 잡고, 그 안에서 이분법으로 좁힌다.
# Section 6: the smallest n with 1 / n < eps, by doubling and then bisection
def first_n_with_reciprocal_below(eps):
"""Smallest positive integer n with Fraction(1, n) < eps."""
low, high = 1, 1
while Fraction(1, high) >= eps:
low, high = high, 2 * high
while high - low > 1:
middle = (low + high) // 2
if Fraction(1, middle) < eps:
high = middle
else:
low = middle
return high
print(f"{'eps':>12} {'smallest n':>12} {'1 / n':>22} {'1 / n < eps':>12}")
for eps in [Fraction(1, 2), Fraction(3, 7), Fraction(1, 10),
Fraction(1, 1000), Fraction(1, 10 ** 6)]:
n = first_n_with_reciprocal_below(eps)
print(f"{str(eps):>12} {n:>12} {float(Fraction(1, n)):>22.15f}"
f" {str(Fraction(1, n) < eps):>12}")
eps smallest n 1 / n 1 / n < eps
1/2 3 0.333333333333333 True
3/7 3 0.333333333333333 True
1/10 11 0.090909090909091 True
1/1000 1001 0.000999000999001 True
1/1000000 1000001 0.000000999999000 True
\(\epsilon\)이 아무리 작아도 \(n\)이 있다. 그리고 그런 \(n\) 중 가장 작은 것이 하나로 정해진다.
이 따름정리는 1회에서 근거 없이 쓴 사실을 메운다. 1회 3절에서 우리는 “양수 \(d\)가 무엇이든 \(b^3/n < d\)가 되는 자연수 \(n\)이 있다”를 썼다. 따름정리 4을 \(\epsilon = d/b^3\)에 적용하면 된다.
# Section 6: filling the gap left in lecture 1, b ** 3 / n < d
d = Fraction(1, 1000)
for b_len in [Fraction(1), Fraction(2), Fraction(5, 2)]:
eps = d / b_len ** 3
n = first_n_with_reciprocal_below(eps)
value = b_len ** 3 / n
print(f"b = {str(b_len):>5} d = {str(d):>6} eps = d / b ** 3 = {str(eps):>10}")
print(f" n = {n:>8} b ** 3 / n = {float(value):.12f}"
f" less than d : {value < d}")
b = 1 d = 1/1000 eps = d / b ** 3 = 1/1000
n = 1001 b ** 3 / n = 0.000999000999 less than d : True
b = 2 d = 1/1000 eps = d / b ** 3 = 1/8000
n = 8001 b ** 3 / n = 0.000999875016 less than d : True
b = 5/2 d = 1/1000 eps = d / b ** 3 = 1/15625
n = 15626 b ** 3 / n = 0.000999936004 less than d : True
\(b\)를 바꾸어도 조건을 만족하는 \(n\)이 언제나 나온다. 1회에서 넓이를 구할 때 계단의 개수를 얼마든지 늘릴 수 있다고 한 것의 근거가 이것이며, 그 근거는 정리 17를 거쳐 공리 1까지 올라간다.
마치며#
1절과 2절에서 정의 7의 두 조건과 정리 14의 \(\epsilon\) 서술을 시험하였다. 조건 3만으로는 최소상계를 가려내지 못하고 “\(b\)가 상계이다”라는 전제가 반드시 필요하다는 것도 함께 확인하였다.
3절과 4절에서 유리수 안의 사정을 보았다. 이분법으로 상계를 줄여도 멈추지 않았고, (5.3)의 사상은 어떤 유리수 상계를 받아도 더 작은 유리수 상계를 돌려주었다. 유한 번의 계산은 최소상계가 없다는 것을 증명하지 못하지만, (5.3)을 함수로 옮겨 놓고 보면 증명이 무엇을 하는 장치인지가 분명해진다. 5절에서 실수 범위로 넘어가자 최소상계가 나왔고 그 값은 유리수가 아니었다.
6절에서는 따름정리 4을 써서 1회에서 미뤄 둔 사실을 메웠다. 계단을 얼마든지 잘게 나눌 수 있다는 것은 당연한 사실이 아니라 완비성 공리의 결과이다.
서술 파트가 주장한 것과 이 노트북에서 그것을 확인한 코드를 나란히 둔다.
서술 파트의 내용 |
이 노트북의 코드 |
|---|---|
정의 7 의 조건 1, 상계이다 |
|
정리 14 의 조건 3, \(b-\epsilon\) 을 넘는 원소가 있다 |
|
(5.3) 은 유리수 상계를 더 작은 유리수 상계로 보낸다 |
|
공리 1, 실수 안에는 최소상계가 있다 |
5절의 |
따름정리 4, \(1/n < \epsilon\) 인 \(n\) 이 있다 |
|
더 해 볼 것#
1절의
K_SHOWN을 \(30\)으로 바꾸어 본다. 후보 \(0.99\)가 상계가 아니라는 판정은 그대로인가.K_SHOWN을 \(5\)로 줄이면 어떻게 되는가. 유한한 표본으로 상계 여부를 판정할 때 무엇이 위험한지 생각해 보자.4절의
iterate_map출발값을Fraction(3),Fraction(1, 2),Fraction(7, 5)로 바꾸어 본다. 출발값의 제곱이 \(2\)보다 큰지 작은지에 따라 표의b ** 2 > 2열이 어떻게 달라지는가. \(2\)보다 큰 쪽에서 출발하면 항상 상계만 나오는가.정리 18을 직접 확인해 보자. \(a\)와 \(b\)를 \(-3\)부터 \(3\)까지 \(0.5\) 간격으로 훑으며 \(|a+b|\)와 \(|a|+|b|\)를 비교하고, 등호가 성립하는 쌍만 모아 본다. 그 쌍들의 공통점은 무엇인가. 같은 방식으로 따름정리 5도 확인할 수 있다.
짝이 되는 서술