Category Archives: Proofs

PENS DOWN!

September 4, 2016 Adrian 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!

Proofs, Text Books

Things you need to be told at the beginning

July 12, 2016 Adrian Leave a comment

These quotes are from pages 89 and 90 of Velleman's "How To Prove It". If only I'd read all this when I was first introduced to a proof, I wouldn't have been so stressed!

"When mathematicians quote proofs, they usually just write the steps needed to justify their conclusions with no explanation of how they thought of them."

"Although this lack of explanation sometimes makes proofs hard to read, it serves the purpose of keeping two distinct objectives separate: explaining your thought processes and justifying your conclusions."

"The primary purpose of a proof is to justify the claim that the conclusion follows from the hypotheses, and no explanation of your thought processes can substitute for adequate justification of this claim. Keeping any discussion of thought processes to a minimum in a proof helps to keep this distinction clear."

"Don't worry if you don't immediately understand the strategy behind the proof you are reading".

I could hug this book right now.

Bertrand Russell, Books, Proofs, Text Books

End of the Quantifiers

July 7, 2016 Adrian Leave a comment

A month and a week, and I've just come to the end of the second chapter. Reasonably happy with the progress, but I could be going a bit quicker... Mind you, over just two chapters I've now created 46 pages of A4 of exercises. So there has been a LOT of material to go through. Frankly, just these first two chapters have worked wonders for my understanding of logic and what proofs are founded upon.

This second chapter mainly introduced quantifiers. The concept of "for all x" and "there exists at least one x...", but quickly branched off into more involved set theory.

The biggest issue I had towards the end of the second chapter was that on a couple of occasions, I don't think I thought carefully enough about the kind of answer the questions required. ie: in this context, whether the answer was required in logical notation, or whether it was required in set theory notation. Translating between the two is something I certainly found tricky. As such, I decided to write my own definitions of notation in the form of a list (thanks Lara Alcock!). Though the lack of lists of definitions could be considered a slight shortfall of the book, I think I benefited from constructing my own notes and definitions.

I found that towards the end of the questions (because of the more lengthy logical notation) I was concentrating more on the definitions than what the notation actually meant. Not convinced this is so good for the learning process, but at least I'm mindful of it now.

Last little question the second chapter covered was Russell's Paradox, as discovered by Bertrand Russell in 1901. The fact that I'm being introduced to stuff like this in the second chapter is pretty cool. Very enjoyable!

Next up, proof technique!

Books, General, Proofs

The Joy Of Sets

May 31, 2016 Adrian Leave a comment

54 pages, and 5 large exercise sections later, I've finally finished the first chapter of "How To Prove It". With the first chapter being about sentential logic, I've now covered truth tables, derivations of logical operations, set theory, and the conditional and bi-conditional connectives.

The next chapter covers further foundational logical concepts and only in Chapter 3 are the intricacies of actual proofs discussed. Having taken this long to cover the first chapter, and looking at the amount of paper I've used to do all the exercises so far, I'm not that surprised I was finding proofs so difficult. It turns out my intuition was right, I was missing a lot of foundational knowledge.

So far, it's all been going well. Nothing I've looked at in this first chapter has left me mystified and overall I feel like I'm learning. This is exactly where I wanted to be... Just need to up the pace, perhaps...

Proofs, Text Books

Books For Understanding Books - Part 2

April 4, 2016 Adrian Leave a comment

So this is getting ridiculous. I know, I can only apologise. I'll write some maths on here at some point, I promise.

It turned out that the super-valuable forum post I had on the OU forums has now been deleted. Apparently if a post isn't pinned it gets auto-nuked after two months. So now all that valuable information is gone.

But let's not dwell on it. Especially when there's a new book looming!!!!!

howToProveIt

Now, despite the fact that I've read Lara Alcock's books about how to learn Analysis, and started Brannan's Analysis book (see earlier posts) I realised I was missing more foundation-level knowledge. How To Prove It by Daniel J. Velleman looks like it'll be the book to give it to me. I remember it as being recommended on the deleted forum post, and the reviews generally are very very positive.

Already I've come to the end of the first (admittedly short) section and I can actually attempt all of the exercises! I totally understand everything he's saying and I really feel like I'm learning something with every page. At last!

More of a proper review of this on the way, but for the moment I'll be nose-deep in this for the next couple of months...

Analysis, General, Proofs

Readjusting Learning Methodologies

November 18, 2015 Adrian Leave a comment

I've just finished reading Lara Alcock's book on how to learn about Analysis. Or rather, I've finished reading the first part, and the part on the real number system.

Overall, the book has led me to reconsider my current learning technique. So much so, I've compiled a list of steps to follow depending on whether I read about a new definition, theorem or proof.

In turn, this has made me realise I may benefit from starting my main book on Analysis again from the beginning, but applying these new steps as I go. After all, I am still only at the beginning (kind of), and I don't have any kind of deadline looming over me (which is really nice). Overall it seems like the perfect opportunity to try out some new learning methodologies!

