We have seen how to write down statements concerning the convergence
of sequences in a previous web page.
We now look at how such statements may be proved. You will also learn
how to disprove such statements here, as to disprove a statement
The objective is to give you a number of rules-of-thumb that will enable you to write down such proofs in as painless a way as possible. I will follow these rules in all the examples I do in this course, and you may use them in this course and in any other you do in this university.
Many of the rules-of-thumb for writing down proofs are plain common sense and are exactly the sort of thing you were learning last term in the first part of this module. For example, it is important to learn to argue forwards, starting with the assumptions and ending with the conclusion. Or at least that is how the finished proof should look. Of course it is not always easy to write the proof out straight away in this way, so I suggest:
Rule.
Write all the assumptions you are allowed to use at the top of a blank sheet of paper, and write the conclusion you want to reach at the bottom. Now fill in the space in between, either by arguing forwards (working from the top downwards), or by simplifying the required conclusion (working from the bottom upwards), or a combination of these.
Much of the initial part of proof-writing involves working out what the assumptions and conclusion actually mean. This may not be easy, and is certainly part of the exercise, so don't try to skip this step. In fact, if you do it right it really will help you in the next part of proof-writing.
Rule.
Use the definitions to re-write the assumptions and conclusion in a proof into other forms that are easier to deal with.
That presumes you have learnt the definitions, or at least have them to hand. Occasionally a new definition may be given as part of a question, and you would be expected to read and use it.
One of the most common ways of writing proofs, is to use proof-by-contradiction or reductio ad absurdum. This allows you to make a brand new assumption and prove it wrong by getting a contradiction.
Rule.
In a proof you are allowed to make a new assumption (that must be clearly labelled as such) and prove it wrong by getting a contradiction from it. (This part of the proof could be called a subproof. It too should be clearly identified.) If successful, the assumption and subproof together prove the negation of your original assumption.
Example.
There are infinitely many primes.
Proof.
We use reductio ad absurdum.
Subproof.
Assumption: suppose there are finitely many primes
_{1,}
_{2,,}
_{ }
Subproof.
Then we may form the product of these primes
_{1}
_{2 }
_{ }
_{1,}
_{2,,}
_{ }
_{}
_{1,}
_{2,,}
_{ }
And so we get a contradiction.
Therefore there are infinitely many primes.
I shall indicate subproofs by indenting the text like this, and sometimes
with a vertical line down the left margin where the indent is. It is important to
indicate such subproofs somehow because you are not allowed to use any statement
proved in a subproof once the subproof has finished. The reason for this is
that any such statement may depend on an erroneous assumption such as
there are only finitely many primes
.
The real joy about breaking proofs into subproofs (like we did for reductio ad absurdum above) is that statements involving quantifiers become much easier to prove using subproofs. In fact the statements actually tell you the form the proof must take, and once you have written this down there is usually only one or two more lines to write down before the proof is finished.
There are two rules here to learn, one involves a statement with
the
Rule.
Suppose you wish to prove a statement of the form
(
(
Letand in a subproof prove thatbe an arbitrary element of
(
It is important that you use a new letter not used up to this point
in the proof. So if
(
Rule.
Suppose you wish to make use of an assumption
that you have, where (
(
is a property that Let
and prove your conclusion from this assumption and your
other assumptions.(
Once again, it is essential to use a brand new letter that
hasn't been used before. Feel free to choose whatever you like.
Purists would say that you should introduce a subproof for
this
The connective and
rarely causes problems.
If we know
On the other hand, or
can occasionally be awkward. The difficulty
is that if we are trying to prove
Rule.
The point is, by making the assumption
is going to be true then it had better
be the part that is true.
Rule.
A variation on this is proof by cases. Here we make an assuption
that some statement holds and show that this gives us our required
conclusion, and then show that the assumption
Rule.
Since we saw that an implication
or
statement,
Rule.
It is potentially more difficult to show a sequence does not converge to any limit than it does converge. This is because there is an extra quantifier involved (because we need to consider all possible limits).
Example.
The sequence (_{ ) } defined by _{ =(-1) } does not converge to any limit.
Proof.
Remark.
I will sometimes make remarks written like this inside proofs: they are not part of the proof but are just comments indicating some feature of the proof or how I was thinking about it. They are not necessary for a correct proof, and could be deleted completely, but are provided to help you understand it better.
Remark.
Subproof.
Let
Remark.
We now need to define a suitable
Subproof.
Define
Remark.
We now want to prove a statement starting
Subproof.
Let
Remark.
We must find a suitable
Subproof.
Define
Subproof.
Subproof.
In both cases we have shown
So
So
So
This proof is complicated to write down fully, but the idea of taking best
embedded
reductio ad absurdum inside the proof
where we had assumed both