Talk:Paris–Harrington theorem

From Wikipedia, the free encyclopedia

"Roughly speaking, Paris and Harrington showed that the Paris–Harrington principle is unprovable in Peano arithmetic by showing that (in Peano arithmetic) it implies the consistency of Peano arithmetic. Since Peano arithmetic cannot prove its own consistency by Godel's theorem, this shows that Peano arithmetic cannot prove the Paris–Harrington principle."

On the surface, and for a reader without a larger knowledge of the literature surrounding Gödel's results, this paragraph may seem outright false. This reader could cite the definition of Gödel's second Incompleteness theorem

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

cited in wikipedia's Gödel article and argue thus; the only thing that could stop us from accepting a consistency proof of Peano Arithmetic is if we take the consistency of PA already. Working solely within a formal system F, if we write a proof of the consistency of F completely in F, then what we have shown is that F is actually inconsistent. As worded, the original paragraph can be confusing to someone trying to reason through this subject for the first time.

I beleive the "author" of the article is aware of the true facts of Paris-Harrington, so what is meant is in fact true. It has been shown that PA is consistent only when working with PA from a "larger" formal system of SET THEORY; the trick is that we must assume the consistency of SET THEORY in order to show the consistency of PA(we just pushed the consistent/inconsistent issue up the "hierarchy" of axiomatic systems). Paris and Harringtons proof showed that the provabilty of the Paris-Harrigton principle implied the consistency of PA in PA, and because we are working in "bigger" SET THEORY were the assumption of consistency of SET THEORY implies the consistency of PA, then we can apply Gödel's result to arrive at a contradiction and conclude that the Paris-Harrington priciple is unprovable in PA. To make this article fully correct to a reader, these extra concerns need to be incorporated in such a way as not to seem extraneous. It's nice to be written well, but not at the price of being read incorrectly. Dr.Slop 05:41, 12 April 2006 (UTC)DR.Slop

It is not necessary to assume the consistency of set theory to prove the P-H principle. It can be proved in (say) ZF set theory without assuming the consistencyof ZF set theory. R.e.b. 14:05, 12 April 2006 (UTC)

[edit] Date for the theorem?

It would be nice to have the date the theorem was proved, if someone has this information to add to the article. 165.189.91.148 15:01, 3 July 2006 (UTC)