108
$\begingroup$

An irrational number is a real number that cannot be expressed as a ratio of integers.

Is it possible to formulate a "positive" definition for irrational numbers?

A few examples:

  • An irrational number is a real number that can be expressed as...
  • An irrational number is a real number that can be expressed only as...

I cannot find any such definition which does not include the term irrational number to begin with.

Since not all irrational numbers are computable, I believe that the answer is No.

Any idea how to prove it formally?

Thanks

$\endgroup$
  • 30
    $\begingroup$ For a proof of this kind of fact (if it were true), you'd need to define what counts as a "positive" definition. For example, clearly "A real number $x$ is irrational if $\mathbb{Q} \cup \{x\} \neq \mathbb{Q}$." is not, because it just hides "is not rational" in the $\neq$. But how about "A real number $x$ is irrational if $(\mathbb{Q} \cup \{x\}) \setminus \mathbb{Q} = \{x\}$"? It says the same thing, but contains no negations, (except in the definition of the set difference $\setminus$). $\endgroup$ – JiK Sep 6 '16 at 9:00
  • 1
    $\begingroup$ @JiK: I agree that the definition of "positive" is somewhat vague. For instance, even the term infinite could be considered "negative" (i.e. not finite). It is also mentioned in a comment to one of the answers below. I am not so sure how it could be phrased mathematically. $\endgroup$ – barak manos Sep 6 '16 at 9:02
  • 28
    $\begingroup$ There are trivial one: an irrational is a real number $x$ such that for every rational $r$ we have $|x-r|>0$. $\endgroup$ – Carl Mummert Sep 6 '16 at 11:03
  • 10
    $\begingroup$ Any statement that works will be equivalent to "$x$ is not rational", or the statement wouldn't be correct. The point seems to make a positive definition, but is the point to also make a non-obvious one? Note that $a > b$ is a positive statement about reals - it says that something does exist, namely a rational between $a$ and $b$. $\endgroup$ – Carl Mummert Sep 6 '16 at 11:48
  • 3
    $\begingroup$ @barakmanos People love arguing, and they love puzzles involving twisting words around. Most of the answers are simply theorems about irrationals, not definitions. SInce the question is "how to state a definition without a 'not'," I stand by my position that this is not a math problem. $\endgroup$ – Carl Witthoft Sep 7 '16 at 17:59

19 Answers 19

140
$\begingroup$

An irrational number is a real number that can be expressed as an infinite simple continued fraction.

$\endgroup$
  • 39
    $\begingroup$ Infinite is by definition not finite. Is this really "positive"? $\endgroup$ – MathematicsStudent1122 Sep 6 '16 at 7:06
  • 89
    $\begingroup$ That's one definition. On the other hand, you could define an infinite set as a set that can be put in one-to-one correspondence with a proper subset of it, and a finite set as one that is not infinite. $\endgroup$ – Robert Israel Sep 6 '16 at 7:17
  • 12
    $\begingroup$ @WillR: The continued fraction for $\sqrt2$ is infinite; there are an infinite number of terms in the continued fraction. The fact that the terms are chosen from a finite set is irrelevant. $\endgroup$ – robjohn Sep 6 '16 at 8:57
  • 8
    $\begingroup$ @MathematicsStudent1122 “Infinite continued fraction” is an indivisible term, referring to certain objects involving sequences indexed by $\mathbb N$ (whence “infinite”) that represent real numbers by means of certain limits. It’s not that you would take a more general “continued fraction” and then count the size of some its parameter to find it is infinite. Finite and infinite continued fractions are just different (though of course related) kinds of objects. $\endgroup$ – Emil Jeřábek Sep 6 '16 at 14:18
  • 5
    $\begingroup$ No, I'm emeritus. $\endgroup$ – Robert Israel Sep 7 '16 at 2:46
77
$\begingroup$

A irrational number is a real number $x$ such that for any integer $q'$ there exists a rational number $p/q$ with $q > q'$ and

$$0 < \left|x - \frac pq \right| < \frac{1}{q^2}.$$

