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!

Looking for a Counterexample to show that a PowerSet is False!

  1. Mar 4, 2013 #1
    1. The problem statement, all variables and given/known data

    I am trying to find a counterexample to show why the below statement is False!
    ρ = PowerSet since I couldn't find the symbol.

    ρ(A x B) = ρ(A) x ρ(B)

    2. Relevant equations

    N/A

    3. The attempt at a solution

    Aside from googling for three days. I read/reread my Discrete Mathamatics book over and over again. I've assigned simple test cases for A & B and it always comes out true whether I calculate the powersets of A & B first, then take the cartesian product or I take the cartesian product first and then calculate the powerset.

    The only solution I can come up with is assigning one set to be anything non-null and the other set to be empty or Null. For instance:

    A = (1,2) B = ∅

    A x B = {∅}
    ρ(A x B) = {0, {∅}}

    ---------------------------------------------

    A = (1,2) B = ∅

    ρ(A) = {∅, {1}, {2}, {1,2}}
    ρ(B) = {0,{∅}}

    ρ(A) x ρ(B) = {(∅,∅),(1,∅),(2,∅),(1,∅),(2,∅)}

    -------------------------------------------------

    The only time I come up with a False counterexample is anytime one of the sets contains a ∅ so I guess I a just asking if my assessment is correct or if I am way off base. Not sure if I am calculating the cardesian product correctly when it contains a set with ∅.

    Any insight would be appreciated...
     
  2. jcsd
  3. Mar 4, 2013 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't see how 0 is in any of your power sets. Why don't you look at something simpler? Say A has 2 elements and B has 3 elements. How many elements are in ##\rho(A)##? ##\rho(B)##? ##A\times B##? ##\rho(A\times B)##?
     
    Last edited: Mar 4, 2013
  4. Mar 4, 2013 #3
    Oops, Sorry. Those zeros we're suppose to be ∅. A null, and a null set.

    In any case, I have tried simple sets with just 1 item in each and they do come out equal. I am being asked to find a counterexample in which they do not come out equal. I am thinking one set must be ∅ since when you multiply any set by ∅ you get ∅. And by taking the powersets first, your adding null into the calculation. By doing the multiplication first, there is no null yet so it produces less sets. I think I'm confusing myself...

    Example:

    A = {1} B = {2}

    A x B = {1, 2}

    ρ(A x B) = {∅, {1}, {2}, {1,2}}
    ------------------------------------------

    And the other side:

    A = {1} B = {2}

    ρ(A) = {∅, {1}}
    ρ(B) = {∅, {2}}

    ρ(A) x ρ(B) = {∅, {1}, {2}, {1,2}}

    --------------------------------------------

    I'm just confused with calculating cardesian products with Nulls them.




     
    Last edited: Mar 4, 2013
  5. Mar 4, 2013 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Why don't you try answering my questions in post #2?
     
  6. Mar 4, 2013 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Is ##A \times B## supposed to be the Cartesian product of ##A## and ##B##? If so, your ##A \times B## above is wrong: you have given ##A \cup B##.
     
  7. Mar 4, 2013 #6
    Are you sure about that Ray? I only ask because even the calculators come up with

    A×B = {1}×{2} = {(1,2)}

     
  8. Mar 4, 2013 #7
    Sorry LCKurtz. I thought I did answer you question to use something simpiliar by only using a set A with 1 element, and set B with only 1 element. I guess I am not understanding your question to use something simpler because if you add elements, than your sets go up 2^2[/itex] powers.

    Your example of 2 elements for A would produce 2^2= 4 subsets. and sets B would produce 2^3[/itex] sets = 8 sets for the powerset that is.

    I guess I'm not sure what your asking. The instructor didn't give us any specific elements for the sets. He wants us to come up with a specific set that would cause the statement to be false. Sorry if I'm misunderstaning your question..

    George


     
  9. Mar 4, 2013 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'm sure Ray is sure. That's correct but it's not what you wrote. You wrote AxB={1,2}. So AxB has one element, not two. Try it again and distinguish between what is an ordered pair and what is not.
     
  10. Mar 4, 2013 #9

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    If there are 2 elements in set A, and 3 elements in set B, how many elements are there in A×B ?

    You still haven't answered this.
     
  11. Mar 4, 2013 #10
    Ahh, got it. I just learned this a week ago so I'm glad everyone is setting me straight.
    I am gonna get slaughtered on quiz day next week.

     
  12. Mar 4, 2013 #11
    ρ(A) ? 2 elements in A produces 4 sets.

    ρ(B) ? 3 elements in B produces 8 sets

    A×B ? 6 sets

    ρ(A×B) ? powerset of 6 elements produces 64 elements

    none of this was in the original question so I guess I am just confused as to where this info is coming from.

    Thanks,
    George

     
  13. Mar 4, 2013 #12

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    George,

    Where is this question coming from ?

    In post #2 LCKurtz asked you the following:
    Say A has 2 elements and B has 3 elements. How many elements are in [itex]\rho(A)\,?\ \rho(B)\,?\ A\times B\,?\ \rho(A\times B)?[/itex] ​
    You had previously only given a partial answer. Now you have answered completely.

    Also, even though you mentioned nothing about the above situation in your original post, you would do well to consider the implications of the complete answer to this question and how it relates to the goal you are looking for in your original post.

    Added in Edit:

    It may also be helpful to consider the number of elements in [itex]\rho(A)\times \rho(B)\ .[/itex]
     
    Last edited: Mar 4, 2013
  14. Mar 4, 2013 #13
    Thanks for being patient with me :approve:

    I guess I just thought LCKurtz didn't understand my question but now I see you guys are helping me piece it all together.

    Out of all LCKurtz questions yours in the one that I am not sure of. I know how to calculate everything but I am not sure of ρ(A) x ρ(B) because now the cartesian product will include the {∅} in each of the sets. Thanks for getting me on the right track. I think part of my solution to make the original statement false includes a ∅ in one of the sets.

    I apologise if I am coming off as rude in some of my post. I don't mean to. I am just confused and learning and posting incorrect info...

    Sincerely,
    George



     
  15. Mar 4, 2013 #14

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    {∅} is just like any other element of ρ(A) .

    If the number of elements in set M is m, and the number of elements in set N is n, then how many elements are there in set M×N ?
     
  16. Mar 5, 2013 #15
    It would just be m x n elements, correct?

    I understand how to calculate the powersets now and how to calculate cartesian product but this original equation is still stumping me with what sets are requires to be a counterexample and make it false. The way I am calculating it it looks like it is always false and can never be true. Is the counterexample all real numbers?

    Look at this example I am calculating with just 1 element in each set. Please yell at me if I get the syntax incorrect again.

    Set A = {5}
    Set B = {5}

    Cartesian product of A x B = {(5,5)}
    The powerset of ρ(A x B) = {∅,{5},{5},{5,5}} is it ∅ or {∅}?

    Now the other way which should also be equal according to ρ(A x B) = ρ(A) x ρ(B)

    ρ(A) = {∅, {5}}
    ρ(B) = {∅, {5}}
    Cartesian product of ρ(A) x ρ(B) = {(∅,∅),(∅,5),(5,∅),(5,5)}

    Sorry if you guys are pointing me in the right direction and I am just not getting it..



     
  17. Mar 5, 2013 #16

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Yes. That's correct.

    Apply this to LCKurtz's suggested case.
    In this example, the set A×B has only one element, (5,5) . It has only two subsets, ∅ , and {(5,5)} .

    Therefore, the power set of A×B has two elements. This is consistent with the fact that a set of a set with n elements has a power with 2n elements.

    ρ(A×B) = {∅, {(5,5)}}

    It's important to keep in mind that a power set is a set whose elements are themselves sets, i.e. each element of a power set is a set.
     
  18. Mar 5, 2013 #17

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    @topgun_68 I have been following the discussion and followups in this thread, and I still can't tell whether you have solved your original question. You do realize that two sets that have a different number of elements can't be the same set, right?

    If, as I suggested in my original post, A has two elements and B has 3 elements and you look at both sides of your presumed equality: ρ(A×B) = ρ(A)×ρ(B), you can figure out how many elements are on each side, right? You don't even have to write the sets down to calculate how many elements are on each side. If the numbers aren't equal they can't be the same set. Have you put it all together yet?
     
  19. Mar 5, 2013 #18
    Yes I did follow your example and came to that same conclusion, but what confused me is the question from the instructor asking for a counterexample that makes it false. I just needed to hear someone say it, because I think this was a trick question. I kept thinking that I was missing some key piece to make it true. I am going to answer it that all real numbers are a counterexample because it can't ever be true.

    I still learned a lot from this thread so thanks for everyones input..

    George


     
  20. Mar 5, 2013 #19

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    A counter-example is generally an example which shows a statement to be false.

    I don't see how "the instructor asking for a counterexample that makes it false" causes confusion.
     
  21. Mar 5, 2013 #20
    Only because all of the statements are usually true for most but not all x and you have to figure out what the conterexample is. This is the first time I've seen an example from him that can never be true and is false for every set. It just made me overthink it when the answer was right in front of my face.


     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Looking for a Counterexample to show that a PowerSet is False!
  1. True or false (Replies: 1)

  2. Show that (Replies: 4)

  3. Counterexample help (Replies: 12)

  4. Show that (Replies: 8)

Loading...