10-Jun-2013, 04:24 AM

After attending the intro course to Logic on coursera, I got a vague idea of Godel's incompleteness theorem and would like to share my understanding here.

One of the key term to note here in the above statement is provable. In general language this can mean a lot more than what is implied in the statement. In logic provability has a very very specific meaning and the statement has to be understood ONLY in that context. For any axiomatic system, one can have a "proof system". The reason for having the proof system is as follows:

Now a complete system is a logic system which has a proof system by which every true statement can be proven so.

And a consistent system is a logic system whose axiomatic propositions (the ones that are assumed to be true as given) don't have any inconsistency (one proposition being true doesn't lead to other proposition being false).

Now what Godel proved that was for a sufficiently complicated logic system it cannot be complete and consistent at the same time. i.e. There doesn't exist a proof system such that every true statement in that logic system can be proved so, or if such a proof system exists, it is guaranteed that the axiomatic propositions are inconsistent.

Now this part is absolutely not applicable to Physical sciences because they don't have the so called "proof system" as used in logic. Infact physical sciences don't deal with ONE logic system but with TWO logic systems. One being the laws of universe and second being human's formulation of those. So what scientists actually do is check if these two logic systems match by comparing their outputs. The truth value for scientists is thus "comparative'" and not based on some proof system.

Second should be pretty straightforward to understand. It merely states that a sufficiently complicated logic system cannot prove consistency of its axiomatic propositions. If it is able to do that then it is certainly inconsistent.

In here as well its important to note that its about provability in the sense defined above and nothing in the sense what physical sciences (empirical evidence or inference to best explanation) use.

Quote:First incompleteness theorem:

Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true,[1] but not provable in the theory (Kleene 1967, p. 250).

One of the key term to note here in the above statement is provable. In general language this can mean a lot more than what is implied in the statement. In logic provability has a very very specific meaning and the statement has to be understood ONLY in that context. For any axiomatic system, one can have a "proof system". The reason for having the proof system is as follows:

- A logic system is defined by its axioms, i.e. some propositions which are considered to be true as given.

- Now a statement's truth value can be evaluated substituting the truth values of these proposition. For example consider an axiomatic system which assumes A and ~B (not B) propositions to be true and defines standard logic operators | and &, i.e. "or" and "and". Then the truth value of statement "A | B" can be evaluated as True and "A & B" as false by mere substitution of truth values of A and B.

- But its not always easy to do so as number of such propositions or variables can be huge and infact infinite (like all numbers in a number system). So in such cases an alternate approach is followed to derive the truth values of statements.

- This is done via defining a "proof system" for that logic system and then following its rules to derive the truth value of the statement.

Now a complete system is a logic system which has a proof system by which every true statement can be proven so.

And a consistent system is a logic system whose axiomatic propositions (the ones that are assumed to be true as given) don't have any inconsistency (one proposition being true doesn't lead to other proposition being false).

Now what Godel proved that was for a sufficiently complicated logic system it cannot be complete and consistent at the same time. i.e. There doesn't exist a proof system such that every true statement in that logic system can be proved so, or if such a proof system exists, it is guaranteed that the axiomatic propositions are inconsistent.

Now this part is absolutely not applicable to Physical sciences because they don't have the so called "proof system" as used in logic. Infact physical sciences don't deal with ONE logic system but with TWO logic systems. One being the laws of universe and second being human's formulation of those. So what scientists actually do is check if these two logic systems match by comparing their outputs. The truth value for scientists is thus "comparative'" and not based on some proof system.

Quote:Second incompleteness theorem:

For any formal effectively generated theory T including basic arithmetical truths and also certain truths about formal provability, if T includes a statement of its own consistency then T is inconsistent.

Second should be pretty straightforward to understand. It merely states that a sufficiently complicated logic system cannot prove consistency of its axiomatic propositions. If it is able to do that then it is certainly inconsistent.

In here as well its important to note that its about provability in the sense defined above and nothing in the sense what physical sciences (empirical evidence or inference to best explanation) use.