Consistency and Completeness in Arithmetic and Set Theory
In theories of arithmetic, such as Peano arithmetic, there is an intricate relationship between the consistency of the theory and its completeness. A theory is complete if, for every formula φ in its language, at least one of φ or ¬ φ is a logical consequence of the theory.
Presburger arithmetic is an axiom system for the natural numbers under addition. It is both consistent and complete.
Gödel's incompleteness theorems show that any sufficiently strong effective theory of arithmetic cannot be both complete and consistent. Gödel's theorem applies to the theories of Peano arithmetic (PA) and Primitive recursive arithmetic (PRA), but not to Presburger arithmetic.
Moreover, Gödel's second incompleteness theorem shows that the consistency of sufficiently strong effective theories of arithmetic can be tested in a particular way. Such a theory is consistent if and only if it does not prove a particular sentence, called the Gödel sentence of the theory, which is a formalized statement of the claim that the theory is indeed consistent. Thus the consistency of a sufficiently strong, effective, consistent theory of arithmetic can never be proven in that system itself. The same result is true for effective theories that can describe a strong enough fragment of arithmetic – including set theories such as Zermelo–Fraenkel set theory. These set theories cannot prove their own Gödel sentences – provided that they are consistent, which is generally believed.
Because consistency of ZF is not provable in ZF, the weaker notion relative consistency is interesting in set theory (and in other sufficiently expressive axiomatic systems). If T is a theory and A is an additional axiom, T + A is said to be consistent relative to T (or simply that A is consistent with T) if it can be proved that if T is consistent then T + A is consistent. If both A and ¬A are consistent with T, then A is said to be independent of T.
Read more about this topic: Consistency
Famous quotes containing the words consistency and, consistency, completeness, arithmetic, set and/or theory:
“All religions have honored the beggar. For he proves that in a matter at the same time as prosaic and holy, banal and regenerative as the giving of alms, intellect and morality, consistency and principles are miserably inadequate.”
—Walter Benjamin (1892–1940)
“The lawyer’s truth is not Truth, but consistency or a consistent expediency.”
—Henry David Thoreau (1817–1862)
“Poetry presents indivisible wholes of human consciousness, modified and ordered by the stringent requirements of form. Prose, aiming at a definite and concrete goal, generally suppresses everything inessential to its purpose; poetry, existing only to exhibit itself as an aesthetic object, aims only at completeness and perfection of form.”
—Richard Harter Fogle, U.S. critic, educator. The Imagery of Keats and Shelley, ch. 1, University of North Carolina Press (1949)
“O! O! another stroke! that makes the third.
He stabs me to the heart against my wish.
If that be so, thy state of health is poor;
But thine arithmetic is quite correct.”
—A.E. (Alfred Edward)
“John Brown of Ossawattamie
Who died to set Abstraction free
Stole Washington’s gold-handled sword
Less for the gold than for the Lord....”
—Allen Tate (1899–1979)
“The theory of the Communists may be summed up in the single sentence: Abolition of private property.”
—Karl Marx (1818–1883)