$\endgroup$
  • 3
    $\begingroup$ The geometric argument there shows that irrational numbers can be that well approximated, not that rational ones can't. (Though the latter is also true.) $\endgroup$ – Gareth McCaughan Sep 6 '16 at 11:59
  • 2
    $\begingroup$ @BradThomas: I would also like to be sure that this covers the entire set of irrationals, and no real value outside of this set (i.e., no rational value). So I'm waiting for some more comments on it. I favor this answer in the fact that it does not make use of the term infinite (which is equivalent to "not finite"). $\endgroup$ – barak manos Sep 6 '16 at 15:03
  • 7
    $\begingroup$ The "not" in this definition is hiding in the symbols "$0<$", which translate to "greater than and not equal to zero". $\endgroup$ – Oscar Cunningham Sep 6 '16 at 17:49
  • 4
    $\begingroup$ @OscarCunningham If you like, we can remove the "$0 <$" and instead assert that $p$ and $q$ are coprime. (But there is no precise definition of a "positive" definition, anyway.) $\endgroup$ – Eric M. Schmidt Sep 6 '16 at 18:02
  • 4
    $\begingroup$ @OscarCunningham, by that token, you can't use any relation. $=$ is not greater than and not less than. $\endgroup$ – Paul Draper Sep 8 '16 at 17:59
66
$\begingroup$

If you want simple definition that's not based on Dirichlet's or Hurwitz's theorem, try this:

A real number $x$ is irrational if and only if for all positive integers $n$ there exists an integer $m$ such that $0\lt nx-m\lt1$.

The underlying theorem here is that for all real numbers $x$ and all positive integers $n$ there is a unique integer $m$ (namely, $m=\lfloor nx\rfloor$) such that $0\le nx-m\lt1$. If $0=nx-m$, then $x=m/n$ is rational, and vice versa.

$\endgroup$
  • 4
    $\begingroup$ Very elegant solution! $\endgroup$ – MinecraftShamrock Sep 6 '16 at 17:12
  • 1
    $\begingroup$ This is Eric Schmidt's answer multiplied by Q^2, isn't it? $\endgroup$ – Carl Witthoft Sep 7 '16 at 17:56
  • 1
    $\begingroup$ @CarlWitthoft, no, Eric's answer involves a stronger property of irrational numbers (i.e., Dirichlet's approximation theorem -- see the remark at the beginning of Laurent Duval's answer). $\endgroup$ – Barry Cipra Sep 7 '16 at 18:01
47
$\begingroup$

You can give one such characterization using continued fractions. An irrational number is a real number that can be expressed as an infinite continued fraction $$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + {_\ddots} }}}$$ for a sequence $(a_n)_{n\in\mathbb{N}}$ where $a_0\in\mathbb{Z}$ and $a_n\in\mathbb{Z}_+$ for all $n>0$. (In fact, the sequence $(a_n)$ is then unique, and this correspondence is actually a homeomorphism between the space of irrational numbers and the space of such sequences in the product topology.)

$\endgroup$
  • 1
    $\begingroup$ Thank you. So I take it that rational numbers cannot be expressed as an infinite simple continued fraction? $\endgroup$ – barak manos Sep 6 '16 at 7:04
  • 6
    $\begingroup$ That's right. The proof is basically that you can prove by induction that the numbers $a_n$ are uniquely determined, but if you follow the process for uniquely determining them for a rational number, you are essentially performing the Euclidean algorithm which will terminate at some point and so you would get $a_n=0$. $\endgroup$ – Eric Wofsey Sep 6 '16 at 7:09
  • $\begingroup$ This answer is beautiful ^_^ $\endgroup$ – ABcDexter Sep 7 '16 at 7:41
  • $\begingroup$ This answer is wrong. The irrational numbers are uncountable, but the infinite continued fraction formula can only generate a countable number of different values, given all possible integer values for a0,a1 etc. So there must be some irrational numbers that the continued fraction cannot generate. $\endgroup$ – Adam Gawne-Cain Sep 9 '16 at 7:49
  • 8
    $\begingroup$ @AdamGawne-Cain: There are uncountably many infinite continued fractions, since there uncountably many different sequences $(a_n)_{n\in\mathbb{N}}$. $\endgroup$ – Eric Wofsey Sep 9 '16 at 7:50
