14
$\begingroup$

This is inspired by the Alexander Shen's post here: https://www.facebook.com/groups/mathpuz/permalink/1058782384297603/ (the post is in Russian, but it is easy Russian, and google translate should work fine).

All proofs of irrationality of $\sqrt{n}$ where $n$ is not a perfect square that I know are using (explicitly of implicitly) the induction axiom of the Peano arithmetic.

Question: Can the induction axiom be replaced by the axiom that $\sqrt{2}$ is irrational?

$\endgroup$
8
  • 17
    $\begingroup$ Peano arithmetic can't be finitely axiomatised so you can't replace the axiom scheme of induction with a single axiom. (This depends on your definition of PA.) $\endgroup$
    – Dan Piponi
    Commented Jul 26, 2018 at 1:03
  • $\begingroup$ @DanPiponi: I see, but if I change the "definition of PA", the question makes sense? What is the "right" (or "wrong") definition? $\endgroup$
    – user6976
    Commented Jul 26, 2018 at 1:08
  • 1
    $\begingroup$ Do we know a proof of such irrationality in Robinson's arithmetic? Gerhard "Showing Some Models With Holes" Paseman, 2018.07.25. $\endgroup$ Commented Jul 26, 2018 at 1:11
  • 5
    $\begingroup$ @Mark Unique factorization is first-order. $\endgroup$ Commented Jul 26, 2018 at 1:16
  • 5
    $\begingroup$ You can use Goedel's trick of coding finite sequences of numbers by numbers to express unique factorization in a first order way. Kaye's book "Models of Peano arithmetic" contains the relevant details. For what is worth, I think your question is interesting. $\endgroup$ Commented Jul 26, 2018 at 1:29

1 Answer 1

23
$\begingroup$

One can prove that $\sqrt{2}$ is irrational and indeed that any particular $\sqrt{n}$ is irrational (if $n$ is not a perfect squares) assuming only the principle of induction for $\Delta_0$ formulas, which is much weaker than the full strength of PA. In this sense, the answer is negative.

The classical proof of the irrationality of $\sqrt{2}$ relies on the fact that every rational number has a representation in lowest terms, and this can be proved with a very weak induction principle, using no unbounded quantifiers. Namely, every $p/q$ has a lowest-term representation, since if this is true for all pairs of numbers whose numerator is smaller than $p$, then it is true for $p/q$, since otherwise we would immediately reduce to a case with a smaller numerator. Thus, we never need to embark on unbounded searches to find the lowest-terms representation of a rational number.

And once one has the lowest-term representations, one can easily prove the classical result that $\sqrt{2}$ is irrational, since otherwise one gets $2q^2=p^2$ and so on, as we all know, ultimately showing that both $p$ and $q$ are even, a contradiction.

For the case of $\sqrt{n}$, for fixed $n$, then one can also prove this using just the existence of lowest-terms representations. Basically, $\sqrt{n}$ is irrational, unless $n$ is a perfect square, since otherwise $nq^2=p^2$ and the prime exponent parities don't work out, as you know.

To prove the universal statement about all such $n$, however, that is, the statement "for all numbers $n$, the square root $\sqrt{n}$ is irrational unless $n$ is a perfect square," it seems that one uses the fundamental theorem of arithmetic, asserting that every number has unique prime factorization, which can be proved using $\Sigma_1$ induction. Namely, if every number smaller than $n$ has a unique factorization into primes, then $n$ also has this, since otherwise one can factor $n$ and reduce to the smaller case. (Here, we have to search a little bit, but not much, to find the code of the factorization.) But once you have the factorization into primes, then again the classical argument shows as above that $\sqrt{n}$ is irrational unless $n$ is a perfect square.

I'm not sure if one can prove the fundamental theorem using only $\Delta_0$-induction. And because we moved up to $\Sigma_1$ induction to get the fundamental theorem, it is conceivable to me that one might be able to have a bizarre model of $\Delta_0$-induction in which the universal claim about all $\sqrt{n}$ was not true, even if it was true in every standard-finite instance, and this would be an interesting answer to your question. I would want the proof theorists to weigh in on this.

Since PA proves the consistency of $\Sigma_0$ induction, and indeed of $\Sigma_n$-induction for any fixed $n$, it follows by the incompleteness theorem (as mentioned in the comment of Dan Piponi) that we cannot axiomatize PA by adding the assertion "$\sqrt{2}$ is irrational" or "$\sqrt{n}$ is irrational for all non-perfect squares $n$" to any finite list of axioms.

The essence of PA is the induction axiom for increasingly difficult arithmetic properties. No bounded amount of complexity for induction, limited to $\Sigma_n$ induction for fixed $n$, is sufficient to capture the full power of PA.

$\endgroup$
13
  • 1
    $\begingroup$ Thank you! It would help me (not a logician) if you provide a reference to the "principal of induction for $\Sigma_0$ formulas". $\endgroup$
    – user6976
    Commented Jul 26, 2018 at 1:27
  • 3
    $\begingroup$ This is the induction principle asserting $[\varphi(0)\wedge\forall n\ \varphi(n)\to\varphi(n+1)]\to\forall n\ \varphi(n)$, where $\varphi$ is any assertion in the language of arithmetic using only bounded quantifiers. Probably the proof-theorists can say more precisely what level of induction is needed. Open induction (i.e. quantifier-free induction) is not enough, since there are models of open induction where $\sqrt{2}$ is rational, due to Shephardson, as explained by Francois Dorais here: mathoverflow.net/a/20944/1946. $\endgroup$ Commented Jul 26, 2018 at 1:33
  • 2
    $\begingroup$ Hi Joel. When I first read the question, I thought it was asking whether replacing induction with the irrationality of $\sqrt2$ would suffice to prove the irrationality of $\sqrt n$ for all relevant $n$. Do you have any thoughts on this variant? $\endgroup$ Commented Jul 26, 2018 at 1:33
  • 2
    $\begingroup$ The question would be whether one can do a Shephardson-like analysis to construct a model where $\sqrt{2}$ is rational, but not some other instance, such as $\sqrt{17}$. $\endgroup$ Commented Jul 26, 2018 at 1:59
  • 2
    $\begingroup$ The irrationality of $\sqrt n$ for all $n$ that are not perfect squares, as well as the more general schema that any model of arithmetic (or rather, its extension with negative numbers to form a ring) is integrally closed in its fraction field, follows from the existence of gcd for any pair of numbers (this is a standard algebraic fact). In turn, the existence of gcd (along with Bézout cofactors) can be proved in a straightforward way using just $IE_1$ (a fragment of $I\Delta_0$ with induction only for bounded existential formulas). $\endgroup$ Commented Jul 26, 2018 at 5:58

You must log in to answer this question.