| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 1997년03월07일(금) 05시06분15초 KST 제 목(Title): [re] 무한대 그런식으로 자연수를 이진수로 나타낸 도표를 만들고...(Hypothetical Table) 이진수를 least significant bit 먼저 썼다고 해보죠. 자연수 1부터.. 100000000000000....... 010000000000000000.. 1100000000000000... 001000000000000.. 1010000000000000... ... 여기서 대각선을 취하면 11000.... 그런 식으로 나오는데 각 bit마다 toggle 시키면 00111.....어쩌구 나오겠죠. (1) 그 toggle 시킨 수는 분명히 나타나지 않는 수입니다. 왜냐하면 해당 row i 에서 i번째 bit가 toggle된 수이기 때문에 어느 row에도 나타나지 않는 수임에 틀림 없습니다. (2) 반면에 그 toggle 시킨 수는 one-to-one 되는 자연수가 있을것이므로 도표에 나타나야만 합니다. (1)과 (2)는 모순이므로 [0,1] 의 실수를 자연수에 one-to-one 대응 시키는 것은 불가능하며 cardinality는 자연수를 N이라고 했을 때 [0,1]은 2^N (즉 uncountable) 이 됩니다. diagonal method라고 불리우는 증명방법인데 이 방법 쓰는게 맞을까요 틀릴까요?:) 나중에 Turing Machine 과 non-r.e. 어쩌구 하는데도 이 방법이 쓰입니다. 궁금한 사람은 Hopcroft & Ullman 의 오토메이터 책 183페이지 보시면 나옵니다. --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@ |