Logic for analysis: statements

1. Introduction

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 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 . 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 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 or even there is x such that for all y there is a z such that , and we need to understand and work with such statements. This is the point of the current page.

2. Quantifiers

The phrases for all and there exists will be used so frequently that we adopt special symbols for them: and respectively. In all cases, these symbols will be followed by a variable, as in x   and y   , meaning for all x and there exists y . The variable represents a mathematical object, such as a number, and the statement that follows (here written as ) 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 n   , β   , 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 n   ( 2  is a factor of  n ( n + 1 ) ) represents a natural number without us explicitly saying so, as in n   ( 2  is a factor of  n ( n + 1 ) ) . 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 ε > 0   , meaning for all positive real numbers ε .

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.

  1. x   x 2 0 , the square of any real number is nonnegative
  2. x   y   x + y = 0 , every real number has an additive inverse
  3. e   y   e - y y , there is no identity for the operation - on the reals
  4. ε > 0   N   n > N   | a n | < ε , the sequence ( a n ) is a null sequence.
  5. ε > 0   N   n > N   | a n - l | < ε , the sequence ( a n ) converges to the particular number l .
  6. l   ε > 0   N   n > N   | a n - l | < ε , the sequence ( a n ) tends to some limit.

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 0 there is a number x / y . This might be the statement x   y   ( y 0 z   z × 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 x   y   ( y 0 z   z × 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 x   x 2 0 and y   y 2 0 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 x   y   x = y + 1 and y   x   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.

3. Negations

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 ¬ 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 x A   Y ( x ) then ¬ X is the statement x A   ¬ Y ( x ) .

Proof.

If x A   Y ( x ) is false then it is incorrect to say that every x A has the property Y ( x ) . So some x A does not have the property Y ( x ) . That is to say there is some x A having the property ¬ Y ( x ) . Conversely, if x A   ¬ Y ( x ) is true then some x A satisfies ¬ Y ( x ) so x A   Y ( x ) is false.

Rule.

If X is the statement x A   Y ( x ) then ¬ X is the statement x A   ¬ Y ( x ) .

Proof.

If x A   Y ( x ) is false then it is incorrect to say that there is some x A with the property Y ( x ) . So every x A fails to have the property Y ( x ) . That is to say: for all x A , x has the property ¬ Y ( x ) . Conversely, if x A   ¬ Y ( x ) is true then every x A satisfies ¬ Y ( x ) so there is no x A satisfying Y ( x ) , i.e., x A   Y ( x ) 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 ) and or (written as ) and Implies (written as ). 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 Z then ¬ X is the statement ¬ Y ¬ Z .

If X is the statement Y Z then ¬ X is the statement ¬ Y ¬ Z .

If X is the statement ¬ Y then ¬ X is the statement Y .

4. Implication

The connective Implies causes many people some trouble as they tend to think that in a statement A 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.

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 Z then X is equivalent to the statement ¬ Y Z . Also, ¬ X is equivalent to the statement Y ¬ Z .

There is one final point to do with which if you remember it should stop you making the most common and most ugly errors. 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 B C . If you are tempted into this habit then almost certainly you should be writing A B and B C or avoid 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 ¬ x < y is the statement x y . Similarly ¬ | x | < ε is the statement | x | ε .

Example.

The statement that a sequence ( a n ) converges to a limit l is

ε > 0   N   n   ( n N | a n - l | < ε )

So the statement that the sequence ( a n ) converges to some limit is

l   ε > 0   N   n   ( n N | a n - l | < ε )

And, using the rules in this web page, the statement that the sequence ( a n ) does not converge to any limit is

l   ε > 0   N   n   ( n N | a n - l | ε )

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.)

5. Conclusion

With all of this background you are in good shape to understand and work with statements in analysis such as the sequence ( a n ) 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.