Proving that an Integer lies between x and y using Set Theory

[Hall]

Homework Statement

Show that there exits an integer between x and y if $x, y \in R$ and $y-x \gt 1$.

Relevant Equations

Without Archimedean Property.

$y-x \gt 1 \implies y \gt 1+x$

Consider the set $S$ which is bounded by an integer $m$, $S= \{x+n : n\in N and x+n \lt m\}$.

Let's say $Max {S} = x+n_0$, then we have
$$
x+n_0 \leq m \leq x+(n_0 +1)$$
We have,
$$
x +n_0 \leq m \leq (x+1) +n_0 \lt y+ n_0 $$
Thus,
$x+n_0 \leq m \lt y +n_0$
$$
x \leq m-n_0 \lt y$$
Since, m and n were integers, we have an integer between x and y.

As I didn't use Archimedean property, I'm a little doubtful if I'm correct.

 

[nuuskur]

The argument is correct. For sufficiently large $m$, the set $S$ is nonempty and what you say follows. Obviously, $m\leqslant x+n_0+1$ has to be true, because ..?

Use \max to obtain $\max S$ instead. Also $S := \left \{x+n \mid n\in\mathbb N \ \text{and}\ x+n<m \right \}$. When you press the Reply button to my post, you see the syntax I use.

 

[Delta2]

Hmm, but the relative axiom we use here (one of the axioms on the set of real numbers) is that every bounded non empty set has supremum and infimum, not necessarily maximum and minimum.. How do we prove that the supremum of S is the maximum of S?

 

[nuuskur]

The Archimedean property is invoked for the set $S$. More specifically, given $x+1$, there exists $m\in\mathbb N$ such that $x+1<m$. Hence, $S\neq\emptyset$.

The completeness axiom is not necessary, because $S$ is finite.

 

[Delta2]

The completeness axiom is not necessary, because S is finite.

How do we know that S is finite?

 

[Hall]

How do we know that S is finite?

There are finite number of integers between any two real numbers, in our case the real numbers are $x$ and $m$. Integers are not dense.

 

[Hall]

The argument is correct. For sufficiently large $m$, the set $S$ is nonempty and what you say follows. Obviously, $m\leqslant x+n_0+1$ has to be true, because ..?

Use \max to obtain $\max S$ instead. Also $S := \left \{x+n \mid n\in\mathbb N \ \text{and}\ x+n<m \right \}$. When you press the Reply button to my post, you see the syntax I use.

Yes, I can see the subtle point that choice of $m$ should be greater than $x$, else the proof collapses down.

 

[nuuskur]

How do we know that S is finite?

If $x+1<m$, then there are finitely many $n$ for which $x+n<m$.

Yes, I can see the subtle point that choice of $m$ should be greater than $x$, else the proof collapses down.

My question is why $x+n_0+1 \geqslant m$ is necessarily true. How did we pick $n_0$?

 

[PeroK]

It seems to me that the answer depends on what we assume we already know about integers and real numbers.

E.g we could use the density of the rationals to explicity construct an integer between $x$ and $y$.

Can we assume $\mathbb Q$ is dense in $\mathbb R$?

 

[nuuskur]

If $x+1<m$, then there are finitely many $n$ for which $x+n<m$.

Suffices to apply the Archimedean property again to conclude this. It is required to accept that there are finitely many integers between any two integers, which is reasonable, I think.

Alternatively, one might assume $S$ is countable, but that means it's unbounded (this requires Archimedean property) and it leads to contradiction using the ordering-related axioms in $\mathbb R$.

My preference would be to denote $S := \{n\in\mathbb N \mid x+n <m\}$ instead. For aesthetical reasons and also it's clear that $S$ can be at most countable.

Some comments regarding assumptions.

1. Completeness implies density. Density implies Archimedean property (AP).
2. AP and well-orderedness of $\mathbb N$ imply density of $\mathbb Q$ in $\mathbb R$.
3. AP is strictly weaker than completeness.

AP is sufficient to solve this problem.

 

[Hall]

My question is why x+n0+1⩾m is necessarily true. How did we pick n0?

That’s how we designed the things. We said, $x +n_0$ is the last candidate (in the series $x+n$, where $n$ is a natural number) which is less than $m$, that surely implies the next candidate will be greater than $m$.

 

[Hall]

It seems to me that the answer depends on what we assume we already know about integers and real numbers.

E.g we could use the density of the rationals to explicity construct an integer between $x$ and $y$.

Can we assume $\mathbb Q$ is dense in $\mathbb R$?

Actually, I’m using this result to prove the density of $\mathbb Q$.

I’m finding it a little tough to digest that in Real Analysis, we accept a complicated thing like Completeness axiom without a proof, yet doesn’t accept such an evident thing as the existence of an integer between two numbers which are off by more than 1.

 

[PeroK]

Actually, I’m using this result to prove the density of $\mathbb Q$.

I’m finding it a little tough to digest that in Real Analysis, we accept a complicated thing like Completeness axiom without a proof, yet doesn’t accept such an evident thing as the existence of an integer between two numbers which are off by more than 1.

Your first problem is to define what you mean by a Real Number. You can assume something intuitive like the number line. Or, you have a hard task to define the set of real numbers and proving their properties.

That's why my response was that a question like this all depends on your starting point.

For example, if we take the Real numbers to be the set of Cauchy sequences of rationals then the density of $\mathbb Q$ in $\mathbb R$ follows immediately.

 

[Hall]

Your first problem is to define what you mean by a Real Number. You can assume something intuitive like the number line. Or, you have a hard task to define the set of real numbers and proving their properties.

That's why my response was that a question like this all depends on your starting point.

For example, if we take the Real numbers to be the set of Cauchy sequences of rationals then the density of $\mathbb Q$ in $\mathbb R$ follows immediately.

Yes, you got a valid point, the moment I said $y$ and $x$ were reals, “a snake lurked in” (I don’t if that expression even mean anything here).

 

[nuuskur]

accept a complicated thing like Completeness axiom without a proof, yet doesn’t accept such an evident thing as the existence of an integer between two numbers which are off by more than 1.

Intuitively something might be evident. But it's not an axiom. Hence it needs to be proved using the axioms. In principle, you want your proof to assume as little as possible. In this case, assuming AP is enough. You also have to be careful of running in circles, i.e, if you're not sure whether you are using any consequence of the thing you are trying to prove, then don't use it.

In a complete ordered field like $\mathbb R$, completeness is an axiom and needs not be proved.

 

[PeroK]

Intuitively something might be evident. But it's not an axiom. Hence it needs to be proved using the axioms. In principle, you want your proof to assume as little as possible. In this case, assuming AP is enough. You also have to be careful of running in circles, i.e, if you're not sure whether you are using any consequence of the thing you are trying to prove, then don't use it.

In a complete ordered field like $\mathbb R$, completeness is an axiom and needs not be proved.

Are you sure you need Completeness? It's true for the rationals and other dense subsets of $\mathbb R$.