PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Low Entry average rating: No information on entry rating
[parent] principle of finite induction proven from the well-ordering principle for natural numbers (Proof)

We give a proof for the “strong" formulation.

Let $ S$ be a set of natural numbers such that $ n$ belongs to $ S$ whenever all numbers less than $ n$ belong to $ S$ (i.e., assume $ \forall n(\forall m<n\ m\in S)\Rightarrow n\in S$, where the quantifiers range over all natural numbers). For indirect proof, suppose that $ S$ is not the set of natural numbers $ \mathbb{N}$. That is, the complement $ \mathbb{N}\setminus S$ is nonempty. The well-ordering principle for natural numbers says that $ \mathbb{N}\setminus S$ has a smallest element; call it $ a$. By assumption, the statement $ (\forall m<a\ m\in S)\Rightarrow a\in S$ holds. Equivalently, the contrapositive statement $ a\in \mathbb{N}\setminus S \Rightarrow \exists m<a\ m\in \mathbb{N}\setminus S$ holds. This gives a contradition since the element $ a$ is an element of $ \mathbb{N}\setminus S$ and is, moreover, the smallest element of $ \mathbb{N}\setminus S$.



"principle of finite induction proven from the well-ordering principle for natural numbers" is owned by smw. [ full author list (2) | owner history (1) ]
(view preamble | get metadata)

View style:

Keywords:  number theory

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: contrapositive, well-ordering principle for natural numbers, complement, quantifiers, numbers, natural numbers, strong, proof
There is 1 reference to this entry.

This is version 11 of principle of finite induction proven from the well-ordering principle for natural numbers, born on 2001-10-18, modified 2007-06-21.
Object id is 337, canonical name is PrincipleOfFiniteInductionProvenFromWellOrderingPrinciple.
Accessed 4204 times total.

Classification:
AMS MSC: 03E25 (Mathematical logic and foundations :: Set theory :: Axiom of choice and related propositions)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)