29
$\begingroup$

In addition to Dirichlet's approximation theorem as given by @Eric M. Schmidt, you have Hurwitz's theorem, saying that an irrational number $\alpha$ is a real number such that there exist infinitely many relatively prime integers $p$, $q$ such that $$\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{{\sqrt {5}}\,q^{2}}}.$$

Here, $\sqrt {5}$ is the best possible constant. It is attained for instance by the irrational $\phi = \frac{1+\sqrt{5}}{2}$ (the golden mean or golden ratio). The reason is explained in Why is there a $\sqrt {5}$ for instance in Hurwitz's Theorem? See for instance Introduction to number theory, M. Klazar.

As a side note, what happens to mere rationals: if $\alpha = \frac{r}{s}$, ($r$ and $s$ relatively prime):

$$ \left| \frac{r}{s} - \frac{p}{q}\right| = \left| \frac{rq-ps}{sq} \right| \geq \frac{\left| \frac{q}{s}\right|}{q^2}$$

and

$$\frac{\left| \frac{q}{s}\right|}{q^2}> \frac{k}{q^2}$$ except for a finite number of $q$ such that $|q|\leq |ks|$. Nice graphic versions with circles of Hurwitz's theorem (and some more on fractions) can be found in Ford, Fractions, 1938, American Mathematical Monthly. You can check that out, for instance, at Ford circles:

Ford circles

$\endgroup$
  • 1
    $\begingroup$ Wow, I read about this "threshold" somewhere a few years ago, forgot where, and had no idea how find it. Thanks!!! $\endgroup$ – barak manos Sep 6 '16 at 11:10
  • 1
    $\begingroup$ Thank you for the extra information. As I mentioned, I was looking for it for quite some time, though I had no lead, except for the fact that I read it on Wikipedia (but couldn't remember under what search-criteria). Now I finally have that lead :) $\endgroup$ – barak manos Sep 6 '16 at 15:06
20
$\begingroup$

An irrational number is a number $c$ such that $\{cn \text{ mod } 1 \mid n \in \mathbb{N}\}$ is dense in $[0, 1]$.

More strongly, an irrational number is a number $c$ such that for every continuous function $f : [0, 1] \rightarrow \mathbb{R}$,

$$\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N f(nc \text{ mod } 1) = \int_0^1 f \text{d}x.$$

$\endgroup$
17
$\begingroup$

Some of the answers here are trying to define an irrational number via some of their non-obvious properties which are not shared by a rational number. This strikes me as quite counter-intuitive and perhaps not so helpful for a person trying to study about irrational numbers.

To give an analogy let's compare the following definitions of a prime number:

1) A natural number $p > 1$ is said to be prime if it can't be expressed as product $p = ab$ where $a, b$ are natural numbers greater than $1$. This one according to you is a negative definition.

2) A natural number $p > 1$ is said to be prime whenever $p \mid ab$ implies $p \mid a$ or $p \mid b$ where $a, b$ are natural numbers. This is a slightly complicated but positive definition.

3) A natural number $p > 1$ is said to be prime whenever $(p - 1)! + 1$ is divisible by $p$. This is again a very very complicated but positive definition.

Out of these I prefer the first definition because it is much much simpler than others and can be explained to a kid of 7-8 years who knows how to multiply small numbers. I have written a post on definitions which highlights other important qualities of a good definition but I don't see the positivity as a sufficiently desirable quality to trump simplicity.


Coming back to the definition of irrational number the simplest possible answer is that defining irrational numbers on the basis of existing knowledge of rational numbers is a reasonably hard problem which was solved only in 19th century by the likes of Cantor, Dedekind and Weierstrass. Some amount of simplicity can be achieved (at the cost of having difficult proofs for properties of irrational numbers) by defining irrational numbers as numbers with non-repeating non-terminating decimal representation.

