Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 1 more comment

5 Answers 5

up vote 1 down vote accepted

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

share|improve this answer
    
A very good formal explanation. Thanks! –  Georger Aug 21 '12 at 2:21
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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