 To see that the theorem is true, it suffices to notice that if there were no such number formula_15, one could algorithmically test membership of a number formula_27 in this non-computable set by simultaneously running the algorithm formula_33 to see whether formula_27 is output while also checking all possible formula_43-tuples of natural numbers seeking a solution of the equation

We may associate an algorithm formula_33 with any of the usual formal systems such as Peano arithmetic or ZFC by letting it systematically generate consequences of the axioms and then output a number formula_27 whenever a sentence of the form

is generated.Then the theorem tells us that either a false statement of this form is proved or a true one remains unproved in the system in question.We may speak of the "degree" of a Diophantine set as being the least degree of a polynomial in an equation defining that set.