Does there exist a function f : R → R such that for every two distinct real numbers a and b , f ( a ) and f ( b ) differ by at least 1 ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Very nice!
I didn’t know about Cantor, thanks!
Could you explain further why "a 1-1 correspondence between the real numbers and (a subset of) the integers" but not "a 1-1 correspondence between the real numbers and the integers"? Thanks!
Log in to reply
Since every value in the range of f must differ by AT LEAST 1, after taking the floor of each value, it is possible to skip some integer values.
Log in to reply
You have to prove that it MUST skip at least one integer values to make this hold. In fact, why can't we set f values distributed on the one-dimensional grid of integers, and for every different real number a , we could always find an integer that hasn't been occupied yet?
Log in to reply
@Manqing Ma – For your first question, any set is a subset of itself (though not a proper subset of itself), so even if no integer values are skipped it can still be considered a "subset." This is mostly just a language problem and does not affect the proof itself.
For your second question, the set of real numbers is uncountably infinite, which means it is not possible to assign each real number a distinct natural number. In other words, it is impossible to "list" all real numbers. There are proofs for this fact, of course.
Log in to reply
@Zain Majumder – Thanks for your further explanation. I get it now. I mistook real number for rational number.
It seems interesting that this extends to any fixed separation interval>0, not just 1.
Since (by the condition of the problem) all values of f(x) differ by at least one, we see that h(x) takes a different integer value for every real number.
I have an issue with this statement. It could be that the function f alternates between just two values that are at least one apart. You haven't proven why the functions f, and/or h are mapping each real value to a different integer. The function h doesn't necessarily "set up a 1-1 correspondence between the real numbers and a (possibly improper) subset of the integers." Since I believe the statement is correct, I don't see a way to define an f such that for any pair of reals we get values that differ by one, but that is not a proof that such an f doesn't exist. I think you need to use some sort of Cantor's diagonalization in the proof directly, rather than make any assumptions about f or h being 1-1.
This question seems a bit deeper than I originally thought, as I had considered a proof similar to the one you gave. Also most of the answers to this question incorrectly assume that f is continuous, and some assume that f is differentiable which were not assumptions stated in the problem.
Log in to reply
Hi David,
f cannot oscillate as you suggest and still fulfil the conditions of the problem.
If f(x) alternates between two integers (no matter how far apart!) then for some real numbers a and b we will have f(a) = f(b). But the conditions of the problem insist that f(a) and f(b) differ by at least one, so they certainly cannot be equal!
I hope this helps.
The function f takes only one value on the intervals [k, k+1) for all integers k, therefore, the set of its values is at most countable.
Can you give a proof of why the function takes exactly one value on the interval [k, k+1)?
Log in to reply
I also don't see why.
Log in to reply
He means the range of f not the domain , if it took on 2 different values, say 3.2 and 3.4, we would have a contradiction
It happens to be true, but it certainly needs to be proven and not merely asserted.
I think he means "at most one value" and the argument works anyway.
If such function f exist, then a function h=f(g(x)) is also solution, where g:R->R is bijection. If g(x) = x - 0.5, then h has two values on every interval [k, k+1). So property you described does not have to hold.
Log in to reply
The values of a function are in the range, and shifting the domain does nothing to the range.
I wonder if such function existed when its domain is a finite interval. Start with (-1,1) let the decimal point be the symmetry axis for example0.1→1 0.01→10 0.89→98 -0.4→-4 Then each real number in interval (-1,1) has an integer "partner". For interval (-m,n),let x ∈(-m,n) y=[x-(m-n)/2]/[(m+n)/2] y lands in (-1,1) Then x can have an integer "partner". (Bur when it comes to R,we can not find m and n.) I am not sure whether this is correct or not. (´;ω;`)
Log in to reply
We could just use the arctan function to make the domain a finite interval, so there is a problem with your argument.
Specifically, which integer value does your function assign to the infinite decimals? E.g. what value is assigned to 1/3, or 1/e, or any irrational number in the interval?
Suppose that such a function f ( x ) exists. f must be one-to-one (injective), because if it were not, then there would be two distinct values in its domain that output to the same element in its range, contradicting the condition that ∣ f ( a ) − f ( b ) ∣ ⩾ 1 . We can therefore assume that f is always increasing, although the same argument will hold if it is always decreasing.
Let's examine two distinct real numbers m and n > m . We see that f ( m ) differs from f ( n ) by some constant C 1 that is greater than or equal to 1. We also see that f ( m ) differs from f ( 2 m + n ) by some constant C 2 that is greater than or equal to 1. And we also see that f ( 2 m + n ) differs from f ( m + 4 n − m ) by some constant C 3 that is greater than or equal to 1. And we also see that f ( m + 4 n − m ) differs from f ( m + 8 n − m ) by some constant C 4 that is greater than or equal to 1. In fact, we can continue defining such constants ad infinitum . Therefore, the absolute difference between f ( m ) and f ( n ) must be greater than C 1 + C 2 + C 3 + ⋯ ⩾ 1 + 1 + 1 + ⋯ . However, this series diverges, meaning that the difference in the distinct outputs of the function must be infinitely great. Therefore, reductio ad absurdum, the function cannot exist.
Why does the fact that f is injective imply it is increasing or decreasing? You have merely shown such an f cannot be continuous.
Log in to reply
Sorry, you are correct about that. I believe it is my unclear usage of "increasing;" I mean that for all a > b , we find that f ( a ) > f ( b ) .
Log in to reply
Then you should say strictly increasing. But this still doesn‘t follow from injectivity.
If f has the property in question, so does -f. That makes me very suspicious of your claim that f "must be increasing".
Please let me know if my reasoning is correct:
I consider the case where a and b can be made arbitrarily close, while in keeping with the conditions in the question, f(b) - f(a) ≥ 1. As b approaches a, f(b) - f(a) is still greater than or equals to 1, which means that f(b) - f(a) / (b-a) will go to infinity as b approaches a. Hence, the graph of such a function will be a vertical line, in which case, it is no longer a function.
Therefore, such a function cannot possibly exist.
I am not convinced why your argument is rigorous.
Indeed the limit of this ratio when a->b is the derivative of f in b. It then shows that the derivative of the function f is infinite in every point b... which is not acceptable...
Log in to reply
Why would this not be acceptable? Just imagine this other function g(x) = 1 iff x is rational, 0 otherwise. This function is a proper function, but it is not derivable in any x. You seem to imply that f(x) has to be monotonic, which I think is not required by the question.
I don't understand your argument. Are you assuming that f is differentiable everywhere?
Log in to reply
I suppose I have inadvertently assumed the function to be differentiable (which I now realise that I should not) everywhere in my argument, and in that case, the derivative of the function will be infinite at "a" and since "a" can be any arbitrary real number, the derivative will be infinite everywhere.
We know the real numbers are uncountably infinite. By contradiction, assume such an f did exist. Then it should be obvious you can form a function g that takes the range of f to the natural numbers. Therefore the function h=gf takes the real numbers to the natural numbers, thus contradicting our claims of R being an uncountable set. See Cantor's diagnolisation proof to see that R is uncountable, though this should be somewhat intuitive.
I realise it may not be obvious you that you can form a function g that takes the range of f to the natural numbers. Let me show how. Since by assumption the range of f is formed by unique numbers, all at least 1 unit apart, we can order these numbers. Now since the range of f can be ordered we can order the domain of f (the real numbers) by saying: a is ordered below b iff f(a) is ordered below f(b). Thus we have ordered the real numbers, contradicting Cantor
As it is the function of real numbers to real numbers there may be the situation such that both "a" and "b" will be the same number and then it will not satisfy the condition.
This is wrong. The question already states that a and b are distinct.
Since the set of real numbers is uncountably infinite, no function can map it the merely countable infinite set of integers.
But we are not looking for a function that is mapping it to the integers, are we?
When a > b , let me set a − b = d x and f ( a ) − f ( b ) = d y . Then d y ≥ d x + 1 , d x d y ≥ 1 + d x 1 .
But since d x goes to 0 , 1 + d x 1 goes to infinity, which makes explicit function f ( x ) impossible.
Assuming this function exists, that means you could map every real number in R Where |R| = א to a group that is countable, as in every real number having a unique whole number, where the power of the whole numbers Z is א0 hence because א > א0 there is no function that maps R to Z injectjvly and fully.
Can you explain how to get this map?
Problem Loading...
Note Loading...
Set Loading...
Relevant wiki: Cardinality
Here is a proof by contradiction that no function such as f ( x ) exists.
First assume that f ( x ) exists and define another function h : R → Z ∣ h ( x ) = ⌊ f ( x ) ⌋
Since (by the condition of the problem) all values of f(x) differ by at least one, we see that h(x) takes a different integer value for every real number.
The function h ( x ) thus sets up a 1-1 correspondence between the real numbers and a (possibly improper) subset of the integers. But we know (since Cantor ) that such a correspondence is impossible.
And so our starting assumption - that f ( x ) exists - must be incorrect.