Author: Nalin Pithwa

Number Theory: Historical Introduction: Tom Apostol

Posted by

0

Reference: Introduction to Analytic Number Theory by Tom Apostol.

The theory of numbers is that branch of mathematics which deals with properties of the whole numbers: 1, 2, 3, 4, 5, …

also called the counting numbers, or positive integers.

The positive integers are undoubtedly man’s first mathematical creation. It is hardly possible to imagine human beings without the ability to count, at least within a limited range. Historical record shows that as early as 5700 BC the ancient Sumerians kept a calendar, so they must have developed some form of arithmetic.

By 2500 BC, the Sumerians had developed a number system using 60 as a base. This was passed on to the Babylonians, who became highly skilled calculators. Babylonian clay tablets containing elaborate mathematical tables have been found, dating back to 2000BC.

When ancient civilizations reached a level which provided some leisure time to ponder about things, some people began to speculate about the nature and properties of numbers. This curiosity developed into a sort of number-mysticism or numerology, and even today numbers such as 3,7, 11 and 13 are considered omens of good or bad luck.

Numbers were used for keeping records and for commercial transactions for over 5000 years before any one thought of studying numbers themselves in a systematic way. The first scientific approach to the study of integers, that is, the true origin of the theory of numbers, is generally attributed to the Greeks. Around 600 BC, Pythagoras and his disciples made rather thorough studies of the integers. They were the first to classify integers in various ways: Even numbers, odd numbers, prime numbers, composite numbers.

A prime number is a number greater than 1 whose only divisors are 1 and the number itself. Numbers that are not prime are called composite numbers, except that the number 1 is neither prime nor composite.

The Pythagoreans also linked numbers with geometry. They introduced the idea of polygonal numbers: triangular numbers, square numbers, pentagonal numbers, etc. The reason for this geometrical nomenclature is clear: when the numbers are represented by dots arranged in the form of triangles, squares, pentagons, etc. …E.g.: Triangular numbers: 1, 3, 6, 10, 15, 21, 28, ….; square numbers: 1, 4, 9, 16, 25, 36, ….; pentagonal numbers: 1, 5, 12, 22, 35, 51, 70, ….

Another link with geometry came from the famous Theorem of Pythagoras which states that in any right triangle the square of the length of the hypotenuse is the sum of the squares of the lengths of the two legs. The Pythagoreans were interested in right triangles whose sides are integers. Such triangles are called Pythagorean triangles. The corresponding triple of numbers (x,y,z) representing the lengths of the sides is called a Pythagorean triple. Example (3,4,5)

A Babylonian tablet had been found dating from about 1700 BC, which contains an extensive list of Pythagorean triples, some of the numbers being quite large. The Pythagoreans were the first to give a method for determining infinitely many triples. In modern notation, it can be described as follows:

x=n, y=\frac{1}{2}(n^{2}-1), \frac{1}{2}(n^{2}+1);

the resulting triple (x,y,z) will always be a Pythagorean triple with z=y+1.

Here are some examples:

(3,4,5), (5,12,13), (7,24,25), (9,40,41), (11,60,61), (13,84,85), (15,112, 113), (17,144, 145), (19,180, 181)

There are other Pythagorean triples besides these, for example:

(8,15,17), (12,35,37), (16,63, 65), (20,99,101)

In these examples, we have z=y+2. Plato had found a method for determining all these triples : in modern notation, they are given by the formulas:

x=4n, y=4n^{2}-1, z=4n^{2}+1

Around 300 BC, an important event occurred in the history of mathematics. The appearance of Euclid’s Elements,a collection of 13 books, transformed mathematics from numerology into a deductive science. Euclid was the first person to present mathematical facts along with rigorous proofs of these facts. Three of the thirteen books were devoted to theory of numbers (books VII, IX and X). In book IX Euclid proved that there are infinitely many primes. His proof is still taught in the classroom today. In Book X, he gave a method for obtaining all Pythagorean triples although he gave no proof that his method did, indeed, give them all. The method can be summarized by the formulas:

x=t(a^{2}-b^{2}), y=2tab, z=t(a^{2}+b^{2}),

where t, a, b are arbitrary positive integers such that a>b, a and b have no prime factors in common, and one of a or b is odd, the other even.

Euclid also made an important contribution to another problem posed by the Pythagoreans —- that of finding all perfect numbers. The number 6 was called a perfect number because 6=1+2+3, the sum of all its proper divisors (that is, the sum of divisors less than 6). Another example of a perfect number is 28 because 28=1+2+4+7+14, and 1, 2, 4, 7 and 14 are the divisors of 28 less than 28. The Greeks referred to the proper divisors of a number as its “parts.” They called 6 and 28 perfect numbers because in each case the number is equal to to the sum of all its parts.

In Book IX, Euclid found all even perfect numbers. He proved that an even number is perfect if it has the form:

2^{p-1}(2^{p}-1)

where both p and 2^{p}-1 are primes.

Two thousand years later, Euler proved the converse of Euclid’s theorem. That is, every even perfect number must be of Euclid’s type. For example, for 6 and 28, we have:

6=2^{2-1}(2^{2}-1) = 2 \times 3 and 28=2^{3-1}(2^{3}-1)= 4 \times 7/

The first five even perfect numbers are

6,28,496,8128 and 33,550,336.

Perfect numbers are very rare indeed. At the present time (1975) only 24 perfect numbers are known. They correspond to the following values of p in Euclid’s formula:

2,3,5,7,13,17,19,31,61, 89,107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937.

Numbers of the form 2^{p}-1, where p is a prime, are now called Mersenne numbers and are denoted by M_{p} in honour of Mersenne, who studied them in 1644. It is known that M_{p} is prime for the 24 primes listed above and composite for all other values of p \leq 257, except for possibly

p=157,167, 193, 199, 227, 229