But the really useful approach here is to define real numbers in terms of rationals (like a rational number is defined in terms of integers) and then define an irrational number as a real number which is not rational. This is the most frequently used definition in practice (say while proving that some particular number is irrational). The name irrational itself has negative connotation because of ir-prefix and hence it is somewhat natural to expect a definition with negative connotation. The real problem with this definition is not its negative connotation, but rather the fact that almost always whenever we encounter this definition, it is accompanied by a total lack of definition of "a real number" and in general this leads to a circularity in the definition game:

  • An irrational number is a real number which is not rational.
  • A real number is either a rational number or an irrational number.

And the blame for this circularity is entirely on textbook authors. It is better to be intellectually honest and say: Real numbers/irrational numbers are difficult to define in terms of rationals and henceforth we will take their existence for granted and assume some of their properties which are almost similar to rationals. You will study a proper definition when you have attained reasonable mathematical maturity. Unfortunately this attitude is very rare in textbooks authors and instead student is expected to be content with the circularity involved above.

$\endgroup$
  • 3
    $\begingroup$ But the examples of defining a prime number negatively as "a natural number $p \gt 1$ with no factors other than $1$ or $p$" or positively as "a natural number with exactly two factors" may be closer to the question $\endgroup$ – Henry Sep 6 '16 at 12:58
  • $\begingroup$ @Henry: Agree. I should have used this definition. Thanks. $\endgroup$ – Paramanand Singh Sep 6 '16 at 19:40
  • $\begingroup$ @Henry I would say that "a prime number has no factors other than $1$ or $p$" is actually a positive property when you write it out: All factors of $p$ are equal to $1$ or $p$. $\endgroup$ – Mario Carneiro Sep 9 '16 at 5:37
  • $\begingroup$ For other people wondering about (3), see Wilson's theorem. $\endgroup$ – Mark Hurd Sep 13 '16 at 7:11
14
$\begingroup$

Dirichlet's approximation theorem implies that irrational numbers are those that can be well-approximated by rational numbers, in a certain precise sense. Curiously, rational numbers cannot be approximated well by rational numbers.

$\endgroup$
  • $\begingroup$ Thank you (got several different answers here, all interesting). $\endgroup$ – barak manos Sep 6 '16 at 7:05
  • 1
    $\begingroup$ @AOrtiz, no. In the certain precise sense that I mentioned, rational numbers cannot be approximated well by rational numbers. $\endgroup$ – Mariano Suárez-Álvarez Sep 6 '16 at 17:45
  • 2
    $\begingroup$ The correct statement is that rational numbers cannot be well-approximated by other rational numbers. Under any definition of good approximation, rational numbers have better approximations than is possible for irrational numbers, by approximating $a/b$ by $na/nb$ for any nonzero $n$. $\endgroup$ – zyx Sep 6 '16 at 20:05
  • 1
    $\begingroup$ Well, no. The «certain precise sense» which I intentionally did not make explicit, trusting the googling powers of anyone interested, is certainly a good one and excludes that, simply because including it is not useful. $\endgroup$ – Mariano Suárez-Álvarez Sep 6 '16 at 23:11
  • 2
    $\begingroup$ The first result with any search engine is the Wikipedia page on rational approximation. The section of that page elaborating your observation is titled: "Approximation of a rational by other rationals". en.wikipedia.org/wiki/… $\endgroup$ – zyx Sep 7 '16 at 3:33
13
$\begingroup$

Whether a definition is positive or negative seems to be rather subjective and not significant to the elegance of a definition (as @ParamanandSingh pointed out). In fact you can formulate any idea positive as well as negative. Starting with your originally negative definition:

An irrational number is a real number that is not rational.

The Idea "real and not rational" can also be formulated positively:

An irrational number is a real number $x$ such that $\vert \{x\} \cup \mathbb Q \vert > \vert \mathbb Q \vert$

