Analyzing logical forms clarification

59 Views Asked by At

This example is from Velleman's "How To Prove It":

Example 2.3.6. Analyze the logical forms of the following statements.

  1. $x \in \bigcup \{ \mathscr{P}(A)| A \in F \}$

On the next page, the solution is written as $\exists A \in F(x \in \mathscr{P}(A))$. This makes sense to me, but it does not seem to follow the expansion rules. I worked it out as \begin{align*} x & \in \bigcup \{ \mathscr{P}(A)| A \in F \} \\ \exists B & \in \{ \mathscr{P}(A)| A \in F \} (x\in B) & \text{(definition of union)} \\ \exists B & (B \in \{ \mathscr{P}(A)| A \in F \} \wedge x \in B) \\ \exists B & (\exists A \in F(B =\mathscr{P}(A) ) \wedge x \in B) \end{align*} How does one go from $\exists B (\exists A \in F(B =\mathscr{P}(A) ) \wedge x \in B)$ to $\exists A \in F(x \in \mathscr{P}(A))$? Should it just be inferred, or can we transform one side into the other using basic rules?

2

There are 2 best solutions below

4
On BEST ANSWER

I guess you are missing that the last step of your derivation
$$\exists B (\exists A \in F(B =\mathscr{P}(A) ) \wedge x \in B)$$ is equivalent to (for a "formal" proof, see $(*)$ below) $$\exists B (\exists A \in F(B =\mathscr{P}(A) \wedge x \in B))$$ which is equivalent to (since the order of two quantifiers of the same kind can be inverted) $$\exists A \in F(\exists B (B =\mathscr{P}(A) \wedge x \in B))$$

Now, it is clear that $\exists B (B =\mathscr{P}(A) \wedge x \in B)$ is equivalent to $x \in \mathscr{P}(A)$.


$(*)$ Indeed, $$\exists A \in F(B =\mathscr{P}(A)) \wedge x \in B$$ means that $$\exists A (A \in F \land B =\mathscr{P}(A)) \wedge x \in B,$$ which is equivalent to $$\exists A (A \in F \land (B =\mathscr{P}(A) \wedge x \in B)),$$ which is equivalent to $$\exists A \in F (B =\mathscr{P}(A) \wedge x \in B).$$

2
On

$\begin{align} &x\in\bigcup\{\mathcal P(A)\mid A\in F\}\tag 1 \\& \exists B~\in\{\mathcal P(A)\mid A\in F\}~.(x\in B)\tag 2 \\&\exists B~.\exists A\in F~.(B=\mathcal P(A)\wedge x\in B)\tag 3 \\&\exists B~.\exists A\in F~.(B=\mathcal P(A)\wedge x\in\mathcal P(A)) \tag 4 \\&\exists A\in F~.\exists B~.(B=\mathcal P(A)\wedge x\in\mathcal P(A)) \tag 5 \\&\exists A\in F~.(\exists B~.(B=\mathcal P(A))\wedge x\in\mathcal P(A)) \tag 6 \\&\exists A\in F~.(\top\wedge x\in\mathcal P(A)) \tag 7 \\&\exists A\in F~.(x\in\mathcal P(A)) \tag8 \end{align}$