괴델의 불완전성 정리

수학 채널

알림 알림 중 알림 취소

구독자 2300명 알림수신 53명 @시스티나

각종 수학 이야기를 해는 채널

괴델의 불완전성 정리

시리얼티

추천 2 비추천 0 댓글 12 조회수 612 작성일 2022-07-08 15:03:20

https://arca.live/b/math/54009738

제1정리. 페아노 공리계를 포함하는 어떠한 공리계도 무모순인 동시에 완전할 수 없다. 즉 자연수 체계를 포함하는 어떤 체계가 무모순이라면, 그 체계에서는 참이면서도 증명할 수 없는 명제가 적어도 하나 이상 존재한다

여기에서 참이면서도 증명할 수 없는 명제 라는 것이 유클리드 기하학의 공준 같은 건가요?

댓글 [12] 글쓰기

ㅇㅇ

2022-07-08 15:36:35 답글

*수정됨

참이면서 증명할 수 없는 명제의 예시는 우리가 들 수 없음. (<< 이에 대한 다른 얘기가 있음. 아래 댓글 참고)
아직 증명할 수 없는데 우리가 그게 참임을 어떻게 알겠음?

일반적으로는 존재성을 증명했다고 하여 반드시 그게 구체적으로 무엇인지 알 수 있단걸 의미하지 않음. 존재성이라는것은 단지 어딘가에 존재하기는 한다는 걸로도 충분함.

또 공준에 대해 말했는데, 공준은 그 증명을 위한 토대에 해당함. 그러니까 공준이 참임을 증명하는게 아니라, 참임을 애초에 가정하고 시작하는 토대가 공준임. 이러한 공리나 공준 없이 애초에 증명이라는 것은 할 수 없음.

펼쳐보기▼

ㅇㅇ (124.50)

2022-07-08 21:12:53 삭제 수정 답글

...

펼쳐보기▼

막걸리

2022-07-08 21:30:31 답글

참인데 증명할 수 없는 명제 괴델이 훌륭하게 제시해줬음

펼쳐보기▼

ㅇㅇ

2022-07-08 22:29:41 답글

*수정됨

아아 내가 증명불가능에대해 잘못 이해하고 있었음 ㅈㅅㅈㅅ 진짜 미안 여태껏 잘못 알고있었네....
증명불가하다는게, 증명 또는 반증하는것이 불가능함을 증명한 개념이구나 

찾아보니 그 예시로 연속체 가설에 대해 얘기하고 있음. 이런 명제는 참이라고하든 거짓이라고하든 아무런 문제가 없다고함.
아마 주딱은 이걸 얘기한거겠지?
덕분에 더 확실하게 알아감...

펼쳐보기▼

ㅇㅇ

2022-07-08 22:45:28 답글

*수정됨

하지만 생각해보니, 그런 의미에서 나는 아직도 괴델의 정리를 잘 이해 못했음.

그래서 이건 내가 하는 질문인데,
그러면 참이지만 증명불가능하다는 뜻은 내가 이해하는 그 뜻이 아닌건가?

나는 어떤 명제가 참이라는 것은 거짓이 아님을 의미한다고 알고 있었음. 따라서 맨 위와 같은 댓글을 단 것임.
그런 의미에서 참이어도 모순이 없고 거짓이어도 모순이 없다는 명제(연속체가설 등)가 왜 참이면서도 증명할 수 없는 것의 예시인지는 잘 이해가 되지 않음.
그러니까 연속체 가설은 참이라 '가정'해도 문제가 없다는 것이잖음. 만약 이게 '참인데 증명불가능'한 명제라면, 결국에는 '참값이라 가정했는데 참값임을 증명불가하다'는, 그런 이상한 명제가 되어버리지 않나?

 혹시 내가 잘못 이해하고 있는 점이 있을까? 아니면 괴델의 정리가 수리논리학 분야라던데, 수리논리학에서는 참이라는 것을 좀 다르게 해석하는건가? (위에서 내가 '증명불가능'을 잘 못 이해한 것처럼)

펼쳐보기▼

ㅇㅇ

2022-07-08 23:09:18 답글

