편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
{{학술}} | |||
== 개요 == | == 개요 == | ||
[[파일:dominostanding.jpg|섬네일|[[도미노]]를 일렬로 늘어세운 후 처음 세운 도미노를 넘어뜨린다고 가정하자. 만약 앞에 있는 도미노가 쓰러지면서 다음 도미노를 무조건 넘어뜨린다면, 첫번째 도미노를 넘어뜨리면 세워진 모든 도미노가 넘어지지 않을까?]] | [[파일:dominostanding.jpg|섬네일|[[도미노]]를 일렬로 늘어세운 후 처음 세운 도미노를 넘어뜨린다고 가정하자. 만약 앞에 있는 도미노가 쓰러지면서 다음 도미노를 무조건 넘어뜨린다면, 첫번째 도미노를 넘어뜨리면 세워진 모든 도미노가 넘어지지 않을까?]] | ||
15번째 줄: | 16번째 줄: | ||
== 증명 == | == 증명 == | ||
=== 정렬순서원리를 공리로 둔 경우 === | === 정렬순서원리를 공리로 둔 경우 === | ||
<math>n'\in \mathbb{N}</math>이 존재하여 <math>P(n')</math>이 거짓이라고 가정하자. 그리고 [[집합]] ''S''를 다음과 같이 정의하자. | <math>n'\in \mathbb{N}</math>이 존재하여 <math>P(n')</math>이 거짓이라고 가정하자. 그리고 [[집합 (수학)|집합]] ''S''를 다음과 같이 정의하자. | ||
: <math>S=\{n\in \mathbb{N}\vert \neg P(n)\}</math> | : <math>S=\{n\in \mathbb{N}\vert \neg P(n)\}</math> | ||
그러면 <math>\neg P(n')</math>이 참이므로 <math>n'\in S</math>이다. 따라서 ''S''는 [[공집합]]이 아니고 <math>\mathbb{N}</math>의 부분집합이므로, [[정렬순서원리]](well-ordering principle)에 의해 ''S''의 최소원소가 존재한다. 이 원소를 <math>n_0</math>라고 하자. 이때 <math>P(0)</math>은 참이므로, <math>n_0\ne 0</math>이고 따라서 <math>n_0 \ge 1</math>이다. 그러면 <math> n_0 -1 \ge 0</math>인데, <math>n_0-1</math>은 ''S''의 최소원소가 아니므로 <math>n_0 -1\not\in S</math>이다. 따라서 <math>P(n_0 -1)</math>는 참이다. 그러면 가정에 의해 <math>P(n_0)</math>는 참이므로 <math>n_0\not\in S</math>이다. 그러면 <math>n_0\in S</math>이고 <math>n_0\not\in S</math>이므로 <math>n'\in \mathbb{N}</math>이 존재하여 <math>P(n')</math>이 거짓이라는 가정에 모순이다. 따라서 원하는 결론을 얻게 된다. | 그러면 <math>\neg P(n')</math>이 참이므로 <math>n'\in S</math>이다. 따라서 ''S''는 [[공집합]]이 아니고 <math>\mathbb{N}</math>의 부분집합이므로, [[정렬순서원리]](well-ordering principle)에 의해 ''S''의 최소원소가 존재한다. 이 원소를 <math>n_0</math>라고 하자. 이때 <math>P(0)</math>은 참이므로, <math>n_0\ne 0</math>이고 따라서 <math>n_0 \ge 1</math>이다. 그러면 <math> n_0 -1 \ge 0</math>인데, <math>n_0-1</math>은 ''S''의 최소원소가 아니므로 <math>n_0 -1\not\in S</math>이다. 따라서 <math>P(n_0 -1)</math>는 참이다. 그러면 가정에 의해 <math>P(n_0)</math>는 참이므로 <math>n_0\not\in S</math>이다. 그러면 <math>n_0\in S</math>이고 <math>n_0\not\in S</math>이므로 <math>n'\in \mathbb{N}</math>이 존재하여 <math>P(n')</math>이 거짓이라는 가정에 모순이다. 따라서 원하는 결론을 얻게 된다. | ||
68번째 줄: | 69번째 줄: | ||
=== 그래프 === | === 그래프 === | ||
[[분류:수리논리학]] | [[분류:수리논리학]] |