Notation: The logical product, or conjunction, of two declarations P and Q is expressed PQ (P and Q) or P.Q.
A logic language uses a finite set of symbols. A declaration is a legal arrangement of symbols in a string of finite length. It doesn't matter whether the declaration "makes sense."
A theory T contains a denumerable (finite or not) set of axioms and a denumerable set of declarations. That that set is infinite is shown by the simple P --> P --> P --> ad infinitum.
In any case, we need worry about nothing but the axiom subset of T. That is, if a declaration is regarded as provable, then it must be derived from axioms via modus ponens, as in AxAy --> Q, where Q is a theorem.
Note that though the axiom set may be infinite, proofs demand that a finite subset be used since an infinite chain of conjunctions means that a deduction is never realized. So then any provable or derivable theorem has a finite chain of declarations linking the theorem to some finite subset of axioms. This last statement expresses the deduction theorem. Hence, we can simply cite the axioms that yield the theorem. The intervening chain is built and checked by mechanical procedure, of course.
So we may express any provable theorem of T thus:
Π Ai --> P, in which case P is customarily taken as an element of T, though not always.
Now suppose we write Π Ai --> P. This may be rewritten ~(Π Ai) v P. Then, ~~[~(Π Ai) v P]. Then ~[(Π Ai).~P].
We denote that last declaration by R (some would call this a meta-declaration). R denies that the axiom subset can be true while P is false. But suppose P says, "This declaration cannot be derived from axioms" (or "This declaration is not provable in T")? Yet R assures P cannot be false. So, intuitively, we are inclined to accept it as true. Yet P cannot be proved. So, if P is true then T is incomplete. If P is false, then it can be derived from axioms, which tells us that R expresses an inconsistency, which is to be found in the axioms.
This is a snapshot because it does matter what the declaration means. A proof requires the use of logic symbols only. We must be able to use symbols to justify a declaration like "This declaration is not provable in T." By the use of a Goedel-type method, to include Goedel numbers, this snapshot can be made rigorous. That is, it is possible to encode the string represented by P as an element of Number Theory. That, in turn, shows that not all theorems -- or posed problems -- of Number Theory are decidable. (Goedel and others base their results on a subset of Peano's axioms.) Because the logic L of symbol strings can represent Axiomatic Set Theory, we then have that even that theory (usually ZFC) cannot be fully provable. Any system sufficient to be encoded by Goedel's tool will not be fully provable or decidable.
It has been shown that when Number Theory is limited to addition (and multiplication), that system is complete and consistent. So any system that cannot be encoded only at that level must be inconsistent or incomplete.
No comments:
Post a Comment