4

Find all finite sets $A$ so that $A\times\mathcal P(A) =\mathcal P(A)\times A$, where $\mathcal P(A)$ is the power set of $A$.

Now I'm a beginner at Discrete Math so I'm not sure how to tackle this problem. I was expecting that a set with elements would provided to prove this. My best hunch is that all sets should work since its the same on both sides of the equal sign. If you could help me find out how work through the question, instead of just an answer that would be great!

Asaf Karagila
  • 393,674
Brownie
  • 667
  • 1
  • 5
  • 17
  • If by $\times$ you mean the Cartesian Product, then it is not true that $A \times \mathcal{P}(A) = \mathcal{P}(A) \times A$. $\mathcal{P}(A)$ is composed of sets of $A$ and $A$ is composed of elements of $A$, so I can't think of any scenario where this would be true. – Hyperion Jan 28 '19 at 03:11
  • In fact, $A \times B \neq B \times A$ unless $A = B$, and because $\mathcal{P}(A) \neq A$, they can never be equal. – Hyperion Jan 28 '19 at 03:14
  • @Hyperion $ \emptyset \times \mbox{ anything } = \mbox{ anything } \times \emptyset$. – N. S. Jan 28 '19 at 03:17
  • @N.S. I didn't catch that; you're right. – Hyperion Jan 28 '19 at 03:24

2 Answers2

4

Hint 1: $\mathcal P (A)$ always has more elements than $A$. In particular $A \neq \mathcal P(A)$.

Hint 2: If $A \times B =B \times A$ then you can prove that either $A=B$ or one of $A,B$ is empty.

Indeed, if you assume by contradiction that you have $A \neq B$ and that neither $A$ nor $B$ is empty, then you can find an element $x$ which is in exactly one of the sets $A$ or $B$. Now, by using that neither $A$ nor $B$ is empty, you can pick some $y$ in the other set. Look at $(x,y)$.

Hint 3 Conclude that $A=\emptyset$ is the only solution.

N. S.
  • 132,525
  • This helps out a lot, I understand why it works this way because of how a Cartesian products of sets are defined. If you don't mind me asking how would I continue to prove that they are not equal. Is it sufficient to state that because of how we define a Cartesian product , and because P(A) and A are not the same unless A is an empty set the two sides cannot be equal? Also this is my first post ever, and the lightning fast detailed response is really great, and super helpful. Thanks for helping people out – Brownie Jan 28 '19 at 03:29
  • 1
    @Viz-sa There are many ways to show that $\mathcal P(A)$ is bigger. For example $f : A \to \mathcal{P}(A)$ defined by $f(x)= { x }$ is one to one but not onto, since it doesn't take the "value" ${ \emptyset } \in P(A)$.... Or you can show that if $A$ has $n$ elements, then $P(A)$ has $2^n$ and that $2^n >n$ for all $n \geq 0$. – N. S. Jan 28 '19 at 03:32
  • 1
    @Viz-sa Or you can use the Cantor theorem, which proves the claim even for infinite sets :) – N. S. Jan 28 '19 at 03:33
2

Assuming that "x" is the Cartesian product of two sets, we have the definition

For two sets $A$ and $B$, the cartesian product is given by $$A\times B=\{ (a,b):a\in A, b\in B\}$$

Suppose that $A\times P(A)$ for some set $A$. Then, each element of $P(A)$ must be in $A$. However, by Cantor's theorem, we have that $|A|<|P(A)|$ for any $A$, thus there is at least one element of $P(A)$ that is not in $A$.
Thus it cannot be true that $A\times P(A)=P(A)\times A$ for any set $A$.

高田航
  • 2,125
  • 13
  • 30
  • 1
    "Then, each element of $P(A)$ must be in $A$" is not true.... You need the extra assumption that $A$ is not empty to deduce that. – N. S. Jan 28 '19 at 03:24
  • 3
    Note that $A=\emptyset$ satisfies $A \times P(A)=P(A) \times A$. – N. S. Jan 28 '19 at 03:25
  • 1
    Note that if $B \times C \subset D \times E$, you need the extra assumption that $C \neq \emptyset$ to conclude that $B \subset D$. – N. S. Jan 28 '19 at 03:30
  • Thank you for the correction, will edit. – 高田航 Jan 28 '19 at 03:40