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

1. Mar 4, 2013

### Topgun_68

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. Mar 4, 2013

### LCKurtz

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
3. Mar 4, 2013

### Topgun_68

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
4. Mar 4, 2013

### LCKurtz

Why don't you try answering my questions in post #2?

5. Mar 4, 2013

### Ray Vickson

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$.

6. Mar 4, 2013

### Topgun_68

Are you sure about that Ray? I only ask because even the calculators come up with

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

7. Mar 4, 2013

### Topgun_68

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

8. Mar 4, 2013

### Dick

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.

9. Mar 4, 2013

### SammyS

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

10. Mar 4, 2013

### Topgun_68

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.

11. Mar 4, 2013

### Topgun_68

ρ(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

12. Mar 4, 2013

### SammyS

Staff Emeritus
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 $\rho(A)\,?\ \rho(B)\,?\ A\times B\,?\ \rho(A\times B)?$ ​

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.

It may also be helpful to consider the number of elements in $\rho(A)\times \rho(B)\ .$

Last edited: Mar 4, 2013
13. Mar 4, 2013

### Topgun_68

Thanks for being patient with me

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

14. Mar 4, 2013

### SammyS

Staff Emeritus
{∅} 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 ?

15. Mar 5, 2013

### Topgun_68

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..

16. Mar 5, 2013

### SammyS

Staff Emeritus
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.

17. Mar 5, 2013

### LCKurtz

@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?

18. Mar 5, 2013

### Topgun_68

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

19. Mar 5, 2013

### SammyS

Staff Emeritus
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.

20. Mar 5, 2013

### Topgun_68

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.