Citizendia
Your Ad Here

In mathematics, a Diophantine set of j-tuples of integers is a set S for which there is some polynomial with integer coefficients

f(n1, . Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations . . , nj, x1, . . . , xk)

such that a tuple

(n1, . . . , nj)

of integers is in S if and only if there exist some (non-negative) [1] integers

x1, . . . , xk with
f(n1, . . . , nj, x1, . . . , xk) = 0.

Such a polynomial equation over the integers is called a Diophantine equation. In Mathematics, a Diophantine equation is an indeterminate Polynomial Equation that allows the variables to be Integers only In other words, a Diophantine set is a set of the form

\{\, (n_1,\dots,n_j) : \exists x_1\,\dots\,\exists x_k\, f(n_1,\dots,n_j,x_1,\dots,x_k )=0 \,\}

where f is a polynomial function with integer coefficients. [2]

Matiyasevich's theorem, published in 1970, states that a set of integers is Diophantine if and only if it is recursively enumerable. In Computability theory, traditionally called Recursion theory, a set S of Natural numbers is called recursively enumerable, computably A set S is recursively enumerable precisely if there is an algorithm that, when given an integer, eventually halts if that input is a member of S and otherwise runs forever. This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or recursion-theoretic terms. Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes This is far from obvious, however, and represented the culmination of some decades of work.

Matiyasevich's theorem effectively settled Hilbert's tenth problem. Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900 It implies that Hilbert's tenth problem is unsolvable. This problem is the challenge to find a general algorithm which can decide whether a given system of Diophantine equations has a solution among the integers. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation David Hilbert posed the problem in his celebrated list, from his 1900 address to the International Congress of Mathematicians. David Hilbert ( January 23, 1862 &ndash February 14, 1943) was a German Mathematician, recognized as one of the most The International Congress of Mathematicians (ICM is the largest congress in the Mathematics community

Contents

Examples

The well known Pell equation

x^2-d(y+1)^2=\pm 1

is an example of a Diophantine equation with a parameter. Pell's equation is any Diophantine equation of the form x^2-ny^2=1\ where n is a nonsquare integer and x As has long been known, the equation has a solution in the unknowns x,y precisely when the parameter d is 0 or not a perfect square. This article refers to the REM live recording For the mathematical term see Perfect square. In the present context, one says that this equation provides a Diophantine definition of the set

{0,2,3,5,6,7,8,10,. . . }

consisting of 0 and the natural numbers that are not perfect squares. Other examples of Diophantine definitions are as follows:

Matiyasevich's theorem

Matiyasevich's theorem says:

Every recursively enumerable set is Diophantine. In Computability theory, traditionally called Recursion theory, a set S of Natural numbers is called recursively enumerable, computably

A set S of integers is recursively enumerable if there is an algorithm that behaves as follows: When given as input an integer n, if n is a member of S, then the algorithm eventually halts; otherwise it runs forever. That is equivalent to saying there is an algorithm that runs forever and lists the members of S. A set S is Diophantine precisely if there is some polynomial with integer coefficients f(n, x1, . In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations . . , xk) such that an integer n is in S if and only if there exist some integers x1, . . . , xk such that f(n, x1, . . . , xk) = 0.

It is not hard to see that every Diophantine set is recursively enumerable: consider a Diophantine equation f(n, x1, . . . , xk) = 0. Now we make an algorithm which simply tries all possible values for n, x1, . . . , xk, in the increasing order of the sum of their absolute values, and prints n every time f(n, x1, . . . , xk) = 0. This algorithm will obviously run forever and will list exactly the n for which f(n, x1, . . . , xk) = 0 has a solution in x1, . . . , xk.

Proof technique

Yuri Matiyasevich utilized an ingenious trick involving Fibonacci numbers in order to show that solutions to Diophantine equations may grow exponentially. Yuri Vladimirovich Matiyasevich, (Юрий Владимирович Матиясевич born March 2, 1947 in Leningrad) is a Russian Mathematician In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci Exponential growth (including Exponential decay) occurs when the growth rate of a mathematical function is proportional to the function's current value Earlier work by Julia Robinson, Martin Davis and Hilary Putnam had shown that this suffices to show that every recursively enumerable set is Diophantine. Julia Hall Bowman Robinson ( December 8, 1919 – July 30, 1985) was an American Mathematician, born in St This page is on the mathematician For the former tennis player see Martin Davis (tennis. Hilary Whitehall Putnam (born July 31 1926 is an American Philosopher who has been a central figure in Western philosophy since the 1960s especially in Philosophy In Computability theory, traditionally called Recursion theory, a set S of Natural numbers is called recursively enumerable, computably

Application to Hilbert's Tenth problem

Main article: Hilbert's tenth problem

Hilbert's tenth problem asks for a general algorithm deciding the solvability of Diophantine equations. Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900 The conjunction of Matiyasevich's theorem with a result discovered in the 1930s implies that a solution to Hilbert's tenth problem is impossible. The result discovered in the 1930s by several logicians can be stated by saying that some recursively enumerable sets are non-recursive. In this context, a set S of integers is called "recursive" if there is an algorithm that, when given as input an integer n, returns as output a correct yes-or-no answer to the question of whether n is a member of S. It follows that there are Diophantine equations which cannot be solved by any algorithm.

Logical structure

Here an argument taking exactly the form of an Aristotelian syllogism is of interest:

(Major premise): Some recursively enumerable sets are non-recursive. A syllogism, or logical appeal, (συλλογισμός &mdash "conclusion" "inference" (usually the categorical syllogism) is a kind of
(Minor premise): All recursively enumerable sets are Diophantine.
(Conclusion): Therefore some Diophantine sets are non-recursive.

The conclusion entails that Hilbert's 10th problem cannot be solved. The most difficult part of the argument is the proof of the minor premise, i. e. Matiyasevich's theorem, which itself is much stronger than the unsolvability of the Tenth Problem.

Refinements

Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977) or 11 integer variables (Zhi Wei Sun, 1992). Sun Zhiwei ( b October 16, 1965) is a Chinese Mathematician, working primarily on Number theory, Combinatorics, and

Further applications

Matiyasevich's theorem has since been used to prove that many problems from calculus and differential equations are unsolvable. Calculus ( Latin, calculus, a small stone used for counting is a branch of Mathematics that includes the study of limits, Derivatives A differential equation is a mathematical Equation for an unknown function of one or several variables that relates the values of the

One can also derive the following stronger form of Gödel's first incompleteness theorem from Matiyasevich's result:

Corresponding to any given axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization. In Mathematical logic, Gödel's incompleteness theorems, proved by Kurt Gödel in 1931 are two Theorems stating inherent limitations of all but the most

Footnotes

  1. ^ The two definitions are equivalent. This can be proved using Lagrange's four-square theorem. Lagrange's four-square theorem, also known as Bachet's conjecture, was proven in 1770 by Joseph Louis Lagrange.
  2. ^ Note that one can also use a simultaneous system of Diophantine equations to define a Diophantine set, because the system
    f_1=0,\ldots,f_k=0
    is equivalent to the single equation
    f_1^2+\cdots+f_k^2=0.\,

References

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic