Noldorin's Blog

For whatever reason, I remember quite clearly the first time I was introduced to the wonder of paradoxes. Curiously, it was during an English class in my first year of secondary school, and the rather eccentric teacher had a particular tendency to ramble on about any interesting topic (usually well outside of the syllabus). A criticism this is not, as it was many years before the seriousness of GCSEs and A-levels. I think that in looking back I took great enjoyment out of those classes, even if I did not so much realise it then. (And it wasn’t just for the fact that we didn’t spend countless hours analysing poetry or Shakespeare.) Moreover, it is plain now that he was, through a variety of ways, trying to open our young and malleable minds so that they might perhaps (idealistically) become sharp and inquisitive, and remain so through the future years of drudgery.

Before I continue too far on such a tangent myself, let me present the focus of this post, that is one of the paradoxes with which I became acquainted during one of those many unusual English classes. I have forgetten the precise details, but the following I think is a half-way accurate rendition of what was then told (though the many embellishments may differ to those of my former teacher). As you may guess from the title, I term this little problem the “Traveller’s Paradox”, though I don’t think it has any conventional name, and has undoubtedly been repeated in many varying forms.

Warning to unsuspecting readers: the following paradox is presented in the style of a fairy-tale. I was first told it this way, so that’s how I shall gladly repeat it – logic appears far too dull otherwise!

A wearied prince has travelled many leagues on his quest to reach the all but forgotten castle that is the target of his quest; the location of the the legendary gem that is the final chance to save his kingdom from ruin. The pale sun is gradually vanishing behind the horizon as the young man approaches a great fork in the road ahead, far beyond which he can glimpse the tall spires of the castle that is his destination. Having sought his goal by his wits and instincts alone thus far, he is now unsure of which path to take from this point. Alas, time permits him to delay no longer if he is to succeed in his quest, and he must make the choice of road before darkness falls.

Approaching the split in the wide path, he scarcely notices two giants standing motionlessly at the side of the path. In this moment the prince recalls the words of the sage whom he had oft consulted; these twin giants, identical in appearance, were the only living creatures who know the safe pafe to the fabled castle. Yet he has a dilemma, for one of them always lies while the other always tells the truth, and what is worse, no-one may ask either of them but a single question.

Making the wrong choice of path will lead inevitably to peril and the ultimate failure of his quest. Only one of the roads provides a safe route directly to his goal. Not willing to let the fate of his realms rest in the hands chance, the prince knows he must ask one of the giants the question that will tell him the safe path – but which giant, and what question?

Now, before continuing, do ponder for a while the nature of this paradox, if you are not already. I do promise  that this dilemma does in fact have a sane solution, and unlike other paradoxes, is not a fundamental contradiction of logic and reason. Read on only when you wish to see the answer, and more relevantly, the formal (mathematical) method we can use in treating such a paradox.

Mathematical (or formal) logic is arguably at the heart of mathematics itself, and is to many the foundation of all science, philosophy, and general reason. Logic is unfortunately not such an intuitive thing to we as humans (without exception) – at least, beyond the very superficial level. Certainly, what has developed into the field of formal logic (in particular modern research into higher-order logics) would make little to zero sense to anyone discovering it upon the first time. It does not take much consideration to realise that the human mind, not unalike to those of other creatures, is one tailored by the eons of evolution to the tasks of survival and continuation of the species. Indeed, we were never remotely designed to unravel the mysteries of the universe, and it is only through our higher level capacities developed through other means that we may begin to do so. (That is at least the brutal atheists approach, and I am among those who would argue the point at a higher level.)

Without assuming too much prior knowledge of fundamental mathematics, specifically formal logic, I will now introduce an approach to resolving in a (simple?) mathematical manner what initially appears to be a very counter-intuitive situation. Do not fret though, for I myself have barely touched the surface of these areas. Still, for the sake of conciseness, I am going to assume you either have an elementary knowledge of formal logic, or can look up the ideas involved, where necessary. If you haven’t yet seen it, I mentioned a great tutorial for starting out in a previous post. (The Wikipedia pages may be enough if you just want an overview though.)

Firstly, let us formulate the given problem in the language of propositional logic, which involves nothing more than the manipulation of true and false values, in essence. There is no fool-proof way of doing this translation, of course, but read on and I think you will see it all works out pretty well.

Note that I use for the truth value and for the false value here.

