1. 제1 불완전성 정리를 \'표준 자연수 모델에서 참이지만 증명 불가능한 문장이 페아노 공리계를 포함하는 형식 체계에는 모두 존재한다\'로 알고 있는데, 위 사진의 줄그어진 부분엔 오메가 라고 되어 있는데, 정의를 보니 순서수 오메가가 맞네요. 수알못이라 \'표준 자연수 모델\'이 무엇인지 명확히 모를뿐더러 오메가랑은 뭔 상관인지 더 모르겠슴다.
2. 일차논리에서 문장집합 S의 귀결이 문장 p인 것과 S에서 p가 증명 가능하다 는 같은 걸로 아는데, 페아노 공리계와 여타 형식체계에서 괴델 문장 g를 구성할 때 g는 모든 모델에서 참이 될 수밖에 없는 문장인지(교양서적에 나오는 \'난 증명할 수 없다\'같이) 아니면 그냥 표준 자연수 모델에서 참이 되는 건지 잘 모르겠슴다. 전자는 아니겠죠? 또 요 문장g가 그 모델에서 참이란 걸 어캐 증명했는지도 궁금...
3. 연속체 가설이니 하는 것들이 불완전성 정리의 대상이 되는 이유도 모르겠슴다. 저건 부정해도 모델이 성립되고 공리로 추가해도 모델이 성립되는 거라는데, 괴델 문장은 그냥 \'참\'인데 형식체계로 포착하지 못하는 문장인 반면 저 연속체 가설인가 뭔가는 참도 되고 거짓도 되고 하는 느낌이라...
2. 일차논리에서 문장집합 S의 귀결이 문장 p인 것과 S에서 p가 증명 가능하다 는 같은 걸로 아는데, 페아노 공리계와 여타 형식체계에서 괴델 문장 g를 구성할 때 g는 모든 모델에서 참이 될 수밖에 없는 문장인지(교양서적에 나오는 \'난 증명할 수 없다\'같이) 아니면 그냥 표준 자연수 모델에서 참이 되는 건지 잘 모르겠슴다. 전자는 아니겠죠? 또 요 문장g가 그 모델에서 참이란 걸 어캐 증명했는지도 궁금...
3. 연속체 가설이니 하는 것들이 불완전성 정리의 대상이 되는 이유도 모르겠슴다. 저건 부정해도 모델이 성립되고 공리로 추가해도 모델이 성립되는 거라는데, 괴델 문장은 그냥 \'참\'인데 형식체계로 포착하지 못하는 문장인 반면 저 연속체 가설인가 뭔가는 참도 되고 거짓도 되고 하는 느낌이라...
일단은 이걸 참조하시면 도움이 많이 될 듯 합니다.(영어)
https://www.lesswrong.com/posts/i7oNcHR3ZSnEAM29X/standard-and-nonstandard-numbers
표준 자연수 모델이라는 것은 우리가 a priori하게 알고 있는 그냥 자연수들입니다. 0 포함하고, 1=s0 포함하고, 2=ss0 포함하고, ... "딱 그것까지만" 포함하는 것들이요. 여기서 ω는 순서수라기보다는 그냥 집합론 학자들이 자연수 집합으로서 쓰는 것 뿐입니다(두줄그은 N보다 많이 씁니다.)
2. 완전성 정리라고 모든 (가산)모델의 semantic consequence는 증명가능하다, 라는 게 있습니다. 자명하진 않아요. 근데 괴델문 G는 '우리가 a priori하게 아는 자연수 모델'에서는 분명 참인데 PA(페아노 산술체계) 위에서 증명할 수 없는 형태로 잡은 문장입니다. 즉 PA의 모델 중에 우리가 아닌 자연수가 아닌 모델이 있다는 거죠.
G가 참인 건 어떻게 아느냐.. 'PA가 무모순이다'라는 문장을 Con(PA)라고 두면, PA+Con(PA)⊢G는 되는데, PA+Con(PA)⊢ ¬(PA⊢G) 도 얻는다는 겁니다.
그러면 비표준 모델이 있으면 Con(PA)가 거짓이니까 PA에는 모순이 있는거 아니냐 하면 그것도 아닌게 Con(PA)는 '모순을 증명하는 자연수가 존재하지 않는다'라서, ¬Con(PA)여도 모순의 증명수가 비표준 모델에만 들어가는 자연수(비표준 자연수. 0, s0, ss0, sss0, ..가 아닌 것)라면 PA가 계속 무모순일 수 있습니다.
(말하자면 Con(PA)는 "PA가 무모순"보다 강한 주장인 셈인데, "PA가 무모순"이란 주장은 모델의 모호성이 있는 양화사를 안 쓰고 유한한 길이의 산술 문장으로 나타낼 수가 없는 주장입니다.)
그 비표준 자연수가 어떻게 생겼냐고 하면 집합론을 빡세게 해서 ultrafilter라는 애를 써서 만들어 볼 수는 있습니다. 이쪽은 알못이라 nLab같은 영어 링크는 봐도 모르겠고 (bit쩜ly쩜2Nz45dn) 가 설명은 잘해놨는데 일어에요..
오메가에서 참인 게 PA로 증명불가능하다 에서 PA의 모델 중 이상한 모델이 있다 로 진행한 게 이해가 안됩니다 ㅠㅠ 문송
G가 ω 위에서 참인데, 만약 G가 딴 모델 아무거나 주워와도 그 위에서 참이었으면 그건 semantic consequence를 의미하며 완전성 정리에 의해 G는 PA로 증명가능해야 합니다. 근데 그게 불가능하니까 '딴 모델이 있다'라는 결론이 나오게 됩니다.
귀류법으로 존재를 증명한다는듯이 써서 석연치 않을수는 있는데, 완전성 정리는 원래 "임의의 무모순인 공리계는 모델을 가진다"입니다(이건 증명이 constructive) PA로 G를 증명불가능하니 PA+¬G가 무모순이고 모델이 있는데, ¬G가 ω위에서 거짓이므로 그 모델은 ω는 아닐겁니다. 이게 비표준모델인거죠.
3. 연속체가설 같은 경우 ZFC라는 집합론을 기반으로 하는데 얘네는 PA와는 다르게 'a priori한 모두가 동의할 수 있는 모델'이라는 게 존재하지 않습니다. 존재하더라도 불완전성의 한계 때문에 기술이 안 됩니다. 최소한 PA의 표준모델은 '유한한 것들의 집합'이란 비형식적 조건이라도 있었는데.
대표적으로 선택공리가 있는데 "공집합 아닌 집합 무한개를 어떻게 줘도 각 집합에서 원소 한개씩 뽑을 수 있다"라는 심플한 공리인데, 당연히 참일 것 같지만 이걸 받아들임으로서 발생하는 괴현상이 있습니다.(바나흐-타르츠키 역설 등) 그래서 ZFC에 관해서 '표준' 모델이 있을 거라는 플라톤주의는 영향력이 크지 않습니다.
불완전성 정리는 계산가능성 이론 관련 글을 읽어보는 게 좋음
전 고 김영정 교수의 <타르스키정리 처치정리 괴델정리>만 읽어봐서 지식이 짧습니다. ㅠ
근데 ω무모순까지 다룰정도의 책인데 계산가능성은 하고 들어가지 않나요..?