Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 drobotv@gmail.com Posts: 14 Registered: 5/21/07
Re: primes of the form n^2+1
Posted: Jul 11, 2008 8:16 AM

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

http://en.wikipedia.org/wiki/Arithmetical_hierarchy

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

Sincerely

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
* Retired and gainfully unemployed
* http://www.vdrobot.com
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

On Jul 10, 7:42Êam, tc...@lsa.umich.edu wrote:
> In article <g54t69\$204...@dizzy.math.ohio-state.edu>,
>
> drob...@gmail.com <drob...@gmail.com> 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