PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Low Entry average rating: No information on entry rating
[parent] well-ordering principle for natural numbers proven from the principle of finite induction (Proof)

Let $S$ be a nonempty set of natural numbers. We show that there is an $a\in S$ such that for all $b\in S$ $a\leq b$ Suppose not, then $$(*)\ \ \ \ \ \forall a\in S,\exists b\in S\ \ b<a.$$ We will use the principle of finite induction (the strong form) to show that $S$ is empty, a contradition.

Fix any natural number $n$ and suppose that for all natural numbers $m<n$ $m\in \mathbb{N}\setminus S$ If $n\in S$ then (*) implies that there is an element $b\in S$ such that $b< n$ This would be incompatible with the assumption that for all natural numbers $m<n$ $m\in \mathbb{N}\setminus S$ Hence, we conclude that $n$ is not in $S$

Therefore, by induction, no natural number is a member of $S$ The set is empty.




"well-ordering principle for natural numbers proven from the principle of finite induction" is owned by smw.
(view preamble | get metadata)

View style:

See Also: natural numbers are well-ordered


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

Cross-references: induction, implies, strong, principle of finite induction, natural numbers
There is 1 reference to this entry.

This is version 2 of well-ordering principle for natural numbers proven from the principle of finite induction, born on 2007-01-27, modified 2007-06-21.
Object id is 8835, canonical name is WellOrderingPrincipleForNaturalNumbersProvenFromThePrincipleOfFiniteInduction.
Accessed 1597 times total.

Classification:
AMS MSC03E25 (Mathematical logic and foundations :: Set theory :: Axiom of choice and related propositions)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

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