Talk:Paris–Harrington theorem

Parsing Errors

There are currently errors displaying on the page Ourous (talk) 23:32, 21 October 2013 (UTC)

Fixed, looks like it was a WP server error rather than malformed math markup. --Mark viking (talk) 13:51, 22 October 2013 (UTC)

Untitled

"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)

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)

Two firsts

Both this article and the article for Goodstein's theorem both claim to be the first natural theorem not provable by PA. I'm not sure which article is correct, but I suspect they cannot both be correct at the same time. 165.125.144.16 (talk) 20:33, 13 April 2009 (UTC)

A note to the effect that I appreciated the joke.--109.145.154.140 (talk) 17:02, 24 September 2013 (UTC)

This seems like a degenerate result

Tell me if I am missing anything: the finite Ramsey theorem is a result from combinatorics, not arithmetic (that is, the elements of the sets involved do not have to be integers with arithmetic operations defined upon them). The "strengthend" finite Ramsey theorem says that if we consider the elements to be nonnegative integers, one of the members of Y must be smaller than the order of Y. But since we can map the non-integer elements (from Ramsey) to nonnegative integers (in strengthened Ramsey) however we please, we can simply place 1 in Y. We are still not using arithmetic. The elements do not even have to be a well-ordered set, they just have to have a smallest element which we call 1. So how is "strengthened Ramsey" able to tell you anything about arithmetic?

Spope3 (talk) 20:09, 5 June 2009 (UTC)

In the strengthened version, the integers themselves are colored, so one cannot trivially assure 1 is in the homogeneous set. The truth of the theorem itself is not what tells us about arithmetic; it is the provability of the theorem, or lack thereof, that is of interest when we look at axiom systems for arithmetic. — Carl (CBM · talk) 04:16, 6 June 2009 (UTC)

Can the strengthened finite Ramsey theorem be formulated in PA-Language?

If it cannot, then there's nothing instructive in the non-provability of this theorem within PA, just as ZF is not provable in PA. However, if the strengthened finite Ramsey theorem can be formulated in PA-Language, then why does the article present it in a Set-theoretical-Language? That misleads the reader! We would be very grateful if anybody might "translate" the strengthened finite Ramsey theorem into a PA-Language theorem. We don't need a well formed formula: we would get satisfied if the theorem dealt with natural numbers only, without any other objects like: mappings (colorings), sets, or subsets. HOOTmag (talk) 19:46, 16 August 2009 (UTC)

Maybe someone will correct me if I have this wrong, but I think the answer is: Yes, PA can state any arithmetic proposition, and this is one. Are you worried about "for each of the n-element subsets..." looking like a second-order quantifier? That's not a problem because because the subsets are all in the finite set {1,2...N} where N is bound by an outer quantifier. So you can treat "for each of the n element subsets" as a first order quantifier ranging over the numbers {0,1,2...2^N-1} which each encode a "bit string" specifying a subset. Put yet another way, given n, k, m, N, you can write a computer program to test the predicate being stated about them, so the predicate is recursive. See also: arithmetic hierarchy. 66.127.55.192 (talk) 09:58, 7 February 2010 (UTC)

How many characters will you need for formularting the strengthened finite Ramsey theorm in PA-Language? If not that many characters, then try to formulate this theorem in PA. Thank you in advance. HOOTmag (talk) 13:18, 23 August 2010 (UTC)

I would like to add the following paragraph to the article. Please correct whatever needs a correction.

Actually, the Strengthened Finite Ramsey Theorem (as opposed to the regular Finite Ramsey Theorem), is not expressible in Peano Language (because of the condition that the number of elements of Y is at least the smallest element of Y), so no wonder this theorem is unprovable in PA. In fact: the statement - whose unprovability in PA is claimed by Paris-Harringtion Theorem, was not the Strengthened Finite Ramsey Theorem itself, but rather was a much more complex one - whose phrasing in Peano Language is extremely long - similarly to that of some statements which are both expressible in Peano Language and encoded in Goedel numbers, as follows: The Strengthened Finite Ramsey Theorem can be encoded in a Goedel number - n - about which there is an arithmetical statement φ(n), which is expressible in Peano Language, and whose meaning in the Goedel deciphering method is - that the statement encoded in n is unprovable in PA. Paris-Harringtion theorem states, that even though φ(n) is both provable outside PA and is expressible in Peano Language - it's still unprovable in PA.

HOTmag (talk) 15:29, 1 September 2016 (UTC)

The strengthened finite Ramsey theorem is expressible in PA, though, as a sentence in the language of arithmetic. — Carl (CBM · talk) 00:08, 2 September 2016 (UTC)

How roughly speaking is the "Roughly speaking, …"? If HOTmag is right, the complexity of what Paris and Harrington proved is at least one order greater than that stated in the article. And altho' I love to translate maths into ordinary language as much as possible, this might be a step too far. yoyo (talk) 20:43, 3 November 2017 (UTC)

Further to this, I quote Andrey Bovykin's 2006 paper from the "External links" section:

The first PA-unprovable statements of ‘mathematical’ character (not referring to arithmetisation of syntax and provability) appeared in 1976 in the work of J. Paris (building upon joint work with L. Kirby [52]) and led to the formulation in [69] of the Paris-Harrington Principle (denoted PH): “for any numbers m, n and c, there exists a number N such that for every colouring f of m-subsets of {0, 1, . . . , N − 1} into c colours, there is an f-homogeneous H ⊂ {0, 1, . . . , N − 1} of size n such that |H| > min H”. This statement PH is not provable in Peano Arithmetic.

where [52] and [69] are internal references, both dated 1977. Unfortunately, at first glance, Bovykin seems not to explain all his terms, e.g. what he means by "f-homogeneous" or even "homogeneous". But this statement does seem simpler than HOTmag's, as it nowhere (explicitly) mentions Gödel numbering. And it also seems closer to that of the present article. The most important question for us (IMO) has to be: Is the article accurate enough? yoyo (talk) 21:08, 3 November 2017 (UTC)