|
|
|
Viewing Version
6
of
'principle of finite induction proven from well-ordering principle'
|
[ view 'principle of finite induction proven from well-ordering principle'
|
back to history
]
| Title of object: |
principle of finite induction proven from well-ordering principle |
| Canonical Name: |
PrincipleOfFiniteInductionProvenFromWellOrderingPrinciple |
| Type: |
Proof |
| Created on: |
2001-10-18 15:38:43 |
| Modified on: |
2006-03-06 14:52:55 |
| Classification: |
msc:03E25 |
| Keywords: |
number theory |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic} |
Content:
| Let $T$ be the set of all postive integers not in $S$. Assume $T$ is nonempty. The Well-Ordering Principle for natural numbers says $T$ contains a least element; call it $a$. Since $1 \in S$, we have $a > 1$, hence $0 < a-1 < a$. The choice of $a$ as the smallest element of $T$ means $a-1$ is not in $T$, and hence is in $S$. But then $(a-1)+1$ is in $S$, which forces $a \in S$, contradicting $a \in T$. Hence $T$ is empty, and $S$ is all positive integers. |
|
|
|
|
|
