# His Dark Materials

My material has finally arrived for my next module.

Only 2 DVDs, 9 audio CDs, 25 Booklets, a large assignment to complete every month, plus countless exercises.

No problem...

: /

# PENS DOWN!

So that's it! The Summer has ended!

How far has my extra study got me? Well I've managed to get through around 120 pages of "How To Prove It" by Velleman, and have generated just over 70 double-sided pages of A4's worth of exercises from the book. Not bad for an extra-curricular topic!

This book has helped me loads. It's succeeded in taking away a lot of the mystery involved in reading and writing proofs.

Every topic in the book up until now has flowed well, and allowed me to think about solutions to the various problems fairly naturally. What I mean by that is, I never became absolutely stuck and unable to answer a question.

Having said that, the sub-topic I'm finishing on is proofs involving quantifiers. This is the one area in which I'll admit I've been struggling. At this point in the book, I've learned so much about the number of ways in which to decon/reconstruct a problem that any possible method by which to prove a theorem has actually become less obvious.

Here's an example of how convoluted the scratch work of a basic proof has become. Here's question 14 from p.122:

Suppose  $\{A_i\: |\: i \in I\}$ is an indexed family of sets. Prove that $\cup_{i \in I} \mathscr{P} (A_i) \subseteq \mathscr{P}(\cup_{i \in I} A_i)$.

It's a short question, but this immediately looks like a nightmare to a beginner like myself. We've got a mix of indexed sets, a union over them, and power sets.

First off I need to properly understand the damn thing. Seems sensible to draw up an example using the theorem...

Let's say $I$ is $\{1,2\}$. So we've got $\{A_{1},A_{2}\}$.

Now let's say that $A_1 = \{1,2\}$ and $A_2 = \{2,3\}$.

Looking at the LHS of the thing I need to prove, it's actually pretty easy to break down:

$\mathscr{P} (A_1) = \{ \varnothing, \{1\}, \{2\}, \{1,2\}\}$

$\mathscr{P} (A_2) = \{ \varnothing, \{2\}, \{3\}, \{2,3\}\}$

Which means that the union of all the elements of the power sets of $A_i$ is:

$\cup_{i \in I} \mathscr{P} (A_i) = \{ 1,2,3\}$

A little half-way recap: the theorem says that in my example, $\{1,2,3\}$ should be equal to, or be a subset of $\mathscr{P}(\cup_{i \in I} A_i)$ (the RHS).

Let's see if that's true shall we?

Within the parenthesis of the RHS we've got $\cup_{i \in I} A_i$. So this is the union of all elements of all indexed sets. In this example:

$\cup_{i \in I} A_i = \{1,2,3\}$

Only thing missing now is the power set of this:

