Looking for a Counterexample to show that a PowerSet is False

[Topgun_68]

Homework Statement

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)

Homework Equations

N/A

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

 

[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)$?

 

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

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)$?

 

[LCKurtz]

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

 

[Ray Vickson]

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.

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

 

[Topgun_68]

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

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

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

 

[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

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)$?

 

[Dick]

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

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

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.

 

[SammyS]

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

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.

 

[Topgun_68]

Ahh, got it. I just learned this a week ago so I'm glad everyone is setting me straight.
I am going to get slaughtered on quiz day next week.

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.

 

[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

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.

 

[SammyS]

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

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)?$​

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 $\rho(A)\times \rho(B)\ .$

 

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


George

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)?$​

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 $\rho(A)\times \rho(B)\ .$

 

[SammyS]

...

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

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

 

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

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

 

[SammyS]

It would just be m x n elements, correct?

Yes. That's correct.

Apply this to LCKurtz's suggested case.

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

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

 

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

 

[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

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

 

[SammyS]

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 everyone's input..

George

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.

 

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

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.

 

[LCKurtz]

I am going to answer it that all real numbers are a counterexample because it can't ever be true.

George

I assume you will lose most of the credit on the problem if you give that answer. Do you understand why?

 

[Dick]

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.

The statement ρ(A×B) = ρ(A)×ρ(B) is false for any choice of A and B. The left side is a subset of ordered pairs (a,b) where a is in A and b is in B. The right side is ordered pairs (Pa,Pb) where Pa is a subset of A and Pb is a subset of B. Even aside from counting them the elements of the two sides are different kinds of things. If you'd stuck to A={1}, B={2} and carefully written out what both sides are you'd know this.

 

[Topgun_68]

I was going to explain how taking the Powerset of the sets first, P(A) x P(B) produces an uneven amount of sets, due to ∅ which causes them not to be equal, but I kinda like Dicks by the book response better. And yes, my instructor is very very picky so he would've gave me little credit on a non-formal answer.

I assume you will lose most of the credit on the problem if you give that answer. Do you understand why?

 

[Topgun_68]

That's exactly how the book would write it, Nice.

The important part is that I understand it, which is what counts most on exam time next week.

Thanks,

The statement ρ(A×B) = ρ(A)×ρ(B) is false for any choice of A and B. The left side is a subset of ordered pairs (a,b) where a is in A and b is in B. The right side is ordered pairs (Pa,Pb) where Pa is a subset of A and Pb is a subset of B. Even aside from counting them the elements of the two sides are different kinds of things. If you'd stuck to A={1}, B={2} and carefully written out what both sides are you'd know this.

 

[Dick]

That's exactly how the book would write it, Nice.

The important part is that I understand it, which is what counts most on exam time next week.

Thanks,

You're welcome! Good luck in the exam!