Tuesday, December 06, 2016

A students unusual proof might be a better proof

I asked a student to show that between any two rationals is a rational.

She did the following: if x < y are rational then take δ << y-x and rational and use x+δ

This is correct though more complicated then what I had in mind: (x+y)/2

I then asked her to prove that between two irrationals is an irrational.

She did the following: if x < y are irrational then take δ << y-x and rational and use x+δ


I had a different proof in mind: the number of reals in (x,y) is uncountable while the number of rationals is countable, so there must be at least one (in fact uncountable many) irrationals in (x,y).
(NOTE- I originally had `the number of irrationals in (x,y) is ...' which, as comment by stu below
points out, is assuming what I want to prove. Typo on my part.)

These proofs raise questions about our criteria of goodness-of-proof.

1) Which proof for rationals is better:

The delta-proof or the (x+y)/2 proof?

The (x+y)/2 proof is simple, but the delta-proof also works for irrationals.

2) Which proof for irrationals is better:

The delta proof or the uncountable proof?

Which one is simpler?

The uncountable proof gives more information (the number of irrationals is unctble)
but is nonconstructive.

3) Are there other proofs for either theorem?

Which proof do you prefer? Why? What is your criteria?


  1. Formally, you still need to show the existence of an irrational number between 0 and y-x. So for me, both proofs are the same.

    You however do not need to use any counting argument for this: observe u(n) = sqrt(2)^{-2n+1} is irrational for all n and -> 0. Then with your proof or your student's proof, take n such that u(n) < y-x and choose x+u(n).

  2. The sum of two irrational numbers is not necessarily irrational, right? e.g. sqrt{2} and (2 - sqrt{2}). So it is not clear to me that the second proof is complete.

  3. holf: given that x,y are irrational taking delta small and rational, clearly x+delta is irrational. So I begin with two irrationals. Hence I see the proofs as diffeent.

    Anon- not sure whose proof you are commenting on, mine or Holfs. In my proof we take irrational + ratiaonal which is clearly irrational.

    1. How can you just assume there is a small and rational delta between x and y? I'd want that proven to me otherwise the "proof" is just hand waving.

    2. Aaah I misread and believed you asked to find an irrational between to rationals, my bad... Then right, the proof is different (and mine is then wrong as the hypothesis I had in mind are not the right ones). So OK, the only missing thing is a formal definition of <<. Taking delta = 1/n does the trick as you say below.

  4. Bill: the student's proof about existence of irrational number between two irrationals is very nice! But the first one is incomplete: Why can you assume there is 0 < δ << y - x that is rational?

    1. AH- for one thing I should define << more carefully.
      We need to find a rational delta such that

      x+ delta < y

      OH- all I need is delta < y-x.

      Okay then. For all n, 1/n is rational and the sequence
      cvg to 0. Hence there is an n such that 1/n < y-x

      bill g.

  5. A proof is a proof ...

  6. Saying it another way, the quantity
    x + 1/ceil(1/(y-x))
    is no more than y, since
    1/ceil(1/(y-x)) <= 1/(1/(y-x)) = y-x,
    and since the rationals are closed under addition, the quantity is rational when x is.

    The closure of the rationals under addition implies that the sum of a rational and an irrational is irrational, so the same quantity is irrational when x is irrational.

    Using (x+y)/2 instead is just as easy for the rational x,y case, but not for irrational x,y.

  7. Knowing that the reciprocals of the integers are dense near zero is enough. I don't buy your proof of the irrational theorem, which (it seems to me) begins by assuming what it is supposed to prove.

    I think what you wanted to say is that there are uncountably many numbers between x and y (consider the natural linear surjection between [0,1] and [x,y]), only countably many of which are rational, ergo, uncountably many irrationals.

    Here's an alternative :-). Consider the midpoint z of (x,y). If z is irrational, we're done. Otherwise the midpoint of (x,z) must be irrational (as it is the average of a rational and an irrational).

  8. Yes- I meant to say `there are an uncountable number of REALS'
    and have made that correction.

    I like your midpoint/midpoint proof!

    1. Today I learned about Hilbert's 24. problem (https://en.wikipedia.org/wiki/Hilbert's_twenty-fourth_problem) and today I read Bill's question.
      Sounds a little bit related.

  9. What I like about both my proof and the student's is that they are constructive in the rather extreme sense of relying on algebraic properties of reals that can be demonstrated by classical compass and straightedge constructions (cf., Galois theory).

    There's an interesting difference between them, which may well be sharp. The student gives a fully constructive proof, beginning with the lengths [1,x,y]. I give a nonconstructive proof beginning with just [x,y]. Is it possible to give construct a number z from lengths x, y such that z will be irrational whenever x and y are? [I.e., without a unit reference]. I doubt it.

  10. I realize the remarks above may seem to contradict themselves. Let me clarify. I can construct the midpoint z of (x,y) with compass and straightedge. I can construct the midpoint w of (x,z) with compass and straightedge. I can argue that one of z or w must be irrational (given that x and y are), but I can't (constructively) tell you which.

    The student's proof doesn't have this nonconstructivity. She constructs the sequence 1/2, 1/3, etc., until she finds an n such that 1/n < y-x. Then she claims x + 1/n as a witness.