Chap ter 6
Computability
6.1 FORMAL SYSTEMS
The necessary properties of a satisfactory formal system are as follows:
(a) Completeness: It should be possible either to prove or disprove any
proposition that can be expressed in the system.
(b) Consistency: It should not be possible to both prove and disprove a
proposition in the system.
Consistency becomes crucial if it becomes possible to prove and disprove
some proposition in the system, which means the same can be done for every
proposition in the system.
In the late 1800’s there were a lot of mathematicians who were working on
a method of putting together all of mathematics, starting from the axions of set
theory.
In fact, sets can have other sets as members. In 1901 Bertrand Russel
discovered the Russel’s Paradox:
Rus sel’s Par a dox
“Consider the set of all sets that do not have themselves as a member. Is this set
a member of itself?”
This problem was tried to be resolved by the way of defining “type”. This
theory of types though not accepted fully have paved way for new
philosophies of mathematics.
Godel was able to express proofs as numbers like considering a computer
program to be a very large binary number. Godel proved the following result:
“If it is possible to prove, within a formal system, that the system is
consistent, then the formal system is not, in fact, consistent.”
Equivalently, we can say,
“If a formal system is consistent, then it is impossible to prove (within
the system) that it is consistent.”