## Wednesday, April 17, 2013

You've almost certainly heard some of these (logical) paradoxes. They're fun brain puzzles, and people like to share them. Surprisingly, most people who share them do not know their solution, nor try to solve them. Here are some of the most well known paradoxes and their solutions.

Note that these are paradoxes of more logical nature (i.e. "mind puzzles"), and consequently, their solutions explore logic and language.

There are also paradoxes within scientific theories, with scientific solutions, which I might write about another time.

### Problem

Perhaps the most well known paradox. The version of the paradox that is the most clear is the following. Consider the sentence: "This sentence is false". We are wondering whether the sentence itself is true or false.

Assume the sentence is true.
Then clearly the sentence is false, a contradiction.

Now assume the sentence is false.
Then the sentence is true, also a contradiction.

It seems we cannot assign a binary truth value (true/false) to the sentence.

This paradox is sometimes given in the form: A person says that he is lying. Is he telling the truth or a lie?

### Solution

There are two things that are unusual about the sentence.

First, it makes a reference to itself, by using the word "this sentence". This is known as self reference, and the statement is said to be self-referential.

Second, the sentence assumes that it can express the truth/falsehood of other statements.

To see this, imagine that we were to express the sentence in a more formal language. It would look something like:

Sentence 1: not is_true(get_sentence(1))

In other words, we are assuming that we can get a sentence by it's label ("get_sentence(1)", which is the sentence itself, since we gave it label 1) and that we have a predicate "is_true" which returns true/false accurately (we need not assume anything about the computability of these functions, only that they are definable within the language).

If you haven't studied logic you might be inclined to think that the first point is a pretty serious problem whereas the second is trivial. You'd be wrong, however, because it's the other way around: assuming we can express "is false" is a much more problematic issue than using self references.

Here's why:
Self-referential statements are everywhere. I can easily get rid of the self reference in the liar paradox by doing the following:

Sentence 1: "Sentence 2 is true"
Sentence 2: "Sentence 1 is false"

If Sentence 1 is true, then both are true, which in turn means that Sentence 1 is false, a contradiction.
If Sentence 2 is false, then both are false, which in turn means that Sentence 1 is true, a contradiction.

You might feel like this point is moot, cause all I've done is replaced "this" with a reference to another sentence, which in turn references back to the first sentence. After all, decoupling the sentence does solve much since we can still express everything using get_sentence and is_true:

Sentence 1: is_true(get_sentence(2))
Sentence 2: not(is_true(get_sentence(1)))

That's a good point, except that the problem doesn't go away even if you forbid all kinds of references (to the language itself). In particular, almost any logical system can be re-encoded so that the sentences can be seen to implicitly contain self references. This is done using something called Gödel encodings, and it is roughly the equivalent of assigning every sentence in the English alphabet a unique number in a systematic way. get_sentence is easy to construct, even in languages where it was not intended to exist.

The same cannot be said for is_true: it does not in general exist. For example, arithmetic does not admit a truth predicate so there is no way of expressing "1+2=3 is true" in arithmetic. This result is known as Tarski's undefinability theorem.

You might wonder what all of this has to do with the English language, in which the paradox is presented. Well the point is that if we allow unrestricted use of natural languages (such as English), we can express pretty much anything. The problem is that many things we can express in English won't even be logical sentences, in the sense that they will not have truth values (such as the sentence under consideration). Unrestricted use of language also opens up the possibility for expressing nonsense.

What we can learn from the liar paradox is that we must clearly handicap our "language" if we wish to have a "no nonsense" language (e.g. predicate logic, modal logics, Horn clause logic). How do we handicap such languages to make sure the liar paradox doesn't appear? Gödel has shown us that there isn't much point in trying to remove self references; they occur very easily. Taski has shown us that a truth predicate "is true" is not usually available, so this is certainly more of a comfort.

