The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math.research

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: primes of the form n^2+1
Replies: 16   Last Post: Jul 16, 2008 12:41 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 14
Registered: 5/21/07
Re: primes of the form n^2+1
Posted: Jul 11, 2008 8:16 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Thanks to all the replies about Pi_1 question. Another introductory
article on the subject is

The trick of finding the information is to search for "arithmetical
hierarchy." Searching for
Pi-1 yields, among other entries, 2.141...


* Vladimir Drobot
* Retired and gainfully unemployed

On Jul 10, 7:42Êam, wrote:
> In article <g54t69$>,
> <> wrote:

> >I have a silly request. Can someone explain what is exectly "Pi-1 form" ?
> Again an informal answer may help. ÊA Pi_1 statement is one having the
> form "For all integers n, phi(n)" where phi(n) is some statement whose
> truth can be found by a finite computation, given a fixed value of n.
> For example, the following statements are (or are easily shown to be
> equivalent to) Pi_1:
> Ê- For all n, either n is odd or or n < 4 or there exist primes p and q
> Ê Êsuch that p + q = n.
> Ê- For all tuples (n, x, y, z), if n > 2 and x^n + y^n = z^n, then xyz = 0.
> Note that "all tuples" is really no different from "all n" since tuples
> can be encoded as single integers. ÊOn the other hand, consider
> Ê- For all n, there exists p > n such that p is prime and p + 2 is prime.
> Here, we don't know how to check phi(n) with a finite computation even if
> we're given a fixed n. ÊSo we can't conclude that the statement is Pi_1.
> But it *is* Pi_2, because if we move past the *second* quantifier (there
> exists p) then we *do* know how to check that p > n, that p is prime,
> and that p + 2 is prime.
> --
> Tim Chow Ê Ê Ê tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. Ê---Galileo, Dialogues Concerning Two New Sciences

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.