Proving the Falsehood of y = x + ceiling[x] for All Real Numbers y and x

[jumbogala]

Homework Statement

Prove that the following statement is either true or false:

For all real numbers y, there is a real number x such that y = x + ceiling[x].

Note: ceiling[x] = n such that n-1 < x ≤ n. For example, if x = 3.2, then ceiling[x] = 4.

Homework Equations

The Attempt at a Solution

I think the statement is false. So I am going to prove its negation is true.

Negation: There exists a real number y such that for all real numbers x, y ≠ x + ceiling[x].

Proof:
Suppose x is a real number.

Suppose y = 2x + 1. Then y is a real number because x is a real number. (I think I can do this because I just have to show that my statement holds for at least one y.)

Now suppose that y = x + ceiling[x].

Define x₁ = ceiling[x] - x. Then 0 ≤ x₁ < 1.

So ceiling[x] = x₁ + x. Plug this into y = x + ceiling[x].

So y = x + x₁ + x = 2x + x₁

But by one of my assumptions, y= 2x + 1. Therefore, x₁ = 1.

However, x₁ < 1. This is a contradiction.

So y ≠ x + ceiling[x]. Negation of the statement is proved, so the original statement is true.

--
Is this correct? I showed it to a friend who told me this doesn't prove the right thing. Apparently this only shows that y ≠ x + ceiling[x], and doesn't actually prove my original statement. I'm confused because I think it works. Help!

 

[SammyS]

It is not a correct proof for this problem. Yes, you can choose a y, but you can't specify how it is related to x.

Try some fairly simple examples & see what happens.

Pick several values for y, see if you can find a value for x that works.

Pick several values for x, see you get for y. (I think this way works best.)

 

[jumbogala]

But for all x, there exists a y such that y = 2x + 1 right?

So why can't I pick that particular y? I don't understand why I can't specify how it's related to x. The statement just has to work for one y right, why can't it be the one I pick?

I tried picking several values for x, and seeing what I got for y. y jumps.

 

[SammyS]

But you need to show that for ALL x that y ≠ x + ceiling[x] . However by saying y = 2x+1, you have already limited what x can be.

Actually, a better way to say y ≠ x + ceiling[x] would to say | y - (x + ceiling[x]) | > 0 .

I suggest: Find a specific y --- a number. Do this by trying several different values for x & see what values of y seem to be missed. --- or --- Perhaps Graph y = x + ceiling[x]). Look for gaps in the range of this graph.

 

[jumbogala]

I can't quite get my head wrapped around this. How does that limit what x can be? For y = 2x + 1, x can still be any real number since there is no condition on y.

If I said let y = 5, then I could show that there is no x such that 5 = x + ceiling[x]. I figured out how to do that:

x = 5 - ceiling[x]. Ceiling[x] is an integer, so x must be an integer. So x = ceiling[x].

Then 5 = 2x, or x = 5/2. But 5/2 is not an integer so you arrive at a contradiction. This definitely works.

I still want to understand why I can't do what I originally did though.

 

[SammyS]

Fine, but then you need to use a different variable than x in the expression x + ceiling[x] , i.e.

y ≠ t + ceiling[t] , for all t.

 

[jumbogala]

And then how would that change my proof?

So I'm still supposing y = 2x + 1 where x is any real number.

Then I suppose that y = t + ceiling[t].

Then I still show all that stuff with x₁, arrive at a contradiction, and so y ≠ t + ceiling[t]? And then my proof works?

 

[SammyS]

You're just showing that one particular number, x₁ + x , where x₁ - ceiling(x) -x , gives inequality. But, all values of x must also give inequality.

 

[jumbogala]

Okay, I think that makes a bit more sense. I'll give it some more thought and hopefully it will be clearer to me. Thanks for your help!

 

[SammyS]

Actually saying that y = 2x+1 doesn't say anything about y, unless you are somehow restricting x in some way, such as making it be an integer.

By the way, you are correct in saying that the statement is false.