The Well Ordering and Pigeonhole Principle
The Well Ordering Principle
The Well Ordering Principle: A least element exist in any non empty set of positive integers.
This principle can be taken as an axiom on integers and it will be the key to proving many theorems. As a result, we see that any set of positive integers is well ordered while the set of all integers is not well ordered.
The Pigeonhole Principle
The Pigeonhole Principle: If s objects are placed in k boxes for s > k, then at least one box contains more than one object.
Proof. Suppose that none of the boxes contains more than one object. Then there are at most k objects. This leads to a contradiction with the fact that there are s objects for s > k.
Post a Comment for "The Well Ordering and Pigeonhole Principle"