August
08, 2017 Tuesday
Bedtime
Story
A More Rigorous Version of
Earlier,
if you recall, I had told you that I would be discussing a simplified and a
non-formal version of Tarski’s undefinability theorem.
Now
let us consider the stronger theorem that Tarski actually proved.
This
theorem is applicable to any formal language that has negation and wherein the
diagonal lemma holds true.
Stating
diagonal lemma is complicated to say the least.
It
should suffice for us that this lemma or theorem establishes the existence of
self-referential sentences in some formal theories of natural numbers.
Proving
the fundamental limitations of Gödel’s incompleteness theorems and Tarski’s
undefinability theorem becomes possible in those systems wherein the diagonal
lemma is applicable.
First-order
arithmetic has both negation and also a system where the diagonal lemma holds
true.
The
interpreted formal language is defined as (L,N) as we did previously.
The
Gödel number is g(x) as assigned before.
For
every L-formula A(x) there is a formula B such that
B ↔
This
left right arrow represents biconditional logical connective or if and only if.
Let
T* represent the set of Gödel numbers of L-sentences true in N.
With
all this framework of his work, the theorem that Tarski derived was this:
There
is no L-formula True(n) that defines T*.
This
means to say that there is no L-formula True(n) such that for every L-formula
A, True(g(A)) ↔
I
will not go too much into the proof.
Very
briefly, the proof is obtained by using the good old argument of reductio ad
absurdum.
In
this trick one starts with an assumption and then showing that if it were to be
true, it would lead to absurd conclusions which is a proof that it has to be
false.
So
Tarski begins his proof with the assumption that L-formula True(n) defines T*.
He
considered a sentence A of arithmetic.
If
the sentence A is true in N, then True(g(A)) holds in N.
Then
for all A, the Tarski T-sentence True(g(A)) ↔
We
had agreed that diagonal lemma is applicable to first-order arithmetic.
Diagonal
lemma when applied to this theorem gives a result that is contrary to the above
equivalence.
Stay tuned to the voice of an average story storytelling
chimpanzee or login at http://panarrans.blogspot.com
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