Rewriting $\mathscr P(\bigcup_{i \in I} A_i)\not\subset\bigcup_{i \in I} \mathscr P(A_i)$ in more fundamental terms.

Question

Working through Velleman's "How to Prove It" and currently having a bit of difficulty with a problem where I'm asked to rewrite this:

$$\mathscr P\left(\bigcup_{i\in I} A_i\right)\not\subset\bigcup_{i \in I} \mathscr P(A_i)$$

. . . using only . . .

$$\land \lor \exists \forall \in \notin \to \iff = \neq$$

Here's what I've come up with so far:

$$ \mathscr P\left( \bigcup_{i\in I} A_i \right) \not\subset \bigcup_{i\in I} \mathscr P(A_i) $$

The first element I look at here is the 'not a subset' element.

$$ \exists x\,\left( x\in \mathscr P\left( \bigcup_{i\in I} A_i \right) \wedge x\notin \bigcup_{i\in I} \mathscr P(A_i) \right) $$

I know being a member of the power set of something is basically being a subset of that thing.

$$\exists x \left( \left(\forall y(y \in x \to \exists i \in I(y \in A_i)\right) \land x \notin \bigcup_{i\in I} \mathscr P(A_i)\right)$$

This next part is where I feel like I'm making some kind of mistake. I feel like I've got something wrong about the union of a power set here.

$$\exists x(\forall y(y \in x \to \exists i \in I(y \in A_i)) \land \lnot \exists i \in I(\forall y(y \in x \to y \in A_i)))$$

If $x$ is the member of a union of some indexed family of sets, then there exists some some index $i$ in the index set $I$ such that $x$ is a member of the set $A_i$. So if the set it's a member of is the $\mathscr P(A_i)$ . . . I just substitute the definition of membership in a power set in where I'd otherwise state the set?

I feel like I'm making a really silly mistake in my reasoning, but I'm not sure what.

Answer 1

What you have is correct, though not the first translation that I’d have come up with. I’d work a bit informally first. Suppose that

$$x\in\wp\left(\bigcup_{i\in I}A_i\right)\setminus\bigcup_{i\in I}\wp(A_i)\;;$$

then $x\subseteq\bigcup_{i\in I}A_i$, but for each $i\in I$ we have $x\nsubseteq A_i$. The first of these says that

$$\forall y\in x\,\exists i\in I(y\in A_i)\;;$$

the second says that

$$\forall i\in I\,\exists y\in x(y\notin A_i)\;.$$

Putting the pieces together:

$$\exists x\Big(\big(\forall y\in x\,\exists i\in I(y\in A_i)\big)\land\big(\forall i\in I\,\exists y\in x(y\notin A_i)\big)\Big)\;.$$

As you can see, it’s very similar; it just expresses the second part a bit differently by pushing the negation inside the quantifiers. You can get rid of the bounded universal quantifiers with implications, just as you did in your version. You can also get rid of the bounded existential quantifiers using conjunctions. I’ll not write out the whole thing, but for example the first clause can be expanded to

$$\forall y\big(y\in x\to\exists i(i\in I\land y\in A_i)\big)\;.$$

Answer 2

Set $B=\bigcup_{i\in I}A_i$, for the moment. You want to state that there exists $x\subset B$ such that $x\notin\mathcal{P}(A_i)$, for all $i\in I$, that is, $x\not\subset A_i$, for all $i\in I$.

The condition $x\not\subset A_i$ can be expressed by $$ \exists y(y\in A_i\land y\notin x) $$

Applying the universal quantifier: $$ \forall i(i\in I\to(\exists y(y\in A_i\land y\notin x)) $$ Thus the statement is $$ \exists x(x\subset B\land\forall i(i\in I\to(\exists y(y\in A_i\land y\notin x))) $$ Now we want to translate $x\subset B$: for any $z\in x$, there must exist $j\in I$ with $z\in A_j$; so $$ \forall z(z\in x\to\exists j(j\in I\land z\in A_j)) $$ Finally, the formula should be $$ \exists x((\forall z(z\in x\to\exists j(j\in I\land z\in A_j)))\land\forall i(i\in I\to(\exists y(y\in A_i\land y\notin x))) $$