In arithmetic, you cannot express sentences such as the liar paradox, not because it is self referential, but because it asserts the truth of arithmetical sentences. Put differenty, in arithmetic, is_true is not definable.

### Problem

The barber's paradox arises from the following assumption and question: A barber shaves everyone who doesn't shave themselves. Does he shave himself?

As we did for the liar paradox, we check to see which is true:

Assume the barber shaves himself.
Then he doesn't have himself, since he only shaves those that don't shave themselves.

Now assume the barber doesn't shave himself.
Then he shaves himself, a contradiction again.

### Solution

So this sentence is neither true nor false. As mentioned in the liar paradox, that is not so much of a problem in English, because we really shouldn't expect all sentences to even make sense. There is no problem in imagining a barber that shaves everyone who don't shave themselves, except that he shaves himself too. Or a barber that goes to another barber. The problem is within the confines of language, physically, there is no way to create the contradiction.

The lesson to learn from this was a hard one historically. Russell's paradox is a more formal (mathematical) version of the paradox, which has to do with set theory. Imagine that a set is a box. We can have an empty box, or put boxes inside empty boxes. So denote the empty box with { }. If we have something, X, inside a box, we'll write {X}. And if we have two things, like X and Y, we'll write {X,Y} and so on. Assume we're allowed to create boxes by (perhaps infinitely) repeating the following:

The empty box {} is a box.
{X,Y,...} is a box if X,Y,... are all boxes.

So we know that {} is a box, and { {} } is a box (the box that contains an empty box). Then we can put that box inside a box: { {{}}}. But these are not the only ways we can make boxes. We can put all three of these boxes into one box: { {}, {{}}, {{{}}} }. If you're wondering why this is useful to do in mathematics, it's because from this you can create all numbers. For example, define:

0 = {}
1 = {0} = { {} }
2 = {0,1} = { {}, {{}} }
3 = {0,1,2} = { {}, {{}}, {{},{{}}} }
...

These seems all good, until you define the following box (set):

B is the box containing all boxes that do not contain themselves. Does it contain itself?

What is meant by a box that contains itself? It quite literally means that you can find a copy of the box inside the box. If you think that's impossible, it's because you're thinking only about finite boxes. If we have infinite nesting, such as {{{{...}}}}, then if we "box it", i.e. wrap it around one more { }, we can see that the box has a "copy of itself". So let X = {{{....}}}. Then {X} is a box containing itself, but so is {X,X}, {X,{}}, {X,{},{{}}}, and so on. So there's not just one box that contains itself, but an infinite number.

Now back to the paradox: Does B contain itself?
Assume it does. Then B is inside B, i.e. B = {B,...}. But B is the box containing all boxes (say X) that do not contain themselves. Since B contains B, B cannot be X here. Therefore B does not contain itself.
Now assume B does not contain B. Then, since B contains all X that do not have X, and B is precisely such an X, B contains itself.

So we have: B in B if and only if B not in B, i.e. the set contains itself if and only if it does not contain itself. It's usually said to be a contradiction, but it is technically not: you can't prove "B in B" or "B not in B", only that "B in B iff B not in B". It's only a contradiction if you assume that the sentence must be true or false.

Regardless, it is an undesirable feature of a logical system to say the least.
So these simple rules to create boxes actually lead to the possibility of creating a sentence that is neither true nor false (or both). What set theorists learnt from this is that the creation of boxes (sets) must be restricted (see Von Neumann Universe for three intuitive rules that create sets without this paradox).

Technical note: Boxes are defined so that they can contain multiple copies, e.g. { {}, {} }, whereas (non-fuzzy) sets either contain or do not contain an element. Boxes are in fact multisets. None of this changes the argument however: from sets one can create multisets, and vice versa.

### Problem

Zeno's paradox has many forms, here's one that is easy to understand: A man is going to walk 100 meters. To reach there, he must first cross 50 meters. But to reach that, in turn, he needs to cross 25 meters. It's easy to see that when we keep halving the distances, we get increasingly smaller numbers (but never exactly zero). This suggests that the man most move "infinitely much" in order to reach the 100 meters (in fact, in order to reach anywhere at all!).