*수정됨

아래 댓글('참이지만 증명불가'보다는 '참이더라도 증명불가'가 더 정확하다) 보고 번역 이슈가 혹시 있을까 싶어 원문에서는 괴델의 정리를 어떻게 서술할까 궁금해서 영문위키를 찾아봤음 (개인적 한계로 서적을 다루지 않고 위키를 다룬 점 양해해주셈)

영문위키에서는 '참이면서도 증명 불가능한 명제'는 언급되기는 하지만, 이는 괴델의 1정리의 증명과정 및 1정리의 한 결과로서 다뤄졌음. 즉 이 글의 본문처럼 '제1정리' 자체로서 다뤄지지 않음

그리고 선택공리나 연속체가설이 '참이면서 증명불가한' 예시로 소개되지도 않는 것처럼 보였음. 단지 undecidable statement의 예시라고 소개되고있었음. 즉 '증명불가능(무모순성)'과 '참이지만 증명불가능'은 별개로 받아들여진다고 보였음.

결국 아직도 나는 맨 위 댓글의 글 자체는 틀리지 않았다고 생각함. (단지 증명불가능함에 대한 개인적 오해만 제한다면 말임)
그러니까 나는 아직 "연속체가설 등은 제1정리의 예시(무모순성을 입증할 수 없는 예시)이지만, '참이지만 증명불가능한 명제'의 예시는 아니다"라고 생각함

아직도 이렇게 생각되어지니, 이 생각이 틀림을 보이기 위해 항목을 뒤져봤는데... 가장 관련 깊어보이는 truth of the Godel sentence와 example of undecidable sentence에서도 내가 원하는 답은 찾을 수 없었음.

혹시나 이어서 찾아볼 사람들을 위해, '참이지만 증명불가능'이라는 말이 대체, 제1정리가 아니라면 어디피셜로 나온 말인지 찾아본 결과를 여기 적어둠.
(전략) ... For this reason, the sentence G_F is often said to be "true but unprovable." (Raatikainen 2015)

문서가 너무 길어서 띄엄띄엄 읽어서 내가 못 봤을수도 있으니 혹시 이 문제에 대해 꽤 잘 아는 분이 있다면, 내가 잘못 알고있을 수 있으니 대댓 달아주면 정말 감사하겠음!

펼쳐보기▼

막걸리

2022-07-09 07:39:25 답글

*수정됨

연속체가설이 참이지만 증명불가능한 명제에 해당하지 않는다는 말은 맞음. 그렇지만 맨 처음에 '참이면서 증명할 수 없는 명제의 예시는 우리가 들 수 없음' 이건 틀린 말임

펼쳐보기▼

ㅇㅇ

2022-07-09 08:02:29 답글

아아 연속체가설 얘기한게 아니었구나 근데 어째서 틀린거임?

펼쳐보기▼

ㅇㅇ (223.39)

2022-07-09 17:01:18 삭제 수정 답글

참이면서 증명불가능하다는건 참이라는걸 어떻게암? 참인게 확실하다면 그게 증명된거아님?

펼쳐보기▼

막걸리

2022-07-09 17:41:16 답글

따로 글 쓰겠음

펼쳐보기▼

Specificity

2022-07-08 20:55:31 답글

설령 참이더라도 증명할 수 없다고 말하는 게 정확할 듯

펼쳐보기▼

ㅇㅇ (106.244)

2022-07-09 09:25:50 삭제 수정 답글

공준이랑은 다른 것일껄? 공리/공준은 참으로 사소하게 인정하고 넘어가는 문장인 거잖슴. 쌍둥이 소수 추측처럼 현재 증명이 불가능하단 것과 무모순 체계인데도 그 체계내에서 증명 불가능한 명제가 반드시 하나 이상 존재한다는 다른 말임. 그리고 다른 말일 수 있는 이유는 괴델의 정리가 어떤 무모순 체계 A가 있으면, 이 A에 대해서 직접 말하는 게 아니라 A가 무모순 체계임을 증명해 줄 메타 A의 관점에서 이야기 하기 때문인거고.

펼쳐보기▼

댓글 작성