Here we turn Hilbert’s Hotel on its head. Instead of frantically

shuffling infinitely many guests for one room to the next in

Hilbert’s mythical infinite hotel, we start with a leisurely walk

through an ordinary and quite finite village.

Click for full text

*The Drinker’s Theorem: Consider the set of all drinkers in the world, and the set of all people in a given pub. Then there exists a person who, if he or she is drinking, then everyone in that pub is drinking. *

It doesn’t matter how many people are there. Or how many are drinking. Or how few. No one needs to be taking their cues from some “lead drinker,” but in every pub, in every town and village, it just happens! How is this possible?

There are several possible approaches to this problem. Here, we will turn to British philosopher and mathematician, Bertrand Russell (1872 – 1970). His famous Paradox is the key.

Click for full text

(Important revisions: March 13, 2015)

The Definition of the set of natural numbers

is given by nothing more or less than

Peano’s Axioms.

Click for full text

Revised: October 20, 2014

Click here for Full Text

Important revision: January 12, 2015

Now featuring a formal construction of the

partial function for exponentiation on *N*x*N.*

The Cantor-Bernstein-Schroeder Theorem (CBST), is one of the most important and widely applied results in set theory:

If set

Xcan be mapped one-to-one into setY(an injection), and setYcan be mapped one-to-one into set X (an injection), then X can be mapped one-to-oneonto Y(a bijection).

Though seemingly self-evident, some proofs of CBST can make your head spin! Every line of my machine-verified, formal proof (updated 2014-09-11) is justified by one of a very limited list of simple axioms and rules of inference (indicated in a grey font at the end of each line).

Such complete rigour does come at a price, however. While it is completely free of any of the sort of the hand-waving that plagues many informal versions of this proof, like most formal proofs of any complexity, it is *very* long. My commentary (indicated by a blue font) is inserted throughout using *DC Proof.* I believe this makes my proof considerably more readable than machine-generated formal proofs in other systems.

This proof was written to demonstrate he capabilities of the *DC Proof* system. Though designed for ease of use by the complete beginner, *DC Proof* is quite capable of some mathematical heavy lifting.

Revised: April 8, 2015

According to the Pigeonhole Principle, if you have more pigeons than pigeonholes (as in photo), then at least two pigeons will be in the same hole. Here we present a *non-numeric* version.

Usually, *more* pigeons than pigeonholes is taken to mean that the *number* of pigeons is *greater than* the *number* of pigeonholes. Here, we take more pigeons than pigeonholes to mean that the set of pigeonholes cannot be mapped *onto* the set the pigeons.

In this sense then, we can prove that, if we put a non-empty set of pigeons into a set of pigeonholes and there are more pigeons than holes, then we will have put at least two pigeons in the same hole. Note that there is no requirement here that there be finitely many pigeons or pigeonholes.

See formal proof (51 lines) at The Pigeonhole Principle: A non-numeric version.

The set of natural numbers can show up in the oddest places! Suppose, for example, that *f* is *any* function defined on *any* non-empty set *S*, subject only to the following conditions:

*1. f* is injective (one-to-one)

*2. f* is not surjective (not onto) *

Since *f* is not surjective, by definition, there must exist at least one element of *S* that has no pre-image under* f*. Each such element can be shown to be the starting point (the 0 or 1) of its own distinct number system satisfying Peano’s Axioms for the natural numbers, with* f* as the required successor function.

See the formal proof (112 lines in the DC Proof format) at Constructing the Natural Numbers

**Follow-up **(2016-01-16)

Interestingly, if *f* is just an arbitrary function on *S*, then, for every element *x* in *S*, we can construct a subset of *S* on which induction will hold, using *f* as the successor function and *x* as the “first element” of that subset.

See the formal proof (89 lines in the DC Proof format) at Minimum Requirements for Induction.