To begin let us define the propositional variables and functions we will be using:

By arbitrarily labelling the pair of giants, let represent the truth-telling one and the lie-telling one.

Note that $\equiv$ is not actually a symbol in propositional logic, but just syntax for defining a variable.

Now, using this notation, and carefully analysing the situation (problem) presented in the above text, we can see that the problem is to find a formula for that satisfies a proposition that represents the problem. First, observe that whichever giant you ask, the reply you get will be either or in response.

The proposition that defines the situation is then:

In words, that is: asking the particular question to either giant, you will get the same response (yes/no answer) every time, and this answer will also indicate that you should take path (if true, the “first” path; if false, the “second” path).

Unsurprisingly perhaps, there is no well-defined procedure for finding the correct formula for . (There are in fact a number of perfectly valid/equivalent solutions that are relatively simple.) Now, since is simply a function of the propositional variable , we can quite easily factor out the dependence on and still write without loss of generality as:

If one wanted to be utterly rigorous, one could then take this formula for , substitute it into the problem definition, and use the rules of inference (for whatever formal system) to manipulate it into a form that explicitly gives and . On the other hand, I’d rather not lose any readers I still have at this point, so let’s do things the slightly more intuitive way by using some simple human analysis!

The propositional operator , while defined as the bidirectional application of the logical implication operator (i.e. ), can also be seen as representing equivalence of two formulas. (This can indeed by proven formally, though again it’s not really worth the space here I feel.)

Taking the original proposition, we can see (again, with a bit of higher-level analysis) that it implies both:

and

By straightforward substitution for , and a bit of simplification, we can then deduce that:

With the understanding of as representing identity, as previously stated, we can substitute the values for and back into the previous formula to get the following.

Problem solved… right? Well no, not quite actually. If we had mechanically applied the rules of inference from the axioms and the formulaic representation of the problem, we would undoubtedly be able to stop at this point (requiring a good few more pages of derivation however). Since we have not been completely rigorous, we must now prove that this definition of is indeed a correct solution to the problem. Let us substitute the formula back into the problem definition and see.

Hence, we now know that the above solution is correct. What remains is only to translate this formula into plain English. Not so trivial, I think we would agree. The first thing to note is that the parameter is unknown to the prince who asks the question. Well, enough hints…  let’s see if anyone can figure it out first (no cheating), and I’ll update the post with an answer when I get the chance

Interpretation of Solution

After a much undue delay, let me at last conclude this cliff-hanger post with an interpretation of the solution that was presented in the original version. My apologies to those who have been waiting for the “final chapter”, since I did initially suggest that this edit would be following shortly. Fortunately however, I have had a few comments during this period that have insured this post did not totally slip out of memory! Thanks to Jerry for a concise worded explanation of the correct solution to this paradox.

I have in fact realised after a bit more consideration that the tricky part of this whole problem is in fact the translation from formal logic back into human context. Here is the explanation anyway; hopefully this discourse into formal logic, while perhaps shooting the proverbial fly with the cannon, will at least serve as a gentle and intriguing introduction to the subject.

We start with the form for that was previously derived.

A bit of manipulation using the standard rules of inference (boolean algebra, if you will) gives the identical definition:

Now we are in a slightly better position to analyse the form of the logical predicate (practically, the question to ask the giant). Firstly, note that the expression returns the wrong path if you ask the truth-telling giant, and similarly returns the correct path if you ask the lie-telling giant. Hence, the combined expression can be summarised as “what giant X knows the other giant would tell you to take”. Of course, what giant X himself says may truthful or false, but if you recall the original statement of the problem; ; it should be apparent that you will be told to take the same path irrespective of which giant you ask the question! It has already been proven at the end of the main section that this is indeed the correct path, that is, the one that will lead to the success of the quest and the saving of the kingdom.

We can now finally translate the paradox’s solution into words, which goes something like:

You ask either giant the question: what is the opposite of the path the other giant would tell me to take? That path is without doubt the road to your goal, so you immediately take it.

Or in a slightly more natural phrasing:

You ask the giant the question: what path would the other giant tell me to take? That path is then without doubt the road to peril, so you immediately take the other one.

Enlightening or just a round-about way of stating what is a surprisingly simple solution to a paradox, I do not know! Regardless, I hope at least that my argument has all fallen together cohesively by now, and that it has been an enjoyable excursion into the realms of formal logic and giants.