Can I use recursion/induction to show that N <= x < N+1 for x real

[yucheng]

Homework Statement:: Show that for every real number $x$ there is exactly one integer $N$ such that $N \leq x < N+1$. (This integer is called the integer part of $x$, and is sometimes denoted $N = \lfloor x\rfloor$.)
Relevant Equations:: N/A

I have tried reading the solution given here: https://taoanalysis.wordpress.com/2020/05/06/exercise-5-4-3/

Rules available to us:
trichotomy of order
x<y is defined
We know everything about integers and rational numbers i.e. their laws or algebra and order.
We also know that rational numbers are also real numbers, thus the laws of algebra of rationals also apply to reals.

My thoughts and approach:

1. Prove that such an interval exists.
2. Prove its uniqueness

However, I have some questions.

1. The last part of the solution: The important point is that we have M−1<x<M+2. Now we just have to hunt down x by using order trichotomy. Why not just use the order trichotomy from the start? That is to say, by recursion. We first separate into three cases, where x is an integer, x is not an integer. If x=N where N is an integer, N≤x≤N+1. If x is not an integer, we then have two cases: x is a negative real, or x is a positive real. If x is positive, we test the base case where N=1. If x>1, we proceed, otherwise, we can conclude that 0≤x<1. Suppose x>N is proven. We test the case for N+1. If x>N+1, we proceed. If x<N+1, then N≤x<N+1.

A posible problem might be: what if N≤x<N+2? This is only possible if x might possibly be in both intervals: N≤x<N+1 and N+1≤x<N+2 i.e. it reduces to a uniqueness problem. Now, if x<N+1, and x≥N+2, it implies that N+2<N+1, which is impossible, thus there is only a unique interval such that N≤x<N+1.

Is my reasoning correct? I know that it might be less elegant afterall!

 

[member 587159]

I'm sorry but I do not want to go through the trouble of reading the entire proof at the link, especially since the approach there seems too difficult:

Here is how I would approach it:

Suppose to the contrary that there are two integers $N\neq M$ with $K \leq x < K+1$ for $K \in \{N,M\}$. Then WLOG $N < M$. But then
$$N \leq x < N+1 \leq M \leq x < M+1$$
so $x < x$, which is impossible.

 

[Dr.AbeNikIanEdL]

Suppose x>N is proven. We test the case for N+1. If x>N+1, we proceed. If x<N+1, then N≤x<N+1.

But how do know that this procedure will ever terminate, i.e., that for every positive real $x$ you will find some integer $N$ so that $x<N+1$? You might just forever be stuck with “ok, $x>N+1$ so we proceed”. Or, as Prop. 4.4.1 in you link puts it “there is no such thing as a rational number larger than all natural numbers”, you still need the equivalent statement for real numbers.

I guess this is also a problem with @Math_QED ’s approach: it easily shows uniqueness, but at least from the model solution it is clear that you are supposed to show existence of integers with $N\leq x<N+1$ first...

 

[yucheng]

But how do know that this procedure will ever terminate, i.e., that for every positive real $x$ you will find some integer $N$ so that $x<N+1$? You might just forever be stuck with “ok, $x>N+1$ so we proceed”. Or, as Prop. 4.4.1 in you link puts it “there is no such thing as a rational number larger than all natural numbers”, you still need the equivalent statement for real numbers.

Actually, all real numbers are bounded... By the definition of reals, specifically formulated using limits, it is the limit of a Cauchy sequence, which is bounded... looks like it is an important premise that must not be omitted!

 

[Office_Shredder]

An alternate proof that every real number is bounded above by an integer. Let X be the set of reals that are bigger than every integer. If it's nonempty it's bounded from below by 1, so has an infimum, let's call it z. If z is an integer, it must be the largest integer (since every element in X is larger than all integers, and there's an element in X which is only slightly bigger than z), which is a contradiction. So z is not an integer. Then there must be some $\epsilon > 0$ such that there are no integers in the interval $(z-\epsilon,z]$, and hence that interval must be in X, contradicting that z is the infimum. So X must be empty.

I'm not sure if they've proven at this point in the thing you're reading that infimums exist for all sets that are bounded before, but I think this style of proof is actually far more typical once you get out of the prove results that are super obvious in practice phase.

 

[sysprog]

An alternate proof that every real number is bounded above by an integer.

Wouldn't that mean that there is an integer than which no other real number is higher?

Attempting to symbolize "every real number is bounded above by an integer":

$\forall x [(x \in \mathbb R) \Rightarrow (\exists \ y [(y \in \mathbb Z) \wedge (y \geq x )])]$

$-$ wouldn't diagonalization establish a surjection failure?

 

[Dr.AbeNikIanEdL]

Actually, all real numbers are bounded... By the definition of reals, specifically formulated using limits, it is the limit of a Cauchy sequence, which is bounded... looks like it is an important premise that must not be omitted!

Yes, I think arguing this needs to be part of a complete solution here.

Wouldn't that mean that there is an integer than which no other real number is higher?

No,

”for every real number x, there is an integer $N>x$”

and

”for every integer N, there is a real number $x>N$”

are not in contradiction...

 

[SSequence]

Wouldn't that mean that there is an integer than which no other real number is higher?

Attempting to symbolize "every real number is bounded above by an integer":

$\forall x [(x \in \mathbb R) \Rightarrow (\exists \ y [(y \in \mathbb Z) \wedge (y \geq x )])]$

