Finding polynomials with a specific propertyShow that there exist a n ∈ N and polynomials p , q ∈ N [ x 1 , … , x n ] such that neither the formula ϕ ( n , p , q ) = ∀ x 1 ⋯ ∀ x n : ¬ ( p ( x 1 , … , x n ) = q ( x 1 , … , x n ) )nor ¬ ϕ are not theorems of formal arithmetic.

Question

Finding polynomials with a specific propertyShow that there exist a   n  ∈      N   and polynomials   p  ,  q  ∈      N    [      x    1    ,  …  ,      x    n    ] such that neither the formula  ϕ  (  n  ,  p  ,  q  )  =  ∀      x    1    ⋯  ∀      x    n    :  ¬  (  p  (      x    1    ,  …  ,      x    n    )  =  q  (      x    1    ,  …  ,      x    n    )  )nor   ¬  ϕ are not theorems of formal arithmetic.

erlentzed · Accepted Answer

Step 1Let R(y) be a recursively enumerable predicate which is not recursive. Then by the result of Matiyasevich, there exists an n, and a polynomial A(y) with integer coefficients, such that for any natural number y, R(y) iff   ∃      x    1    ∃      x    2    …  ∃      x    n    (  A  (  y  ,      x    1    ,  …  ,      x    n    )  =  0) is true in N.By separating the positive and negative coefficients, we can rewrite   A  =  0 as   P  =  Q, where P and Q have coefficients in N.Step 2If we use recursively axiomatized arithmetic T all of whose axioms are true in N, such as (first-order) Peano Arithmetic, and for every k the sentence obtained by replacing y by k is provable or refutable in T, then R(y) is recursive.

Finding polynomials with a specific property. Show that there exist a n in N and polynomials p, q in N[x_1,…,x_n].

Answered question

Answer & Explanation

New Questions in Algebra II