Set theory - Logic proof verification

Question

Prove that: $$ \mathscr P(U_{i\in I}A_i)\subset U_{i\in I}\mathscr P(A_i) \rightarrow \exists i \in I\ \forall j \in I (A_j \subset A_i) $$

---

Here are the definitions I've used to figure out how to prove it: $$ U{i\in I} A_i = \{ k \text{ | }\exists i \in I(k\in A_i) \}\\ U{i\in I} \mathscr P(A_i) = \{ k \text{ | }\exists i \in I(k\in \mathscr P(A_i)) \} = \{ k \text{ | }\exists i \in I(k \subset A_i) \} $$

---

Here's my proof.

It's true that $\forall j \in I: A_j \subset U_{i\in I}A_i$, thus $A_j \in \mathscr P(U_{i\in I}A_i)$. Therefore $\forall j \in I:A_j \in U_{i\in I}\mathscr P(A_i)$ which is the same as $ \forall j \in I: \big( \exists i \in I (A_j \subset A_i) \big)$.

But I want to prove that: $$ \exists i \in I: \big( \forall j \in I (A_j \subset A_i) \big) $$

So now I'll prove : $\forall j \in I: \big( \exists i \in I (A_j \subset A_i) \big) \rightarrow \exists i \in I: \big( \forall j \in I (A_j \subset A_i) \big)$ by contradiction.

Let $i$ be an arbitrary element of $I$. Therefore $A_{j0} \not\subset A_i$. That contradicts the fact that $ \forall j \in I: \big( \exists i \in I (A_j \subset A_i) \big) $, hence $\exists i \in I: \big( \forall j \in I (A_j \subset A_i) \big)$.

---

I'm new to math formalism and I struggled to get this. Is everything correct? I know that I'm using a lot of logic symbols, but it's because it's still more clear to me to write a proof like that then write it using plain English. I'm open to constructive criticism, and hope for a help.

Thanks!

Answer 1

This is not commentary on your proof, see David C. Ullrich's earlier answer for that. Here is an alternative proof that might appeal to you, because of your preference for using symbols-- so we will try to use them to our advantage here.$% \require{begingroup} \begingroup \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \{\:} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\{\:} } \newcommand{\hint}[1]{\mbox{#1} \:\} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\rightarrow} \newcommand{\when}{\leftarrow} \newcommand{\equiv}{\leftrightarrow} \newcommand{\P}[1]{\mathscr P\left(#1\right)} %$

Letting $\;i,j\;$ range over your index set $\;I\;$, you are asked to prove $$ \tag{0} \P{\cup_j A_j} \subset \cup_i \P{A_i} \;\then\; \exists i \forall j (A_j \subset A_i) $$ (I've renamed your leftmost $\;\cup_i\;$ to $\;\cup_j\;$, to avoid having to rename in the middle of the proof below.)

So let's start with what seems to be the most complex side of $\Ref{0}$, the left hand side, expand the definitions and simplify, and work towards the other side.

---

We calculate as follows:

$$\calc \P{\cup_j A_j} \;\subset\; \cup_i \P{A_i} \op\equiv\hint{definition of $\;\subset\;$} \forall D \left(D \in \P{\cup_j A_j} \;\then\; D \in \cup_i \P{A_i}\right) \op\equiv\hint{LHS: definition of $\;\P{\ldots}\;$; RHS: definition of $\;\cup_\ldots\;$} \forall D \left(D \subset \cup_j A_j \;\then\; \exists i (D \in \P{A_i})\right) \op{\then \tag{*}}\hints{choose $\;D := \cup_j A_j\;$, using $\;\forall V(V \subset V)\;$}\hints{-- the simplest way I see to move $\;\exists\;$ to the outside,}\hint{which is what the RHS of $\Ref{0}$ requires} \exists i (\cup_j A_j \in \P{A_i}) \op\equiv\hint{definition of $\;\P{\ldots}\;$} \exists i (\cup_j A_j \subset A_i) \op\equiv\hint{basic property of $\;\cup_\ldots\;$} \exists i \forall j (A_j \subset A_i) \endcalc$$

---

Note how this proof consists almost completely of applying definitions and basic properties, driven by our desire to reach the RHS of $\Ref{0}$.

The only step that required some "inspiration" is the key step $\Ref{*}$. But even there, the symbols --the shape of the formulas-- help to motivate this step. And so the key choice, which is to consider the set $\;\cup_j A_j\;$, is not a complete surprise anymore, as in the earlier answer. Instead it has become something that seems at least reasonable to try.

Finally, note how leaving out $\;\in I\;$ throughout makes the formulas much easier to read.

$% \endgroup %$

Answer 2

You can't prove $\forall j \in I: \big( \exists i \in I (A_j \subset A_i) \big) \rightarrow \exists i \in I: \big( \forall j \in I (A_j \subset A_i) \big)$, by contradiction or otherwise, because it's not true. (Your proof of this makes no sense. First, you have no reason for saying that $A_{j_0}\not\subset A_i$, and more important if you did know this was true it would not contradict the fact that $\forall_{j\in I}\exists_{i\in I}A_j\subset A_i$, because of the "$\exists_{i\in I}$".)

Hint for proving the implication at the top: Let $$A=\bigcup_{i\in I}A_i.$$

$\newcommand\P{\mathcal P}$

Then $A\in\P\left(\bigcup_{i\in I}A_i\right)$, so the hypothesis implies that $$A\in\bigcup_{i\in I}\P(A_i).$$So (by definition of union) there exists $j\in I$ such that $A\in \P(A_j)$.

Edit: I've been asked to explain my thought processes in defining $A$ the way I did. I don't recall what I was actually thinking at the time, but it seems fairly natural:

The hypothesis says exactly that if $A\subset\bigcup_1 A_i$ then there exists $j$ such that $A\subset A_j$. Hmm, what choice of $A$ would allow us to conclude $A_i\subset A_j$ for every $j$, given $A\subset A_j$? Oh of course, that would follow if $A_i\subset A$ for every $i$... Is there an $A\subset \bigcup_iA_i$ such that $A_i\subset A$ for every $i$?