O'Reilly logo

An Introduction to Mathematical Reasoning by Peter J. Eccles

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

11

Properties of finite sets

There are a number of special techniques available for proving results which involve finite sets. It is clearly possible to determine whether or not a finite set contains an element with a certain property simply by trying each element in turn. More interestingly it is possible on occasion to use ‘counting arguments’ to demonstrate the existence of an element with a certain property without considering the properties of individual elements at all. We consider these techniques in this chapter.

11.1 The pigeonhole principle

We begin by recalling the key step used in the last chapter to prove that the cardinality of a finite set is a well-defined concept. We left for this chapter the proof of the following result. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required