Tuesday, 2 September 2014

lo.logic - Why is every finite set Diophantine?

If $kgeq0$ and $f$ is a polynomial in $k+1$ variables with integer coefficients, let $$X(f)={ninmathbb Z:exists x_1,dots,x_kinmathbb Z:f(n,x_1,dots,x_k)=0}.$$ This is the typical diophantine subset of $mathbb Z$.



Clearly $X(f)cup X(g)=X(h)$ with $h(n,x_1,dots x_{k+l})=f(n,x_1,dots,x_k)g(n,x_{k+1},dots,x_{k+l})$. It follows that a finite union of diophantine subsets of $mathbb Z$ is diophantine. It follows that to show that a finite set is diophantine, then, it suffices to check that for all $ainmathbb Z$ the set ${a}$ is diophantine.



Let then $ainmathbb Z$ and let $f(n)=n-a$. Then obviously ${a}=X(f)$.

No comments:

Post a Comment