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)
“People who love only once in their lives are ... shallow people. What they call their loyalty, and their fidelity, I call either the lethargy of custom or their lack of imagination. Faithfulness is to the emotional life what consistency is to the life of the intellect—simply a confession of failures.”
—Oscar Wilde (1854–1900)
“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)
“Under the dominion of an idea, which possesses the minds of multitudes, as civil freedom, or the religious sentiment, the power of persons are no longer subjects of calculation. A nation of men unanimously bent on freedom, or conquest, can easily confound the arithmetic of statists, and achieve extravagant actions, out of all proportion to their means; as, the Greeks, the Saracens, the Swiss, the Americans, and the French have done.”
—Ralph Waldo Emerson (1803–1882)
“The sun set; but set not his hope:
Stars rose; his faith was earlier up:
Fixed on the enormous galaxy,
Deeper and older seemed his eye:
And matched his sufferance sublime
The taciturnity of time.”
—Ralph Waldo Emerson (1803–1882)
“... liberal intellectuals ... tend to have a classical theory of politics, in which the state has a monopoly of power; hoping that those in positions of authority may prove to be enlightened men, wielding power justly, they are natural, if cautious, allies of the “establishment.””
—Susan Sontag (b. 1933)