Or alternatively:

An irrational number is a real number $x$ such that $\forall q \in \mathbb Q: \vert x-q \vert > 0$

Which is of course the "positivised" formulation of:

An irrational number is a real number $x$ such that $\forall q \in \mathbb Q: x-q \neq 0$ or equivalently $\forall q \in \mathbb Q: x \neq q$

Generally speaking, we can always create a negative formulation from a positive one by negating its negation and a positive formulation from a negative by introducing new symbols. Since all correct definitions are logically equivalent, what is negative and what is positive is only a question of our language of describing things. (Looking forward to discussing this)

$\endgroup$
  • 1
    $\begingroup$ What if we define positive as meaning asserting something about a finite number of things. $\endgroup$ – Brad Thomas Sep 6 '16 at 17:42
  • 2
    $\begingroup$ @BradThomas While I am thinking about this, could you define what a thing is? How about using a finite number of things that structurally contain infinitely many other things? E.g. how about a finite number of irrational numbers, which we could think of an infinite series of integers $\endgroup$ – MinecraftShamrock Sep 6 '16 at 17:47
  • 1
    $\begingroup$ @BradThomas The problem with this, however, is that we can't use irrationals as we're just defining them. To even generalize the question: Is $x \in M$ an assertion about a finite number of things if M is an infinite set? $\endgroup$ – MinecraftShamrock Sep 6 '16 at 17:50
  • 1
    $\begingroup$ Great points, probably worthy of their own question! $\endgroup$ – Brad Thomas Sep 6 '16 at 18:16
  • 2
    $\begingroup$ What does the notation $\vert \{x\} \cup \mathbb Q \vert > \vert \mathbb Q \vert$ mean? $\endgroup$ – Jeppe Stig Nielsen Sep 9 '16 at 5:33
9
$\begingroup$

I think the fundamental distinction is not positive/negative, but that irrationals cannot be defined without quantifying over the set of rationals (or something equivalent to that, such as the set of all integers). They are of "higher type" than rationals.

More precisely, irrationality cannot (it seems) be defined without alternating at least two quantifiers, $\forall \exists$, while rationality can be defined with an $\exists$ quantifier, where the quantifiers range over integers.

It is similar, as is hinted at in the question, to the asymmetry of defining halting and non-halting Turing machines. One definition quantifies over inputs and the other has alternating quantification over inputs and computation times.

$\endgroup$
  • $\begingroup$ Not a direct answer to my question, but a very interesting one nevertheless. Thanks. $\endgroup$ – barak manos Sep 7 '16 at 4:37
  • $\begingroup$ Interestingly, this is also a litmus test for "positive" irrational definitions vs "negative" ones: negatively defined irrationals have complexity $\forall$, but positively defined irrationals have complexity $\forall\exists$. (The literal transcription of the negative irrational definition is $\forall m\in\Bbb Z,\forall n\in\Bbb N,m/n\ne\alpha$.) $\endgroup$ – Mario Carneiro Sep 9 '16 at 5:53
  • $\begingroup$ The negative definition hides one quantifier in " $\neq \alpha$". Maybe this is also true for some of the positive definitions. @MarioCarneiro $\endgroup$ – zyx Sep 9 '16 at 6:03
  • $\begingroup$ @zyx By $m/n\ne\alpha$ I mean no more or less than $m/n=\alpha\to\bot$; no further quantifiers are needed. (For the positive definitions involving $<$, I presume an apartness condition, which is an extra $\exists$ quantifier.) In set theory, at least, equality of objects is already at the foundation so you don't need to go further. $\endgroup$ – Mario Carneiro Sep 9 '16 at 6:09
  • $\begingroup$ I mean that real numbers are a "higher type" object in the same sense as irrationals are of higher type than rationals. If you build them out of integers then real number is $\forall \exists$ (the quantifiers that say a sequence of rationals converges) while rational is $\exists$. @MarioCarneiro $\endgroup$ – zyx Sep 9 '16 at 6:16
