April 02, 2017 Sunday
Bedtime Story
Provability, Effective Axiomatization and Recursively Enumerable Set
A formal system of arithmetic allows one to derive new theorems
from the basic axioms.
The first order Peano arithmetic is an example of such a formal
system of arithmetic.
I have stated these axioms of Peano in one of my bedtime stories.
It is a way of deriving all the natural numbers from pure logic.
The very first assumption or the axiom is that 0 is a natural
number.
This is not a fact; it has to be assumed.
A word on the provability that these theorems speak about.
The provability of any theorem refers to its ability to be derived
from the axioms that have been used to construe such a formal system.
That has to be carried out using specific rules of inference.
The other terms that are crucial for understanding these two
theorems are completeness, consistency and effective axiomatization.
I had discussed the concept of completeness and consistency when I
had enlisted the Hilbert’s Program in one of my bedtime stories.
We had also discussed axiomatization when we had come across the
contradictions that Cantor’s set theory gave rise to and how Zermelo and
Fraenkel came out with their own axioms along with the axiom of choice to get
rid of them.
Here the new term is effective axiomatization.
Effective axiomatization of a formal system means that a system
can list all its theorems without listing any theorem that is not a part of it.
In the language of mathematics and also computing, the term used
is recursively enumerable set.
A better way of understanding this (and both the theorems) is to
speak in terms of programming and algorithm.
So a formal system (say that of the natural numbers), would be
recursively enumerable if one can develop an algorithm that will list all its
members (whether they be numbers or theorems) in an orderly way without listing
any member that is not a part of it.
Now we have laid enough ground work to grasp the essence of the
two theorems.
For recall, let me once again state the first incompleteness
theorem.
“Any consistent formal system F within which a certain amount of
elementary arithmetic can be carried out is incomplete; i.e., there are
statements of the language of F which can neither be proved nor disproved in
F.”
Let me warn you that Gödel’s proof is extremely difficult, more so
if you are untrained in mathematics and mathematical logic.
It requires knowing of at least 46 prefatory definitions and many
theorems before reaching the main chunk of the proof.
Yet it’s worth making an attempt to understand it to make this
life worthwhile.
Stay tuned to the voice of an average story storytelling
chimpanzee or login at http://panarrans.blogspot.in/
Good night mon ami and my fellow cousin ape.
Advertisements
Another great educator and a teacher that I am aware of is
Professor Subhashish Chattopadhyay in Bangalore, India.
While I narrate stories, Professor Subhashish an electronic
engineer and a former professor at BARC, does and teaches real mathematics and
physics.
He started the participation of Indian students at the
International Physics Olympiad.
Do visit him here:
All his books can be downloaded for free through this link:
For edutainment and English education of your children, I
recommend this large collection of Halloween Songs for Kids:
No comments:
Post a Comment