Out of the handful of additions, there are two really big changes for me.

The first being mind maps. As I go through my Analysis, I'll be creating a mind map of concepts, seeing how one builds on another. I'd tried to use mind maps before at university and they'd largely proved completely useless. Here, however, mind maps appear to offer a perfect way to visualise the building of concepts into larger concepts. Here's the beginning of my first mind map!

I'm using draw.io as the tool of choice. It seems flexible enough for what I need it for, it can save as XML, and it supports mathematical notation! (mathjax latex formatting I believe)

The second big change to my learning involves learning by self-explanation. This technique, mentioned in Lara Alcock's book, appears to be one of the key processes involved in truly understanding and appreciating Analysis. You can find out more about self-explanation training from Loughborough University's Mathematics Education Centre website. My difficulty here will lie in concentrating on actually doing self-explanation, rather than just paraphrasing (turns out, it's a very easy trap to fall in). So long as I do it regularly enough, self-explanation will be more likely to come to me naturally.

Expected result: More effective learning and better notes!

Maths, Proofs

Reading Mathematics

October 25, 2015 Adrian Leave a comment

Still working through my book on Analysis (which I will be until July 2016, so I should probably stop mentioning it...), but I recently came across another proof that I had difficulty understanding. I had to reach out to the mathematics forums in the end, but after getting a reply and working through some further steps that they mentioned, everything fell into place.

I felt really good that I'd finally understood the proof, but I also tried to work out what I could've done to push for that answer myself (so hopefully next time, I won't have to post a question to the forum).

I realised that I might not be reading through the mathematics effectively enough. After reading through Lara Alcock's book I realised how important it is to make effective notes whilst reading through "all the symbols". When reading through proofs I have this nasty habit of reading them like a novel, keeping this story of logic in my head... and then very quickly becoming confused because I didn't see how you could logically progress from one sentence to another.

This sounds really simple, and almost obvious, but I think all it really takes is to sit down with a pen and go through the mathematics of the proof in gritty detail, liberally re-arranging things as you go. It's worth mentioning that this is perhaps quite a different act than just "taking notes".

Being completely confounded by something only to solve the issue entirely on your own is enormously satisfying. The hope is that if I stay mindful and remain aware as to when to write the right kinds of notes, not only will I be able to solve more complicated problems on my own, but also in time these seemingly large logical steps will become second nature.

Anyway, doing independent reading of mathematics is proving, generally, to be really satisfying. Let's see if I can become a more effective reader...

Analysis, Maths, Proofs

Proof of Inequalities by Mathematical Induction

October 2, 2015 Adrian Leave a comment

Still reading though my book in Analysis, I've come across a section on proving inequalities. I'm glad to say that all of this made sense... until I reached a sub-section on proving an inequality by mathematical induction.

As I've written previously, I find that proofs are notoriously unintuitive. In the past however, I have been particularly puzzled by the logical steps involved in proving an inequality by mathematical induction.

To explain my difficulties, let's have a look at the example provided in the book:

Prove that $2^n \geq n^2$ , for $n \geq 4$ .

If we're proving this by mathematical induction, we generally follow these steps:

Let $P(n)$ be the statement $2^n \geq n^2$ .
Show that $P(4)$ is true.
Assume that $P(k)$ is also true for $k \geq 4$ .
Show that $P(k) \Rightarrow P(k+1)$ . Or rather, show that if $P(k)$ is true, then $P(k+1)$ is also true.

Step 4 is the key step here in the proof as it shows that if any number is true, and the next number is also true, then you can apply this rule forever, and your original statement must be true for all numbers!

Anyway, lets jump to step 2. Show that $P(4)$ is true. Well if $n=4$ , then $2^4 = 16$ and $4^2 = 16$ . So $P(4)$ is true! Easy.

Let's look at step 3. Let's ASSUME that $P(k)$ is true for some $k \geq 4$ .

Now, this is the part that caught me by surprise... At this step, the text in the book reads as follows:

"So, we are assuming that $2^k \geq k^2$ . Multiplying this inequality by 2 we get:

$2^{k+1} \geq 2k^2$

,

so it is therefore sufficient to prove that $2k^2 \geq (k+1)^2$ ."

Wait, what? How is it that all of a sudden, all we need to prove is that $2k^2 \geq (k+1)^2$ ? This isn't explained explicitly in the text so I had to close the book and do a bit more thinking.

First thing I had to realise here is that the "Step 4" I've listed above requires a bit more detail... What you're actually trying to do is show that you can progress naturally from $P(k)$ to $P(k+1)$ . ie: We should be able to show that we can progress naturally from:
$2^k \geq k^2$
to:
$2^{k+1} \geq (k+1)^2$ .

Now, if we multiply $2^k \geq k^2$ by 2, as mentioned in the text, we do arrive at:
$2^{k+1} \geq 2k^2$

This is good, as we've managed to get the $2^{k+1}$ we were looking for on the left-hand side of the inequality. But the right-hand side looks nothing like the right-hand side of $P(k+1)$ ie: $(k+1)^2$ .

Here's the key though... It doesn't matter they they're not the same. We only need to see how $2k^2$ and $(k+1)^2$ relate to each other. Look back at Step 3. Part of this assumption is that $k \geq 4$ . Just as a test, let's try $k=4$ :

$2k^2 = 2 \times 4^2 = 32$
and
$(k+1)^2 = (4+1)^2 = 25$

Well this is interesting. It's looking as if $2k^2 \geq (k+1)^2$ . This is exactly what was written in the text!

But to really ram it home, what we really have now is the following:

$2^{k+1} \geq 2k^2 \geq (k+1)^2$

So.... this show us that IF we can prove that last bit $(2k^2 \geq (k+1)^2 )$ is true for all $k \geq 4$ , and not just $k=4$ we have managed to prove that we can get from $P(k)$ to $P(k+1)$ !!! This is exactly why the text in the book said "so it is therefore sufficient to prove that $2k^2 \geq (k+1)^2$ ."

I'm sure in future I'll jump on this immediately and say "oh yes, of course that's all we need to do now", but working through the derivation of why it was sufficient was extremely useful. Long-winded... but useful.

Ah, the learning process...

Books, Proofs, Text Books

How To Study For A Mathematics Degree

August 22, 2015 Adrian

After my third module, completed in June 2005, I realised that although I enjoyed the module immensely, I still wasn't entirely happy with my ideas behind how to present proofs. Apparently this is a common problem. The shift from normal arithmetic to proofs is a jump that a lot of students find difficult.

I was so bothered by it I decided to post a query on the Open University forums about further reading. Part of my post read:

"...[I] consistently struggle with all kinds of proofs. I either start off completely incorrectly, or have no idea where to even begin."

The response was amazing, everyone (including more advanced students) agreed with me on the difficulty proofs and the shift of mindset required, and I now have a sizeable reading list to work through!

One of the books suggested in the forum was How To Study For A Mathematics Degree by Lara Alcock. I've tagged this post as being about a text book, but only because it's certainly more of a text book than a pop(ular) book. Although pitched at students that have just finished their A-levels and are about to start at university for the first time, I thought I may benefit from picking it up.

I came away with some good notes as to how to adjust my learning slightly, and she talked a lot about the basics of proofs and how to acclimatise yourself to them. One of the parts that I feel was key was the realisation that I can try to construct premises and conclusions in terms of definitions. "Starting with the definitions" seems so obvious in retrospect, but when shown something so unfamiliar it can be difficult to align your brain so as to give yourself a solid starting point. Outlining all the definitions you might need gives you that solid starting point. I'll be keeping all this in mind as I start through my first text book...

Another section I benefited from was a section on how to reading mathematics. Or rather, how to benefit whilst reading mathematics. After spending three years of reading mathematics and feeling I've so far done a pretty good job, but Lara introduced some thoughtful comments on note-taking and comprehension. Again... I'm looking forward to applying this when sifting through my next text book.

As good as the book was, I must say I didn't benefit much from the second part on "Study Skills", but this section was only about 80 pages long. The section covers what "university life" is like, and how best to be a student in such an environment. If you've already been to university it'll be of limited use, but if you're straight out of your A-levels it could make for quite an insightful read.

All in all I feel I took away from it what I wanted to take away; that is a base understand of how to approach proofs in a more structured way. At the very least, I now have a starting point!

Group Theory, Maths, Proofs

Year Three

August 15, 2015 Adrian

My third module, completed last June, took me by surprise. As I'd started my statistics In February 2014, and completing in September 2014, I was hoping for a nice break before starting this third module.

The module I needed to take was MS221, rather innocently called "Exploring Mathematics". However, it transpired that the class that would be starting in September 2014 was to be the last ever of MS221. Normally this wouldn't be a problem, but MS221 followed on directly from material presented in my first module, and I was told I had to take this course. If I waited to take the replacement course I would face a ton of catch-up material .

So in summary, due to the slight course re-structure, I ended up not stopping to have a break between my second module and my third. This meant I was studying non-stop from February 2014 to July 2015. Exhausting.

I did manage to take a long holiday at the beginning of 2015, but tried to make sure I was several weeks ahead of my study before doing so.

Although "Exploring Mathematics" sounds rather unassuming, it covered some rather in-depth topics. On the one hand I was presented with proof by mathematical induction (which only proved itself to be baffling) but on the other I was also presented with group theory which describes a really nice formal form of symmetries. Seriously cannot wait to learn more about group theory...

Once July arrived, and I had taken my final exam I was once again a free man. Finally free to enjoy a Summer.

So that brings us up to date! I'm now enjoying my first proper break away from mathematics in 17 months, and the materials for my next module are due to arrive in under a month!

…is learning mathematics.