1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Ceiling Proof

  1. Oct 17, 2011 #1
    1. The problem statement, all variables and given/known data
    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.


    2. Relevant equations



    3. 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 x1 = ceiling[x] - x. Then 0 ≤ x1 < 1.

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

    So y = x + x1 + x = 2x + x1

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

    However, x1 < 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!
     
    Last edited: Oct 18, 2011
  2. jcsd
  3. Oct 17, 2011 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.)
     
  4. Oct 17, 2011 #3
    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.
     
  5. Oct 18, 2011 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  6. Oct 18, 2011 #5
    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.
     
  7. Oct 18, 2011 #6

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  8. Oct 18, 2011 #7
    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 x1, arrive at a contradiction, and so y ≠ t + ceiling[t]? And then my proof works?
     
  9. Oct 18, 2011 #8

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    You're just showing that one particular number, x1 + x , where x1 - ceiling(x) -x , gives inequality. But, all values of x must also give inequality.
     
  10. Oct 18, 2011 #9
    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!
     
  11. Oct 18, 2011 #10

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Ceiling Proof
  1. A proof (Replies: 3)

Loading...