하기 싫은 공부를 더 이상 미룰 수 없다.
과연 컴퓨터로 임의의 숫자를 표현하는게 가능한지 증명을 해보자.
요즘 메타버스 어쩌구 하던데, 과연 컴퓨터는 현실세계의 데이터를 담아내는 것이 이론적으로 가능한 것인가?
결론: 컴퓨터의 메모리가 무한히 크고, CPU 연산량이 무한히 빠르면 가능하다
하지만 당연하게도 현실적으로 불가능하다.
Reference 링크 에 적힌 책을 읽고 요약 정리해보았다.
Definition 1.1 (one-to-one)
function f:S→T is injective if
∀x,x′∈S, x=x′⇒f(x)=f(x′)
Lemma 1.2
S,T=∅ and f:S→T is one to one.
Then, ∃ onto function g:T→S s.t g(f(s))=s for ∀s∈S
Proof
Choose some s0∈S and define g:T→S as follows.
g(t)={ss0if ∃s∈S s.t f(s)=tif ∄s∈S s.t f(s)=t
Since f is one-to-one, ∀s,s′∈S,s=s′⇒f(s)=f(s′).
Let t=f(s),t′=f(s′). Then, t=t′⇒g(t)=g(t′).
∴ g is a function.
Since f is a function, ∀s∈S,∃t∈T s.t f(s)=t.
⇒ ∀s∈S,∃t∈T s.t g(t)=g(f(s))=s
∴ g is onto.
Definition 2.7
{0,1}∗ = set of all finite sequences of bits = set of all bit strings
{0,1}∞ = set of all infinite sequences of bits
Let f:N→{0,1}
Then, (f(0),f(1),f(2),…) is an infinite sequence of bits
⇒f is an infinite sequence of bits
∴{0,1}∞={f∣f:N→{0,1}}
Lemma 2.8
∄ one-to-one map FtS:{0,1}∞→{0,1}∗
proof
∄ one-to-one map FtS:{0,1}∞→{0,1}∗
⇔∄ onto function StF:{0,1}∗→{0,1}∞
Suppose ∃ onto function StF:{0,1}∗→{0,1}∞
⇒∀d∈{0,1}∞,∃x∈{0,1}∗ s.t StF(x)=d
Define d∈{0,1}∞ as follows.
d(n)=1−StF(xn)(n)
Where n∈N, xn∈{0,1}∗, and
StF(xn)(n)∈{0,1} is the n-th bit of StF(xn)∈{0,1}∞.
Since d is a "diagonal argument", ∄x∈{0,1}∗ s.t StF(x)=d
∴ Proved by contradiction.
Lemma 2.9
∃ one-to-one map FtR:{0,1}∞→R
proof
For f∈{0,1}∞, Define FtR as follows.
FtR(f)=i=0∑∞f(i)⋅10−i=f(0).f(1)f(2)…
Then, FtR(f)∈R and FtR is one-to-one.
Theorem 2.5 (Cantor's Theorem)
The reals are uncountable.
proof
The reals are uncountable.
⇔∄ onto function NtR:N→R
⇔∄ one-to-one function RtS:R→{0,1}∗
Suppose there exists one-to-one function RtS.
From Lemma 2.9, ∃ one-to-one map FtR:{0,1}∞→R
Let FtS=FtR∘RtS
Then, FtS:{0,1}∞→{0,1}∗ is an one-to-one function.
However, FtS can not be one-to-one from Lemma 2.8.
∴ Proved by contradiction.