PlanetMath: Diophantine set

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (213)
Orphanage (1)
Unclass'd (1)
Unproven (473)
Corrections (40)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

Diophantine set

(Definition)

A set is said to be Diophantine if

it is a subset of $\mathbb{N}^n$ , the set of all -tuples of positive integers, and
there is a polynomial over $\mathbb{Z}$ in variables, $k\ge 0$ , such that $x\in S$ iff there is some $y\in \mathbb{N}^k$ , such that .

So can be thought of as a set such that, there is a Diophantine equation and a non-negative integer , so that when each element in is “combined” with some -tuple, makes up a solution to a Diophantine equation . In other words, if $f_n^{n+k}:\mathbb{N}^{n+k}\to \mathbb{N}^n$ is a projection function given by $f_n^{n+k}(x,y)=x$ where $x\in \mathbb{N}^n$ and $y\in \mathbb{N}^k$ , then is a Diophantine set iff $S=f_n^{n+k}(Z)$ , where is the zero set of some Diophantine equation . Equivalently, a set $S\in \mathbb{N}^n$ is Diophantine if there is a $p\in \mathbb{Z}[X_1,\ldots , X_{n+k}]$ , such that

$% latex2html id marker 388 $\displaystyle S=\lbrace x\in \mathbb{N}^n\mid \exists y\in \mathbb{N}^k \; p(x,y)=0\rbrace.$$

For example, $\mathbb{N}$ itself is Diophantine, for the polynomial works. Another trivial example: the set of all positive integers divisible by is Diophantine, for the polynomial works.

For a less trivial example, let us show that the set of all triples such that $a\le b\le c$ is Diophantine. For the inequality $a\le b$ , let . Then the sentence $% latex2html id marker 406 $ \exists y \; p(x_1,x_2,y)=0$$ is equivalent to $x_1\le x_2$ . Similarly, for the inequality $b\le c$ , we have the same polynomial . Putting the two inequality together amounts to setting . Thus, the sentence $% latex2html id marker 416 $ \exists (y_1,y_2)\; q(x,y)=0$$ , where and is the same as the inequality $x_1\le x_2\le x_3$ .

Some other Diophantine sets are:

the set $A=B\cup C$ , where and are Diophantine
the set $A=B\cap C$ , where and are Diophantine
the set $\lbrace a \mid a \equiv b \pmod n\rbrace$
the set of composite numbers
the set of prime numbers
the set of powers of a number $\lbrace m^n\mid n=0,1,\ldots \rbrace$

Associated with the concept of a Diophantine set is that of a Diophantine function: a function if its graph $\lbrace (x,f(x)) \mid x\in \operatorname{dom}(f)\rbrace$ is a Diophantine set.

More to come...

"Diophantine set" is owned by CWoo.

(view preamble)

Also defines:

Diophantine function

Log in to rate this entry.
(view current ratings)

Cross-references: graph, powers, prime numbers, composite numbers, sentence, inequality, divisible, zero set, function, projection, solution, Diophantine equation, iff, variables, polynomial, integers, positive, subset

This is version 6 of Diophantine set, born on 2008-05-07, modified 2008-05-08.
Object id is 10571, canonical name is DiophantineSet.
Accessed 75 times total.

Classification:

AMS MSC:	03D80 (Mathematical logic and foundations :: Computability and recursion theory :: Applications of computability and recursion theory)
	03D99 (Mathematical logic and foundations :: Computability and recursion theory :: Miscellaneous)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact