Exploding Barbers (Paradoxes — Part I) | Oxford Protein Informatics Group

Prelude

I came upon a traveller on a dust-swept road at dusk.
Along the cliff’s high edge it ran, where seabirds rode the gust;
Upon a stone he rested still, with gaze toward the deep,
As though the sea held secrets vast that mortals may not keep.
Behind us wound the ancient way through heather wild and wood,
To where a castle, firm and fair, upon the hilltop stood.

Then spake the man, his voice a husk: “Now whither goest thou?”
“To yonder keep,” I gave reply, “that crowns the ridgehead brow.”
He nodded once, as if he knew the place as well as I,
And rose as slow as starlight wakes amid a darkening sky.
“Then let us tread,” said softly he, “this path so long and steep—
for those who climb such roads alone may find their footing weak.”

We trod a while in silence ’til I asked him for his name;
He smiled but said, “What’s lost to time is seldom worth reclaim.”
But I shall tell thee of my kin—my brother, eldest born,
A barber dwelling in a vale, both dutiful and sworn.
He shaves the men within his town who shave not for their own—
Yet shaves he not those gentlemen who tend their beards alone.”

I paused, then frowned, and shook my head. “But how can this be true?
If he should shave himself, then lo!—he breaks his rule in two.
Yet if he shave not his own chin, then by his law he must.
The man you speak of cannot be—he’s naught but wind and dust.”
The traveller smiled with cryptic mien, and met my searching eye:
“Perhaps,” he said, “yet still he lived—at least as well as I.”

Basics

This ill-judged little lyrical prelude furnishes our discussion for some elementary remarks on classical logic, starting with propositions. In a very loose sense, propositions are simply statements of (potential) fact about the world—some world, at least. Not everything we might call a “statement” in everyday speech is a proposition, but a lot of those we really care about are: “water boils at 100°C”; “the Earth is not flat”; “Ody may be overthinking his blogpost”.

Propositions may be true ( $T$ ) or false ( $F$ )—the above are all true, in case you’re wondering—and these concepts are mutually exclusive. Something cannot be true and false at the same time; that would be oxymoronic. It may be that the truth value of a proposition is unknown, for lack of information, or it may be that a statement is ambiguous with unclear definitions (in which case it may correspond to multiple possible propositions), but once you nail your definitions down firmly enough, the underlying truth value, known or not, is generally taken to exist (a metaphysically loaded term) ‘out there’ in the void and it is one of these two: $T$ or $F$ . So far, so simple.

Propositions may be composed into new ones by the familiar logical operators ( $\lnot,\land,\lor,\rightarrow, \leftrightarrow$ ) also known as connectives. Given known truth values for the (atomic) components, they yield the truth value of the composite by mindless, mechanical evaluation. This is what we have built the modern world upon. Such a composite proposition is therefore a truth function (typically defined via a truth table) with truth values as inputs and outputs. Implications, i.e. conditional if-then propositions like $p\rightarrow q$ , are particularly important logical connectives. Just like $p\land q$ , an implication is a truth function: if $p$ but $\lnot q$ then $p\rightarrow q$ is $F$ , for example (in fact only then). Some of us like to additionally adorn our propositions with quantifiers ( $\forall,\exists$ ), which make the whole formalism quite a bit more expressive and complicate things a bit, but we shall not go into the details here.

Implications are not be confused with inferences which are statements that connect premises (propositions) and a conclusion (also a proposition) into a logical move, such as $p,\ p\land q \vdash q$ , also written

$\displaystyle \frac{p, p\land q}{q},$

and itself not a proposition. Inferences are not truth functions—they are statements of an argument (a structural relationship between propositions, i.e. potential facts), rather than statements of fact themselves—but they do have a binary property: they can be valid or invalid, and these concepts are mutually exclusive. An inference is (deductively) valid if the conclusion necessarily follows from the premises, i.e. there is no situation in which all the premises are $T$ , but the conclusion is not $T$ .

Implications and inferences alike have some counterintuitive edge cases. The relevant truth table will inform you that $F\rightarrow T$ evaluates to $T$ , for example; this is known as a vacuously true implication. The statement ‘all cell phones in the room are turned off’ is vacuously true in this way if there are no cell phones in the room; the converse is also (vacuously) true—they’re also turned off—which means the conjunction is true, as well (they’re both on and off)—this is no contradiction so long as the phones don’t exist¹. Similarly there are vacuously valid inferences. To illustrate, let’s consider two propositions: “(O)Pigs can fly.” ( $p$ ) and “The Queen was² rich.” ( $q$ ). Two independent (non-vacuously) valid inferences constructed from these propositions would be $(i)\ q \vdash q \lor p$ and $(ii)\ q \lor p, \lnot q \vdash p$ (each conclusion is always true when all of its premises are; you can go through the truth table algebra, if you don’t believe me). Chaining two valid inferences together $(i + ii)$ should give us another valid inference, so we plug in $q$ at the start and get out $p$ . In other words, pigs can fly.

No, wait. What went wrong? We first assumed $q$ in $(i)$ and later assumed $\lnot q$ in $(ii)$ — a contradiction. Therefore there is no situation in which all the premises are true and the conclusion isn’t—in fact, there is no situation in which all the premises are true at all. So the inference is (vacuously) valid by definition, but as a conditional statement whose antecedent is always false, it can never lead us to conclude the conclusion. It gives us no information about the world. And I was so looking forward to my flying lessons…

For this reason vacuous validity does not threaten the integrity of the logical machinery as a means to reason about the world and derive novel facts from known ones. It does demonstrate, however, why contradictions like $q \land \lnot q$ must be defined to be $F$ . If so much as a single contradiction were ever $T$ , you could exploit it by exactly the above inference to derive … anything (ex contradictione quodlibet) and blow up the entire edifice. Appropriately, this is known as the principle of explosion.

The Man That Must Not Be

Which brings us back to the traveller’s elder brother, the barber who shaves all those—and only those—who do not shave themselves. Does he shave himself? Well, if he does, he mustn’t; and if he doesn’t, he must³. A contradiction. We can show this symbolically, too: let’s define $P(x)$ as “ $x$ is a person that needs regular shaving” and $S(x,y)$ as “ $x$ shaves $y$ “. We then describe the barber thus: $\exists x: P(x)\ \land\ (\forall y : P(y) \rightarrow (\lnot S(y,y) \leftrightarrow S(x,y)))$ . Now, $y$ is universally quantified, so there comes a time when we must evaluate the case $y=x$ , in which case we get $\lnot S(x,x) \leftrightarrow S(x,x)$ , which is a contradiction (and hence $F$ ). So we end up with $\exists x: P(x)\ \land\ F$ , which, believe it or not, is $F$ . No such barber can exist. He must not exist.

… right?

The plot thickens in Part II (coming soon)…

Footnotes

Defining $F\rightarrow T$ (an implication—i.e. conditional—with an antecedent that is false or fails to refer to anything) as $T$ rather than $F$ is actually quite important for the syntax to work as one would expect. We want to be able to make statements like $\forall x:\ P(x)\rightarrow Q(x)$ and have them be true even if there are $x$ for which $P(x)$ fails and $Q(x)$ happens to be true. $F\rightarrow F$ evaluates to $T$ for the same reason. ↩︎
RIP ↩︎
At least if we assume he needs shaving in the first place—work with me here. ↩︎

Author

Odysseas Vavourakis

View all posts