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 * http://www.vdrobot.com * mailto:firstname.lastname@example.org -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
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