1
$\begingroup$

According to Godel's incompleteness theorem, some statements about rational numbers are independent from the axioms of the rational numbers given in Wikipedia--an ordered field generated by 1. So can anyone give a concrete example of such a proposition about rational numbers that is undeducible from the axioms of $\mathbb{Q}$ but provable in the axioms of $\mathbb{R}$? Or if such a preposition doesn't exists?

$\endgroup$
  • 3
    $\begingroup$ Why should such a proposition exist? $\endgroup$ – Hagen von Eitzen Feb 10 '18 at 4:32
  • 1
    $\begingroup$ Btw, the linkeed WP page gives a construction, not an axiomatization of $\Bbb Q$. $\endgroup$ – Hagen von Eitzen Feb 10 '18 at 4:40
  • $\begingroup$ @HagenvonEitzen: Can't you take the classic statements independent of PA over to $\Bbb Q$?. Then you can decide them in $\Bbb R$ because the completeness axiom (which is second order and violates the hypotheses of Godel incompleteness) eliminates the threat of nonstandard (infinite) naturals? I'm not sure this works because you can't get a predicate in the reals that says $x$ is a natural. $\endgroup$ – Ross Millikan Feb 10 '18 at 4:49
  • 1
    $\begingroup$ Is it possible that in your question your are confusing the set of rational numbers $\mathbb{Q}$ with Robinson arithmetic $Q$? $\endgroup$ – Taroccoesbrocco Feb 10 '18 at 7:45
  • 1
    $\begingroup$ Could you clarify where you saw the claim that the incompleteness theorem applies to the rationals? That might help us understand what exactly the author was claiming, and then to explain it. $\endgroup$ – Carl Mummert Feb 10 '18 at 13:58
2
$\begingroup$

There is some vagueness in the question, but I want to write an answer about Julia Robinson's work in the area, particularly her 1949 paper Definability and Decision Problems in Arithmetic, Journal of Symbolic Logic 14(2). This paper proves some undecidability results for theories about the rational numbers, which are similar to the undecidability results that the incompleteness theorem gives for theories about natural numbers.

Robinson first proves some lemmas about the interdefinability of arithmetical operations. For example, addition of natural numbers is first-order definable from the multiplication and successor operations.

The next theorem, one of the main results, is that the set of integers and the set of positive integers are first-order definable in the field of rational numbers, using only addition and multiplication operations on the rationals as well as quantifiers over the rationals. This is a remarkable result, because we might think that the rationals are somehow "better behaved" than the integers, or at least "differently behaved" from the integers. Robinson's result uses a mixture of logic and number theory, much like her later contributions to Hilbert's 10th problem.

Robinson then turns to the undecidability of the theory of $(\mathbb{Q}, 0,1,+, \times,=)$. A theory is decidable if the set of sentences provable from the theory is decidable by an algorithm, and undecidable otherwise.

By using her definition of the integers into the rationals, along with logical methods, Robinson shows that the theory consisting of the set $T$ of true sentences in the rationals is undecidable, as is the theory generated from any subset of $T$. This is not quite an "incompleteness" result, because the theory consisting of all true sentences in the rationals is a complete theory.

Robinson obtains a nice corollary from her theorem about the rationals: the theory of fields (i.e. the theory generated by axioms for a field) is undecidable. The parallel result for rings instead of fields was proved earlier by Tarski.

The formula that defines the integers within the rationals is not too hard. Let $\phi(A,B,K)$ be $$(\exists X,Y,Z \in \mathbb{Q})[2+ABK^2 + BZ^2 = X^2 + AY^2].$$ Then a rational number $N$ is an integer if and only if $$ (\forall A,B \in\mathbb{Q})[ ( \phi(A,B,0) \land (\forall M \in \mathbb{Q})[\phi(A,B,M)\to\phi(A,B,M+1)] ) \to \phi(A,B,N)].$$ The proof that this is correct is not trivial.

$\endgroup$
  • $\begingroup$ what does this symbol $\rightarrow$ mean? $\endgroup$ – T.... May 15 '18 at 16:56
1
$\begingroup$

The set of rational numbers $\mathbb{Q}$ (as well as the set of nonnegative rational numbers $\mathbb{Q}^{>0}$) does not satisfies any kind of principle of induction, which is a key ingredient in (the proof of) Gödel's incompleteness theorem. So, I don't see how Gödel's incompleteness theorem could say something about $\mathbb{Q}$ or $\mathbb{Q}^{>0}$.

By the way, what do you mean by giving an axiomatic characterization of $\mathbb{Q}$? First of all, you have to fix a language for this axiomatization. To maintain the analogy with Peano arithmetic, let us say that the language is first order logic with the symbols for an order relation, addition, multiplication and their neutral elements. If you want to characterize $\mathbb{Q}$, you would like to say that $\mathbb{Q}$ is an ordered field, isn't it? In such a language you can easily axiomatize the fact of being an ordered field.

According to Löwenheim–Skolem theorem, there is no axiomatic characterization of $\mathbb{Q}$ in such a language. Indeed, $\mathbb{Q}$ is a countably infinite ordered field and by Löwenheim–Skolem theorem for any infinite cardinality $\kappa$ there exists an ordered field $F$ of cardinality $\kappa$ which is elementary equivalent to $\mathbb{Q}$ (i.e. it satisfies the same formulas as $\mathbb{Q}$ in such a language). In particular, if $\kappa$ is greater than the cardinality of $\mathbb{Q}$ (and $\mathbb{N}$), then $F$ is not isomorphic to $\mathbb{Q}$ because there is no bijection between $F$ and $\mathbb{Q}$.

Summing up, your question presumes (when you say "axioms of the rational numbers") the existence of an axiomatic characterization of $\mathbb{Q}$, but unfortunately, this axiomatic characterization does not exist.

$\endgroup$
  • 1
    $\begingroup$ @DavidReed - How can you distinguish between natural and non-natural numbers by means of a first order formula in the language of ordered fields? $\endgroup$ – Taroccoesbrocco Feb 10 '18 at 5:59
  • $\begingroup$ @DavidReed: It's not clear what you mean. The rationals don't satisfy the axioms of Robinson arithmetic, and it is not immediately obvious that one can define in the language of ordered fields a subclass of the rationals that would satisfy those axioms. $\endgroup$ – user14972 Feb 10 '18 at 8:25
  • 4
    $\begingroup$ @Taroccoesbrocco There is a first-order characterization of natural numbers in rationals (see e.g. here). By Godel this implies that the first-order theory of rationals is undecidable. $\endgroup$ – Wojowu Feb 10 '18 at 9:03
  • $\begingroup$ The rational numbers do satisfy a structural kind of induction principle: any set of rationals that is nonempty, contains 1, and is closed under addition, subtraction, and inverse, must be the entire set of rationals. $\endgroup$ – Carl Mummert Feb 10 '18 at 14:02
  • $\begingroup$ @Taroccoesbrocco Nvm, there are two axioms that the rationals fail to satisfy. I was wrong. $\endgroup$ – David Reed Feb 10 '18 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.