How do you prove the greatest integer theorem?

If x is an arbitrary real number, prove that there is exactly one integer n which satisfies the inequalities n<=x<n+1. This n is called the greatest integer in x and is denoted by [x].


I am trying to prove this by first showing that the set of all integers smaller than x has a maximum value (and this maximum value is n). But I don't know how to prove this.

Can this be considered something that is 'self evident' - that if a set of integers is bounded above by a REAL number (as opposed to an integer), then it has a maximum and that maximum is an integer?

It seems 'obvious' so I'm not sure if there's a way to prove it as I am entirely new to proofs. I'm teaching myself so I have no 'teacher' to double check with.

 

Log in or Sign up to hide all adverts.

Wow, this is very wierd. When I look at the "Reply" screen I see something completely different from the above. The Reply screen has the correct inequalities: n<=x<=n+1.

Anyway, you are asked to do a uniqueness proof here. A standard way to prove uniqueness is to assume nonuniqueness and then prove uniqueness by contradiction. So assume that there are two distinct numbers m and n that satisfy the above inequalities, and then show that m and n must be equal.

 

Log in or Sign up to hide all adverts.

That's because HTML code is on for this board and the "greater than" and "less than" symbols are used to denote HTML tags. The system must be mistaking the second symbol as the start of a tag.

 

Log in or Sign up to hide all adverts.

