# How do you go from $x\in\cup\{\mathcal{P}(A)|A\in\mathcal{F}\}$ to $\exists A\in\mathcal{F}(x\in \mathcal{P}(A))$?

These are statement 4 of example 2.3.6 and its solution from section 2.3 in Daniel J. Velleman's "How to Prove It - A Structured Approach" (great book), where the author asks the reader to analyze the logical form of several statements. On the solution to this particular statement, i.e.:

$x\in\cup\{\mathcal{P}(A)|A\in\mathcal{F}\}$

he argues that, according to the definition of union given earlier:

$\cup\mathcal{F}=\{x|\exists A\in\mathcal{F}(x\in A)\}=\{x|\exists A(A\in\mathcal{F}\wedge x\in A)\}$

the statement means that "... $x$ is an element of at least one of the sets $\mathcal{P}(A)$, for $A\in\mathcal{F}$. In other words, $\exists A\in\mathcal{F}(x\in\mathcal{P}(A))$."

Intuitively it makes sense, but I can't write it down formally. If I state that $x\in\cup\mathcal{F}$ is true, I know that $\exists A\in\mathcal{F}(x\in A)$. But I get lost when I try to replace $\mathcal{F}$ with $\mathcal{P}(A)$, and can't figure out the rest.

-
What exactly is the question? – William Aug 21 '12 at 1:56
When I tried to write down the definitions, I got to the point where I said that $\exists A\in\mathcal{F}(x = \mathcal{P}(A))$. Clearly I got it wrong, both formally and intuitively. – Georger Aug 21 '12 at 1:59
I see the question is in the title. I didn't read the title. – William Aug 21 '12 at 2:01
I'm not familiar with this notation. What are P and F? – Dan Christensen Aug 21 '12 at 3:05
$\mathcal{P}(A)$ is the power set of $A$ and $\mathcal{F}$ is a family of sets. – Georger Aug 21 '12 at 13:00

Define $\mathcal{G} = \{P(A) : A \in \mathcal{F}\}$. Then

$x \in \bigcup \{P(A) : A \in \mathcal{F}\}$

is equivalent to

$x \in \bigcup \mathcal{G}$

By definition of union, it is equivalent to

$(\exists B \in \mathcal{G})(x \in B)$

Recall that $(\exists B \in \mathcal{G}$ if and only if there $(\exists A \in \mathcal{F})(B = \mathcal{P}(A))$. So replacing $B$ by $\mathcal{P}(A)$, you get

$(\exists A \in \mathcal{F})(x \in \mathcal{P}(A))$

-
A very good formal explanation. Thanks! – Georger Aug 21 '12 at 2:21

From $x\in\cup\{\mathcal{P}(A)|A\in\mathcal{F}\}$ you can conclude that there is an $A\in \mathcal{F}$ such that $x\in \mathcal{P}(A)$. The $x$ is a subset of $A$ and (not necessarily) an element of $A$.

-

Suppose $x \in \cup \{ \cal{P}(A) | A \in \cal{F} \}$. Since $x$ is in the union of a set, that means there is an element of the set of which $x$ is an element. That is, there is an element of $\{ \cal{P}(A) | A \in \cal{F} \}$ for which $x$ is an element. Every element of this set has the form $\cal{P}(A)$ for some $A \in \cal{F}$, so there must be an $A \in \cal{F}$ such that $x \in \cal{P}(A)$, in symbols $\exists A \in \cal{F}(x \in \cal{P}(A))$.

-

Something in what you wrote looks a little suspicious: if I'm understanding correctly your notation, $\,\mathcal F\,$ is a set of sets and, thus, its elements are sets, whereas that $\,x\,$ there seems to be an element of some set in $\,\mathcal F\,$...

I think the problem is: by $\,x\in\cup\{P(A)\;|\;A\in\mathcal F\}\,$ , we have that x in an element of $\,P(A)\,$ , for some $\,A\in\mathcal F\,$ , so $\,x\,$ is a subset of some such $\,A\,$ .

Yet later we have that $\,x\in A\,$ , for some $\,A\in\mathcal F\,$...and this already messes all up, since above we saw $\,x\,$ is a subset of some set, yet now it is an element of some set...so unless some, or all, the elements in $\,\mathcal F\,$ are sets that contain both elements and the sets determined by them, we've reached a dead-end here.

Now, what you say the author says is correct: the statement $\,x\in\cup\{P(A)\;|\;A\in\mathcal F\}\,$ means "there exists some set $\,A\,$ in $\,\mathcal F\,$ s.t. $\,x\subset A\,$ , but I can't make any sense of $\,\cup\mathcal F\,$ ...

-
You're right, $\mathcal{F}$ is a family of sets. And yes, in the book there are times when $x$ is an element and also times when it's a set. – Georger Aug 21 '12 at 2:24
Oh, I don't criticize the use of $\,x\,$ as different things (number, element, set, a watermelon); the problem here, as you posed it, is that they're using it as two different things within the same problem. That's wrong or, at least, pretty confussing – DonAntonio Aug 21 '12 at 2:26
Agreed. Most of the time the book is very clear and precise, but in this case it's really confusing. – Georger Aug 21 '12 at 2:39

This is the same as other answers in essence, written down differently (except that personally I don't like this way of writing quantifiers).

For me, these kind of problems are just about carefully unpacking of the definitions, and then using logic to simplify.

So I would calculate as follows:

\begin{align} & x\in\cup\{\mathcal{P}(A)|A\in\mathcal{F}\} \\ \equiv & \qquad \text{"Velleman's definition of $\;\cup\;$, but using $\;B\;$ to prevent confusion"} \\ & x\in\{x|\exists B (B\in\{\mathcal{P}(A)|A\in\mathcal{F}\} \land x\in B)\} \\ \equiv & \qquad \text{"definition of set builder notation"} \\ & \exists B (B\in\{\mathcal{P}(A)|A\in\mathcal{F}\} \land x\in B) \\ \equiv & \qquad \text{"definition of (a more complex version of) set builder notation"} \\ & \exists B (\exists A \in \mathcal{F} (B = \mathcal{P}(A)) \land x\in B) \\ \equiv & \qquad \text{"logic: pull $\;x\in B\;$, which does not use $\;A\;$, into $\;\exists A\;$"} \\ & \exists B \exists A \in \mathcal{F} (B = \mathcal{P}(A) \land x\in B) \\ \equiv & \qquad \text{"logic: exchange $\;\exists\;$ quantifiers"} \\ & \exists A \in \mathcal{F} \exists B (B = \mathcal{P}(A) \land x\in B) \\ \equiv & \qquad \text{"logic: one-point rule"} \\ & \exists A \in \mathcal{F} (x\in \mathcal{P}(A)) \\ \end{align}

The OP seems gone, but this may still help someone...

-