for these it it not yet (1975) known whether M_{p} (PS: you can google and find out the status now) is prime or composite.

No odd perfect numbers are known, it is not even known if any exist. But, if any do exist they must be very large; in fact, greater than 10^{50}.

We turn now to a brief description of the history of theory of numbers since Euclid’s time.

After Euclid in 300 BC, no significant advances were made in number theory until about 250 AD when another Greek mathematician, Diophantus of Alexandria, published 13 books, six of which have been preserved. This was the first Greek work to make systematic use of algebraic symbols. Although his algebraic notation seems awkward by present-day standards, Diophantus was able to solve certain algebraic equations involving two or three unknowns. Many of his problems originated from number theory and it was natural for him to seek integer solutions of equations. Equations to be solved with integer values are now called Diophantine equations, and the study of such equations is known as Diophantine analysis. The equation x^{2}+y^{2}=z^{2} for Pythagorean triples is an example of a Diophantine equation.

After Diophantus, not much progress was made in the theory of numbers until the seventeenth century, although there is some evidence that the subject began to flourish in the Far East — especially in India — in the period between AD 500 and AD 1200.

In the seventeenth century the subject was revived in Western Europe, largely through the efforts of a remarkable French mathematician, Pierre de Fermat (1601-1665), who is generally acknowledged to be the father of modern number theory. Fermat derived much of his inspiration from the works of Diophantus. He was the first to discover really deep properties of the integers. For example, Fermat proved the following surprising theorems:

Every integer is either a triangular number or a sum of 2 or 3 triangular numbers; every integer is either a square or sum of 2, 3, or 4 squares; every integer is either a pentagonal number or the sum of 2, 3, 4 or 5 pentagonal numbers, and so on.

Fermat also discovered that every prime number of the form 4n+1 such as 5, 13, 17, 29, 37, 41, etc. is a sum of two squares. For example,

5=1^{2}+2^{2}; 13=2^{2}+3^{2}; 17=1^{2}+4^{2}; 29=2^{2}+5^{2}; 37=1^{2}+6^{2}; 41=4^{2}+5^{2}

Shortly, after Fermat’s time, the names of Euler (1707-1783), Lagrange (1736-1813), Legendre (1752-1833), Gauss (1777-1855), and Dirichlet (1805-1859) became prominent in the further development of the subject. The first textbook in number theory was published by Legendre in 1798. Three years later Gauss published Disquisitiones Arithmeticae, a book which transformed the subject into a systematic and beautiful science. Although he made a wealth of contributions to other branches of mathematics, as well as to other sciences, Gauss himself considered his book on number theory to be his greatest work.

In the last hundred years or so since Gauss’s time there has been an intensive development of the subject in many different directions. It would be impossible to give in a few pages a fair cross-section of the types of problems that are studied in the theory of numbers. The field is vast and some parts require a profound knowledge of higher mathematics. Nevertheless, there are many problems in number theory which are very easy to state. Some of these deal with prime numbers, and we denote the rest of this introduction to such problems.

The primes less than 100 have been listed above. A table listing all primes less than 10 million was published in 1914 by an American mathematician, D. N. Lehmer. There are exactly 664579 primes less than 10 million, or about 6.5 %. Later, D. H. Lehmer (the son of D. N. Lehmer) calculated the total number of primes less than 10 billion; there are exactly 455052512 such primes, or about 4.5% although all these primes are not known individually.

A close examination of a table of primes reveals that they are distributed in a very irregular fashion. The tables show long gaps between primes. For example, the prime 370261 is followed by 111 composite numbers. There are no primes between 20831323 and 20831533. It is easy to prove that arbitrarily large gaps between prime numbers must eventually occur.

On the other hand, the tables indicate that consecutive primes, such as 3 and 5, or 101 and 103, keep recurring. Such pairs of primes, which differ only by 2 are known as twin primes. There are over 1000 such pairs below 100000 and over 8000 below 1000000. The largest pair known to date (around 1975 AD) is 76.3^{139}-1 and 76.3^{139}+1. Many mathematicians think there are infintely many such pairs, but no one has been able to prove (I think the advanced reader can refer to Google to see the progress in work on twin primes: the work of Dr. Yitang Zhang; I think Dr. Terence Tao also did some further work based on it. Refer to terrytao.wordpress.com)

One of the reasons for this irregularity in distribution of primes is that no simple formula exists for producing all the primes. Some formulas do yield many primes. For example, the expression:

x^{2}-x+41

gives a prime for x=0, 1, 2, \ldots, 40, whereas

x^{2}-79x+1601

gives a prime for x=0,1,2, \ldots, 79. However, no such simple formula can give a prime for all x, even if cubes and higher powers are used. In fact, in 1752 Goldbach proved that no polynomial in x with integer coefficient can be prime for all x, or even for all sufficiently large x.

Some polynomials represent infinitely many primes. For example, as x runs through the integers 0, 1, 2, 3, ….the linear polynomial

2x+1

gives all the odd numbers, hence, infinitely many primes. Also, each of the polynomials

4x+1 and 4x+3

represent infinitely many primes. In a famous memoir published in 1837, Dirichlet proved that, if a and b are positive integers with no prime factors in common, the polynomial

ax+b

gives infinitely many primes as x runs through all the positive integers. The result is now known as Dirichlet’s theorem on the existence of primes in a given arithmetical progression.

To prove the theorem, Dirichlet went beyond the realm of integers and introduced tools of analysis such as limits and continuity. By so doing, he laid the foundations for a new branch of mathematics called analytic number theory, in which ideas and methods of real and complex analysis are brought to bear on problems about integers.

It is not known if there is any quadratic polynomial ax^{2}+bx+c with a \neq 0 which represents infinitely many primes. However, Dirichlet had used his powerful analytic methods to prove that, if a, 2b, and c have no prime factor in common, the quadratic polynomial in two variables

