High School Mathematics Extensions/Set Theory and Infinite Processes

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

Introduction

As soon as a child first learns about numbers, they become interested in big ones, a million, a billion, a trillion. They even make up their own, a zillion etc. One of the first mathematical questions a child asks is "what is the largest number?" This will often lead to a short explanation that there are infinitely many numbers.

But there are many different types of infinity - in fact, there are infinite types of infinity! This chapter will try to explain what some of these types mean and the differences between them.

Finite and Infinite Sets

There was once a mathematician called Georg Cantor who created a new branch of mathematics called set theory in the late 19th century. Set theory involves collections of numbers or objects. Here's a set:

$\{1,2,3,4,5\}$

This set consists of five elements, namely the first five natural numbers. Now consider the set:

$\{6,7,8,9,10\}$

Are these sets of the same size? Yes, they are. This is because they both have five elements. As we will see later, this method of comparing sizes does not work for all sets. An alternate method for comparing set sizes is to match elements of sets in a one-one fashion.

Think of a small child who wants to compare the number of marbles she has with her brother's collection. Let's say she doesn't know how to count beyond ten. She can still compare the sizes of their collections of marbles by lining up their marbles in two parallel lines. The line on the left contains her marbles while the one on the right contains her brother's. If each marble on the left is aligned with exactly one marble on the right, then they both have the same number of marbles.

We can use the same idea to compare infinite sets. If we can find a way to pair up one member of set A with one member of set B, and if there are no members of A without a partner in B and vice versa then we can say that set A and set B have the same number of members. Formally, two sets $A$ and $B$ are of the same size if there is a function $f$ such that for every $a$ in $A$, we have $f(a)$ in $B$ and moreover, for every $b$ in $B$, there exists an $a$ in $A$ such that $f(a)=b$.

Example

Consider our previous example. We want to know if the sets $\{1,2,3,4,5\}$ and $\{6,7,8,9,10\}$ have the same size. We can create the following matching.

1	6
2	7
3	8
4	9
5	10

Example

Let Set N be all counting numbers. N is called the set of natural numbers. 1,2,3,4,5,6,... and so on. Let Set B be the negative numbers -1,-2,-3, ... and so on. Can the members of N and B be paired up? The formal way of saying this is "Can A and B be put into a one to one correspondence"?

Obviously the answer is yes. 1 in set N corresponds with -1 in B. Likewise:

N   B

1   -1

2   -2

3   -3

and so on. Here, the one-one function that maps from A to B is $f(x)=-x$.

So useful is the set of counting numbers that any set that can be put into a one to one correspondence with it is said to be countably infinite.

Example

The set of integers is the set containing all elements from the set N, the set B and the element 0. That is

{... -3,-2,-1, 0, 1, 2, 3, ...}

The set of integers is usually denoted by Z. Note that N the set of natural numbers is a subset of Z. All members of N are in Z, but not all members of Z are in N.

Is the set of integers countably infinite? In other words, can the set of integers be put in one-one correspondence with the set of all natural numbers?

Since the set N is contained in the set Z, we may be tempted to declare that these two sets are not of the same size. However, we can

Z   N

 0   1

-1   2

 1   3

-2   4

and so on. We can write this one-one correspondence as a function

