You will probably already seen an introduction to rigorous pure mathematics: some set theory; equivalence relations; and a very brief introduction to some algebraic systems such as the integers, the rationals and the idea of a group. In particular, you will have learnt that every statement, however innocuous it may seem should be proved. There is good reason for this: mathematicians, being human, often make mistakes, and it would be such a shame to base a life-time's work on an erroneous statement made by someone else. The way to weed out any possible mistakes is to write down a watertight proof and check it carefully—and, if possible, have someone else check it for you too.
We are going to look at the mathematical subject of real analysis, and the properties of $\mathbb{R}$ and in particular the sums of infinite series and limits of sequences. This is a particularly dangerous area in the sense that it is very easy to make mistakes. In fact, it is probably true to say that mathematicians first really realised the need for modern rigorous arguments when they discovered paradoxical conclusions from less-than-perfect arguments using sequences and series.
The complexity of the logical arguments does increase when arguments
concerning convergence of sequences are involved. You should be
used to statements of the form for all $x\dots $
.
You now know that such a statement requires a proof (if it is true) or a
counter-example (if false). Similarly, a statement of the form
there exists $x$ such that $\dots $
requires an example (to show
it is true) or a proper proof (to show it to be false). In analysis, most
statements are more complicated than this, and might take the form
for all $x$ there is a $y$ such that $\dots $
or even there is $x$ such that
for all $y$ there is a $z$ such that $\dots $
, and we need
to understand and work with such statements. This is the point of the
current page.
The phrases for all $\dots $
and there exists $\dots $
will be
used so frequently that we adopt special symbols for them: $\forall $ and
$\exists $ respectively. In all cases, these symbols will be followed by
a variable, as in $\forall x\dots $ and $\exists y\dots $,
meaning for all $x\dots $
and there exists $y\dots $
.
The variable represents a mathematical object, such as a number,
and the statement that follows (here written as
$\dots $
) is typically
some mathematical property of the object represented by $x$ or $y$.
In all cases the mathematical object represented by $x$ or $y$ will
come from a domain or set; sometimes this set will be stated
explicitly, as in $\forall n\in \mathbb{N}\dots $, $\exists \beta \in \mathbb{R}\dots $, and
some cases the set is implicitly determined by the context or the name of the
variable. For example, it is probably understood that the
variable $n$ in the statement
$\forall n\left(2\text{is a factor of}n\right(n+1\left)\right)$
represents a natural number without us
explicitly saying so, as in
$\forall n\in \mathbb{N}\left(2\text{is a factor of}n\right(n+1\left)\right)$.
This is because the variable $n$ is somehow normally thought
of as ranging over natural numbers, and because the divides
relation only usually makes sense for integers or natural numbers.
Occasionally we will wish to partially specify the domain of the variable
and leave the rest of the specification to be implicit. Thus there will
be many cases where we write $\forall \epsilon >0\dots $, meaning
for all positive real numbers $\epsilon \dots $
.
Example.
The following are all mathematical statements involving quantifiers. You should check that you can read them accurately, including the (implicit or explicit) domain that the variables range over. In some cases, the statements have particularly straightforward informal alternatives in ordinary English; you should check that you see why the formal statement and the informal English one are equivalent.
There are three very important and very basic
things to note about quantifiers and variables before
we can start to use them properly. These are not really theorems, but sort of
rules-of-thumb that you must learn. (In fact, they are closer to being a kind
of mathematical way-of-life that should become completely second nature to you
by the end of this module.) I will introduce them through examples, and then
sum up each one with a moral
afterwards. It is needless to say it, but
not understanding or abiding with these rules will lead to mistakes
of the sort we are trying to avoid.
Example.
For every $x$ and every $y\ne 0$ there is a number
$x/y$.
This might be the statement $\forall x\in \mathbb{R}\forall y\in \mathbb{R}(y\ne 0\Rightarrow \exists z\in \mathbb{R}z\times y=x)$ which is true. On the other hand, the original statement in English
didn't say what the domain should be, so it might be $\forall x\in \mathbb{Z}\forall y\in \mathbb{Z}(y\ne 0\Rightarrow \exists z\in \mathbb{Z}z\times y=x)$ which is false.
Moral.
A statement with quantifiers may mean something completely different if the domains of the variables are not interpreted correctly. Changing the domain(s) may even turn a true statement into a false statement or vice versa. Forgetting to take note of the domain may lead to an incorrect proof.
Example.
The statements $\forall x\in \mathbb{R}{x}^{2}\u2a7e0$ and $\forall y\in \mathbb{R}{y}^{2}\u2a7e0$ are the same statements.
Moral.
The choice of names of variables in a statement with quantifiers is unimportant. Consistently changing a variable name with another variable name results in the same statement (provided the new name doesn't clash with an existing variable name).
Example.
The statements $\forall x\in \mathbb{R}\exists y\in \mathbb{R}x=y+1$ and $\exists y\in \mathbb{R}\forall x\in \mathbb{R}x=y+1$ are quite different statements.
Moral.
Changing the order of quantifiers in a statement with more than one quantifier of different types will usually change the meaning of the statement completely.
Any mathematical statement, in particular one involving quantifiers, will be either true or false; there are no other possibilities. Much of the work we will do will involve determining which of these two possibilities is actually the case. A true statement should be proved. (How to do this is the subject of another web page.) A false statement has to be proved false. It turns out to be much easier to turn a false statement $X$ into a true statement not-$X$ and then prove that not-$X$ is true, since the statement not-$X$ can be re-written nicely using the rules we describe in this section.
The main advantage of writing our mathematics in formal mathematical language is that we can then perform operations on the statements we get (like finding the statement not-$X$ from a statement $X$) according to simple and very general rules. These rules are quite mechanical and simple to remember. If you learn them you will be able to work with them more quickly and more accurately than you possibly could work with informal statements in English. Thus this helps you to avoid mistakes and work much faster, allowing you more time to think about the more important mathematical features of a problem. As you read this section, you should learn the rules given here, but also check you understand the reasons why they are correct. If you understand the reasons behind them, learning the rules will be much easier.
We use the sign $\neg $ to mean not
. This symbol is like a
modified minus sign, and is therefore quite suggestive of not
, so
should be easy to remember.
Rule.
If $X$ is the statement $\forall x\in AY\left(x\right)$ then $\neg X$ is the statement $\exists x\in A\neg Y\left(x\right)$.
Proof.
If $\forall x\in AY\left(x\right)$ is false then it is incorrect to say that every $x\in A$ has the property $Y\left(x\right)$. So some $x\in A$ does not have the property $Y\left(x\right)$. That is to say there is some $x\in A$ having the property $\neg Y\left(x\right)$. Conversely, if $\exists x\in A\neg Y\left(x\right)$ is true then some $x\in A$ satisfies $\neg Y\left(x\right)$ so $\forall x\in AY\left(x\right)$ is false.
Rule.
If $X$ is the statement $\exists x\in AY\left(x\right)$ then $\neg X$ is the statement $\forall x\in A\neg Y\left(x\right)$.
Proof.
If $\exists x\in AY\left(x\right)$ is false then it is incorrect to say that there is some $x\in A$ with the property $Y\left(x\right)$. So every $x\in A$ fails to have the property $Y\left(x\right)$. That is to say: for all $x\in A$, $x$ has the property $\neg Y\left(x\right)$. Conversely, if $\forall x\in A\neg Y\left(x\right)$ is true then every $x\in A$ satisfies $\neg Y\left(x\right)$ so there is no $x\in A$ satisfying $Y\left(x\right)$, i.e., $\exists x\in AY\left(x\right)$ is false.
These two rules deal conveniently with quantifiers. However a statement
may be built up from more than just quantifiers: it may involve connectives
such as and
(written as $$ or $\wedge $)
and or
(written as $\vee $)
and Implies
(written as $\Rightarrow $). Of course, if you
prefer to write the word and
, or
or Implies
in English
rather than using the symbol for it, that's fine. I will use symbols
and I present further rules to allow you to deal with these when you need to.
If $X$ is the statement $Y\wedge Z$ then $\neg X$ is the statement $\neg Y\vee \neg Z$.
If $X$ is the statement $Y\vee Z$ then $\neg X$ is the statement $\neg Y\wedge \neg Z$.
If $X$ is the statement $\neg Y$ then $\neg X$ is the statement $Y$.
The connective Implies
causes many people some trouble as they tend to
think that in a statement $A\Rightarrow B$ there should be some connection
between $A$ and $B$. (In other words, many people think that
$A$ Implies $B$ means the statement $B$ is somehow caused
by $A$ being true.) For example, If there are little green men on
Mars then it will rain tomorrow
feels like it should be false, since
the little green men on Mars don't have any control over our weather (we
hope!)
On the other hand, we will see in a moment that the mathematical interpretation
of the statement If there are little green men on
Mars then it will rain tomorrow,
is in fact true
.
Natural language behaves in a very complicated way, and in
one that is very difficult to model mathematically. Much
of the problem is that natural language is not even consistent with itself.
For example, If $1+1=3$ then I am a Dutchman
is a correct (i.e.,
true) statement using a popular idiom in English. (But the same idiom does not
work in Dutch, presumably...) So you should forget about all idea of connections
or causality between the two parts of an implication-statement such as
$A$ Implies $B$
and just concentrate on whether $A$ and
$B$ are true or false.
If
$A$ Implies $B$
only depends on whether $A$ and
$B$ are true or false it is easy to see that there
are only four possibilities, so we should be able to check each quite
quickly and hence
define what Implies
should mean in each of these four possibilities by
just looking at some examples.
$1+1=3$ Implies $2+2=6$seems to be a true implication, as the second equation is got from the first by multiplying by $2$. But both parts are false, so we define
false Implies falseto be true.
$1+1=3$ Implies $0+0=0$seems to be a true implication, as the second equation is got from the first by multiplying by $0$. But the second part is now true, so we define
false Implies trueto be true.
$1+1=2$ Implies $2+2=4$seems to be a true implication, as the second equation is got from the first by multiplying by $2$. But both parts are true, so we define
true Implies trueto be true.
$1+1=2$ Implies $2+2=6$seems to be a false implication, since we don't expect to be able to deduce any false statement from only true statements. So we define
true Implies falseto be false.
The upshot of this is that
$A$ Implies $B$
is true if
$A$ is false or if $B$ is true (or both).
$A$ Implies $B$
can only be false if
$A$ is true and $B$ is false. So for example
If there are little green men on Mars then it will rain tomorrow
is true
since there are no little green men on Mars and I don't have to be a weather
forecaster to be sure!
If $X$ is the statement $Y\Rightarrow Z$ then $X$ is equivalent to the statement $\neg Y\vee Z$. Also, $\neg X$ is equivalent to the statement $Y\wedge \neg Z$.
There is one final point to do with $\Rightarrow $ which if you remember it should stop you making the most common and most ugly errors. $\Rightarrow $ is a special logical connective joining (or connecting) exactly two mathematical statements.
This means you shouldn't
ever use it at the beginning of a sentence or the beginning of a line.
If you are ever tempted to do this, stop yourself and use the
therefore
symbol $$ instead.
Also, you shouldn't ever use it
in the form $A\Rightarrow B\Rightarrow C$. If you are tempted into this
habit then almost certainly you should be writing
$A\Rightarrow B$
and
$B\Rightarrow C$
or avoid $\Rightarrow $
altogether and write it in correct English as
$A$ implies $B$, which in turn implies $C$
.
Note that
$A$ implies $B$ implies $C$
isn't even
grammatically correct English.
All of these rules reduce the problem of negating a mathematical
statement to negating their innermost atomic
parts. We presume you
know how to do that. For example, if $x$ and $y$ are
variables representing real numbers then $\neg x<y$
is the statement $x\u2a7ey$. Similarly $\neg \left|x\right|<\epsilon $
is the statement $\left|x\right|\u2a7e\epsilon $.
Example.
The statement that a sequence $\left({a}_{n}\right)$ converges to a limit $l$ is
So the statement that the sequence $\left({a}_{n}\right)$ converges to some limit is
And, using the rules in this web page, the statement that the sequence $\left({a}_{n}\right)$ does not converge to any limit is
The last example is particularly important. Try to follow it in detail, and take plenty of time over this. If you can follow the details you will not have to learn them by rote. (Learning by rote, i.e. without understanding, is to my mind the last resort and is always dangerous because it is easy to make an error. But if you can't follow the arguments you will have to learn the last example and many more like it.)
With all of this background you are in good shape to understand
and work with statements in
analysis such as the sequence $\left({a}_{n}\right)$ tends to $l$
as $n$ tends to infinity
. The next step is to learn how to prove
(and disprove) such statements. That's the subject of the
next web page.