0
$\begingroup$

Let $A,B$ be sets. Prove $\forall A,B(\:\mathcal{P}(A)\cup\mathcal{P}(B)\subset\mathcal{P}(A\cup B)\:)$

Attempt:
$a\in \mathcal{P}(A)\cup\mathcal{P}(B)\iff a\in\mathcal{P}(A)\vee a\in \mathcal{P}(B) \iff a\subset A\vee a\subset B\iff a\subset A\cup B\iff a\in \mathcal{P}(A\cup B)$

Comment:
This proof is wrong as it turns out that equality is impossible, though I don't understand why the presented logic isn't logical.

$\endgroup$
  • $\begingroup$ You are using $\iff$ symbols. Many of these are not $\iff$'s but are instead only $\implies$ $\endgroup$ – JMoravitz Apr 9 '18 at 17:15
  • $\begingroup$ Yes, why though? $\endgroup$ – Slavik Egorov Apr 9 '18 at 17:15
  • 1
    $\begingroup$ Consider the specific step $a\subset A\vee a\subset B\iff a\subset A\cup B$. Consider $a=\{1,2\}$, $A=\{1\}$ and $B=\{2\}$. $\endgroup$ – JMoravitz Apr 9 '18 at 17:16
2
$\begingroup$

The correct implications: $$ a\in \mathcal{P}(A)\cup\mathcal{P}(B)\iff a\in\mathcal{P}(A)\vee a\in \mathcal{P}(B) \iff a\subset A\vee a\subset B\implies a\subset A\cup B\iff a\in \mathcal{P}(A\cup B). $$ The iffs are consequence on the definition of $\cup$ and $\mathcal{P}$. The implication $$ a\subset A\cup B\implies a\subset A\vee a\subset B $$ is false. Can you see why? Hint: $a$ must be "divided" between $A$ and $B$.

$\endgroup$
1
$\begingroup$

Consider $A=\{1,2,3\}$ and $B=\{4,5\}$. So $\{3,4\}\subset A\cup B$ but this does not imply that $\{3,4\}\subset A\vee \{3,4\}\subset B$. So, your third equivalence is not true in general.

$\endgroup$
1
$\begingroup$

One way to investigate dubious proofs is to take a concrete example and spot where the reasoning fails. In this case, observe that $A = \{0\}, B = \{1\}$ is a counterexample to the original statement if $a = \{0,1\}$ since $a \in \mathcal{P}(A \cup B)$ but $a \notin \mathcal{P}(A) \cup \mathcal{P}(B)$. Can you see where the proof fails?

$\endgroup$
1
$\begingroup$

Suppose $X\subset Y$. Then prove that $\mathcal{P}(X)\subset\mathcal{P}(Y)$.

In particular, $\mathcal{P}(A)\subset\mathcal{P}(A\cup B)$ and $\mathcal{P}(B)\subset\mathcal{P}(A\cup B)$.

Therefore $\mathcal{P}(A)\cup\mathcal{P}(B)\subset\mathcal{P}(A\cup B)$.

You have a wrong proof because you're using a wrong double implication. You can have $a\subset A\cup B$, but $a\not\subset A$ and $a\not\subset B$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.