다음은 수학적 귀납법을 적용하는 하나의 예시입니다. 이 중에서 이상한 부분이 있는 것 같아 질문드립니다.
다음을 n에 관한 수학적 귀납법으로 증명하자.
P(n) : n에 관한 명제
먼저 P(0)이 성립함을 보인다.
이제 어떤 양의 정수 k에 대하여 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다고 가정하자.
어찌어찌하여 P(k)가 성립함을 보였다.
따라서 수학적 귀납법에 의해 모든 자연수n에 대해 P(n)이 성립한다.
여기서 제가 질문드리고 싶은 부분은 굵은 글씨로 표시한
"어떤 양의 정수 k에 대하여"
라는 부분입니다.
제가 보기에는 저 문장대로라면 결론은
" 모든 자연수n에 대해 P(n)이 성립한다 "
가 아니고
어떤 양의 정수 k에 대해 " k보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립하면 P(k)가 성립한다"
가 되는 것 같습니다.
그래서
" 어떤 양의 정수 k에 대하여 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다고 가정하자."
를
" k를 'k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립'하는 임의의 양의 정수라 하자"
로 고쳐야 할 것 같습니다.
제가 틀린 부분이 있나요???
논리적으로 옳다면 상관없지않나
예시로 든 수학적 귀납법의 적용이 논리적으로 옳지 않다고 생각해서 글을 썼습니다.
어디가 이상함??
본문에 적었는데 설명이 부족한가요?
아니요, 저 k에 대해 자연수이다 이외에 다른 조건이 없다면, "n<k인 모든 n에 대해 P(n)이 성립하면 P(k)가 성립한다"(이부분을 그냥 G(k)라고 합시다) 에서는 ∀k G(k)를 추론하게 됩니다.
"'어떤' 자연수 k에 대해" 부분을 어떻게 해석하느냐 문젠데, 귀납법에서는 "그런 자연수 k가 존재하여 G(k)" (∃k G(k))가 이니라 그냥 "k를 아무거나 잡고 G(k)" (로부터 다시 ∀k G(k))로 읽어야 합니다.
그렇게 읽어야 하는 근거를 알 수 있을까요?
어떤 양의 정수 k가 k 보다 작은 모든 n에 대해 P(n)이 성립함을 가정한 것으로 부터 시작하는데 ∀k G(k) 가 아니고 ∃k G(k) 가 추론되어 지는 것 아닌가요?
그리고 어떤 x 에 대해서 P(x)이다고 하면 ∃xP(x)를 나타는 것이지 ∀xP(x)를 나타내는 것은 아니지 않나요? 혹시 "어떤 x 에 대해서 P(x)이다" 형태의 문장이 ∀xP(x) 을 나타내는 문장을 하나 제시해주실 수 있나요?
"어떤 자연수 k에 대해서 G(k)" (⇔ ∃k G(k))를 가정한 게 아니고, "어떤 자연수 k"를 가정했더니 G(k)가 따라나온 겁니다.
"모든 자연수에 대해 G이다" 라고 말하려니 모든 자연수에 대해서 통째로 논의할 순 없는 노릇이고, 자연수를 하나 뽑아서 k라 불렀는데 별다른 제약조건(k는 짝수로 뽑았다, 소수로 뽑았다 같은) 없이 G(k)라면 ∀k G(k)로 결론짓는 것은 당연합니다.
귀납법이 어떻게 해서 성립하는 건지 한번 음미해 보는 걸 추천합니다. 정 헷갈리시면 저기서 "어떤"은 "임의의"가 오타났다 생각하는 게 편할지도 모르겠네요.
저 죄송한데 우선 다음 문장이 무엇을 뜻하는지 서로 명확하게 해 봅시다. "어떤 양의 정수 k에 대하여 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다고 가정하자." 이 문장을 형식적으로 고쳐보겠습니다. ∃k∈N, ∀n∈Z, ( 0<n<k → P(n) ) 이렇게 고치는거 맞나요?
그러니까 "어떤"을 생각없이 ∃로 고치는 게 아니라는 겁니다. 제 생각인 "어떤 양의 정수 k에 대해서'도'"인데 한 글자 빠뜨리신 거 같은데요. 그 때의 "어떤"은 ∀입니다.
∀k∈N, ∀n∈Z, ( 0<n<k → P(n) ) 이라는 것인가요?
아니요........ ∀k, ((∀n, (n<k → P(n)) ) → P(k) ) 입니다. 조건문이 겹겹이 있어서 헷갈릴 순 있지만 귀납법을 위해 충당해야 할 조건은 저겁니다.
그리고 그 조건을 보이기 위해서 "어떤 k"를 (아무거나) 고정한 상태에서 ∀n (n<k → P(n))을 가정하고 P(k)를 보이는 겁니다. 이 단계에서는 k에 대한 양화사는 없어요. 이 단계가 끝나면 증명되는 식이 바로 윗 댓글에서 적은 식.
네 "∀도입" 을 하기 위해 k를 "k 보다 작고 영 이상인 정수 n 에대해 P(n)이 성립"하는 양의 정수이다고 하면 아무 문제가 될 것이 없습니다. 하지만 지금은 "어떤 x 에 대해 Q(x)" 이다는 꼴인데 이것은 ∃xQ(x)를 나타낼 수도 있습니다. 또한 "어떤"의 사전 뜻 중 "관련되는 대상이 특별히 제한되지 아니할 때 쓰는 말"로 "어떤"이라는 단어가 사용되었다면 ∀xQ(x)를 나타내었다고 볼 수도 있습니다. 그리고 "∀도입" 을 하기 위해 사용된 문장이라고 볼 수도 있습니다. 문맥상 이중에 마지막의 경우에 해당되는 것이겠지만, 문장자체만 봐서는 애매한 문장이라서 고치는 것이 좋을 것 같다는 것이 제 의견입니다. 제가 본문에서 지적한 문장이 애매한 문장이라는 것은 맞지 않나요?
어떻게 해석하든 님 자유지만, 문장이 수학적 귀납법으로서 기능하기 위한 해석은 제가 말한 거 하나밖에 없습니다. 님이 멋대로 다르게 해석하고서 논리적 오류가 있다느니 하지 마세요.
결과론적으로야 임의의 k에 대해서 "k미만의 모든 자연수 n에 대해 P(n)"(⇐F(k)라고 할게요)가 성립하는 건 맞는데, "F(k)를 만족하는 k"라고 한 순간 이미 ∀도입에 필요한 "임의의 k"라는 조건에 어긋나요. 임의의 k를 가정하고 F(k)→P(k)라는 형태로 써 줘야 제대로 된 형식화죠.
"가정하자" 부분까지만 나타내고 싶은거라면(왜 그러고 싶으신건지 정말 모르겠는데) 이 "어떤 k"는 ∃k일수도 있지만 그냥 "k를 하나 고정했다"라고 읽힐 수 있습니다.(이 경우 ∀k는 아닙니다.) 이 이상은 논리학이라기보단 국어의 문제라서 더 말할 게 없네요.
13:37:32 에 달린 댓글을 보면 "임의의 k를 가정하고 F(k)→P(k)라는 형태로 써 줘야 제대로 된 형식화죠"라고 하셨는데, 저는 수리논리와 집합론 입문(정주희), language, proof and logic 에 나온 방법대로 했을 뿐이입니다. 책 참고해보세요. ∀k [F(k)→P(k)] 를 증명할때는 F(k)를 만족하는 임의의 k를 가정하고 P(k)를 보여줘도 됩니다.
마지막에 달아주신 댓글에서 말씀하신 것처럼 이럴 수도 있고 저럴 수도 있는 애매한 문장을 수학적 귀납법이라는 문맥에 끼워맞춰서 뜻을 확정 짓는 것이 거부감이 들었습니다.
안건을 "수정 전 문구가 괜찮다"와 "수정 후 문구가 나쁘다"로 나누는 게 좋겠군요. 전자에 관해서 전 수정 전 문구도 썩 맘에 들진 않지만, 애매할 뿐 오류는 아니라는 주장입니다. 제안한 문구 말고도 '임의로 k를 잡아'로 수정하는 안도 있고요.
후자에 관해서는.. 결과론적으로 틀리진 않았으나, ∀도입하고 다른 한 스텝을 한 번에 진행하는 꼴이고, "F(k)가 아닌 k가 있을 수도 있지만 그건 논외"의 뉘앙스가 섞여 있어 제가 보기엔 '어떤'을 그대로 쓰는 것보다 더 misleading입니다.
∀k [F(k)→P(k)] 을 증명하는 방식입니다. " "F(k)가 아닌 k가 있을 수도 있지만 그건 논외"의 뉘앙스가 섞여 있어 " 라고 하신 부분은 조건문 F(k)→P(k) 의 의미가 원래 그러하지 않은 것인지 되묻고 싶습니다.
"결과론적으로 틀리진 않았다"라고 했습니다만... 뉘앙스 중요합니다. ∀k (F(k)→P(k))는 자연어로 옮길 때 "모든 F(k)인 k에 대해 P(k)"랑 "모든 k에 대해 F(k)이면 P(k)" 두 가지가 가능한데 귀납법의 작동원리를 생각해보면 전자보다 후자가 명료하지 않을까요.
결과론적으로 틀리지 않았다고 하면서 misleading 이라는 주장을 하셨습니다. 그런데 뭘 사실이 아닌 것을 사실로 믿게 만든다는 것인지 모르겠습니다. 조건문에 대해서 뭔가 오해가 있으신 것 같아서 되물었던 것이구요. "모든 k에 대해 F(k)이면 P(k)" 만 생각해봅시다. 다음과 같은 경우를 생각해봅시다. 자연수 7에 대해서는 F(7)이 거짓이고 7 이외의 모든 자연수 k 에 대해서는 F(k)가 참이고 P(k)도 참인 상황이 주어졌다고 합시다. 그럼 이 경우가 "모든 k에 대해 F(k)이면 P(k)" 가 성립하는지 생각해봅시다. k를 7이 아닌 임의의 자연수라 합시다. 그리고 F(k)를 가정합시다. P(k)가 성립하므로 F(k)이면 P(k)가 성립합니다. 이제 7에 대해 생각해봅시다.
F(7)이 거짓입니다. 따라서 조건문 "F(7)이면 P(7)" 은 참이 됩니다. 즉 모든 자연수 k에 대해 F(k)이면 P(k). 이처럼 "모든 k 에 대해 F(k)이면 P(k)" 이다는 몇몇 k에 대해서는 F(k)가 거짓일 수도 있습니다. 조건문의 진리표를 생각하면 당연하죠. 그래서 수학적 귀납법에서 초기값에 대해서 참임을 주는 것이 들어가는 것입니다. 위의 댓글에서 "귀납법의 작동원리를 생각해보면 전자보다 후자가 명료하지 않을까요?" 라고 하신 부분은 후자도 전자의 뜻을 가지는데 어떤 점이 명료하다는 것인지 모르겠습니다. 그냥 더 익숙하다는 것이어서 이런 반응이 나오는 것이 아닌가하는 추측도 해봅니다.
아무튼 "모든 k 에 대해 F(k)이면 P(k)" 에서도 몇몇 k에 대해서는 F(k)가 성립하지 않을 수도 있는 뉘앙스가 담겨져 있는 것은 매한가지입니다.
전자의 표현에서 "F(k)가 참인지 상관없이 모든 자연수 k에 관한 서술이다"란 걸 확인하려면 "아 A가 거짓이면 A→B는 참이었지 맞다"라고 곱씹어 생각해야 하는데, 후자는 그럴 필요가 없다는 점에서 명료하다고 했습니다.
프레게는 동일한 지시체(reference)더라도 그 표현, 뜻(sense)이 다를 수 있다고 했죠. 적어도 제게는 k의 서술 범위의 sense는 전자에 관해선 "F(k)가 참인 조건이 딸린 자연수 k"고 후자에서는 "자연수 k"로 읽힙니다.
위에 댓글에서 " 전자의 표현에서 "F(k)가 참인지 상관없이 모든 자연수 k에 관한 서술이다"란 걸 확인하려면 "아 A가 거짓이면 A→B는 참이었지 맞다"라고 곱씹어 생각해야 하는데, 후자는 그럴 필요가 없다는 점에서 명료하다"고 하셨습니다. 그런데 후자의 표현을 증명할때를 생각합시다. k를 임의로 가정합니다. 그런 뒤 F(k)를 가정합니다. 여기에서 F(k)가 거짓인 경우는 고려하지 않고 참이라고 생각하고 있는 것입니다. 전자의 표현에 대해서 그런 문제제기를 하였다면 후자에서도 똑같이 문제제기를 해야한다고 생각합니다. 그런데 지금은 그렇지 않은 상황입니다. 별 생각없이 후자의 표현을 써왔다가 이제서야 전자의 표현에서 뭔가 이상하다고 생각하는 것은 아닌지요.
프레게가 누군지도 모르고 지시체가 뭔지도 몰라서 여기에 대해서는 제가 생각을 해볼 수가 없습니다.
물론 후자의 경우에도 증명할 때 F(k) 가정하고 나서 P(k)를 유도하지만, 거기서 F(k)→P(k)로 일단 한 번 →도입을 쓰면 "k에 대한(자연수라는 거 외에) 제약조건이 없다"가 명확해지죠. 연역정리 덕분입니다. 그 다음에 ∀도입을 쓰는 거구요.
위에서도 말했지만 "F(k) 가정해서 P(k)를 증명한 상태서, ∀k (F(k)→P(k))를 추론한다"를 한 스텝으로 보고 계시는 거 같은데 →도입, ∀도입 해서 두 스텝입니다.
지시체 언급한 부분은, 조금 과장된 예겠습니다만 "문재인 대통령은"을 "문용형의 아들은"이라고 쓰는 거하고 똑같습니다. 결국 가리키는 논리식이 똑같다고 해도 자연어로 표현이 다르면 어감이나 강조하고 싶은 부분 같은 것도 달라지는 겁니다.
저는 ∀k (F(k)→P(k)) 를 증명할 때 두 가지로 표현으로 증명할 수 있다고 주장하는 것입니다. 둘 중 하나만 맞다고 하는 게 아닙나다. 첫째 방법은 k 를 임의의 대상으로 가정합니다. 그런 뒤에 F(k)→P(k) 를 유도해 내면 됩니다. 이것이 계속 님이 말해왔던 방법이고 제가 이걸 틀렸다고 한 적이 없습니다. 다른 방법도 있다는 것이지요. 둘째 방법은 k 를 F(k)를 만족하는 임의의 대상으로 가정합니다. 그런 뒤에 P(K)를 유도하는 방법도 있다는 겁니다. 한 스텝으로도 쓸 수 있다는 것입니다. 그것이 "F(k)가 아닌 k가 있을 수도 있지만 그건 논외"라는 뉘앙스 차이가 난다고 뭐라고 하시는 부분은 오히려 더 구체적인 뜻을 나타내준다고 볼 수 있습니다.
앞서 이 쪽 관련해서 misleading 이라고 주장하셨는데 오히려 구체적인 뜻을 나타내는 것인데 이를 misleading 이라 할 수 있을까요? 제가 잘못 이해하고 있으면 어디가 사실이 아닌 것을 사실로 믿게 만든다는 것인지 구체적으로 적어주시면 감사하겠습니다. 암튼 두 스텝으로 진행하든 한 스텝으로 진행하든 상관없이 잘 작동하며 그 뉘앙스 차이가 misleading이 아닌 오히려 구체적인 뜻을 나타내어 준다고 생각합니다.
지시체에 대해서 어떤 개념인지 설명해주셨으니 그것을 토대로 생각해보겠습니다. 위의 댓글 중에서 "적어도 제게는 k의 서술 범위의 sense는 전자에 관해선 "F(k)가 참인 조건이 딸린 자연수 k"고 후자에서는 "자연수 k"로 읽힙니다."라고 하신 부분을 생각해보겠습니다. 네 맞다고 생각합니다. 자연어의 표현이 달라져서 한쪽에서 다른 쪽보다 더 강조하는 부분이 생겼습니다. 그렇지만 강조하는 부분이 생겼을 뿐이지 misleading이라고 할 수는 없다고 생각합니다. 한 쪽이 명료하다 안하다는 문제는 조건문의 뜻을 몸에 익혀두고 있다면 둘 다 비슷하다고 생각하게 될 것이라 생각합니다. 각자의 개인적인 느낌에 관한 것이라고 생각되어서 뭐라 말하기는 힘드네요.
편하게 every로 생각하면 편함
"임의의 양의 정수 k 에 대해서 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다" 로 고쳐봅시다. 그러면 임의의 자연수 m에 대해서 m+1을 생각해보면 P(0) 이고 P(1) 이고 .... 이고 P(m) 이라서 P(m)이 참이 됩니다. 따라서 ∀m, P(m). 역으로 ∀m, P(m) 라 가정합시다. k를 임의의 양의 정수라 합시다. n을 k 보다 작고 영 이상인 정수라 합시다. ∀m, P(m) 이므로 P(n) 따라서 "임의의 양의 정수 k 에 대해서 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다" 가 참입니다. 따라서 단순히 "임의의 양의 정수 k 에 대해서 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다" 로 바꾼 문장은 ∀m, P(m) 과 동치입니다.
수학적 귀납법은 ∀m, P(m) 을 유도해 내는 과정인데 ∀m, P(m) 을 가정하고 ∀m, P(m) 을 유도하는 것과는 다른 것입니다.