$\mathscr{P}(\cup_{i \in I} A_i) = \{ \varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$

And there we go. Now I understand exactly what the theorem means. $\cup_{i \in I} \mathscr{P} (A_i) \subseteq \mathscr{P}(\cup_{i \in I} A_i)$, in this specific example, turns out to be :

$\{1,2,3\} \subseteq \{ \varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$

which is obviously true. Theorem understood. Achievement unlocked. Tick.

As recommended by Velleman, I'll also try to construct the phrasing of the proof along-side the scratch work as I go. Like so:

Suppose a thing is true that will help to prove the theorem.

[Proof of theorem goes here]

Thus, we've proved the theorem.

Okay, let's start.

The theorem means that if $x \in \cup_{i \in I} \mathscr{P} (A_i)$ then $x \in \mathscr{P}(\cup_{i \in I} A_i)$. So one thing implies the other. We can then class $\cup_{i \in I} \mathscr{P} (A_i)$ as a "given", and aim to prove $\mathscr{P}(\cup_{i \in I} A_i)$ as a "goal". So blocking out our answer:

Suppose that $x \in \cup_{i \in I} \mathscr{P} (A_i)$.

[Proof of $x \in \mathscr{P}(\cup_{i \in I} A_i)$ goes here]

Thus, $\cup_{i \in I} \mathscr{P} (A_i) \subseteq \mathscr{P}(\cup_{i \in I} A_i)$.

So let's start analysing $\cup_{i \in I} \mathscr{P} (A_i)$, remembering not to go too far with the logical notation. With baby steps, the definition of a union over a family of sets (here, the outer-most part of the logic) is:

$\exists i \in I (x \in \mathscr{P}(A_i))$

Then, going one step further, using the definition of a power set:

$\exists i \in I (x \subseteq A_i)$

Now we could go further at this point, applying the definition of a subset, but I'll stop the logical deconstruction here. In this instance, I've found that if I keep going so the entire lot is broken down into logical notation it somehow ends up getting a bit more confusing that it needs to be.

With this as our given, I notice the existential quantifier. Here, I can use "existential instantiation" to plug any value I want into $i$ and then assume that what follows is true. So at this point the new "given" is simply:

$x \subseteq A_i$

Nice and simple.

Let's update the outline of our proper proof answer:

Suppose that $x \in \cup_{i \in I} \mathscr{P} (A_i)$.

Let $i \in I$ be such a value that $x \subseteq A_i$.

[Proof of $x \in \mathscr{P}(\cup_{i \in I} A_i)$ goes here]

Thus, $\cup_{i \in I} \mathscr{P} (A_i) \subseteq \mathscr{P}(\cup_{i \in I} A_i)$.

So let's now move on to our "goal" that we have to prove: $\mathscr{P}(\cup_{i \in I} A_i)$.

Again, starting from the outside, going in,

$x \in \mathscr{P}(\cup_{i \in I} A_i)$

by the definition of a power set becomes:

$x \subseteq \cup_{i \in I} A_i$

I can't do a lot with this on it's own so I'll keep going with the logical deconstruction. By the definition of a subset, this becomes:

$\forall a (a \in x \to a \in A_i)$

So now, using "universal instantiation" I can say that here, $a$ is arbitrary (for the sake of argument, it really can be anything), and that leaves us with an updated "givens" list of:

$x \subseteq A_i$
and
$a \in x$

and a new "goal" of

$a \in A_i$

Hey, but wait a sec... Look at our "givens"! If $a$ is in $x$... and $x$ is a subset of $A_i$, then $a$ must be in $A_i$! -and that's our goal!

So update our proof:

Suppose that $x \in \cup_{i \in I} \mathscr{P} (A_i)$.

Let $i \in I$ be such a value that $x \subseteq A_i$.

Let $a$ be an arbitrary element of $x$.

[Proof of $a \in A_i$ goes here]

Therefore $a \in \cup_{i \in I} A_i$. As $a$ is arbitrary, we can conclude that $x \in \mathscr{P}(\cup_{i \in I} A_i)$.

Thus, $\cup_{i \in I} \mathscr{P} (A_i) \subseteq \mathscr{P}(\cup_{i \in I} A_i)$.

So let's wrap this up.

Theorem:
Suppose  $\{A_i\: |\: i \in I\}$ is an indexed family of sets. Prove that $\cup_{i \in I} \mathscr{P} (A_i) \subseteq \mathscr{P}(\cup_{i \in I} A_i)$.

Proof:
Suppose that $x \in \cup_{i \in I} \mathscr{P} (A_i)$. Let $i \in I$ be such a value that $x \subseteq A_i$, and let $a$ be an arbitrary element of $x$. But if $a \in x$ and $x \subseteq A_i$, then $a \in A_i$. Therefore $a \in \cup_{i \in I} A_i$. As $a$ is arbitrary, we can conclude that $x \in \mathscr{P}(\cup_{i \in I} A_i)$. Thus, we conclude that $\cup_{i \in I} \mathscr{P} (A_i) \subseteq \mathscr{P}(\cup_{i \in I} A_i)$. $Q.E.D.$

Overall the task has involved unravelling the symbols into logic, making sure they flow together, and then wrapping them back up again.

See what I mean by convoluted? All that work for that one short answer. I must admit, I still don't know if my reasoning is 100% correct with this. Despite some parts of this seeming simple, this really is the very limit of what I'm capable of understanding at the moment. I picked this example to write up, as so far I've found it to be one of the most complicated.

The next section of the book seems to marry this quantifier work with another previous section about conjunctions and biconditionals, that I found to be quite enjoyable at the time. Then towards the end of the chapter, Velleman seems to sneak in some further proof examples using the terms epsilon and delta. I imagine this is a sneaky and clever way to get the reader comfortable with further Analysis study...

Alas, my study of Velleman's book will have to stop here. I understand a lot more than I did, though not everything there is to know. I feel it may be enough to give me a slightly smoother ride through my next module, which was the whole point of me picking this book up. It's been so good, I hope I have a chance to return to it. I feel later chapters would put me in an even better position for further proof work!

For now... the countdown begins for the release of my next module's materials!