Saturday, January 26, 2013

64. Russell's Paradox

Constituents of a complex system interact with one another, and with the surroundings. This interaction can be viewed as communication of information.

I introduced the basics of information theory in Part 21 and algorithmic information theory in Part 23. Shannon’s formulation of information theory was originally meant for designing better communication channels. An interesting aspect of modern communication theory is that the merit of a particular communication-channel design lies not just in how well the actual message is sent, but also in how well the channel could have sent all the other messages it might have been asked to convey.

It is instructive to adopt a historical approach and trace the development of ideas regarding the nature of information and information-processing (or what is now better known as computation).

Let us begin by talking about 'sets'. [A set is a unification of well-defined objects of thought into a whole. Here are some examples: a set of chairs; a set of red chairs; a set of integers; a set of odd integers; the set of all odd integers.]

At the beginning of the 20th century the mathematician David Hilbert asked a question in the theory of infinite sets: Starting from 1, 2, 3, . . ., what is the largest integral number one can think of? Whatever that integer is, let ω be the first number after all the finite numbers we can think of. So we get 1, 2, 3, … , ω.

We need not stop there, and can go on adding the next higher integers to the set: 1, 2, 3, … , ω, ω+1, ω+2, … . Let 2ω be the next integer after all the integers in this set: 1, 2, 3, … , ω, ω+1, ω+2, … 2ω. We can go on and on:

1, 2, 3, .., ω, ω+1, ω+2, .. 2ω, . . 3ω, . . 4ω, .. ω2, ω3, .. ωω, ...

Even this can go on. We shall reach ω to the power ω to the power ω  . . .; and so on, forever. The set is infinite.

Georg Cantor proved a theorem which said that for any infinite set there is a larger infinite set which is the set of all its subsets. This is sometimes referred to as Cantor’s diagonal argument. [A subset is a portion of the set.]

Now suppose we apply this theorem to the infinite 'universal' set; by definition it is the set comprising of all the sets. Application of Cantor’s theorem here leads to a paradox because the theorem says that there should be a set still larger than the universal infinite set.

This paradox was noticed by Bertrand Russell. The seminal work Principia Mathematica by Whitehead and Russell (1925-1927), the first edition of which was published during 1910-1913, included a new formulation of set theory by Russell; he was led to it during his sustained efforts to solve the following problem posed by him about sets:

Consider a set A, defined as a set containing all sets that are not members of themselves. Does A contain itself?

Unless you are a politician, the two possible answers are Yes or No (a politician may say 'yes and no'). If the answer is Yes, there is a contradiction because set A is defined as a set containing sets which are not members of themselves.

If the answer is No, again there is a contradiction. Since A is defined as a set comprising of all sets which do not belong to themselves, it should contain itself. But according to the second answer, A does not contain itself.

This means that we can have incompatible propositions that imply one another.

This famous paradoxical situation goes by the name of Russell's paradox. Apparently, Yes implies No, and No implies Yes.

Here is another example of the Russell paradox, called the Barber Paradox: There is a barber in a small town where every man is clean-shaven. The barber shaves all men who do not shave themselves and only those men who do not shave themselves. The question is: Who shaves the barber? There is a paradox here, no matter what answer you give:

If the barber does shave himself, then the barber (himself) must not shave himself; and if the barber does not shave himself, then he (the barber) must shave himself.

Russell's work for resolving this paradox that now goes by his name led to a reformulation of mathematics in terms of his new theory of sets, mentioned above. After much mental agony and loss of sleep, his final resolution of the problem was as follows:

He first imagined what we now call a theoretical computer. It was essentially a sequential logic machine. This imaginary machine carries out one logical operation at a time, i.e. it operates in discrete time. The answers about a set are dealt with sequentially, and one at a time. Thus, at any given point of time the answer may be, say, Yes. But the theoretical computer keeps running, and a few time steps later the answer becomes No. The program runs in an infinite loop, alternating between Yes and No. Thus there is said to be no paradox because the answer is never Yes and No at the same time! Are you convinced by this explanation?

Hilbert applied an approach different from that of Russell for tackling the problems posed by Cantor in set theory. He tried to use, and improve upon, Euclid’s axiomatic method. The idea was to take the apparatus of symbolic logic to its extreme. He argued that one reason we get into contradictions in set theory is that words often have a vague meaning. So why not come up with a finite set of formal axioms and an artificial language for doing mathematics? This artificial language must have strictly precise grammatical and other rules.

Did Hilbert succeed? I shall answer that next time.