편의상 반말을 사용하겠습니다.
책에 나오는 정리와 증명은 다음과 같음.
정리 1.11 유한차원 벡터공간 V에 대하여 부분공간 W는 유한차원이고, dim(W) <= dim(V) 이다. 특히 dim(W)
=dim(V)이면 V=W 이다.
증명. dim(V)=n이라 하자. W={0}이면 W는 유한차원이고 dim(W)=0<=n 이다. 그렇지 않으면 W는 영이 아닌 벡터 x1을 가지고, {x1}은 일차독립이다. {x1,x2,...xk}가 일차독립이 되도록 W에서 벡터 x1,x2,...,xk를 순차적으로 하나씩 꺼내자. V의 일차독립인 부분집합은 n개를 초과하는 벡터를 가질 수 없으므로 이과정은 k<=n인 k에서 멈춘다. ...(생략)...
이 증명에서 제시된 알고리즘이 k<=n일때 멈춘다고 했는데, 생각해보면 일반적으로 W는 무한집합일 수 있으므로 벡터를 순차적으로 모두 꺼내는 방법이 없고, 이 경우에 k값이 얼만지 모르므로 종료하지 않는 알고리즘이라고 생각함. 유한 횟수 내에 종료하지 않는 알고리즘을 증명에 사용해도 수학적으로는 오류가 없나? 비슷한 논리가 Thm1.9에서도 사용됐는데 거기서는 유한집합에서 벡터를 순차적으로 꺼내는거라 종료가 보장됨.
dim V = n이라고 했으니 W가 유한차원이고, 그러니까 W의 일차독립인 벡터를 꺼낼 수 있는 것 아닌가? 무한집합인거랑 상관이 있음?
진짜 하나하나 다 꺼내보면서 일차독립인가? 아닌가?를 한땀한땀 파악하라는 게 아님. 만약 일차독립인 xk가 존재하지 않는다면 그 자체로 증명이 끝나고, 존재한다면 그런 xk를 하나 꺼내는 과정을 반복하라는 의미임. 그런 xk가 존재하는지 안 하는지 어떻게 파악하는지는 지금 알 바가 아니야
아 내가 컴공베이스라 튜링머신 관점에서 생각했네. 이건 걍 튜링머신을 초월한 어떤 오라클이 있는거라고 생각하는게 맞겠네.. 수학적으로 존재성은 보장되니까.. 고마웡!
존재성만 보장되면 (임의로 꺼내주는) 오라클님 써도됨
근데 "순차적" 이라는 표현은 자연수와 일대일대응이 될 수 있는 순서적 절차가 존재한다는 의미같아서 이 표현 자체는 부적절한듯?
W의 일차독립인 벡터들을 꺼내서 각각에 w1 w2 ... wk 로 이름을 붙이는 거니까 순차적이라고 표현해도 되지 않나?
벡터들 사이의 순서 자체가 정해져있다기보다 임의로 꺼낼 때마다 거기에 순서를 붙인다는 의미에서 쓴 표현 같기도 하고..
맞네... W-b에서 현재까지 구성된 b={x1,...,xk} 에 일차독립인 벡터를 하나 꺼내는 오라클이 주어졌다고 보는게 맞는듯.. 감사
근데 그냥 V의 기저 중 하나가 유한집합이고, W를 생성하니, 이 기저에 대해 Thm1.9 (S가 유한집합이고 V를 생성하면 S의 부분집합 중 V의 기저가 존재한다.) 적용하는게 깔끔한듯.