|
|
|
Viewing Version
2
of
'proof of pigeonhole principle'
|
[ view 'proof of pigeonhole principle'
|
back to history
]
| Title of object: |
proof of pigeonhole principle |
| Canonical Name: |
ProofOfPigeonholePrinciple |
| Type: |
Proof |
| Created on: |
2003-03-14 00:25:37 |
| Modified on: |
2003-03-15 16:24:37 |
| Classification: |
msc:03E05 |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here |
Content:
It will first be proven that, if a bijection exists between two finite sets, then the two sets have the same number of elements.
Let $S$ and $T$ be finite sets and $f \colon S \to T$ be a bijection. Since $f$ is injective, then $|S|=|\operatorname{ran} f|$. Since $f$ is surjective, then $|T|=|\operatorname{ran} f|$. Thus, $|S|=|T|$.
Since the pigeonhole principle is the contrapositive of the proven statement, it follows that the pigeonhole principle holds. |
|
|
|
|
|