8
$\begingroup$

An irrational number is one whose every representation in any base contains infinitely many digits.

$\endgroup$
  • 3
    $\begingroup$ $0.01001000100001000001\dots$ is an irrational number which contains infinitely many $0$s. $\endgroup$ – barak manos Sep 6 '16 at 8:50
  • 2
    $\begingroup$ and infinitely many nonzeroes too. So what? $\endgroup$ – Lynn Sep 6 '16 at 8:51
  • 1
    $\begingroup$ @barak Well, I guess the other than 0 part isn't even needed here. $\endgroup$ – Lynn Sep 6 '16 at 9:04
  • 3
    $\begingroup$ BTW, you should probably emphasize every natural base. $\endgroup$ – barak manos Sep 6 '16 at 9:05
  • 2
    $\begingroup$ @Hurkyl Yes, I believe nonterminating conveys the same idea, but in a non-positive way. $\endgroup$ – Lynn Sep 6 '16 at 13:06
8
$\begingroup$

There is a somewhat trivial answer:

An irrational number is a real number $x$ such that for every rational number $r$ we have $|x−r|>0$.

Of course, this is equivalent to $x$ being not rational - that is the goal, after all. However, I think the statement has no element that is obviously "negative".

This definition can be phrased in terms of positive knowledge: for each rational $r$, there is a pair of disjoint open intervals, one containing $x$ and one containing $r$. This is to say: $x$ is irrational if and only if it is 'separated' from each rational number.

$\endgroup$
  • $\begingroup$ Is "disjoint" a positive property? (Alternatively, you can phrase your "positive knowledge" as "for each rational $r$, there is a rational $s$ such that $x<s<r$ or $x>s>r$".) $\endgroup$ – Mario Carneiro Sep 10 '16 at 0:32
  • $\begingroup$ Yes - the latter is how the disjointness would be phrased in constructive settings. It is not about the lack of intersection so much as about the ability to examine the given endpoints to see that the intervals cannot overlap. For example, the intervals $(0,1)$ and $(2,3)$ cannot overlap based solely on their endpoints. $\endgroup$ – Carl Mummert Sep 10 '16 at 0:51
6
$\begingroup$

An irrational number is a real number in which every infinite contiguous subsequence of its decimal representation is unique.

$\endgroup$
  • 1
    $\begingroup$ Nice answer! I think it's equivalent to saying that one of the infinite "tails" i.e. all digits after some position $n$ is unique $\endgroup$ – Jay Sep 7 '16 at 23:28
  • $\begingroup$ @Jay or "non-repeating" $\endgroup$ – M.M Sep 9 '16 at 3:38
5
$\begingroup$

If you want a definition that starts with something like this,

An irrational number is a real number that ...

then first you have to define what a real number is.

It's possible to define the real numbers as Dedekind cuts, where by definition a Dedekind cut is a partition of the set of rational numbers, $\mathbb Q$, into an ordered pair of sets $(L,U)$ such that $L \cup U = \mathbb Q$, $\forall a, b: a \in L \land b \in U \implies a < b$, and $\forall a : a \in L \implies \exists b : b \in L \land a < b$. (The last condition is usually expressed, "$L$ has no largest element," but I am trying to avoid the word "no".)

If you have done all the steps to establish that it makes sense to say that every real number is a Dedekind cut, then an irrational number is a Dedekind cut $x = (L,U)$ such that $$\forall a : a \in U \implies \exists b : b \in U \land b < a. \tag1$$ If $x$ were rational, then $U$ would have a smallest element (namely, the element of $\mathbb Q$ corresponding to $x$) and condition $(1)$ would be false.