ax^{2}+2bxy+cy^{2}

represents infinitely many primes as x and y run through positive integers.

Fermat thought that the formula 2^{2^{n}}+1 would always give a prime for n=0,1,2,.... These numbers are called Fermat numbers and are denoted by F_{n}. The first five are

F_{0}=1, F_{1}=5, F_{2}=17, F_{3}=257, F_{4}=65537

and they are all primes. However, in 1732 A.D., Euler found that F_{5} is composite. In fact,

F_{5} = 2^{32}+1= (641)(6700417)

These numbers are also of interest in plane geometry. Gauss had proved that if F_{n} is prime, say F_{n}=p, then a regular polygon of p sides can be constructed with straight edge and compass.

Beyond F_{5}, no futher Fermat primes have been found. (Please check this in Google. This is the author’s claim as of 1975 A.D.) In fact, for 5 \leq n \leq 16 each Fermat number F_{n} is composite. Also, F_{n} is known to be composite for the following further isolated values of n:

n=18,19,21, 23,25,26,27,30, 32, 36, 38, 39, 42, 52, 55, 58, 63,73,77,81,117, 125, 144, 150, 207, 226, 228, 260, 267, 268, 284, 316, 452, 1945.

The greatest known Fermat composite F_{1945} (till 1975 AD) has more than 10^{582} digits, a number larger than the number of letters in the Los Angeles and New York telephone directories combined (then in 1975 AD).

It was mentioned earlier that there is no simple formula that gives all the primes. In this connection, we should mention a result discovered in 1947 A.D. by an American mathematician, W. H. Mills. He proved that there is some number A, greater than 1 but not an integer, such that

[A^{3^{x}}] is prime for all x = 1, 2, 3…

Here, [A^{3^{x}}] means the greatest integer \leq A^{3^{x}}. Unfortunately no one knows what A is. (Again the reader can check the latest about this in Google).

The foregoing results illustrate the irregularity of the distribution of the prime numbers. However, by examining large blocks of primes one finds that their average distribution seems to be quite regular. Although there is no end to the primes, they become more widely spread, on the average, as we go further and further in the table. The question of the diminishing frequency of primes was the subject of much speculation in the early nineteenth century. To study this distribution, we consider a function, denoted by \pi{(x)}, which counts the number of primes less than or equal to x. Thus,

\pi{(x)} = the number of primes p satisfying 2 \leq p \leq x.

Here is a brief table of this function and its comparison with \frac{x}{\ln{x}}.

\begin{array}{cccc} x & \pi{(x)} & \frac{x}{\ln{(x)}} & \frac{\pi{(x)}}{\frac{x}{\ln{(x)}}} \\ 10 & 4 & 4.3 & 0.93 \\ 100 & 25 & 21.7 & 1.15 \\ 1000 & 168 & 144.9 & 1.16 \\ 10000 & 1229 & 1086 & 1.11 \\ 100000 & 9592 & 8686 & 1.10 \\ 1000000 & 78498 & 72464 & 1.08 \\ 10000000 & 664579 & 621118 & 1.07 \\ 100000000 & 5761455 & 5434780 & 1.06 \\ 1000000000 & 50847534 & 48309180 & 1.05 \\ 10000000000 & 455052512 & 434294482 & 1.048 \end{array}

By examining a table like this for x \leq 10^{6}, Gauss and Legendre proposed independently that for large x, the ratio

\frac{\pi{(x)}}{\frac{x}{\ln{(x)}}}

was nearly 1 and they conjectured that this ratio would approach 1 as x approaches \infty. Both Gauss and Legendre attempted to prove this statement but did not succeed. The problem of deciding the truth or falsehood of this conjecture attracted the attention of eminent mathematicians for nearly 100 years.

In 1851 A.D. the Russian mathematician Chebyshev made an important step forward by proving that if the ratio did tend to a limit, then this limit must be 1. However, he was unable to prove that the ratio does tend to a limit.

In 1859, Riemann attacked the problem with analytic methods, using a formula discovered by Euler in 1737 which relates the prime numbers to the function

\zeta{(s)} = \Sigma_{n=1}^{\infty}\frac{1}{n^{s}} for real s greater than 1.

Riemann considered complex values of s and outlined an ingenious method for connecting the distribution of primes to properties of the function \zeta{(s)}. The mathematics needed to justify all the details of his method had not yet been fully developed and Riemann was unable to completely settle the problem before his death in 1866.

Thirty years later the necessary analytic tools were at hand and in 1896 J. Hadamard and and C. J. de la Vallee Poussin independently and almost simultaneously succeeded in proving that

\lim_{n \rightarrow \infty} \frac{\pi{(x)}\ln{(x)}}{x}=1.

This remarkable result is called the prime number theorem, and its proof was one of the crowning achievements of analytic number theory.

In1949, two contemporary mathematicians, Atle Selberg and Paul Erdos caused a sensation in the mathematical world when they discovered an elementary proof of the prime number theorem. Their proof, though very intricate, makes no use of \zeta{(s)} nor of complex function theory and in principle is accessible to anyone familiar with elementary calculus.

One of the most famous problems concerning prime numbers is the so-called Goldbach conjecture (again please refer to Google for the latest reseach results on this). In 1742 A.D., Goldbach wrote to Euler suggesting that every even number greater than or equal to 4 is a sum of two primes. For example,

4=2+2; 6=3+3; 8=3+5; 10=3+7=5+5; 12=5+7

This conjecture is undecided to this day (again, please google for twin prime conjecture, Yitang Zhang and Terence Tao etc.), although it might be true as per the progress suggested. Now, why do mathematicians think it is probably true if they haven’t been able to prove it? First of all, the conjecture has been verified by actual computation for all even numbers less than 33 \times 10^{6}. It has been found that every even number greater than 6 and less than 33 \times 10^{6} is, in fact, not only the sum of two odd primes but the sum of two distinct odd primes. But, in number theory verification of a few thousand cases is not enough evidence to convince mathematicians that something is probably true. For example, all the odd primes fall into two categories, those of the form 4n+1 and those of the form 4n+3. Let \pi_{1}{(x)} denote all the primes less than or equal to x that are of the form 4n+1 and let \pi_{3}{(x)} denote the number that are of the form 4n+3. It is known that there are infinitely many primes of both types. By computation, it was found that \pi_{(x)} \leq \pi_{3}{(x)} for all x \leq 26861. But, in 1957, J. Leech found that for x=26861, we have \pi_{1}{(x)}=1473 and \pi_{3}{(x)}=1472, so the inequality was reversed. In 1914, Littlewood had proved that this inequality reverses back and forth infinitely often. That is, there are infinitely many x for which \pi_{1}{(x)} < \pi_{3}{(x)} and infinitely many x for which \pi_{3}{(x)} < \pi_{1}{(x)}. Conjectures about prime numbers can be erroneous even if they are verified by computations in thousands of cases.

Therefore, the fact that Goldbach’s conjecture has been verified for all even numbers less than 33 \times 10^{6} is only a tiny bit of evidence in its favour.

Another way that mathematicians collect evidence about the truth of a particular conjecture is by proving other theorems which are somewhat similar to the conjecture. For example, in 1930 the Russian mathematician Schnilrelmann proved that there is a number M such that every number n from some point on is a sum of M or lower primes:

n=p_{1}+p_{2}+p_{3}+\ldots+p_{n} for sufficiently large n

If we know that M were equal to 2 for all even n, this would prove Goldbach’s conjecture for all sufficiently large n. In 1956 A.D., the Chinese mathematician Yin Wen-Lin proved that M \leq 18. That is, every number n from some point on is a sum of 18 or fewer primes. Schnilrelmann’s result is considered a giant step toward a proof of Goldbach’s conjecture. It was the first real progress made on this problem in nearly 200 years.

A much closer approach to a solution of Goldbach’s problem was made in 1937 by another Russian mathematician, I. M. Vinogradov, who proved that from some point on every odd number is the sum of three primes:

n=p_{1}+p_{2}+p_{3} when n is odd, n is sufficiently large

In fact, this is true for all odd n greater than 3^{3^{15}}. To date (1975 A.D.) this is the strongest piece of evidence in favour of Goldbach’s conjecture. For one thing, it is easy to prove that Vinogradov’s theorem is a consequence of Goldbach’s statement. That is, if Goldbach’s conjecture is true, then it is easy to deduce Vinogradov’s statement. The big achievement of Vinogradov was that he was able to prove his result without using Goldbach’s statement. Unfortunately, no one has been able to work it the other way around and prove Goldbach’s statement from Vinogradov’s.

Another piece of evidence in favour of Goldbach’s conjecture was found in 1948 by the Hungarian mathematician Renyi who proved that there is a number M such that every sufficiently large even number n can be written as a prime plus another number which has no more than M prime factors:

n=p+A

where A has no more than M prime factors (n even, n sufficiently large). If we know that M=1, then Goldbach’s conjecture would be true for all sufficiently large n. In 1965 A.D., A. A. Buhstab and A. I. Vinogradov proved that M \leq 3, and in 1966 Chen Jing-run proved that M \leq 2.

We conclude this introduction with a brief mention of some outstanding unsolved problems (till date 1975 A.D.) concerning prime numbers:

  1. Goldbach’s problem: Is there an even number greater than 2 which is not the sum of two primes?
  2. Is there an even number greater than 2 which is not the difference of two primes?
  3. Are there infinitely many twin primes?
  4. Are there infinitely many Mersenne primes, that is, primes of the form 2^{p}-1 where p is prime?
  5. Are there infinitely many composite Mersenne numbers?
  6. Are there infintely many Fermat primes, that is, primes of the form 2^{2^{p}}+1?
  7. Are there infinitely many composite Fermat numbers?
  8. Are there infinitely many primes of the form x^{2}+1, where x is an integer? (It is known that there are infinitely many of the form x^{2}+y^{2}, and of the form x^{2}+y^{2}+1, and of the form x^{2}+y^{2}+z^{2}+1.)
  9. Are there infinitely many primes of the form x^{2}+k, where k is given?
  10. Does there always exist at least one prime between n^{2} and (n+1)^{2} for every integer n \geq 1?
  11. Does there always exist at least one prime between n^{2} and n^{2}+n for every integer n>1?
  12. Are there infinitely many primes whose digits (in base 10) are all ones? (Here are two examples: 11 and 11,111,111,111,111,111,111,111)

The professional mathematician is attracted to number theory because of the way all the weapons of modern mathematics can be brought to bear on its problems. As a matter of fact, many important branches of mathematics had their origin in number theory. For example, the early attempts to prove the prime number theorem stimulated the development of the theory of functions of a complex variable especially the theory of entire functions. Attempts to prove that the Diophantine equation x^{n}+y^{n}=z^{n} has no non-trivial solution if n greater than or equal to three (Fermat’s conjecture or Fermat’ s Last Theorem (this has been proved by Sir Andrew Wiles in 1995, Princeton University) led to the development of algebraic number theory, one of the most active areas of modern mathematical research. (1975 A.D. comment by Prof Tom Apostol: Even though Fermat’s conjecture is still undecided, this seems unimportant by comparison to the vast amounts of valuable mathematics that has been created as a result of work on this conjecture.) Another examples has been the theory of partitions which has been an important factor in the development of combinatorial analysis and in the study of modular functions.

There are hundreds of unsolved problems in number theory. New problems arise more rapidly than the old ones are solved, and many of the old ones have remained unsolved for centuries. As the mathematician Sierpinski once said, “…the progress of our knowledge of numbers is advanced not only by what we already know about them, but also by realizing what we yet do not know about them.”

Note: More References:

  1. History of the Theory of Numbers Volumes I, II, III: Dickson
  2. Reviews in Number Theory by LeVeQue, Volumes I, II, III, IV, V, VI.

Happy reading. I hope it arouses tremendous passion/curiosity among some readers to consider number theory as a possible professional option.

Regards,

Nalin Pithwa

Notes I: Sets and Functions: Solutions

Posted by

0

Problem 1:

If \{ A_{i}\} and \{ B_{j}\} are two classes of sets such that \{ A_{i}\} \subseteq \{ B_{j}\}, prove that \bigcup_{i}A_{i} \subseteq \bigcup_{i}B_{i} and \bigcap_{j}B_{j} \subseteq \bigcap_{i}A_{i}.

Answer 1:

The first part is clear as the hypothesis says the set of sets \{ A_{i}\} is a subset of the set of sets \{ B_{j}\}. So, quite clearly \bigcup_{i}A_{i} \subseteq \bigcup_{j}A_{j}. For the second part, we can use the generalized De Morgan’s laws. (Note: if you try to derive it straight, you will prove exactly what is opposite of the required result :-)). For the second part note that X \subseteq Y \Longleftrightarrow Y^{'} \bigcap X^{'}. Using the result in the first part, that is, consider \bigcup_{i}A_{i} \subseteq \bigcup_{j}A_{j} and now take the complement of both sides so we get: \bigcup_{i}A_{i} \subseteq \bigcup_{j}B_{j} \Longleftrightarrow (\bigcup_{j}B_{j})^{'} \subseteq (\bigcup_{i}A_{i})^{'}, that is, \bigcap_{j}B_{j} \subseteq \bigcap_{i}A_{i}. QED.

Problem 2:

The difference between two sets A and B, denoted by A-B, is the set of all elements in A and not in B, thus A-B = A \bigcap B^{'}. Show the following:

(a)A-B = A - (A \bigcap B) = (A \bigcup B) -B.

Answer (a): A-B is the set of elements x \in A, but not in B. Hence, A-B = A-(A \bigcap B), simply by definition. Again, if we consider elements in A or B or both, and then take away elements of B, we are just left with elements of A only, but not of B. That is, A-B = A-(A \bigcap B) = (A \bigcup B) - B. QED. ps: A venn diagram may help visualize v well.

(b) TPT: (A-B) - C = A - (B \bigcup C) (PS: a Venn diagram can help visualize and perhaps, guide the writing of the proof also).

Let x \in A-B, but x \notin C. Then, x \in A, but x \notin B, or x \notin C, or not in both B and C. That is, x \in A-(B \bigcup C). By reversing the argument, we get the other subset relationship. Hence, (A-B)-C = A- (B \bigcap C). QED.

(c) TPT: A - (B-C) = (A-B) \bigcup (A \bigcap C).

Answer (c): Let x \in A-(B-C). That is, x \in A and x \notin (B-C). That is, x \in A, x \notin B, x \in C. That is, x \in A, x \notin B, or x could be both in A and C. That is, x \in (A-B) \bigcup (A \bigcap C). Simply reversing the arguments, we get the reverse subset relation. Hence, the two sets are equal. Hence, A-(B-C) = (A-B) \bigcup (A \bigcap C). QED.

(d) TPT: (A \bigcup B) - C = (A-C) \bigcup (B-C).

answer (d): let x \in A\bigcup B, but x \notin C. Then, x \in A, or x \in B, or x is an element of both A and B, but x is not an element of C. Which clearly means, x is an element of A but not C, OR x is an element of B but not C. That is, x \in (A-C) \bigcup (B-C) (upon reversing the arguments, we get the other subset relations. Hence, the two sets are equal). QED.

problem (e): TPT: A-(B \bigcup C) = (A-B) \bigcap (A-C) (once again, note that for set theoretic relations with up to three sets, venn diagrams are helpful to visualize and guide the proofs..)

answer (c): let x \in A, but not in B \bigcup C. That is, x is an element of A, but not of B, not of C, or not both of B and C. That is, x is an element of A not of B, and x is an element of A not of C. That is, x \in (A-B) \bigcap (A-C). Reversing the arguments, we get the other subset relationship. Hence, the two sets are equal. Hence, A - (B \bigcup C) = (A-B) \bigcap (B-C). QED.

Problem 3:

The symmetric difference of two sets A and B, denoted by A \triangle B, is defined by A \triangle B = (A-B) \bigcup (B-A); it is the union of the difference of two sets in opposite orders. Prove the following:

3(a) Symmetric difference is associative: A \triangle (B \triangle C) = (A \triangle B) \triangle C.

Answer 3a: please refer a previous blog.

3(b): TPT: A \triangle \phi = A; and A \triangle A = \phi. (this is some sort of ‘existence of additive inverse of ‘in a symmetric relation’).

Answer 3b: both results are obvious from definition.

3(c): TPT: Symmetric difference is commutative operation: A \triangle B = B\triangle A.

answer 3c: By definition, LHS is (A-B)\bigcup (B-A) = (B-A) \bigcup (A-B), which is RHS. Hence, done.

3(d): TPT: Some sort of distributive law: A \bigcap (B \triangle C) = (A \bigcap B) \triangle (A \bigcap C).

answer 3d: Let x \in A, and also simultaneously x \in (B \triangle C). That is, x \in A, and x \notin (B \bigcap C). That is, x \in A, x \notin (A \bigcap B)\bigcap (B \bigcap C). That is, x \in RHS. Reversing the arguments, we get the other subset relation. Hence, the two sets are equal. Hence, we can say “intersection distributes over symmetric difference.” QED.

Problem 4:

A ring of sets is a non-empty class A of sets such that if A and B are in A then A \triangle B is in A and A \bigcap B is also in A. Show that A must contain the empty set, A \bigcup B and A-B. Also, show that if a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets. Also, prove that a Boolean algebra of sets is a ring of sets.

Answer 4(i): TPT: A must also contain the empty set, the set A \bigcup B and the set A-B. As A \triangle B is in A, so also A \triangle A = \phi \in A; now, it is already given that the ring of sets is non-empty, so it contains a non empty universal set also, call it U. We know from problem 2 in this blog that A - B = A \bigcap B^{'}. As U exists, so does B^{'} by definition and so A-B is in A. Also, as A-B exists, A-B^{'} exists in A, but A-B^{'}=A\bigcap B also exists in A. QED.

Answer 4(ii): TPT: If a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets.

Let A be any non-empty class of sets. Clearly, it therefore has a non empty universal set. As \phi \in U, so also \phi is contained in A. Hence, the complement of a set A is also in A. Now, A \bigcup B \in A, so U - (A \bigcup B) is in A, that is, by De Morgan law, B^{'} \bigcap A^{'} is in A. That is, again, A \bigcap B is in A. Now, since A-B is in A, hence, B-A is in A, and since A \bigcup B is in A, then (A-B) \bigcup (B-A) is in A also. Hence, A is a ring of sets.

4(iii) TPT: Show that a boolean algebra of sets is a ring of sets.

Answer 4(iii); Firstly, as a boolean algebra of sets is non-empty, and it also contains the empty set and the Universal set. As A is in A implies that A^{'} is in A, so A \bigcup B^{'} is also in A (by definition of Boolean algebra), but this is precisely that A-B is in A. Now, as A \triangle B = (A-B) \bigcup (B-A) clearly is also in A. Hence, a Boolean algebra of sets is a ring of sets.

Problem 5:

Show that the class of all finite subsets (including the empty set) of an infinite set is a ring of sets but is not a Boolean algebra.

Answer 5:

In problem 4 above, we showed that if a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets. The given class is a subclass of all an infinite set such that it contains finite subsets only; that is, again, we know that finite unions of finite subsets and finite intersections of finite subsets also lie in that subclass, but the complements might be infinite sets so that it need not always be a Boolean algebra of sets.

Problem 6:

Show that the class of all finite unions of closed-open intervals on the real line is a ring of sets but is not a Boolean algebra of sets.

Answer 6:

Same reasoning as above tells us that it is indeed a ring of sets; but consider for example the closed-open interval [a,b), the complement of this is not in that class as it is an infinite interval so that it is not a Boolean algebra of sets.

Problem 7:

Assuming that the Universal set U is non empty, show that Boolean algebras of sets can be described as rings of sets which contain U.

Answer 7:

As U \neq \phi, by definition of Boolean algebras, U^{'} is in this class of sets, so that the empty set is also a part of this class of sets. Again, by definition of Boolean algebras, the union of two sets of this class is also in this set so also the intersection of any two sets of this class is also in this class. So, for any two sets A and B, A-B is also in this set (as complement of B exists), and so also, A \triangle B = (A-B) \bigcup (B-A) is also in this set. In other words, this is also a ring of sets.

Regards,

Nalin Pithwa

Set theory: more basic problems to solve and clear and apply

Posted by

0

I am producing the list of questions first so that the motivated reader can first read and try them …and can compare with my answers by scrolling down only much later; here we go:

  1. If \{ A_{i}\} and \{ B_{j}\} are two classes of sets such that \{ A_{i}\} \subseteq \{ B_{j}\}, then prove that \bigcup_{i}A_{i} \subseteq \{ B_{j}\} and \bigcap_{j} B_{j} \subseteq \bigcap_{i}A_{i}.
  2. The difference between two sets A and B, denoted by A-B, is the set of elements in A and not in B; thus, A - B = A \bigcap B^{'}. Prove the following simple properties: (a) A-B = A-(A \bigcap B) = (A \bigcup B)-B; (b) (A-B)-C = A-(B \bigcup C); (c) A - (B-C) = (A-B) \bigcup (A \bigcap C); (d) (A \bigcup B) - C = (A-C) \bigcup (B-C); (e) A - (B \bigcup C) = (A-B) \bigcap (A-C)
  3. The symmetric difference of two sets A and B, denoted by A \triangle B, is defined by A \triangle B = (A-B) \bigcup (B-A); it is thus the union of their differences in opposite orders. Prove the following : (a) Symmetric difference is associative : A \triangle (B \triangle C) = (A \triangle B) \triangle C (b) A \triangle \phi=A (c) A \triangle A = \phi (c) Symmetric difference is commutative: A \triangle B = B \triangle A (d) Some sort of distributive rule also holds: A \bigcap (B \triangle C) = (A \bigcap B) \triangle (A \bigcap C)
  4. A ring of sets is a non-empty class A of sets such that if A and B are in A, then A \triangle B and A \bigcap B are also in A. Show that A must also contain the empty set, A \bigcup B, and A-B. Show that if a non-empty class of sets contains the union and difference of sets any pair of its sets, then it is a ring of sets. Prove that a Boolean algebra of sets is a ring of sets.
  5. Show that the class of all finite subsets (including the empty set) of an infinite set is a ring of sets but is not a Boolean algebra of sets.
  6. Show that the class of all finite unions of closed-open intervals on the real line is a ring of sets but is not a Boolean algebra of sets.
  7. Assuming that the universal set U is non-empty, show that Boolean algebras of sets can be described as a ring of sets which contain U.

I will put up my solutions as soon as I can.

Regards,

Nalin Pithwa.

Symmetric difference is associative

Posted by

0

We want to show that : A \triangle (B \triangle C) = (A \triangle B) \triangle C

Part I: TPT: LHS \subset RHS

Proof of Part I: let x \in LHS

Then, x \in A \triangle (B \triangle C). By definition of symmetric difference,

x \in \{ A - (B \triangle C)\} \bigcup \{(B \triangle C) -A \}

Hence, x \in A, x \notin (B \triangle C), OR x \in B \triangle C, x \in A

That is, x \notin A \bigcap (B \triangle C).

Hence, x \notin A, and x \notin B \triangle C

Hence, x \notin A and x \in B \bigcap C.

Hence, x \in (B \bigcap C)-A.

Hence, x \in B, x \in C, but x \notin A.

Therefore, x \in B, but x \notin A \bigcap C. —- Call this I.

Consider y \in (A \triangle B) \triangle C.

Therefore, y \notin (A \triangle B) \bigcap C.

Therefore, y \notin C, and y \notin A \triangle B

Therefore, y \notin C, and y \in A \bigcap B.

Therefore, y \in (A \bigcap B)-C.

Hence, y \in A, y \in B, but y \notin C.

That is, y \in B, y \notin A \bigcap C. Call this II.

From I and II, LHS \subset RHS.

Part II: TPT: RHS \subset LHS.

Quite simply, reversing the above steps we prove part II.

QED.

Cheers,

Nalin Pithwa

What is the use of Mathematics

Posted by

0

Mathematics Hothouse

Well, you might be asking this question in high school. You might have found that Math is a lot of formulae and manipulations similar to black magic in Algebra and wild imaginations in Geometry — I mean the proofs. So Math means prove this and that. Right?

I agree to some extent. Initially, it is sort of drab or *mechanical*. But, there is a good analogy. Think how you learnt writing the English alphabet — keep on drawing a big A, retracing it 10 times daily and perhaps, your Mom would have whacked you if you did not want to practise it. But, after you know English, the whole world of opportunities opens up for you; your vistas have widened. Exactly same is the case with Mathematics of high school and junior college. But, of course, there are applications of high school math which you learn later when you pursue…

View original post 565 more words

Probability Theory Primer: part I

Posted by

0

Illustrative Example 1:

What is the chance of throwing a number greater than 4 with a fair die whose faces are numbered from 1 to 6?

Solution 1:

There are 6 possible ways in which the die can fall, and of these two are the favourable events required.

Hence, required chance is \frac{2}{6}=\frac{1}{3}.

Illustrative example 2:

From a bag containing 4 white and 5 black balls a man draws 3 at random; what are the odds against these being all black?

Solution 2:

The total number of ways in which 3 balls can be drawn is 9 \choose 3, and the number of ways of drawing 3 black balls is 5 \choose 3; therefore, the chance of drawing 3 black balls is equal to

\frac{{5 \choose 3}}{{9 \choose 3}}=\frac{5.4.3}{9.3.7}=\frac{5}{43}.

Thus, the odds against the event are 37 to 5.

Illustrative example 3:

Find the chance of throwing at least one ace in a single throw with two dice.

Solution 3:

In die games, there is no ace. We can pick up any number as an ace in this question. Once it is chosen, it is fixed.

So, the possible number of cases is 6 \times 6=36.

An ace on one die may be associated with any of the six numbers on the other die, and the remaining five numbers on the first die may each be associated with the ace on the second die; thus, the number of favourable cases is 11.

Therefore, the required probability is \frac{11}{36}.

Illustrative example 4:

Find the chance of throwing more than 15 in one throw with 3 dice.

Solution 4:

A throw amounting to 18 must be made up of 6, 6, 6 and this can occur in one way only; 17 can be made up of 6. 6. 5 which can occur in 3 ways; 16 may be made up of 6, 6, 4 and 6, 5, 5 each of which arrangements can occur in 3 ways.

Therefore, the number of favourable cases is 1+3+3+3, that is, 10.

And, the total number of cases possible is 6^{3}, that is, 216.

Hence, the required probability is \frac{10}{216}=5/108.

Illustrative example 5:

A has 3 shares in a lottery, in which there are 3 prizes and 6 blanks; B has 1 share in a lottery in which there is 1 prize and 3 blanks; show that A’s chance of success is to B’s as 16:7.

Solution 5:

A may draw 3 prizes in one way; A may draw 2 prizes and 1 blank in \frac{3.3}{1.2} \times 6 ways; A may draw 1 prize and 2 blanks in 3 \times \frac{6.5}{1.2} ways; the sum of these numbers is 64, which is the number of ways in which A can win a prize. Also, he can draw 3 tickets in \frac{9.8.7}{1.2.3} ways, that is, 84 ways.

Hence, A’s chance of success is \frac{64}{84} = \frac{16}{21}.

B’s chance of success is clearly \frac{1}{3}.

Therefore, the required ratio is \frac{\frac{16}{21}}{\frac{1}{3}} = \frac{16}{7}.

Tutorial questions:

  1. In a single throw with two dice, find the chances of throwing (a) a five (b) a six.
  2. From a pack of 52 cards, two cards are drawn at random, find the chance that one is a knave and other is a queen.
  3. A bag contains 5 white, 7 black and 4 red balls. Find the chance that 3 balls all drawn at random are all white.
  4. If four coins are tossed, find the chance that there are two heads and two tails.
  5. One of two events must happen; given that the chance of one is two-thirds that of the other, find the odds in favour of the other.
  6. If from a pack four cards are drawn, find the chance that they will be the four honours of the same suit.
  7. Thirteen persons take their places at a round table, show that it is five to one against two particular persons sitting together.
  8. There are three events A, B, C, out of which one must, and only one can happen; the odds are 8 is to 3 against A; 5 to 2 against B; find the odds against C.
  9. Compare the chance of throwing 4 with one die, 8 with two dice and 12 with three dice.
  10. In shuffling a pack of cards, four are accidentally dropped; find the chance that the missing cards should be one from each suit.
  11. A has 3 shares in a lottery containing 3 prizes and 9 blanks; B has 2 shares in a lottery containing 2 prizes and 6 blanks; compare their chances of success.
  12. Show that the chances of throwing six with 4, 3 or 2 dice respectively are as 1:6:16
  13. There are three works, one consisting of three volumes, one of four volumens, and the other of one volume. They are placed on a shelf at random; prove that the chance that the volumes of the same works are all together is \frac{3}{140}.
  14. A and B throw with two dice; if A throws 9, find B’s chance of throwing a higher number.
  15. The letters forming the word Clifton are placed at random in a row; what is the chance that the two vowels come together?
  16. In a hand, what is the chance that the four kings are held by a specified player?

Regards,

Nalin Pithwa.

 

 

 

 

 

Compilation of elementary results related to permutations and combinations: Pre RMO, RMO, IITJEE math

Posted by

0

1. Disjunctive or Sum Rule:

If an event can occur in m ways and another event can occur in n ways and if these two events cannot occur simultaneously, then one of the two events can occur in m+n ways. More generally, if E_{i} (i=1,2,\ldots,k) are k events such that no two of them can occur at the same time, and if E_{i} can occur in n_{i} ways, then one of the k events can occur in n_{1}+n_{2}+\ldots+n_{k} ways.

2. Sequential or Product Rule:

If an event can occur in m ways and a second event can occur in n ways, and if the number of ways the second event occurs does not depend upon how the first event occurs, then the two events can occur simultaneously in mn ways. More generally, $if E_{1} can occur in n_{1}, E_{2} can occur in n_{2} ways (no matter how E_{1} occurs), E_{3} can occur in n_{3} ways (no matter how E_{1} and E_{2} occur), \ldots, E_{k} can occur in n_{k} ways (no matter how the previous k-1 events occur), then the k events can occur simultaneously in n_{1}n_{2}n_{3}\ldots n_{k} ways.

)3. Definitions and some basic relations:

Suppose X is a collection of n distinct objects and r is a nonnegative integer less than or equal to n. An r-permutation of X is a selection of r out of the n objects but the selections are ordered. 

An n-permutation of X is called a simply a permutation of X.

The number of r-permutations of a collection of n distinct objects is denoted by P(n,r); this number is evaluated as follows: A member of X can be chosen to occupy the first of the r positions in n ways. After that, an object from the remaining collections of (n-1) objects can be chosen to occupy the second position in (n-1) ways. Notice that the number of ways of placing the second object does not depend upon how the first object was placed or chosen. Thus, by the product rule, the first two positions can be filled in n(n-1) ways,….and all r positions can be filled in

P(n,r) = n(n-1)\ldots (n-r+1) = \frac{n!}{(n-r)}! ways.

In particular, P(n,n) = n!

Note: An unordered selection of r out of the n elements of X is called an r-combination of X. In other words, any subset of X with r elements is an r-combination of X. The number of r-combinations or r-subsets of a set of n distinct objects is denoted by n \choose r (read as ” n ‘choose’ r). For each r-subset of X there is a unique complementary (n-r)-subset, whence the important relation {n \choose r} = n \choose {n-r}.

To evaluate n \choose r, note that an r-permutation of an n-set X is necessarily a permutation of some r-subset of X. Moreover, distinct r-subsets generate r-permutations each. Hence, by the sum rule:

P(n,r)=P(r,r)+P(r,r)+\ldots + P(r,r)

The number of terms on the right is the number of r-subsets of X. That is, n \choose r. Thus, P(n,r)=P(r,r) \times {n \choose r}=r! \times {n \choose r}.

The following is our summary:

  1. P(n,r) = \frac{n!}{(n-r)!}
  2. {n \choose r}=\frac{P(n,r)}{r!}=\frac{n!}{r! (n-r)!}=n \choose {n-r}

4. The Pigeonhole Principle: Basic Version:

If n pigeonholes (or mailboxes) shelter n+1 or more pigeons (or letters), at least 1 pigeonhole (or mailbox) shelters at least 2 pigeons (or letters).

5. The number of ways in which m+n things can be divided into two groups containing m and n equal things respectively is given by : \frac{(m+n)!}{m!n!}

Note: If m=n, the groups are equal (and hence, indistinguishable), and in this case the number of different ways of subdivision is \frac{(2m)!}{2!m!m!}

6. The number of ways in which m+n+p things can be divided into three groups containing m, n, p things severally is given by: \frac{(m+n+p)!}{m!n!p!}

Note: If we put m=n=p, we obtain \frac{(3m)!}{m!m!m !} but this formula regards as different all the possible orders in which the three groups can occur in any one mode of subdivision. And, since there are 3! such orders corresponding to each mode of subdivision, the number of different ways in which subdivision into three equal groups can be made in \frac{(3m)!}{m!m!m!3!} ways.

7. The number of ways in which n things can be arranged amongst themselves, taking them all at a time, when p of the things are exactly alike of one kind, q of them are exactly alike of a another kind, r of them are exactly alike of a third kind, and the rest are all different is as follows: \frac{n!}{p!q!r!}

8. The number of permutations of n things r at a time, when such things may be repeated once, twice, thrice…up to r times in any arrangement is given by: n^{r}. Cute quiz: In how many ways, can 5 prizes be given away to 4 boys, when each boy is eligible for all the prizes? (Compare your answers with your friends’ answers :-))

9. The total number of ways in which it is possible to make a selection by taking some or all of n things is given by : 2^{n}-1

10. The total number of ways in which it is possible to make a selection by taking some or all out of p+q+r+\ldots things, whereof p are alike of one kind, q alike of a second kind, r alike of a third kind, and so on is given by : (p+1)(q+1)(r+1)\ldots-1.

Regards,

Nalin Pithwa.