High School Mathematics Extensions/Set Theory and Infinite Processes/Solutions

From Wikibooks, open books for an open world
Jump to: navigation, search
High School Mathematics Extensions75% developed

Supplementary Chapters50% developedPrimes and Modular Arithmetic100% developedLogic75% developed

Mathematical Proofs75% developedSet Theory and Infinite Processes50% developed Counting and Generating Functions75% developedDiscrete Probability25% developed

Matrices100% developedFurther Modular Arithmetic50% developedMathematical Programming0% developed

Set Theory and Infinite Processes[edit]

At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.

If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.

These solutions were not written by the author of the rest of the book. They are simply the answers I thought were correct while doing the exercises. I hope these answers are useful for someone and that people will correct my work if I made some mistakes

How big is infinity? exercises[edit]

  1. The number of even numbers is the same as the number of natural numbers because both are countably infinite. You can clearly see the one to one correspondence. (E means even numbers and is not an official set like N)
E   N
2   1
4   2
6   3
8   4

2. The number of square numbers is also equal to the number of natural numbers. They are both countably infinite and can be put in one to one correspondence. (S means square numbers and is not an official set like N)

S   N
1   1
4   2
9   3
16   4

3. The cardinality of even numbers less than 100 is not equal to the cardinality of natural numbers less than 100. You can simply write out both of them and count the numbers. Then you will see that cardinality of even numbers less than 100 is 49 and the cardinality of natural numbers less than 100 is 99. Thus the set of natural numbers less than 100 is bigger than the set of even numbers less than 100. The big difference between infinite and finite sets thus is that a finite set can not be put into one to one correspondence with any of its subsets, while an infinite set can be put into one to one correspondence with at least one of its subsets.
4. Each part of the sum is answered below

infinity + 1 = infinity
You can prove this by taking a set with a cardinality of 1, for example a set consisting only of the number 0. You simply add this set in front of the countably infinite set to put the infinite set and the inifinite+1 set into one to one correspondence.
N   N+1
1   0
2   1
3   2
4   3
infinity + A = infinity (where A is a finite set)
You simply add the finite set in front of the infinite set like above, only the finite set doesn't need to have a cardinality of one anymore.
infinity + C = infinity (where C is a countably infinite set)
You take one item of each set (infinity or C) in turns, this will make the new list also countably infinite.

Is the set of rational numbers bigger than N? exercises[edit]

1. To change the matrix from Q' to Q the first step you need to take is to remove the multiple entries for the same number. You can do this by leaving an empty space in the table when gcd(topnr,bottomnr)≠1 because when the gcd isn't 1 the fraction can be simplified by dividing the top and bottom number by the gcd. This will leave you with the following table.

Now we only need to add zero to the matrix and we're finished. So we add a vertical row for zero and only write the topmost element in it (0/1) (taking gcd doesn't work here because gcd(0,a)=a) This leaves us with the following table where we have to count all fractions in the diagonal rows to see that Q is countably infinite.

2. To show that you have to make a table where you put one infinity in the horizontal row and one infinity in the vertical row. Now you can start counting the number of place in the table diagonally just like Q' was counted. This works because a table of size AxB contains A*B places.

Are there even bigger infinities? exercises[edit]

  1. You have to use a method to map the coordinates in a plain onto a point on the line and the other way around, like the one described in the text. This method shows you that for every number on the line there is a place on the plain and for every place on the plain there is a place on the line. Thus the number of points on the line and the plain are the same.