Proofs, Text Books

PENS DOWN!

2 Comments

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!

2 thoughts on “PENS DOWN!”

  1. In your example, you computed the right-hand side correctly, but not the left-hand side. The left side is:
    union, for i in I, of P(A_i) = P(A_1) U P(A_2)
    = {empty set, {1}, {2}, {1, 2}} U {empty set, {2}, {3}, {2, 3}}
    = {empty set, {1}, {2}, {3}, {1, 2}, {2, 3}}.
    This is a subset of the right-hand side, which includes all the same elements, plus two more: {1, 3} and {1, 2, 3}.
    Your answer for the left-hand side was an *element* of the right-hand side, but not a *subset* of it.
    Your proof is correct!

    1. Thank you Dan!

      How nice of you to comment on this!

      Yes, I see now! When dealing with sets of sets, it seems it's far too easy for me to fall into the trap of mixing up elements and subsets. I'll have to be more mindful in future!

      I suppose something else that tripped me up was the use of "x" as both an element and a subset within my notation. Maybe it would pay for me to use distinct variable names...

      Thanks again! 🙂

Leave a Reply