2011 | OriginalPaper | Chapter
Finite Sets and an Infinite Set
Authors : Ulrich Daepp, Pamela Gorkin
Published in: Reading, Writing, and Proving
Publisher: Springer New York
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We have proved that sets are finite, but we have not yet shown rigorously that a set is infinite. It is not as easy as you might think to do so, nor do we have an exact notion of what it means for a finite set “to have
n
elements.” Our proof of the former and the definition of the latter will depend on a principle known as the
pigeonhole principle
. The pigeonhole principle is something that is familiar to all of us. As a very simple example of this, recall a childhood birthday party in which you played musical chairs. In case you weren’t invited to any parties, we’ll remind you of the rules behind the game. Let’s say there were 10 children at the party. Someone, say the child’s father, would set up 9 chairs in a row. Someone else, say the child’s mother, would play a song on the piano stopping unexpectedly at some point. When the music ended, the 10 children would scramble for the 9 seats. If everyone sat down, two people would sit in the same chair. This game is our first example of the pigeonhole principle. Now we turn to a more elaborate one.