September 23, 2017 Saturday
Bedtime Story
Gödel’s completeness theorem establishes a
formal connection between semantic truth and syntactic provability in
first-order logic.
You will get it once I discuss the theorem
with you.
Gödel proved this theorem in 1929 and he
stated it as follows:
If a formula is logically valid, then there
is a finite deduction (formal proof) of the formula.
In a way, this theorem is implying that the
deductive system of a first-order predicate logic is complete.
By complete, he means that all the logically
valid formulas can be proven using the established rules of inference.
The implication of this theorem is that a
formula is logically valid, if and only if it is the conclusion of a valid
deduction.
It can also be stated in terms of model theory.
Let me tell you briefly what a model theory
is.
Model theory studies classes of
mathematical structures (such as universes of set theory, graphs, groups) from
the perspective of mathematical logic.
The object of study is models of theories
in formal language.
It examines the semantical elements
(meaning and truth) by means of syntactical elements (formulas and proofs) of a
corresponding language.
A simple way of putting model theory is
universal algebra + logic or an even simpler way is to say that model theory
deals with what is true in different models.
Model theory stands on the cross roads of
several fields such as mathematics, computer science and even philosophy.
Gödel’s completeness theorem establishes a
close link between this model theory and proof theory.
If model theory studies what is true in
different models, then proof theory studies what can be formally proven is
specific formal systems.
So in a way it establishes a link between
truth and proof.
So Gödel’s completeness theorem can also be
expressed in terms of model theory in the following way:
Every consistent, countable first-order
theory has a finite or countable model.
A consistent theory is defined as one in
which for no formula F, both F and ¬F can be proven.
That simple means that for a given formula
in a consistent theory, it is not possible for it to be both true and not true
at the same time.
At first glance it does appear that Gödel’s
completeness theorem and incompleteness theorems contradict each other.
So it behooves me to set these two theorems
next to each other and consider if there is any tension between those two.
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