
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 Pi1 yields, among other entries, 2.141...
Sincerely
=================== * Vladimir Drobot * Retired and gainfully unemployed * http://www.vdrobot.com * mailto:vlad@vdrobot.com ==================
On Jul 10, 7:42Êam, tc...@lsa.umich.edu wrote: > In article <g54t69$204...@dizzy.math.ohiostate.edu>, > > drob...@gmail.com <drob...@gmail.com> wrote: > >I have a silly request. Can someone explain what is exectly "Pi1 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 Ê Ê Ê tchowatalumdotmitdotedu > The range of our projectileseven ... the artilleryhowever 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

