자연수를 정의할때 마지막으로 쓰이는 핵심공리가
수학적귀납법 공리인데,
TAO 해석학에서는 다음과 같이 정의를 하더라고
P(n)이 임의의 자연수 n에 대해 정의되는 임의의 성질이라고 가정하고, P(0)가 참이고, 임의의 자연수 n에 대해
P(n)이 참이면 P(n++)도 참이라고 가정하자.
그렇다면 모든 자연수 n에 대해 P(n)이 참이다
라는 "공리"로 정의를 하는데
이 공리덕에
0->1->2->3->4->...
0'->1'->2'->...
와같이 두개이상의 체인을 가질수는없다 (0'은 0으로부터 다음수연산을 해서얻을수없는 독립된체인의시작점)
를 보인다는데..
어떤 특수한 수 0'이 있어서
P(0)가 참이고,임의의 자연수 n에 대해 P(n)이 참이면 P(n++)도 참이 되는
"임의의 성질" P(n)에 대하여
항상 P(0')이 참이되게 한다면, 독립된 체인이 두개이상 존재하는거아님? 그럴 가능성이없다는걸 증명하고싶은데 난 방법을 모르겠음.
Tao해석학의 정의인 "성질"이라는 게 너무 모호해서 이런건가
Tao해석학에선 이리정의하더라구. 왜이런거지
- dc official App
수학적 귀납법에서 P(n)을 n ∈ N으로 두면 N = {0} ∪ {n+ | n ∈ N}을 얻을 수 있음. 그래서 0부터 시작하는 체인과 독립된 체인의 시작점 0'에 대해서 0' ∈ N이 될 수는 없음.
성질이라는 용어는 모호하지 않음. 여기서는 성질 P(n)을 n에 대한 1차 논리식으로 쓴 거
nㅌN이 P(n)이면 왜 N이 저렇게정의됨? 아직 정의하기전인데 저게 되는 보장이잇나 - dc App
저렇게 된다는 건 이미 0이 유일한 체인의시작점이란걸 아는상태에서해야되는거같아서 그부분이 궁금한거라가지구 - dc App
정의라기보다는 공리로 증명된 정리임. S = {0} ∪ {n+ | n ∈N}이라 하셈. 0 ∈ S이고, n ∈ N이면 n+ ∈ N이므로 S ⊂ N은 자명함. 반대로 N ⊂ S를 보이겠음. n ∈ N이라 하셈. 만약 n = 0이면 n ∈ S임. n ≠ 0이면 어떤 k ∈ N에 대해서 k+ = n이고, 따라서 S의 정의에 따라 n ∈ S임. 그러므로 N ⊂ S임. N ⊂ S, S ⊂ N이므로 N = S = {0} ∪ {n+ | n ∈N}임
중간에 n ∈ N이 n ≠ 0이면 어떤 k ∈ N에 대해서 k+ = n이라는 거는 증명없이 썼음
n이 0이 아니면 어떤 kㅌN에 대해 n=k+이다를 수학적귀납공리로 보이는 과정이궁금함 - dc App
그 부분이 제일 궁금한거라서 결국에. n이 0이아니면 어떤 kㅌN에 대해 k+=n이다 라고 말할려면 n이 다른 체인의 시작점(즉 0')이 아닐때만 가능한논리니까. 다른 체인의 시작점(0')이 없음을 수학적귀납공리로 보이는게 핵심같다느껴서 - dc App
이것도 자명함. P(n)을 "n≠0 → 어떤 k ∈ N에 대해 k+ = n"이라 하셈. P(0)은 공허하게(vacuously) 참임. P(n)을 가정하셈.(사실 이 증명에서는 P(n)이라는 귀납적 가정을 안 씀) k = n이라고 놓으면 k+ = n+임. 따라서 P(n) → P(n+)도 참임. 따라서 수학적 귀납법 공리에 의해 모든 자연수 n에 대해 P(n)이 성립함
@ㅆㅅ 아 이게 핵심이네. 반례가 되는 P(n)의 직접적 구성을 저리 할 수가 있어서 다른 체인의 비존재가 증명되는거구나
내가 의문이었던거는 모든 성질 P에 대하여 "P(0),P(1),P(2),P(3),..이 참이면, 모든 자연수 n에 대해 P(n)이 참이다" 가 항상 성립한다고해서 n이 0,1,2,3...밖에 없을까??를 고민했거든. 만약 수학적으로 어떤 성질때문에 P(0),P(1),...,이 모두 참이되는 임의의 성질 P가 항상 P(0'),P(1'),P(2'),..도 참이 돼버리면 체인이 두개이상존재할수있게되니까. 그런데 TAO책에서는 P의 존재를 잡아서 이게 불가능함을 보이는걸 증명을 하지않고 그냥 맞다해버려서,암묵적으로
P(0),P(1),P(2),..가 참일때 항상 모든자연수 n에대해 P(n)이 참이되면 N={0,1,2,3,..}일 수밖에 없다 라고 깔아논거에서 P가 임의니까 아무거나잡아도 성립해야되니,상식적으로 N이 0,1,2,3..밖에 안되겠지라는 "설득력있는" 상상은해도 이게 100% 완전히 확신이들진않앗거든. P를 구체적으로 잡으니까 이해가 바로되네
더욱이 tao에서 계속 엄밀함을 초반에 극도로강조해서, 공리 5를 아예처음부터 자연수집합 N은 0으로부터 다음수 연산을 유한번반복해서 얻을 수 있는 수들만 모인 집합이다. 라고하는거도 "유한번"이라는 것은 결국 자연수를 정의해야 알수 잇는거라 순환논리라고 까지 해버려서 저렇게 수학적귀납공리라는 대체적길을 찾은거거든?근데 이건 또 P를 구체적으로 안잡고 당연하다해버리니 혼란이왔었음.
갑자기궁금한데 0부터 시작하는 체인과 독립된, "시작점이 존재하지 않는 체인" 도 없음은 어떻게보임? -2' -> -1' -> 0' -> 1' -> 2' -> .. 과 같이
N = {0} U {n+ l n ∈ N} 을 이용해서는 힘들듯한데
P(n) := n의 이전 수가 유한하게 존재한다 라 하고 수학적귀납공리쓰고싶은데, "유한하게"라는 걸 자연수정의를안한시점에서 쓰는거자체가 제대로된 증명이 아닌거같아서
@ㅇㅇ(118.37) +(successor)를 중첩해서 사용해서 자연수 덧셈을 정의할 수 있고, 어떤 자연수 c에 대해서 x + c = y이면 x ≤ y가 되도록 자연수 집합 N에 관계(relation) ≤를 정의할 수 있음. ≤가 전순서(total order)면 N은 단일한 체인의 구조를 갖게 되고(보통 체인의 정의를 total order를 갖는 구조로 정의함) 당연히, 실제로도 total order임. 증명은 수학적 귀납법을 여러 번 쓰면 됨
그러면 저 5개의 공리들만을 채택하고 따로 다른 정의들을 일체 사용하지않는다면, 0부터시작하는 체인, 시작점이존재하지않는 체인 두개를 채용한 집합도 자연수집합으로 정의할수도있음? - dc App
@ㅇㅇ(118.235) 체인이 2개 이상인 구조는 total order가 되지가 않아서 모순임. total order의 정의를 사용한 것도 모순을 일으키기 위한 거고, total order 정의를 사용하든 말든 페아노 공리계에 의한 자연수 집합 N 자체는 유일하게 정의됨
아 생각해보니 정의는 공리랑다르게 이것자체가 명제의 참거짓에영향을안주지. 그러네.. 그러면 질문을바꿔서 덧셈,total order등의 정의를 안하고 다른체인의 비존재성을 밝히는 증명은 어떻게가능할까? 공리5개이거아는거만으로 비벼볼려고했는데.. - dc App
0 -> 1 -> 2->.. 외에 다른체인 ...-2' -> -1' -> 0' -> 1' -> 2' ->.. 이 존재한다고하고 P(n):= n은 0'이 아니다 라고 하고 귀납공리를쓰는방법등을 생각해봣는데 이증명은 오류인거같아서 애초에 저 다른 체인이라는 것 자체를 수학적 정의를 하지않고 이미지수식으로만해서그런가 - dc App
@ㅇㅇ(118.235) 아니면 체인을 이룬다는 게 곧 0, 0+, 0++, ... 꼴의 원소만 포함한다는 거니까 N의 모든 원소가 0+...+ 꼴이라는 걸 보여도 충분할 거임. 0+...+ 꼴이라는 말을 좀 더 엄밀하게 쓰자면 "1. 0은 0+...+ 꼴이다, 2. 0이 아닌 자연수 n이 0+...+꼴이면, 어떤 0+...+ 꼴의 자연수 k에 대해서 k+ = n이다"로 결정되는 성질이라 하면 될 것임. P(n)을 "n은 0+...+ 꼴이다"라고 하셈. 그럼 P(0)은 자명하게 참임. P(k)를 가정하면 k가 0+...+ 꼴이니까 k+도 0+...+ 꼴임
@ㅇㅇ(118.235) 사실 방금 답변은 사족에 가깝고, 앞서 말한 것처럼 successor가 toset을 induce한다는 걸 보이는 게 제일 깔끔함. 애초에 페아노 공리계 자체는 자연수의 구조를 최소한으로만 정하기 때문에 덧셈, 곱셈, 순서를 추가적으로 정의하는 게 일반적이기 때문임
@ㅆㅅ 이렇게하면 그냥 다른 시작점이없는 체인의 원소들이 모두 0++..+꼴인 애들만 가져온다고 해버려도 모순이 일어나지않지않음? n이 0+..+꼴이다의 저 정의자체가 0으로부터 다음수연산들을 해서 얻을수잇는 수들만 의미하는게보장되지않는거같은데 - dc App
@ㅇㅇ(118.235) 생각해보니 좀 잘못 정의한 거 같음. 걍 잊으셈 저건. 일반적인 접근법도 아님 애초에
수학적귀납법 5개의 공리를 통해서 이걸 만족하는 자연수집합이 유일하게 정의된다는거 보이는거자체가 굉장히 빡센작업이네 이게 - dc App
존재성은 차치하고 유일성(isomorphic)도 우리가원하는 단일체인만보이는게간단한거같았는데 이게또 시작점이없는체인에대해서는 복잡하게헤줘야되니 - dc App
좀더찾아봣는데 공리5번을 이렇게정의하네 N의 임의의 부분집합 S가 1. 0을 원소로 갖고 2. n이 S의 원소일때 n+도 S의 원소이다 를 만족하면 S=N이다 이 공리쓰면 그런 다른체인들은 바로모순이보여지는거같은데 이 공리가 수학적귀납법공리랑 동치인 공리인걸 증명하면되나? - dc App
@ㅇㅇ(118.235) 그 버전의 수학적 귀납법은 사실상 N = {0} ∪ {n+ | n ∈ N}과 같은 말임
@ㅆㅅ 근데 위키에는 저 공리와 서로 동치라고나와잇는데 앞서말한거처럼 total order등등 정의하면서 증명되는건가 - dc App
@ㅇㅇ(118.235) 내 말은 위키 버전의 수학적 귀납법이 N의 체인 구조를 바로 보장한다면, N = {0} ∪ {n+ | n ∈ N}으로부터도 체인 구조를 바로 보장한다는 거임. 둘은 사실상 같은 말이기 때문임. 또, 두 귀납법이 동치임을 보이려면 N = {0} ∪ {n+ | n ∈ N}과 수학적 귀납법이 동치고, N = {0} ∪ {n+ | n ∈ N}과 위키 버전 수학적 귀납법이 동치임을 보이는 방법을 쓰면 됨