$\endgroup$
  • $\begingroup$ using here Dedekind cuts is a little circular, no ? $\endgroup$ – user354674 Sep 14 '16 at 13:13
  • $\begingroup$ @igael How so? It's one of the well-known ways to construct the real numbers. $\endgroup$ – David K Sep 14 '16 at 13:35
  • $\begingroup$ it is the complementary of something ( means a negative construction ) $\endgroup$ – user354674 Sep 14 '16 at 15:48
  • $\begingroup$ @igael A Dedekind cut is a partition of $\mathbb Q$. Is every partition of a set a "negative" construction? (There is typically a "no largest element" condition in the definition, but I replaced that with what seemed to me a completely positive condition.) $\endgroup$ – David K Sep 14 '16 at 17:59
4
$\begingroup$

Just look at this algorithm which may gets you a continued fraction:

You start with a real number $\alpha_0$, then define $a_i$ recusively by $a_i=\frac{1 }{\alpha_{i-1} -n_i}$ where $n_i$ is the greatest integer strictly smaller than $\alpha_{i-1}$.

Now my claim is:

An irrational number is a real number that can be expressed as continued fraction fraction using this algorithm.

By expressed I mean $$ \limsup_i [n_1;n_2, \dots ,n_i]= \alpha_0 = \liminf_i [n_1;n_2, \dots ,n_i].$$

I used the axiomatic definition of the real numbers,(which to me is somehow positive) that is why I write the limit like this.

$\endgroup$
3
$\begingroup$

I think the notion of "positive" in this question indicates that a constructive definition is requested, as opposed to an existence proof. The unsatisfying part of the traditional definition is that given some particular value $x$, I cannot easily tell whether it's irrational or not. Furthermore, if I want to start enumerating the irrationals, the definition helps me not at all.

For this reason, I think that Eric Wofsey's answer is the only one which satisfies the spirit of the question. It both constructs instances of irrational numbers and offers a method for enumerating them!

From a computational perspective, all definitions require an infinite amount of work to verify the irrationality of $x$, due to the nature of irrational numbers to begin with. But with the continued fraction definition, one can compute increasingly longer approximations which get closer and closer to $x$, which are the convergents of $x$. With the other definitions, it is not clear how to proceed in a manner which increases one's confidence in the irrationality of $x$.

That is, if $x$ is actually rational, then there must be some $n$ at which the sequence equals $x$, and it should always be clear how to adjust the sequence to get closer to $x$. That's because increasing $a_i$ will always produce a bigger change than increasing $a_j$ when $i < j$. Therefore, searching for the sequence $a_0...a_n$ which is closest to $x$ should be linear in $n$.

Of course, this is hand-waving a bit, since this process requires a computer which can represent arbitrary reals to begin with, even though there can be no such thing. But the argument still works if we bound the representation by saying that we can only inspect the first $B$ digits of each value.

More importantly, for rational values of $x$, we know that computing the best rational approximation will terminate in finite time, and that this time is proportional to the "irrationality" of $x$, where I define "irrationality" to be the number of values $n$ in the continued fraction sequence which exactly equals $x$ (meaning, all successive values are 0). When $n = \infty$, $x$ is "completely irrational" or just "irrational". Of course, when $n = 0$, then $x$ is "completely rational", or "integer". When $n$ is small, $x$ is only "slightly irrational". ;)

On the other hand, it is not at all apparent to me how one could use Dirichlet's or Hurwitz's theorems to determine the rationality of $x$ in finite time, let alone an algorithm which is linear in the irrationality of $x$.

$\endgroup$
3
$\begingroup$

I think the spirit of "positive" in the original question is some way to test if a number is irrational in a finite time.

So assume(*) we have a computing engine (CE) that has all the language elements of C, common functions like floor and pow, but which can handle Real numbers with no loss of precision.

With this CE, can you write a function isIrrational(X) that gets the right answer in a finite time, and with a finite number of Real variables (i.e. infinite set of all rationals not allowed)? If not, can you prove that it is impossible with this CE?


(*) I expect this CE is impossible to implement with a Turing machine. But maybe it could be implemented by an analog computer in a non digital Universe, which could store the Real value as some continuous physical property.

