1. Not finding help here? Sign up for a free 30min 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!

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




Similar Discussions: Help with a proof in my discrete math summer class
  1. Discrete Math Proof (Replies: 3)

  2. Discrete Math Proof (Replies: 2)

  3. Discrete Math Proof (Replies: 4)

Loading...