Very discontinuous function

Algebra Level 2

Does there exist a function f : R R f: \mathbb{R} \rightarrow \mathbb{R} such that for every two distinct real numbers a a and b , b, f ( a ) f(a) and f ( b ) f(b) differ by at least 1 ? 1?

Yes No

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.

10 solutions

Peter Macgregor
Jan 8, 2018

Relevant wiki: Cardinality

Here is a proof by contradiction that no function such as f ( x ) f(x) exists.

First assume that f ( x ) f(x) exists and define another function h : R Z h ( x ) = f ( x ) h:\mathbb{R} \rightarrow \mathbb{Z} | \space h(x)=\lfloor f(x) \rfloor

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 ) 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 ) f(x) exists - must be incorrect.

Very nice!

Mustaf Ahmed - 3 years, 5 months ago

Log in to reply

I didn't exactly understand it😟😟

Keshira Jones - 3 years, 5 months ago

I didn’t know about Cantor, thanks!

Tomáš Volejník - 3 years, 5 months ago

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!

Manqing Ma - 3 years, 5 months ago

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.

Zain Majumder - 3 years, 5 months ago

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 f values distributed on the one-dimensional grid of integers, and for every different real number a a , we could always find an integer that hasn't been occupied yet?

Manqing Ma - 3 years, 5 months ago

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.

Zain Majumder - 3 years, 5 months ago

Log in to reply

@Zain Majumder Thanks for your further explanation. I get it now. I mistook real number for rational number.

Manqing Ma - 3 years, 5 months ago

It seems interesting that this extends to any fixed separation interval>0, not just 1.

Michael Erickson - 3 years, 5 months ago

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.

David Chelberg - 3 years, 4 months ago

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.

Peter Macgregor - 3 years ago
George Ivanchyk
Dec 30, 2017

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)?

Agnishom Chattopadhyay - 3 years, 5 months ago

Log in to reply

I also don't see why.

Paweł Samoraj - 3 years, 5 months ago

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

Andrew Morton - 3 years, 4 months ago

It happens to be true, but it certainly needs to be proven and not merely asserted.

Richard Desper - 3 years, 5 months ago

I think he means "at most one value" and the argument works anyway.

A Former Brilliant Member - 3 years, 5 months ago

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.

Paweł Samoraj - 3 years, 5 months ago

Log in to reply

The values of a function are in the range, and shifting the domain does nothing to the range.

Brian Moehring - 3 years, 5 months ago

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. (´;ω;`)

Plantina Kirkland - 3 years, 4 months ago

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?

Brian Moehring - 3 years, 4 months ago
Gary Zhang
Jan 8, 2018

Suppose that such a function f ( x ) f(x) exists. f 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 |f(a) - f(b)|\geqslant 1 . We can therefore assume that f f is always increasing, although the same argument will hold if it is always decreasing.

Let's examine two distinct real numbers m m and n > m n > m . We see that f ( m ) f(m) differs from f ( n ) f(n) by some constant C 1 C_1 that is greater than or equal to 1. We also see that f ( m ) f(m) differs from f ( m + n 2 ) f\left(\frac{m + n}{2}\right) by some constant C 2 C_2 that is greater than or equal to 1. And we also see that f ( m + n 2 ) f\left(\frac{m + n}{2}\right) differs from f ( m + n m 4 ) f\left(m + \frac{n - m}{4}\right) by some constant C 3 C_3 that is greater than or equal to 1. And we also see that f ( m + n m 4 ) f\left(m+ \frac{n- m}{4}\right) differs from f ( m + n m 8 ) f\left(m + \frac{n-m}{8}\right) by some constant C 4 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 ) f(m) and f ( n ) f(n) must be greater than C 1 + C 2 + C 3 + 1 + 1 + 1 + . C_1 + C_2 + C_3 + \cdots \geqslant 1 + 1 + 1 + \cdots. 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.

Noe Blassel - 3 years, 5 months ago

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 a > b , we find that f ( a ) > f ( b ) f(a) > f(b) .

Gary Zhang - 3 years, 5 months ago

Log in to reply

Then you should say strictly increasing. But this still doesn‘t follow from injectivity.

Keine Angabe - 3 years, 3 months ago

If f has the property in question, so does -f. That makes me very suspicious of your claim that f "must be increasing".

Richard Desper - 3 years, 5 months ago
Leonard Ng
Jan 11, 2018

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.

Agnishom Chattopadhyay - 3 years, 5 months ago

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...

t m - 3 years, 5 months ago

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.

Kay Drangmeister - 3 years, 4 months ago

I don't understand your argument. Are you assuming that f f is differentiable everywhere?

Pi Han Goh - 3 years, 5 months ago

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.

Leonard Ng - 3 years, 4 months ago
Seb Motala
Jan 10, 2018

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

Seb Motala - 3 years, 5 months ago
Abhishek Soni
Jan 14, 2018

By using LMVT

Roshan Wani
Jan 12, 2018

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 a and b b are distinct.

Pi Han Goh - 3 years, 5 months ago
Gary Shannon
Jan 11, 2018

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?

Agnishom Chattopadhyay - 3 years, 5 months ago
Pepper Mint
Jan 13, 2018

When a > b a>b , let me set a b = d x a-b=dx and f ( a ) f ( b ) = d y f(a)-f(b)=dy . Then d y d x + 1 , d y d x 1 + 1 d x . dy \geq dx+1, \dfrac{dy}{dx} \geq 1+\dfrac{1}{dx}.

But since d x dx goes to 0 0 , 1 + 1 d x 1+\dfrac{1}{dx} goes to infinity, which makes explicit function f ( x ) f(x) impossible.

עידו שביט
Jan 11, 2018

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?

Agnishom Chattopadhyay - 3 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...