Skip to content

If Pigs Could Fly

In mathematics, for any true-or-false propositions A and B, we can infer that A implies B knowing only that A is false. It’s only logical. Honest! See material implication.

Last updated: 2019-04-14

The Barber Paradox Revisited: Why We Need Set Theory


Here we consider simple variations of the famous Barber Paradox (3 versions) and demonstrate the need for set theory in a very simple and direct way. We will prove using set theory that the fabled village barber can actually shave those and only those men in that village who do not shave themselves if and only if that barber is not a man in the village. This would seem to be impossible to prove using only first-order predicate logic.

Last updated Feb. 10, 2017

Click for full text


Infinity: The Story So Far


Last updated: Nov. 18, 2015

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 Paradox: A Tale of Three Paradoxes

bertrand and friends

Last updated: Oct. 12, 2015

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


What is a number again?

Last updated: Nov. 1, 2016

The Definition of the set of natural numbers
is given by nothing more or less than
Peano’s Axioms.

Click for full text


Oh, the ambiguity!

Oh, the ambiguity!

Extensive revisions: November 12, 2019

Click here for Full Text


Formal Proof of the Cantor-Bernstein-Schroeder Theorem

File:Georg Cantor2.jpg

Georg Cantor
1845 – 1918

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

If set X can be mapped one-to-one into set Y (an injection), and set Y can be mapped one-to-one into set X (an injection), then X can be mapped one-to-one onto 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 the 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.


The Pigeonhole Principle

Ten pigeons in nine holes

Last updated: Oct. 21, 2016

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 (70 lines) at The Pigeonhole Principle: A non-numeric version.

Daddy, where do numbers come from?

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 fEach 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.

Follow-up (2018-11-12):  Accessibility is a Necessary and Sufficient condition for Induction

Suppose X is a set (possibly finite), f is a function mapping X to itself and x_0 is an element of X. Then induction will hold on (X, f, x_0) if and only if there are no isolated subsets P of X that exclude x_0 and  that are not accessible by means of f from outside P.  See formal proof.


The Original Cretan Liar Paradox


The Cretan, Epimenides

The Cretan poet, Epimenides (circa 600 BC), famously wrote that Cretans are “always liars.”

Paradoxically, it would seem that if he was telling the truth, then he was lying. And if he was lying, he only confirmed that he was telling the truth! Well, not exactly.

It turns out that there are many possible narratives that would be logically consistent with the original scenario. Epimenides’ famous rant could, for example, have been the only lie ever told by  a Cretan. All that is required is that Epimenides’ statement be a lie and that at least one Cretan once told the truth.

For a formal proof, see The Original Cretan Liar Paradox.