$f(x)=\left\{{\begin{array}{cl}{\frac {x-1}{2}}&x{\text{ is odd}}\\{\frac {-x}{2}}&x{\text{ is even}}\end{array}}\right.$

We can verify that this function generates all the integers in Z from the natural numbers in N.

Strange indeed! A subset of Z (namely the natural numbers) has the same size as Z itself! Infinite sets are not like ordinary finite sets. In fact this is sometimes used as a definition of an infinite set. An infinite set is any set which can be put into a one to one correspondence with at least one of its subsets. Rather than saying "The number of members" of a set, people sometimes use the word cardinality or cardinal value. Z and N are said to have the same cardinality.

Exercises

1. Is the number of even numbers the same as the natural numbers?
2. What about the number of square numbers?
3. Is the cardinality of positive even numbers less than 100 equal to the cardinality of natural numbers less than 100? Which set is bigger? How do you know? In what ways do finite sets differ from infinite ones?

Is the set of rational numbers bigger than N?

In this section we will look to see if we can find a set that is bigger than the countable infinity we have looked at so far. To illustrate the idea we can imagine a story.

There was once a criminal who went to prison. The prison was not a nice place so the poor criminal went to the prison master and pleaded to be let out. She replied:

"Oh all right - I'm thinking of a number, every day you can have a go at guessing it. If you get it correct, you can leave."

Now the question is - can the criminal get himself out of jail? (Think about if for a while before you read on)

Obviously it depends on the number. If the prison master chooses a natural number, then the criminal guesses 1, the first day, 2,the second day and so on until he reaches the correct number. Likewise for the integers 0 on the first day, -1 on the second day. 1 on the third day and so on. If the number is very large then it may take a long time to get out of prison but get out he will.

What the prison master needs to do is choose a set that is not countable in this way. Think of a number line. The integers are widely spaced out. There are plenty of numbers in between the integers 0 and 1 for example. So we need to look at denser sets. The first set that springs to most peoples mind are the fractions. There are an infinite number of fractions between 0 and 1 so surely there are more fractions than integers? Is it possible to count fractions? Let's think about that possibility for a while. If we try to use the approach of counting all the fractions between 0 & 1 then go on to 1 - 2 and so on we will come unstuck because we will never finish counting the ones up to 1 ( there are an infinite number of them). But does this mean that they are uncountable ? Think of the situation with the integers. Ordering them ...-2, -1, 0, 1, 2, ... renders them impossible to count, but reordering them 0, -1, 1, -2, 2, ... allows them to be counted.

There is in fact a way of ordering fractions to allow them to be counted. Before we go on to it let's revert to the normal mathematical language. Mathematicians use the term rational number to define what we have been calling fractions. A rational number is any number that can be written in the form p/q where p and q are integers. So 3/4 is rational, as is -1/2. The set of all rational numbers is usually called Q. Note that Z is a subset of Q because any integer can be divided by 1 to make it into a rational. E.g. the number 3 can be written in the form p/q as 3/1.

Now as all the numbers in Q are defined by two numbers p and q it makes sense to write Q out in the form of a table.

${\begin{matrix}{\frac {1}{1}}&{\frac {1}{2}}&{\frac {1}{3}}&\cdots \\&&\\{\frac {2}{1}}&{\frac {2}{2}}&{\frac {2}{3}}&\cdots \\&&\\{\frac {3}{1}}&{\frac {3}{2}}&{\frac {3}{3}}&\cdots \\\vdots &\vdots &\vdots &\ddots \end{matrix}}$

Note that this table isn't an exact representation of Q. It only has the positive members of Q and has a number of multiple entries.( e.g. 1/1 and 2/2 are the same number) We shall call this set Q'. It is simple enough to see that if Q' is countable then so is Q.

So how do we go about counting Q'? If we try counting the first row then the second and so on we will fail because the rows are infinite in length. Likewise if we try to count columns. But look at the diagonals. In one direction they are infinite ( e.g. 1/1, 2/2, 3/3, ...) but in the other direction they are finite. So this set is countable. We count them along the finite diagonals, 1/1, 1/2, 2/1, 1/3, 2/2, 3/1....

Exercises

1. Adapt the method of counting the set Q' to show that the set Q is also countable. How will you include 0 and the negative rationals? How will you solve the problem of multiple entries representing the same number ?
2. Show that $\infty \times \infty =\infty$ (provided that the infinites are both countable)

Can we find any sets that are bigger than N?

So far we have looked at N, Z, and Q and found them all to be the same size, even though N is a subset of Z which is a subset of Q. You might be beginning to think "Is that it? Are all infinities the same size?" In this section we will look at a set that is bigger than N. A set that cannot be put into a one to one correspondence with N, no matter how it is arranged.

The set in question is R: the real numbers. A real number is any number on the number line. Remember that the set Q contains all the numbers that can be written in the form p/q with p and q integers, q different from 0. Most real numbers can never be put in this form and they are named "irrational numbers". Examples of irrational numbers include $\pi$, $e,$ and ${\sqrt {2}}$.

The set R is huge! Much bigger than Q. To get a feel for the different sizes of these two infinite sets consider the decimal expansions of a real number and a rational number. Rational numbers always either terminate:

• 1/8 = 0.125

or repeat:

• 1/9 = 0.1111111......

Imagine measuring an object such as a book. If you use a ruler you might get 10cm. If you take a bit more care to and read the mm you might get 10.2cm. You'd then have to go on to more accurate measuring devices such as vernier micrometers and find that you get 10.235cm. Going onto a travelling microscope you may find its 10.235823cm and so on. In general the decimal expansion of any real measurement will be a list of digits that look completely random.

Now imagine you measure a book and found it to be 10.101010101010cm. You'd be pretty surprised wouldn't you? But this is exactly the sort of result you would need to get if the book's length were rational. Rational numbers are dense (you find them all over the number line), infinite, yet much much rarer than real numbers.

How we can prove that R is bigger than Q

It's good to get a feel for the size of infinities as in the previous section. But to be really sure we have to come up with some form of proof. In order to prove that R is bigger than Q we use a classic method. We assume that R is the same size as Q and come up with a contradiction. For the sake of clarity we will restrict our proof to the real numbers between 0 and 1. We will call this set R'. Clearly if we can prove that R' is bigger than Q then R must be bigger than Q also.

If R' was the same size as Q it would mean that it is countable. This means that we would be able to write out some form of list of all the members of R' (This is what countable means, so far we have managed to write out all our infinite sets in the form of an infinitely long list). Let's consider this list.

R₁

R₂

R₃

R₄

.

.

.

Where R₁ is the first number in our list, R₂ is the second, and so on. Note that we haven't said what order the list is to be written. For this proof we don't need to say what the order of the list needs to be, only that the members of R are listable (hence countable).

Now lets write out the decimal expansion of each of the numbers in the list.

0.r₁₁r₁₂r₁₃r₁₄...

0.r₂₁r₂₂r₂₃r₂₄...

0.r₃₁r₃₂r₃₃r₄₄...

0.r₄₁r₄₂r₄₃r₄₄...

.

.

.

Here r₁₁ means the first digit after the decimal point of the first number in the list. So if our first number happened to be 0.36921... r₁₁ would be 3, r₁₂ would be 6 and so on. Remember that this list is meant to be complete. By that we mean that it contains every member of R'. What we are going to do in order to prove that R is not countable is to construct a number in R' that is not already on the list. Since the list is supposed to contain every member of R', this will cause a contradiction and therefore show that R' is unlistable.

In order to construct this unlisted number we choose a decimal representation:

0.a₁a₂a₃a₄...

Where a₁ is the first digit after the point etc.

We let a₁ take any value from 0 - 9 inclusive except the digit r₁₁. So if r₁₁ = 3 then a₁ can be 0, 1, 2, 4, 5, 6, 7, 8, or 9. Then we let a₂ be any digit except r₂₂ (the second digit of the second number on the list). Then a₃ be any digit except r₃₃ and so on.

Now if this number, that we have just constructed were on the list somewhere then it would have to be equal to R_something. Let's see what R_something it might be equal to. It can't be equal to R₁ because it has a different first digit (r₁₁ and a₁. Nor can it be equal to R₂ because it has a different second digit, and so on. In fact it can't be equal to any number on the list because it differs by at least one digit from all of them.

We have done what we set out to do. We have constructed a number that is in R' but is not on the list of all members of R'. This contradiction means that R' is bigger than any list. It is not listable. It is not countable. It is a bigger infinity than Q.

Are there even bigger infinities?

There are but they are difficult to describe. The set of all the possible combinations of any number of real numbers is a bigger infinity than R. However trying to imagine such a set is mind boggling. Let's look instead at a set that looks like it should be bigger than R but turns out not to be.

Remember R', which we defined earlier on as the set of all numbers on the number line between 0 and 1. Let us now consider the set of all numbers in the plane from [0,0] to [1,1]. At first sight it would seem obvious that there must be more points on the whole plane than there are in a line. But in transfinite mathematics the "obvious" is not always true and proof is the only way to go. Cantor spent three years trying to prove it true but failed. His reason for failure was the best possible. It's false.

Each point in this plane is specified by two numbers, the x coordinate and the y coordinate; x and y both belong to R. Lets consider one point in the line. 0.a₁a₂a₃a₄.... Can you think of a way of using this one number to specify a point in the plane ? Likewise can you think of a way of combining the two numbers x= 0.x₁x₂x₃x₄.... and y= 0.y₁y₂y₃y₄.... to specify a point on the line? (think about it before you read on)

One way is to do it is to take

a₁ = x₁

a₂ = y₁

a₃ = x₂

a₄ = y₂

.

.

.

This defines a one to one correspondence between the points in the plane and the points in the line. (Actually, for the sharp amongst you, not quite one to one. Can you spot the problem and how to cure it?)

Exercises

1. Prove that the number of points in a cube is the same as the number of points on one of its sides.

Continuum hypothesis

We shall end the section on infinite sets by looking at the Continuum hypothesis. This hypothesis states that there are no infinities between the natural numbers and the real numbers. Cantor came up with a number system for transfinite numbers. He called the smallest infinity $\aleph _{0}$ with the next biggest one $\aleph _{1}$ and so on. It is easy to prove that the cardinality of N is $\aleph _{0}$ (Write any smaller infinity out as a list. Either the list terminates, in which case it's finite, or it goes on forever, in which case it's the same size as N) but is the cardinality of the reals = $\aleph _{1}$?

To put it another way, the hypotheses states that:

There are no infinite sets larger than the set of natural numbers but smaller than the set of real numbers.

The hypothesis is interesting because it has been proved that "It is not possible to prove the hypothesis true or false, using the normal axioms of set theory"

Further reading

If you want to learn more about set theory or infinite sets try one of the many interesting pages on our sister project en:wikipedia.

• ordinal numbers
• Aleph numbers
• Set theory
• Hilbert's Hotel

Limits Infinity got rid of

The theory of infinite sets seems weird to us in the 21st century, but in Cantor's day it was downright unpalatable for most mathematicians. In those days the idea of infinity was too troublesome, they tried to avoid it wherever possible.

Unfortunately the mathematical topic called analysis was found to be highly useful in mathematics, physics, engineering. It was far too useful a field to simply drop yet analysis relies on infinity or at least infinite processes. To get around this problem the idea of a limit was invented.

Consider the series

${\frac {1}{1}},{\frac {1}{2}},{\frac {1}{3}},{\frac {1}{4}},\cdots ,{\frac {1}{n}}\cdots$

This series is called the harmonic series.

Note that the terms of the series get smaller and smaller as you go further and further along the series. What happens if we let n become infinite? The term would become ${\frac {1}{\infty }}$

But this doesn't make sense. (Mathematicians consider it sloppy to divide by infinity. Infinity is not a real number, you can't divide by it). A better way to think about it (The way you probably already do think about it, if you've ever considered the matter) is to take this approach: Infinity is very big, bigger than any number you care to think about. So let's let n become bigger and bigger and see if 1/n approaches some fixed number. In this case as n gets bigger and bigger 1/n gets smaller and smaller. So it is reasonable to say that the limit is 0.

In mathematics we write this as

$\lim _{n\to \infty }{\frac {1}{n}}=0$

and it reads:

the limit of 1/n as n approaches infinity is zero

Note that we are not dividing 1 by infinity and getting the answer 0. We are letting the number n get bigger and bigger and so the reciprocal gets closer and closer to zero. Those 18th Century mathematicians loved this idea because it got rid of the pesky idea of dividing by infinity. At all times n remains finite. Of course, no matter how huge n is, 1/n will not be exactly equal to zero, there is always a small difference. This difference (or error) is usually denoted by ε (epsilon).

info -- infinitely small

When we talk about infinity, we think of it as something big. But there is also the infinitely small, denoted by ε (epsilon). This animal is closer to zero than any other number. Mathematicians also use the character ε to represent anything small. For example, the famous Hungarian mathematician Paul Erdos used to refer to small children as epsilons.

Examples

Lets look at the function

${\frac {x^{2}+x}{x^{2}}}$

What is the limit as x approaches infinity ?

This is where the idea of limits really come into its own. Just replacing x with infinity gives us very little:

$\ {\frac {\infty ^{2}+\infty }{\infty ^{2}}}=?$

But by using limits we can solve it

$\lim _{x\to \infty }{\frac {x^{2}+x}{x^{2}}}=1+\lim _{x\to \infty }{\frac {1}{x}}=1$

For our second example consider this limit as x approaches infinity of $x^{3}-x^{2}$

Again lets look at the wrong way to do it. Substituting $x=\infty$ into the expression gives $\infty ^{3}-\infty ^{2}$. Note that you cannot say that these two infinities just cancel out to give the answer zero.

Now lets look at doing it the correct way, using limits

$\lim _{x\to \infty }x^{3}-x^{2}=\lim _{x\to \infty }x^{2}(x-1)=\infty$

The last expression is two functions multiplied together. Both of these functions approach infinity as x approaches infinity, so the product is infinity also. This means that the limit does not exist, i.e. there is no finite number that the function approaches as x gets bigger and bigger.

One more just to get you really familiar with how it works. Calculate:

$\lim _{x\to \infty }{\frac {\sin x}{x}}$

To make things very clear we shall rewrite it as

$\lim _{x\to \infty }{\frac {1}{x}}(\sin x)$

Now to calculate this limit we need to look at the properties of sin(x). Sin(x)is a function that you should already be familiar with (or you soon will be) its value oscillates between 1 and -1 depending on x. This means that the absolute value of sin(x) (the value ignoring the plus or minus sign) is always less than or equal to 1:

$|\sin x|\leq 1$

So we have 1/x which we already know goes to zero as x goes to infinity multiplied by sin(x) which always remains finite no matter how big x gets. This gives us

$\lim _{x\to \infty }{\frac {1}{x}}(\sin x)=0$

Exercises

Evaluate the following limits;

1. $\lim _{x\to \infty }{\frac {3x^{2}-4}{2x^{2}+x}}$
2. $\lim _{x\to \infty }{\frac {x^{2}-1}{2x^{3}+3}}$
3. $\lim _{x\to \infty }{\frac {cosx}{x^{2}}}$
4. $\lim _{x\to \infty }(2x^{2}-x^{4})$

Infinite series

Consider the infinite sum 1/1 + 1/2 + 1/4 + 1/8 + 1/16 + .... Do you think that this sum will equal infinity once all the terms have been added ? Let's sum the first few terms.

${\begin{matrix}S_{1}&=&{\frac {1}{1}}&=&1\\S_{2}&=&{\frac {1}{1}}+{\frac {1}{2}}&=&1.5\\S_{3}&=&{\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{4}}&=&1.75\\S_{4}&=&{\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}&=&1.8750\\\end{matrix}}$

Can you guess what $S_{\infty }$ is ?

Here is another way of looking at it. Imagine a point on a number line moving along as the sum progresses. In the first term the point jumps to the position 1. This is half way from 0 to 2. In the second stage the point jumps to position 1.5 - half way from 1 to 2. At each stage in the process (shown in a different colour on the diagram) the distance to 2 is halved. The point can get as close to the point 2 as you like. You just need to do the appropriate number of jumps, but the point will never actually reach 2 in a finite number of steps. We say that in the limit as n approaches infinity, S_n approaches 2.

Zeno's Paradox

The ancient Greeks had a big problem with summing infinite series. A famous paradox from the philosopher Zeno is as follows:

In the paradox of Achilles and the tortoise, we imagine the Greek hero Achilles in a footrace with the plodding reptile. Because he is so fast a runner, Achilles graciously allows the tortoise a head start of a hundred feet. If we suppose that each racer starts running at some constant speed (one very fast and one very slow), then after some finite time, Achilles will have run a hundred feet, bringing him to the tortoise's starting point.

During this time, the tortoise has "run" a (much shorter) distance, say one foot. It will then take Achilles some further period of time to run that distance, during which the tortoise will advance farther; and then another period of time to reach this third point, while the tortoise moves ahead. Thus, whenever Achilles reaches somewhere the tortoise has been, he still has farther to go. Therefore, Zeno says, swift Achilles can never overtake the tortoise.

Feedback

What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.