Math 115. Proof of the Existence of the Greatest-Integer Function

(revised August 28, to reflect the proof given in class)

This handout will prove the following lemma mentioned in class:

Lemma. For each real number x there is a unique integer n such that

n ≤ x < n + 1 .

Proof. We first show existence of n. This part will rely on the following axioms.

Archimedean Property of the Real Numbers. For each x ∈ ℝ there is an integer n with n > x.

Well-Ordering Property of the Natural Numbers. Every nonempty subset of ℕ has a smallest element.

Let x be any real number. By the Archimedean Property, there is an m ∈ ℤ with m > x. Let

S = {k ∈ ℕ : m − k ≤ x} .

Note that 0 ∉ S because m > x. Also, S is a subset of ℕ by construction.

By the archimedean property applied to the real number m−x, there is an integer j > m−x. Since m > x, j > m−x > 0 , so j ∈ ℕ. Also j > m−x implies m−j < x, so j ∈ S. In particular, S ≠ ∅. Since (by construction) S is a subset of ℕ, we may apply the well-ordering property to S. Therefore S has a smallest element k. Since k ∈ S, m − k ≤ x.

Since k is the smallest element of S, we have k − 1 ∉ S. This can happen only if k − 1 ∉ ℕ or m − (k − 1) > x. But k − 1 ∉ ℕ would imply k < 1 , so k = 0 , contradicting the fact that 0 ∉ S. Therefore m − k + 1 > x.

Thus, letting n = m − k, we have

n ≤ x < n + 1 ,

as was to be shown.

Now consider the question of uniqueness. Suppose n, n′ are integers such that n ≤ x < n + 1 and n′ ≤ x < n′ + 1 . Then

n ≤ x < n + 1  and
−n′ − 1 < −x ≤ −n′ ,

where the second line comes from negating all terms of n′ ≤ x < n′ + 1 .

Adding these two double-inequalities gives

n − n′ − 1 < 0 < n − n′ + 1 ,

so adding n′ − n to all three parts gives −1 < n′ − n < 1 . Since n′ − n is an integer in the range (−1, 1) , it must be zero. This gives n′ = n, as was to be shown. □