Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help with a proof in my discrete math summer class

  1. Jul 17, 2011 #1
    1. The problem statement, all variables and given/known data

    Let A be the set of all integers x such that x is = k2 for some integer k
    Let B be the set of all integers x such that the square root of x, SQRT(x), is an integer
    Give a formal proof that A = B. Remember you must prove two things: (1) if x is in A, then x is in B, AND (2) if x is in B, then x is in A


    2. Relevant equations



    3. Why I am so useless
    I am taking an online discrete math class as a prerequisite for my major. The prof is a nice enough person, but the extent of help that he provides on questions that I have asked is "read the book". Which I have...and it didn't help me in this case. If someone could point me in the right direction of how to get this proof underway, I would appreciate it.
     
  2. jcsd
  3. Jul 17, 2011 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Since this is your first post, here's a couple of useful hints.

    You don't mean what you wrote for A. What you have written would mean A was the even integers. You should write it as k^2 or, better, use the X2 key above your edit window. So A = {x: x is an k2 for some integer k} which we might more informally call the perfect squares. And B is, informally, the integers that are square roots of other integers.

    First you might argue that both sets only contain positive integers. Now suppose x is in A. Can you make an argument that it is in B? Then you have to do the other way.
     
  4. Jul 17, 2011 #3

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi CapnCornbread! Welcome to PF! :wink:

    Show us your attempt at (1) first. :smile:
     
  5. Jul 17, 2011 #4
    OK, I was thinking I could do something like this:
    To prove this example of set equality, we need to undertake two steps: first, show that if x is in A then X is in B, and second, show that if x is in B then X is in A.
    First, Assume x ∈A. Then by definition of A, x = k2 for some integer k. Thus by algebra, x = k2 = SQRT(k) * SQRT(k). Therefore x ∈B.
    Next, Assume x ∈B. Then by definition of B, SQRT(x) for some integer k. Thus by algebra, x = SQRT(k) = k2. Therefore x ∈A.
    We have shown that both A⊆B and B⊆A, therefore A = B.
     
  6. Jul 17, 2011 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You really need to use the X2 icon. You are close, but your equality
    k2=SQRT(k) * SQRT(k) isn't true because the left and right sides aren't equal. Think about it a little more.

    Again, sqrt(k) ≠ k2. Do you need that?
     
  7. Jul 17, 2011 #6
    With revisions:
    Assume x ∈A. Then by definition of A, x = k2 for some integer k. Thus by algebra,
    x = k2 = k * k. Therefore x ∈B.
    Assume x ∈B. Then by definition of B, SQRT(x) for some integer k. Thus by algebra, x = SQRT(k) * SQRT(k) = k. Therefore x ∈A.
    We have shown that both A⊆B and B⊆A, therefore A = B.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook