Common logical pitfalls when learning to write mathematical proofs

Mathematics is needed in many scientific disciplines, even though it’s used in somewhat different ways in them. A theoretical physicist usually has to study not only applied math, but also some pure mathematics which involves logical proofs of statements. A mechanical engineering student can usually do without anything containing formal logic and such, but has to learn basic differential equations, volume integrals and similar methods of applied mathematics. Chemistry and biology students also benefit from mathematical knowledge (at least one has to be able to solve a quadratic equation before one can calculate reactant and product concentrations from an equilibrium constant of a chemical reaction).

Rigorous logical thinking is not something that a human being has a natural instinct for (just as the concept of inertia and the Newton’s 1st and 2nd laws are not obvious from everyday earth-bound experience). Let me list some of the most usual logical errors that a beginner does when trying to learn to prove mathematical statements.

1. Inappropriate reversal of an implication

It is easy to see that if x = 3, then also x^2 = 9. But the reversal is not true – if x^2 = 9, we don’t necessarily need to have x = 3, as it could also be -3. Even the statement x^3 = 27 does not mean that x = 3, if we allow for the possibility that x is a complex number (can you find the points on complex plane that solve this equation?).

A more obvious way to demonstrate this is to say that the statement x = 3 implies x \in \mathbf{N} but not every natural number is 3.

To avoid doing this kind of logical errors, make sure that you never start proving a statement by assuming that it is true. In fact, any logical statement can be “proved” if you assume things that contradict each other – it is logically correct to say that “If the Moon is made of cheese and it’s not made of cheese, then also cows are able to fly.”

2. Playing with something that does not exist

Sometimes it seems possible to prove that an object X has properties A, B and C, but after some more thinking you find out that X doesn’t even exist at all. You may have seen some Youtube videos where a math teacher proves something like 1 + 2 + 3 + 4 + \dots = -\frac{1}{12}, which is an absurd statement as the sum on the left side of the equality does not converge, but it is possible to make it look like true if you take a liberty to divide the integer terms into many pieces (with different signs) and rearrange them as you want.

Actually, the terms of a sum with an infinite number of terms can’t be arbitrarily rearranged even in all cases where the sum converges.

3. Assuming without proof that something is unique

This is what we already did in case 1, by assuming that x^2 = 9 implies x=3. There are also some more obviously crazy results that can be made by doing this mistake. One example is to use De Moivre’s formula

e^{iz} = \cos z + i\sin z,

to show that e^{0} = e^{2\pi i}, and then take the natural logarithm of both sides of this equation to “show” that 0 = 2\pi i. The problem with this logic is that the complex logarithm function is not single valued – there is an infinite number of complex numbers that can be called logarithm of a given complex number.

4. Assuming that an infinite set contains everything

I remember seeing in some book a historical claim that the ancient Greeks tried to prove that there is only a finite number of types of an atom in the following way: “If there were an infinite number of different kinds of atoms, there would exist atoms of all possible sizes, and then some of them would have to be large enough to be visible which is not true as we have never seen an individual atom”. This, of course, is poppycock, as we can also say that there is an infinite number of integers that are divisible by 2, but that set still does not contain the number 5.

There are many other ways to do logical errors by making false assumptions about infinity. For one thing, the above mentioned set of even integers is “just as infinite” as the set of all integers, even though it may seem to contain half as many numbers. The set of real numbers is “more infinite” than the set of natural numbers, which you will learn to prove if you study the concept of cardinality and injective/surjective/bijective mappings.

Advertisements

Random Numbers in Computation

When doing numerical simulations on a computer, there is often a need for “random” numbers, The most important application where they are needed is probably Monte Carlo simulations, which are used for things like computing approximate ground state wavefunctions and energy eigenvalues for quantum systems, and the calculation of position- and direction-dependent light intensity functions in an optical system where emission, reflection and absorption of light takes place.

The fact about these random numbers is that they are actually not random at all, and should be described as pseudorandom numbers. A digital computer works deterministically, which means that the same input always produces the same result. This situation might change when quantum computing becomes more commonplace. Those who have studied quantum mechanics may remember that if we have a quantum observable (some measurable quantity) A that has eigenstates \left|a\right> and \left|b\right> corresponding to eigenvalues a and b, and we prepare the quantum system to a state

\left|\psi\right> = \left|a\right> + \left|b\right>