Let S be the set of integers that is less than or equal to x. Show this is non empty (you didn't mention this part!). It then has a least upper bound, say y. Try to find an integer m in S where m+1 is not in S (consider y-1/2 is not an upper bound of S, so...). Conclude m is an upper bound for S, and hence m is the least upper bound.

The text that shows up in the reply screen isn't correct. One of those needs to be a strict inequality if you want uniqueness and x is an integer...

showing existance is the hard part, uniqueness is essentially 'free', as distinct integers differ by at least 1.

 

The bug carried across into your reply. The display software must interpret the less than sign that preceeds the n+1 as the start of a vB code. The code ends with the close square bracket that follows the x. The stuff between the two symbols is meaningless vB code so the interpreter kindly discards the whole shebang.

Hypothesis test: here's some meaningless junk between a less than sign and a close square bracket:<meaningless junk]
Yep. that works (or it doesn't, depending on the meaning of the word "works").
Just put a space after the less than sign: n <= x < n+1

Anyhow, back to the OP: This is an outline of a proof. Unproven assertions lurk within! (They aren't truly lurking. I have explicitly identified them.)

Existence: Denote the subset S1 of the integers that are less than or equal to some arbitrary real number x as S: S={n|n<=x}. S is not empty (assertion #1) and is a well-ordered set with respect to >= (assertion #2). By the well-ordering principle, there exists a least element of S with respect to >=. Denote this as max(S2) or [ x ].

Uniqueness: S is countable (assertion #3) and thus the elements of S can be indexed by an integer. Denote the ith element of S as S_i. Assume that there exists distinct integers i, j such that S_i=S_j. This means there exist two distinct integers that are equal to each other, which is a contradiction. Thus [ x ] is unique.

 

Hmm.. how do I show that S is not empty? If S is a subset of the set of integers (the set of integers is not bounded above) and S is only bounded above, doesn't that imply that S is not empty?

I think for assertion 3, 'countable' means for every n in S, there is an n +1 in S - provided (n+1) < x? Or is that what assertion 2 means?

Sorry I'm new to proofs.. The author of the book I'm using (Tom Apostol) doesn't prove the well ordering principle until a later section (and so I'm inferring I'm not to use it here). Then again the difficulty level of these proofs, provided the meager background he gives in the chapters, is obscene.

"Assume that there exists distinct integers i, j such that S_i=S_j."

Do you mean S_i and S_j are distinct solutions for n?

 

Here is what I came up with as a proof for the above problem. Tell me if it's lacking in anything.

First, to prove that (1) there are integers m such that m <= x for any arbitrary x:

Let Q be the set of integers. For any arbitrary real x there exists an n in Q such that n >= x. If this was not true then the set of integers would be bounded above by x, which leads to contradiction. (the fact that the set of integers is not bounded is proved elsewhere).

-Q is the set of negatives of all elements in Q. -Q is similarly not bound. x in Q corresponds to -x in the set -Q. By the same method, we can say there exists an integer f in -Q such that f >= -x since -Q is not bound.

From f >= -x, we can see that -f =< x and so if m = -f then (1) has been proved.


Now let S be the set of integers bounded above by an arbitrary real number x. Since S has a maximum (this has to be proven..), then that maximum is n. We can prove that S has at most, one maximum.

If B and C are maximums of S, then B >= C and C >= B and so B = C.

There is thus only one such integer n in S (does this prove the uniqueness of n, as the problem requires?).

(n + 1) is not in S since n is the maximum of S. By the definition of the set of all integers, n + 1 is also an integer. Since n is the maximum of hte set of integers bounded above by x, x < n + 1

Also by the definition of an upper bound n <= x and so:

n <= x < n + 1.

-----

I'm sure I made a few jumps so please point them out..

 

I have to prove existence AND uniqueness.

 

Can you actually prove this?

You can prove existence by modifying slightly the proof that the positive integers are not bounded above (this is essentially what I suggested before) and you avoid having to talk about a maximum. You've used the archimedean property to show that S is non-empty. Since it's also bounded above, let y be it's least upper bound. y-1 is not an upper bound, so there is an integer n in S, n>y-1, so n+1>y and n+1 is not in S, therefore n+1>x as well.

Proving you have a maximum is essentially equivalent to proving well ordering.

I think the only way to prove uniquenessat this point is to use some results Apostol mentions but doesn't prove (or wait until well ordering), namely the difference of two integers is an integer. If you have n and m satisfying the property, and n<=m you end up with 0<=m-n<1, which means m-n=0 (you'd want to show 1 is the smallest positive integer though, easy enough as the real numbers >=1 form an inductive set).

 

Hello Schmoe (sorry for being late)

You are right. It can be shown that S has a greatest member in this way:

- S is bounded from above.
- let sup S = n (the existence of n is guaranteed by axiom) so that x <= n for every x in S.
- if S is a set of integers then [n] is an upper bound of S too. Say there is some x in S such that x>[n]. Then x >= n + 1. This leads to contradiction since n is an upper bound of S and thus [n] must be an upper bound of S.

Now since n was already declared the supremum of S, [n] cannot be less than or greater than n. Therefore [n] = n and we prove that the supremum n of S is an integer. Since n is an integer, n is a member of S and max S = n.

Therefore S has a maximum member n.

The well ordering principle can't be applied here since S need not contain only positive integers (it is a subset of the set of reals). It only applies to sets of positive integers.

 

Would you mind helping me with this one anyway?

If x and y are arbitrary real numbers, x <y, prove that there exists at least one irrational number z satisfying x < z < y, and hence infinitely many.

I can prove that there is at least one real z inbetween x and y but I have no clue how to show this for rationals.. hmm. Tell me if this looks good:

---

(y - x) > 0

We must prove that there exists a positive rational number denoted a/b such that

(a/b)(y - x) < (y - x)

a/b exists since 0 < a/b < 1. (Dividing both sides of the inequality by y-x, a positive quantity).
(I think here I might have to show that the interval (0, 1) is not empty; can this be done by simply pointing out that 1/2 is in the interval or is there a more 'elegant' way?

Maybe something like this will work:

a < b
n > 0

a < b + n
0 < a/(b + n) < 1

This will also prove that there are infinitely many rationals in the interval since the set of positive reals is unbounded, so that our choices of n are unlimited.
)

Therefore given 0 < a/b < 1

0 < (a/b)(y - x) < (y - x)
x < (a/b)(y - x) + x < (y - x) + x



Hence:
z = (a/b)(y - x) + x, where 0 < a/b < 1.



Look good?

How would I show that there are "infinitely many"? It would entail showing that there are infinitely many rationals in the interval (0, 1) but I have no clue how to go about that.

 

Oh, and anyone have any clue how I would go about proving the above theorem for irrational numbers?

 

The problem of a maximum came up as you were planning to define [n] as this maximum. You hadn't defined [n] before you had a maximum, so this wouldn't work.

I'm sure you can see how to convert a set of integers bounded above by x to one that the well ordering principle applies to.

 

Do you mean 'define' as in the traditional if x > 0 then [x] = x and if x < 0 then [x] = -x?

If so, I'll add it in.

Well I thought about that before I posted but I couldn't figure it out..

If you had S = {-3, -4, -5}, I think you could add some n (such as 6) to every element of S so that all elements become positive (call this set O). And then use the modified well ordering principle to find the largest member of O.

And then max S = max O - n.

But to find the appropriate n to do this requires knowing before hand what the smallest integer in S is, or at least proving that S has a smallest element so that the addition produces a set O of positive integers only. That brings me back to square one though because if I can prove the existence of a minimum then I wouldn't need this to find the maximum..

Please Register or Log in to view the hidden image!

 

Proving a set is nonempty by exhibiting an element in it is perfectly fine.

There's no reason to bother with this a/b stuff at this point though, just use a/b=1/2. Proceeding as you did, you've then shown you have a real number z where x < z < y. To show infinitely many, apply this again to get a real number w where x < w < z, repeat.


The z you find above is a rational multpile of x and y, so if x and y are rational so is z. See if you can find r1 and r2 where x < r1 < r2 < y and r1, r2 are rational. Then use the above to find a rational between r1 and r2, etc. To find r1 and r2 try looking at 1/(y-x) and use the Archimedean principle...Alternately you can show that any interval (0,a) where a>0 has infinitely many rationals in it. Take a suitable small enough a and shift this interval by a rational so that it lies in between x and y (this will still involve showing you have one rational between x and y).

Have you proven the existence of an irrational number yet? If not then you have no hope of proving infinitely many irrationals. If so, shift it by a rational to get two irrationals in between x and y, then apply the original theorem to find a z in between these two irrationals (the theorem will spit out an irrational in this case), etc.

edit-bollocks, the inequality parsing mucked things up

 

we were using [x] as what we hoped to call the greatest integer function, no?

S is all integers less than x. You found an integer upper bound n. Consider -S+n+1

 

Oooh. I'm sorry. I gave the definition of absolute value because the brackets resembled..

I mean for [x] to be the least integer function.

Wait. Are you saying I'm using what I'm trying to prove in its own proof?

Oops. Scratch that.

Hmm.. If I can't use [x] in its own proof then I can't use this way anymore to find an integer upper bound n..

The existence of a supremum for S is guaranteed but I can't figure out how to show that this supremum is itself an element of S.

 

Bah. Up to this point the only thing the book has said on irrationals is that they are real numbers not included in the set of rationals..
Unless I'm going crazy, that is in fact the only statement Apostol makes on the existence of irrationals for the rest of the chapter. I'll think a bit and get back to you if I get any ideas on how to go about that.

 

I think I've got it. Here it is in theorem form:

Theorem:
If S is the set of all integers bounded above by a real x, S is not empty and S has a maximum n.

Proof:
If S is empty then x is a lower bound of the set of all integers Q. We shall show that this leads to contradiction. The existence of an infimum f of S is guaranteed. There exists a g in Q such that g-1 is NOT an element of Q; if this were false then for every g in Q, g-1 would be an element of Q and Q would not be bounded from below. Hence such an integer g exists and g-1 < x. But this means that g-1 is an integer not included in the set of integers. The contradiction implies that g-1 is an element of Q and as stated before, Q is not bounded below. Since S is a subset of Q with S bounded above only, S is not empty (ie. g - 1 is an element of S)


Now for some integer a in set S (defined above), sup S - a < 1

If sup S - a >= 1, then sup S - 1 >= a; this leads to a conradiction since sup S is the supremum of S and thus such an a must exist in set S.

Assertion: max S = a.

If this were not true, then an integer m = a + 1 is an element of S, but as proved previously:

sup S - a < 1
sup S < 1 + a

Hence m = 1 + a is not an element of S and a is the maximum of S.

 

"least integer function" usually means rounding up, e.g. the least integer greater than 2.3 is 3.

"Greatest integer function" means rounding down and is what the n you were trying to find at the start with n <= x < n+1 was, and is often denoted [x]=n. (though this isn't universal).

Compare with "least upper bound" (aka supremum) and "greatest lower bound" (aka infimum)


To show an irrational exists, think pythagoras.

Why does this integer m have to be a+1? Why can't it be a+1/2 say? You're using the assumption that the difference between any two integers is 1 or more, but this isn't something you've proven. This is what I mentioned before, the difference of two integers is an integer (a detail left out by Apostol), and there is a least positive integer, namely 1.