### Solution

The paradox itself makes some questionable assumptions about the nature of reality. More specifically, it assumes that we can divide distances into halves indefinitely. The existence of a smallest measurable length, the Planck length, certainly puts doubt on this.

But even if we accept the premiss, one could ask where the problem really is anyway.
Is it that we find it unreasonable that he can move an infinite number of times? We have already accepted that there's infinitely much space to move in, so perhaps we should also accept that he can move infinitely much (in finite time), especially since the distances are getting smaller and smaller. Mathematically, he must move: 100/2 + 100/4 + 100/8 + 100/16 + ... = 100 meters. So if we can complete the infinite series, he'll be just fine. From this point of view, Zeno's paradox really illuminates its own assumptions:

1. Space is continuous (we have infinitely many steps to move through).
2. Time is discrete (we are not allowed to pass through all infinite steps).

Modern science suggests both are discrete, in which case there's no problem: at each discrete time step, the person moves forward a finite number of discrete steps. And as shown above, if both are continuous, there isn't any problem either.

Turning the paradox against itself, we can observe that we can indeed move, so the combination of continuous space and discrete time seems incorrect as far as reality goes.

1. Hi John,

Good read, but most of the flaws in perceivable logic seem more like flaws in the English language in that it simply cannot convey any of the above statements in holistic, all-encompassing ways which include all the moving parts of each equation.

I'm no expert in maths, but the idea of "this sentence is false" is a flaw in language, not in logic. Such an event would never exist in nature; a man-made concept with man-made flaws. The simple and most obvious reality is that these paradoxes can't exist without the intervention of flawed man-made language (not logic).

Using flawed language which ignores all variables and moving parts it's easy to make anything seem like a paradox - "The dead have come to life," "My toaster heats all that cannot heat itself," "How can it be 10:00PM when it hasn't been 9:59:999999' yet?" etc.

Discrete time is a man-made concept; it's a trivial way of explaining a supernatural and, so far, unexplainable phenomenon - no different from Aborigines throwing eggs in the sky to make the sun, or some guy with a beard who made the universe and tells us how to live. It was a good enough explanation at the time and serves its purpose (well, not all of my examples serve a purpose).

My point is that I don't believe paradoxes make any questionable assumptions about reality, nor is its nature's job to reveal itself to us. Paradoxes can't exist without mankind's intervention; it is our job to make logic and language that fit without the existence of paradoxes. Limits, like meters or millimeters, are our way of making assumptions that suit our purpose. Nature isn't concerned with our purpose, or our ability to create paradoxes on paper (which are not really paradoxes, just badly-worded statements).

Paradoxes might exist in human language and rationale, but not in reality. The Barber cuts everyone's hair who does not cut their own, as well as his own. My toaster heats all that cannot be self-heated - it also heats itself. The B box contains all boxes that do not contain themselves - no box can contain themselves, so the statement is flawed. It is not a paradox, only a poor expression which could not exist except for mankind's creation of language.

Thoughts?

2. 1. You're essentially restating what I've already stated:
"Note that these are paradoxes of more logical nature (i.e. "mind puzzles"), and consequently, their solutions explore logic and language."

2. And again:
"As mentioned in the liar paradox, that is not so much of a problem in English, because we really shouldn't expect all sentences to even make sense. There is no problem in imagining a barber that shaves everyone who don't shave themselves, except that he shaves himself too. Or a barber that goes to another barber. The problem is within the confines of language, physically, there is no way to create the contradiction."

3. But you're forgetting something:
As can be seen in paradox 1 and 2, they have very real applications within the world of logic, and consequently, the world of computing. You would not be able to read my blog, post, and read my reply, if people didn't consider the logical foundation for information technologies. Enter the abstract but very real world of logic.