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 20

^{th}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.

## No comments:

## Post a Comment