(or more generally any state \left|\psi\right> = e^{i\alpha}\left|a\right> + e^{i\beta}\left|b\right> where \alpha and \beta are real numbers), and measure the value of the observable A in this state, the result of the measurement can be a or b with equal probabilities, otherwise being completely random. Here randomness means that it’s not possible to know beforehand which one of the possible values is obtained in any particular repetition of the experiment.

When one sees the sequence a_n with

a_0 = 0,a_1 = 1, a_2 =2, a_3=3, a_4=4 \dots

it seems to be intuitively obvious that it is not something we’d call random, as every number in the sequence is the previous one plus number 1. Neither is the sequence

a_0 = 0.5431, a_1 = -1.4267, a_2 = 1.1002, a_3 = -0.2983, a_4 = 0.7826, a_5 = -1.9201 \dots

because it is alternating in sign, with a positive number always being followed by a negative number and vice versa. In addition to the appearance of randomness as evaluated by a human observer, there are also many kinds of statistical tests that can be performed on a sequence to see whether there are correlations between the numbers a_n and a_{n+1} (or a_n and a_{n+2} etc.).

Fortunately it is quite easy to construct sequences of numbers that lie in some desired interval of the real number line and are otherwise seemingly random, in the sense of not following any obvious logic/pattern. The best-known example of this is probably the behaviour of the sequence of complex numbers

a_n = e^{in^2}=\cos n^2 + i\sin n^2, with n=1,2,3,4,\dots.

The numbers in this sequence all lie on the unit circle of the complex plane, and as the difference between n^2 and (n+1)^2 is always incommensurate with the period 2\pi, the numbers have an appearance of randomness.

The visual evaluation of the randomness of a number sequence is easiest if the x and y coordinates of a set of points on a plane are assigned values from the sequence. To test this, let us make two sequences, a_n and b_n, defined in a way similar to the real and complex components of the function mentioned above:

a_n = \sin (13+7(n+11)^2)
b_n = \sin (27+17(n+23)^2)

The factors 7 and 17, constant “phases” 13 and 27 and “offsets” 11 and 23 are something I just “pulled from the hat”, and they could as well be any other set of numbers that don’t have common factors.

Now make a C++ code that prints the coordinates of points (x,y) = (a_n , b_n) from n=1 to n=nmax:

#include <stdio.h>
#include <math.h>

main()
{
double n;
double nmax = 5000;

for(n=1; n<nmax; n++)
{
printf(“%f %f\n”, sin(13.0 + 7.0 *(n+11)*(n+11)), sin(27.0 + 17.0 * (n+23)*(n+23)));
}
}

Suppose this code was compiled into an executable file randnum.exe. Now writing

randnum > out.txt

on the Windows command line (or something equivalent in Linux), print the coordinates in the file “out.txt”.

Next draw the data point in the file in a 2D coordinate system, using Grace or some other graphing program. The results for the values nmax = 5000, nmax = 10000 and nmax = 20000 are below:

ran5000.jpgran10000.jpg

ran20000
The points seem to be rather random except that they are more likely to be near the borders of the rectangle that in the middle. The reason for this is the same as why an oscillating pendulum is most likely to be found near the edges of its trajectory at a randomly chosen moment – the derivative of the sine function A\sin \omega t with respect to t has its minimum absolute value when the sine function itself is at its maximum or minimum values. To correct this, change the code so that it converts the sine terms back to angles in interval [-\pi /2 , \pi /2] and divides by \pi / 2:

for(n=1; n<nmax; n++)
{
printf(“%f %f\n”, 2*asin(sin(13.0 + 7.0*(n+11)*(n+11)))/3.141, 2*asin(sin(27.0 + 17.0*(n+23)*(n+23)))/3.141);
}

Below you see a plot of the data points (x,y) obtained with this code.

ranh.jpg

Seems to be random enough for most purposes. Note, however, that you have to be careful with what kind of sequence you use when producing pseudorandom numbers in this way. If we do the same thing but use the same number as n-offset in the two sine functions:

for(n=1; n<nmax; n++)
{
printf(“%f %f\n”, sin(13.0 + 7.0 *(n+11)*(n+11)), sin(27.0 + 17.0 * (n+11)*(n+11)));
}

the plot of the data points looks like this:

lissajous.jpg

which doesn’t appear random at all.