$\endgroup$
  • 1
    $\begingroup$ There are no continuous physical properties in the quantum universe. "Every irrational has a decimal expansion that goes on forever." {No negatives; however, 'forever' may be 'im-possible'} $\endgroup$ – amI Sep 9 '16 at 20:20
  • 2
    $\begingroup$ The issue is that any computable function of real numbers will be continuous. This is because, in finite time, it can only examine its input up to some precision, which means that it will give the same answer for all other reals which agree up to that precision. But any continuous function from reals to naturals has to be continuous, by basic topology. So there is no nonempty proper subset of the reals that is decidable in finite time by a computer program. We cannot even compute whether an arbitrary real is equal to zero. This is a standard fact in a first course on computable analysis. $\endgroup$ – Carl Mummert Sep 10 '16 at 0:54
  • $\begingroup$ @CarlMummert: You're missing the point that he included floor which is discontinuous. In any case, this post does not answer the question, though it would make an interesting question on its own, I think. $\endgroup$ – user21820 Sep 16 '16 at 15:55
2
$\begingroup$

This question is discussed in some detail on a different answer of mine: Are there real numbers that are neither rational nor irrational? See also What's an example of a number that is neither rational nor irrational?.

A small quote, with the actual definition:

Thus there is a measurable gap between the irrationality measures of rational and irrational numbers, and this yields an alternative "constructive" definition of irrational: let $x\in\Bbb I$, read "$x$ is irrational", if $|x-p/q|<q^{-2}$ has infinitely many coprime solutions.

Let me add, to forestall confusion about the word "infinite" in the above: I mean that the set of solutions is denumerable, which is to say that there is a function which takes each solution $(p,q)$ to another solution $(p',q')$ such that $(p,q)<(p',q')$ under some suitable total order (such as lexicographic order).

The definition is equivalent to Eric Schmidt's, but the extra comments about application to intuitionistic logic are worth a read if that is your interest.

$\endgroup$
  • $\begingroup$ Side note: Perhaps the answer to that question is "no, there aren't any such numbers, but there are irrational numbers which cannot be expressed in any algorithm or formula, aka non-computable numbers" (which btw, I have also mentioned in my question here). I believe that the blue part in the diagram depicted in that other question was possibly meant by the author of the diagram to represent all the non-computable numbers. $\endgroup$ – barak manos Sep 20 '16 at 7:44
  • $\begingroup$ @barakmanos I assume it was just a bad drawing; somehow I doubt they had computability in mind. The idea is that the "constructive" definition gives the set of all computable irrational numbers when we assume that all functions in the definition (or $\forall\exists$ instantiations) are computable. If we relax this to all functions, we get the classical irrationals. The negative definition gives classical irrationals regardless of whether we interpret everything as computable or not. $\endgroup$ – Mario Carneiro Sep 20 '16 at 7:48
  • $\begingroup$ My initial concern here (in my question above) was that any "constructive" definition would not include the non-computable irrationals, hence no such definition was viable. But according to several answers here, there seem to be several different such definitions (although the term "constructive" is somewhat vague). Your definition here is indeed close to Eric Schmidt's definition, which is no arguably "constructive" (IMO). $\endgroup$ – barak manos Sep 20 '16 at 7:51
  • $\begingroup$ @barakmanos It is entirely dependent on how you choose to interpret the $\forall\exists$ statements. If you do it the normal (classical) way, then you will get all irrationals, including the noncomputable ones; however the function giving witnesses for this irrational will not be a computable function. (Classically, these are still functions, hence they are included in the set.) It is only when you use tricks like the BHK interpretation that you get a separation of the +ve and -ve definitions, where the first only contains computable numbers. $\endgroup$ – Mario Carneiro Sep 20 '16 at 7:57
2
$\begingroup$

A real number $\alpha$ is irrational precisely when the equation $y=\alpha x$ has one solution in integers, namely $(0,0)$. The number $\alpha$ is rational if and only there are and infinite number of integral solutions. Here is the picture from C. D. Olds' book Continued Fractions:

Olds Page 78

$\endgroup$

protected by Alex M. Sep 9 '16 at 8:57

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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