수학적 귀납법을 적용하는 예시입니다.
다음을 n에 관한 수학적 귀납법으로 증명하자.
P(n) : n에 관한 명제
먼저 P(0)이 성립함을 보인다.
이제 어떤 양의 정수 k에 대하여 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다고 가정하자.
어찌어찌하여 P(k)가 성립함을 보였다.
따라서 수학적 귀납법에 의해 모든 자연수n에 대해 P(n)이 성립한다.
질문은 위의 수학적 귀납법을 적용하는 과정에서 나온 다음 문장을 1계논리의 문장으로 고치면 어떤 문장이 되는 것인가 입니다.
어떤 양의 정수 k에 대하여 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다
∀n∈N[n＜k→p(n)]
그러면 k에 관해서는 forall 인가요 exist 인가요?
수학적 귀납법을 통으로 1계논리 문장으로 쓰면 p(0)∧∀k∈N[∀n∈N[n＜k→p(n)]→p(k)]→∀n∈N p(n) 임
∀k∈N[∀n∈N[n＜k→p(n)]→p(k)] 를 증명하려면 다음과 같은 방법으로 비형식적으로 증명하면 될까요? k를 임의의 양의 정수라 하자. k 보다 작은 임의의 양의 정수 n에 대해 P(n)이라 가정하자. ~~~ . 따라서P(k)가 성립한다.
k를 [k보다 작은 모든 자연수 n에 대해 p(n)이 참]인 임의의 자연수라고 가정하면 됨
네 맞습니다. 그렇게 해도 될 것같습니다. k를 임의의 양의 정수라 하자. k를 임의의 택해놓고 시작해도 되지 않나요?
k를 임의의 자연수로 가정한 다음 k보다 작은 n에 대해 p(n)이 참으로 가정하면 걍 수학적귀납법 필요없이 모든 자연수 k에 대해서 p(k)가 참이잖음
k를 임의의 자연수로 가정합니다. 그리고 k 보다 작은 임의의 양의 정수 n에 대해 P(n)이라 가정합니다. 이 가정으로부터 P(k)를 유도합니다. 그러면 ∀n∈N[n＜k→p(n)]→p(k) 가 유도됩니다. k는 처음에 임의의 자연수라고 했으니 ∀k∈N[∀n∈N[n＜k→p(n)]→p(k)] 가 유도됩니다. 이렇게 하면 안되나요?
k를 먼저 임의의 자연수로 가정 하고, k보다 작은 n에 대해서 p(n)을 참이라고 가정하면 아무 자연수 m에 대해 m+1보다 작은 모든 자연수에 대해 참이니까 p(m)도 참이라서 걍 수학적귀납법이 필요없음
k를 임의의 자연수라 가정합니다. 이 가정의 상황에서 ∀n∈N[n＜k→p(n)]→p(k)을 증명하기 위해서 ∀k∈N[∀n∈N[n＜k→p(n)]이라고 부분가정을 또 합니다. 그 부분가정 안에서 P(k)를 유도합니다. 그러면 ∀n∈N[n＜k→p(n)]→p(k) 가 유도됩니다. k는 처음에 임의의 자연수라고 했으니 ∀k∈N[∀n∈N[n＜k→p(n)]→p(k)] 가 유도됩니다. 이런식으로는 안될까요? 물론 이와는 다르게 임의의 자연수 k에 대해 ∀n∈N[n＜k→p(n)] 라 가정하자고 하면 님 말씀처럼 수학적 귀납법을 적용할 필요도 없이 모든 자연수에 대해 P가 성립합니다.
자연어로 풀어 쓸 땐 자연어의 의미를 살려야죠. 안그러면 자연어로 쓸 이유가 없죠.
무슨 말씀이신지 좀 더 풀어주실 수 있나요? 제 댓글의 어느 부분이 자연어의 의미를 살리지 못하고 있는지 모르겠습니다.
한국말의 의미 자체가 'k 를 임의의 양의 정수라 하자." 라고 했으면 그냥 k는 임의의 자연수가 되는거에요. 여기서 k보다 작은 자연수 n에대해 p(n)이참이라고 또다시 가정하면 그 의미가 "모든자연수 k에 대해 [k보다 작은 자연수 n에 대해서 p(n)]" 가 되는거구요.
하... 그러면 형식증명에서 부분가정 같은 것은 어떻게 자연어로 써야하나요? 저는 이때까지 저렇게 써왔었는데 충격이네요..
글쎄요. 수학의 문제라기 보단 국어의 문제 같은데...
k를 임의의 양의 정수라 하자. ∀n∈N[n＜k→p(n)] 인 경우를 생각해보자. P(k) 이다. 따라서 ∀n∈N[n＜k→p(n)]→p(k) 이다. k는 임의의 양의 정수이므로 ∀k∈N[∀n∈N[n＜k→p(n)]→p(k)]. 이렇게 유도하는 것도 안될까요?
솔직히 한국인으로서 님이 쓴 문장이 무슨뜻인지 모르겠어요. 너무 어렵게 생각하시는것 같은데....
k를 임의의 양의 정수라 하자. k보다 작은 임의의 정수 n에 대해 P(n)이 성립하는 경우를 생각해보자. ~~~. P(k)를 유도했다. 따라서 k 보다 작은 임의의 정수 n에 대해 P(n)이 성립한다고 하면 P(k)이다. 따라서 ∀k∈N[∀n∈N[n＜k→p(n)]→p(k)]. 이렇게 유도하는 것도 한국말이 어색해보이나요?
그렇게 쓰시면 의미가 통할것 같네요
근데 맨 첨에 k를 "임의의" 자연수라고 하는것은 사족 같아요. 그냥 k가 자연수라고 하자 라고 하는게 국어적으로 느낌오는데
이거 참 자연어로 풀어서 증명하는게 문제네요. ∀n∈N [ ( P(n)→H(n) ) ∧ ( Q(n)→K(n) ) ] 같은걸 자연어로 증명한다고 치는 것도 문제인거 같구요. n을 임의의 자연수라 하자. P(n)이라 가정하자. 이러면 안되고 P(n)인 경우를 생각해보자. ~~~ . H(n)이 유도되었다. 따라서 P(n)이면 H(n)이다. 이제 Q(n)인 경우를 생각해보자. ~~~. K(n)이 유도되었다. 따라서 Q(n)이면 H(n)이다. ~~~~~ 뭐 이런 식으로 써야하는데 어렵네요..
"임의의"라는 부분 ∀x∈N ψ(x) 를 증명하기 시작할 때 습관적으로 x를 임의의 자연수라고 하자. 이렇게 자유변수를 지정하고 자연어로 증명했거든요. 이 정도는 봐줄만하지 않을까요
그리고 한가지 또 궁금한게 생겼는데요. 위에 예시로 든 수학적귀납법의 예시에서 "어떤 양의 정수 k에 대하여 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다" (이 문장을 A 로 표시하겠습니다.) 는 ∀n∈N[n＜k→p(n)] 를 나타낸다고 했잖아요? 그런데 이전에 k를 먼저 도입하지 않고 A로 새롭게 k를 도입하여 가정했으니 ∀n∈N[n＜k→p(n)] 은 ∀k∈N∀n∈N[n＜k→p(n)] 가 되는 것이 아닌가요? A 이전에 k를 임의의 자연수라고 하자 또는 그냥 자연수라고 하자 먼저 지정해줘야 하는 상황인 것 같은데 아닌가요?
∀k∈N∀n∈N[n＜k→p(n)] 는 ∀n∈N[n＜k→p(n)]부터 해석해야됨. 즉, 어떤 고정된 자연수 k에 대해서 , k보다 작은 모든 자연수 n에 대해 p(n)이 참이란 거임. 그다음에 이게 ∀k∈N에 대해 성립하는거니까, "[k를 고정했을 때 k보다 작은 모든 자연수 n에 대해 p(n)이 참]이 임의의 자연수 k에 대해 참"이 됨. 그럼 수학적귀납법에서 말하는 귀납가정이랑은 의미가 멀어짐
그리고 원소기호 x랑 집합 X에 대해 ∀x∈X p(x)를 좀더 형식적으로 쓰면 ∀x[x∈X→p(x)]가 되는데 그런 관점에서 k가 자연수인지 뭔지 안써져있다는게 걸리면 k∈N→∀n[n∈N→[n＜k→p(n)]] 라고 쓸 수도 있음. ∀k[k∈N→∀n[n∈N→[n＜k→p(n)]]] 는 아님.
"어떤 양의 정수 k에 대하여 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다"가 명제가 아니라 조건이라서 universal closure을 할 필요가 없음
그리고 1계논리 문장이란것도 전체 집합이 무엇이고 주어진 연산과 관계가 무엇인지에 따라 쓰는게 다름. 예를 들어서 페아노 공리계에서는 ∈N이라는 것도 불필요함. 어차피 원소 기호가 나오면 자연수이기 때문임. 근데 ZFC에서 1계논리 문장이라고 하면 전체 집합이 모든 집합에 대한 고유 모임이고 주어진 관계도 ∈밖에 없어서 'n＜k'라는 문장도 좀 더 엄밀하게 쓴 어떤 문장의 줄임말에 불과함.
∀k∀n∈N[n＜k→p(n)] 를 가정하면 수학적 귀납법과는 달라집니다. 그런데 "어떤 양의 정수 k에 대하여 k 보다 작고 영 이상의 정수 n에 대하여 P(n)이 성립한다" 이 문장이 애매한 문장으로 보여집니다. 예를들면 "어떤 x에 대해서 P(x)" ∃xP(x)를 나타낼 수도 있습니다. "어떤" 이란 단어가 "관련되는 대상이 특별히 제한되지 아니할 때 쓰는 말"의 뜻으로 사용되었다면 "어떤 x에 대해서 P(x)" 는∀xP(x)을 나타낼 수도 있습니다. 그렇지만 지금 수학적 귀납법의 문맥상 "∀도입"을 하려는 것이고 앞서 말한 두가지 경우와 또 다릅니다. 그래서 k가 앞서 임의의 양의 정수라 하거나 위에서 말씀해주신 것처럼 "k를 ~~를 만족하는 임의의 양의 정수라하자"고 하는 것이 옳다고 생각했습니다.