The formalization looks OK to me. But the statement: "there is an integer than which no other real number is higher" seems different to me. Because that's saying that there exists a single integer which is greater-equal than every real in the set of real numbers. This is of course false.

I think that statement would be formalized a little differently. For example, potentially as something like:
$\exists z \in \mathbb Z : \forall r \in \mathbb R \, ( r \leq z )$
This is completely different from:
$\forall r \in \mathbb R \,\, \exists z \in \mathbb Z \, ( r \leq z )$

 

[sysprog]

The formalization looks OK to me. But the statement: "there is an integer than which no other real number is higher" seems different to me. Because that's saying that there exists a single integer which is greater-equal than every real in the set of real numbers. This is of course false.

I agree that the notion of an integer than which no other real number is higher is just as false as any other notion of a highest number in a non-finite positive set, but, considering that among the reals, for every positive integer there is another real number that is higher, doesn't that mean that if it's true that every real number is bounded above by an integer it's only vacuously so? What reason is there for in this context giving integers any special place of prominence?

I think that statement would be formalized a little differently. For example, potentially as something like:
$\exists z \in \mathbb Z : \forall r \in \mathbb R \, ( r \leq z ))$
This is completely different from:
$\forall r \in \mathbb R \,\, \exists z \in \mathbb Z \, ( r \leq z ))$

(It looks like you accidentally included an extra 'right paren' in each of those.)

With the universal quantifier being interpreted as the infinite conjunction, and the existential quantifier as the infinite disjunction (thus pre-supposing, respectively, that every term designates, and that something exists), isn't it true that

$(\exists z \in \mathbb Z : \forall r \in \mathbb R \, ( r \leq z )) \Leftrightarrow (\forall r \in \mathbb R \,\, \exists z \in \mathbb Z \, ( r \leq z ))$

even if, as you say, the two expressions on the two sides of the $\Leftrightarrow$ are "completely different from" each other?

It seems to me that resolving this exceeds the power of first-order logic, and for rigor requires resorting to a second-order logic $-$ while the LHS seems clearly false, the RHS to me seems only vacuously true, and also (ab)usable in first-order logic to 'prove' the LHS, which itself can be used to prove the RHS.

 

[sysprog]

We also know that rational numbers are also real numbers, thus the laws of algebra of rationals also apply to reals.

It's not clear to me what you mean by this $-$ it looks like a non sequitur to me $-$ and, as you presumably already know, most real numbers are not rational, and most irrational numbers are transcendental, not algebraic.

 

[SSequence]

(It looks like you accidentally included an extra 'right paren' in each of those.)

You are right, I have corrected the typo.

... isn't it true that

$(\exists z \in \mathbb Z : \forall r \in \mathbb R \, ( r \leq z )) \Leftrightarrow (\forall r \in \mathbb R \,\, \exists z \in \mathbb Z \, ( r \leq z ))$

even if, as you say, the two expressions on the two sides of the $\Leftrightarrow$ are "completely different from" each other?

It seems to me that resolving this exceeds the power of first-order logic, and for rigor requires resorting to a second-order logic $-$ while the LHS seems clearly false, the RHS to me seems only vacuously true, and also (ab)usable in first-order logic to 'prove' the LHS, which itself can be used to prove the RHS.

I don't quite understand what you are saying. I am not particularly knowledgeable, but here are few things I know based on experience.

The statement:
$(\exists z \in \mathbb Z : \forall r \in \mathbb R \, ( r \leq z ))$
is false. Because it says that there exists an integer that is greater than all real numbers.

On the other hand, the statement:
$(\forall r \in \mathbb R \,\, \exists z \in \mathbb Z \, ( r \leq z ))$
is true. For example, for r=3.5 we can choose z=4, for r=4.7 we can choose z=5 etc.

Therefore the iff proposition that you wrote:
$(\exists z \in \mathbb Z : \forall r \in \mathbb R \, ( r \leq z )) \Leftrightarrow (\forall r \in \mathbb R \,\, \exists z \in \mathbb Z \, ( r \leq z ))$
is also false since the sentence on the left-hand-side is false and the sentence on right-hand-side is true, which makes the proposition false.

I couldn't understand what you are saying in the last paragraph. These statements would both be expressible and proveably true/false in many sufficiently powerful (first-order) axiomatic systems.

I agree that the notion of an integer than which no other real number is higher is just as false as any other notion of a highest number in a non-finite positive set, but, considering that among the reals, for every positive integer there is another real number that is higher, doesn't that mean that if it's true that every real number is bounded above by an integer it's only vacuously so? What reason is there for in this context giving integers any special place of prominence?

I can't fully understand what you are trying to say. Perhaps you are trying to say that since we know
$(\forall z \in \mathbb Z \,\, \exists r \in \mathbb R \, ( z \leq r ))$
to be true, the following must be vacuously true:
$(\forall r \in \mathbb R \,\, \exists z \in \mathbb Z \, ( r \leq z ))$

It isn't clear to me how the second statement follows directly from the first one. Perhaps you were trying to say something else.But I get your basic point. A statement such as: $(\forall r \in \mathbb R \,\, \exists z \in \mathbb Z \, ( r \leq z ))$ is almost "obviously" true. So there is a question of why do we go to lengths to prove it. I suppose one reason is that when we think of such a statement as "obvious" we probably have decimal representation in our mind. However, the axiomatic presentations (of real numbers) usually don't start from decimal representations. So, in that case, one would have to prove even the seemingly obvious statements.