From Georg Kreisel‘s review of The decision problem for exponential diophantine equations, by Martin Davis, Hilary Putnam, and Julia Robinson, Ann. of Math. (2), 74 (3), (1961), 425–436. MR0133227 (24 #A3061).

This paper establishes that every recursively enumerable (r.e.) set can be existentially defined in terms of exponentiation. […] These results are superficially related to Hilbert’s tenth problem on (ordinary, i.e., non-exponential) Diophantine equations. The proof of the authors’ results, though very elegant, does not use recondite facts in the theory of numbers nor in the theory of r.e. sets, and so it is likely that the present result is not closely connected with Hilbert’s tenth problem. Also it is not altogether plausible that all (ordinary) Diophantine problems are uniformly reducible to those in a fixed number of variables of fixed degree, which would be the case if all r.e. sets were Diophantine.

Of course, my favorite quote in relation to the tenth problem is from the Foreword by Martin Davis to Yuri Matiyasevich’s Hilbert’s tenth problem.

During the 1960s I often had occasion to lecture on Hilbert’s Tenth Problem. At that time it was known that the unsolvability would follow from the existence of a single Diophantine equation that satisfied a condition that had been formulated by Julia Robinson. However, it seemed extraordinarily difficult to produce such an equation, and indeed, the prevailing opinion was that one was unlikely to exist. In my lectures, I would emphasize the important consequences that would follow from either a proof or a disproof of the existence of such an equation. Inevitably during the question period I would be asked for my own opinion as to how matters would turn out, and I had my reply ready: “I think that Julia Robinson’s hypothesis is true, and it will be proved by a clever young Russian.”

This entry was posted on Sunday, August 11th, 2013 at 6:06 pm and is filed under Computability theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

Every $P_c$ has the size of the reals. For instance, suppose $\sum_n a_n=c$ and start by writing $\mathbb N=A\cup B$ where $\sum_{n\in A}a_n$ converges absolutely (to $a$, say). This is possible because $a_n\to 0$: Let $m_0

Consider a subset $\Omega$ of $\mathbb R$ of size $\aleph_1$ and ordered in type $\omega_1$. (This uses the axiom of choice.) Let $\mathcal F$ be the $\sigma$-algebra generated by the initial segments of $\Omega$ under the well-ordering (so all sets in $\mathcal F$ are countable or co-countable), with the measure that assigns $0$ to the countable sets and $1 […]

You assume $\omega_\alpha\subseteq M$ and $X\in M$ so that $X$ belongs to the transitive collapse of $M$ (because if $\pi$ is the collapsing map, $\pi(X)=\pi[X]=X$. You assume $|M|=\aleph_\alpha$ so that the transitive collapse of $M$ has size $\aleph_\alpha$. Since you also have that this transitive collapse is of the form $L_\beta$ for some $\beta$, it fol […]

Perhaps the following may clarify the comments: for any ordinal $\delta$, there is a Boolean-valued extension of the universe of sets where $2^{\aleph_0}>\aleph_\delta$ holds. If you rather talk of models than Boolean-valued extensions, what this says is that we can force while preserving all ordinals, and in fact all initial ordinals, and make the contin […]

I do not know of any active set theorists who think large cardinals are inconsistent. At least, within the realm of cardinals we have seriously studied. [Reinhardt suggested an ultimate axiom of the form "there is a non-trivial elementary embedding $j:V\to V$". Though some serious set theorists found it of possible interest immediately following it […]

The number of such partitions is $2^{\mathfrak c}$. First, each partition $\pi$ is a collection of disjoint subsets of $\mathbb R$, so it has size at most $\mathfrak c$, and so there are at most $|[\mathcal P(\mathbb R)]^{\le\mathfrak c}|=2^{\mathfrak c}$ partitions, where $[A]^{\le\kappa}$ denotes the collection of subsets of $A$ of size at most $\kappa$. S […]

I don't think I know of any "natural" result showing that some specific set can only be proved infinite via a contradiction. However: There are several results involving fast-growing functions that perhaps are of this kind. Typically, one describes a certain recursive procedure that, when iterated starting from a positive integer, seems to pro […]

There are many reasonable axioms that have been studied in diverse situations and all are known to contradict instances of GCH. By far the strongest case can be made for strong forcing axioms such us Martin's maximum MM, or some of their significant consequences or close relatives (strong reflection principles). These forcing axioms imply that the conti […]

Given any field automorphism of $\mathbb C$, the rational numbers are fixed. In fact, any number that is explicitly definable in $\mathbb C$ (in the first order language of fields) is fixed. (Actually, this means that we can only ensure that the rationals are fixed, I expand on this below.) Any construction of a wild automorphism uses the axiom of choice. Se […]

This is a great question. I do not know of a full answer that does not simply say that the Cohen algebra completely embeds in the Boolean completion of $\mathbb P$. There are some nice positive results, though. One that comes up frequently in practice is that any finite support iteration of nontrivial posets adds a Cohen real. This is a serious source of dif […]