Tuesday 22 November and Tuesday 29 November classes

Activities: Area paradoxes
Area paradox Math Less Traveled
Area paradox  triangle problem: here is another link with hints and discussion
Both of these have connections to Fibonacci numbers: that is not an accident.

Topics:
• Proving that the power set  of a set S is always strictly larger in size (cardinality) than the original set S, even when S is an infinite set. This is usually called Cantor's Theorem.

We do not exactly do the proof, but rather we indicate how the proof is done. The problem is that the set we start with may be uncountable, so we cannot assume that we can list its elements. If you are interested to see how an actual proof appears, here is a fairly accessible one (The proof is at the end of the article: but be warned that they use some notation and terms that may be new to you!)

The Wikipedia article on Cantor's Theorem contains a description of how the proof would work if the original set is countable (listable), specifically if the original set is the set of natural numbers. In order to make the proof more general, you should notice that it does not depend on being able to list all of the elements of the one-to-one correspondence: that is only done for convenience (in order to be very concrete). The center of the proof is the rule we use for deciding whether or not each element of the original set should be included in the new set we construct, and that rule can be used whether or not we can list all of the elements of the original set. We just have to give up the idea that we can think of using the rule one-by-one on the elements, and think of using it on all of them "at the same time" so to speak.

I have written up rough notes on the proof as I described it in class which are available here. They are unedited, so please let me know if you find anything that looks wrong or any typographical or other errors!

Next we returned to looking at the sizes of power sets. We already found the following result: For a finite set S, if |S| = n, then the size of the power set of S will be 2ⁿ. This is why it is called the power set!

The same thing holds if S is an infinite set, except that then the numbers we get are not real numbers. But there is a way to interpret what 2ⁿ means even if n is an infinite numbers, and the point is, we have proved that 2ⁿ (the cardinality of the power set) is larger than n (the cardinality of the original set) even when n is an infinite number.

Recall that the cardinality of the set of natural numbers (or of any countable set) is denoted by א‎₀ (aleph-naught or aleph-null) : The power set of the set of natural numbers is the set of real numbers (actually, we should say that the power set of the natural numbers can be put in one-to-one correspondence with the real numbers), so the cardinality of the set of real numbers is 2^א‎₀.

The Continuum Hypothesis is the statement that there is no cardinality that is between א‎₀ and 2^א‎₀, so 2^א‎₀ would be the "next in line" in the infinite cardinalities. It is now known that this statement cannot be proved either true or false in the mathematical system we use. (A somewhat accessible article explaining this, by Juliette Kennedy, is available from the Institute for Advanced Study.Warning: it's long, because it gives some history of the problem and also explains some of the concepts and ideas involved.)

However, with or without the Continuum Hypothesis, we can show that there are in fact an infinite number of "sizes of infinity"! How to do this: we can take the power set of a set S, and form the power set of the power set:

So if |S|=3, we know that |P(S)| = 2³ = 8
Form the power set of the power set: its size is |P(P(S))| = 2⁸ = 256
Form the power set of the power set of the power set: its size is |P(P(P(S)))| = 2²⁵⁶ = a really big number! (It has 78 digits)
And we can continue this process indefinitely. This gives us a "tower of powers" where each successive number is 2 to the power of the last one.

The same thing can be done starting with an infinite set, the set of natural numbers. Then we get an infinite "tower of powers" with each one being an infinite cardinality which is strictly larger than the one that came before it. So there are (at least!) countably many sizes of infinity.

Next topic: Stating and proving the Pythagorean Theorem
Note: what we will do through the remainder of the course will be more geometrical, to take a break from the analytical stuff we have done so far. It will still be "Thinking Mathematically", but in a little different way.

For the statement of the Pythagorean Theorem, see the post from Math is Fun, and also the Regent's Prep post
Cut-the-Knot has a list of 118 different proofs of this theorem. Why prove a theorem more than one way? Because every proof sheds a little different light on the theorem. This theorem is so important (maybe the most important theorem in mathematics!) that we keep coming back and looking at it again from different points of view.

The proof we will examine is this one, called "algebraic" by Math is Fun, although it is also geometric.

Next time: We will look more carefully at the picture in that proof, and make sure that all the angles add up as they should! (Being careful after being warned by those area paradoxes.) We will also look at the two proofs given in the original Math is Fun article about the Pythagorean Theorem.(They are near the bottom of the page.)

Homework:
• Go to this Math is Fun article about power sets, and find the Questions at the bottom of the page. Do Questions 1-8 (you can skip #9 and #10). While you do them, record in your journal what work you did to answer the question, what answer you got, was it right or wrong, and what you learned.

• Make sure that you understand how the proof of Cantor's Theorem works, and also how we know that there are an infinite number of sizes of infinity - in other words, an infinite number of infinite cardinalities.

• Read the two links above to Math is Fun on the Pythagorean Theorem and on the proof of the Pythagorean Theorem, looking specifically at the proofs so you are prepared to examine them closely next time.

Thursday 17 November class

Topics:

• Some set notation that we need
  See the Set post from Math is Fun
  Also: cardinality of a set
The cardinality of a set A is the size of that set: we use the notation |A| for the cardinality of the set A.
For a finite set A, the cardinality is just the number of elements in A:
if A has n elements, then |A|=n.
For an infinite set, we have to define different cardinalities, according to which sets are in one-to-one correspondence with each other.
We define the cardinality of the set of natural numbers  (or any countable set) to be aleph-null (or aleph-nought), designated by the symbol  ℵ₀ - this kind of infinite size number is called a transfinite number).

• Power sets
  See the Power Set post from Math is Fun, and also in Wikipedia: the power set of A is the set whose elements are all the subsets of A.
  The important thing we need from Power Sets is that the power set of a set A has size greater than the size of A: If |A|=n, then the power set of A has 2ⁿ elements. We prove that by making a one-to-one correspondence between the elements of the power set and the binary numbers with n digits: we then need to know that there are exactly 2ⁿ binary numbers with n digits.
So in fact, the size of the power set is exponentially greater than the size of A.
This will continue to be true even for infinite sets, as we will discuss more next time.

Homework:
• Make sure that you review the notation for sets and cardinalities of sets given and linked above.
• Problems:
1) Write down all of the 4-digit binary numbers in a list (as is done in the Power Set post from Math is Fun, under "It's Binary!", for 3-digit numbers)
2) For the set {red, yellow, green, blue}, give the power set by listing the subset that corresponds to each binary number in the list from problem #1. How many elements does the power set have?

For next time: We'll look at power sets of infinite sets, how we can prove that the power set of an infinite set has larger cardinality than the original set, and how to show that there is an infinite number of sizes of infinity!

Preliminary Reading: Ask Dr. Math on finding the power set of a power set

P.S. no journals due yet: you'll submit them Tuesday, since there is no class on Thursday next week!

Thursday 10 November class

• Activity: "Dodge Ball" from The Heart of Mathematics

Topics: How to count/measure infinite sets!

First we have to examine closely what we do when we count a finite set. Essentially we are making what is called a one-to-one correspondence between the first however-many counting numbers (the natural numbers) and the items that we are counting.

The idea of one-to-one correspondence is what will carry over into infinite sets.

• David Hilbert's Hotel, and some theorems about the sizes of some infinite sets: See the Science4All article. (Warning: it contains math notation that may not display correctly on a phone. Here is another article which uses less math notation but has fewer details)

If an infinite set of numbers (or anything else) can be put into a one-to-one correspondence with the st of natural numbers (that is, it can be put into the form of an infinite list), we say it is a countable set. In the Science4All article, countable sets are called listable, which is a good name for them but is not standard.

First we discussed Hilbert's infinite hotel. Even if every room is occupied, we can accommodate an additional guest, or even a countably infinite number of guests! So you can say "infinity plus 1 is infinity" or "infinity plus infinity is infinity" - but wait! That second statement needs some care, because it turns out there are different sizes of infinity.

We showed the following in class:
 • The whole numbers are countable (listable)
 •  The even numbers are countable (listable)
 •  The integers are countable (listable) - this is also proved in some of the videos linked below
 •  The rational numbers are countable (listable) - this is also proved in some of the videos linked below
 • The real numbers are not countable. In other words, the set of real numbers is larger than the set of natural numbers (or even the set of rational numbers)!
The implication of this is that the set of irrational numbers is uncountable, which means that it is reasonable to say that there are more irrational numbers than rational numbers. (More on this next time.)

Look for the proofs of the following theorems in the article or in this video and this video (for the Cantor proof) , and here is another video as well. (all three of them are worth watching.)

    • Theorem: The integers are countable (listable)
    • Theorem: all countable (listable) sets have the same size (same number of elements)
    • Theorem: The rational numbers are countable (listable)
   And then the big one:
    • Theorem: The real numbers are uncountable (they are not listable).
The last one is Cantor's diagonal proof, and it relies on the strategy that Player 2 can use for "Dodge Ball" to make sure they always win.


Homework:
• Journal assignment: write the proofs of the Theorems listed above in your own words.
• Prove that the odd numbers are countable (listable) by pairing them up with the natural numbers. (Make a one-to-one correspondence with the natural numbers. Watch the videos linked above if you have doubt about what this means.)

• Next time: Power sets and the Continuum Hypothesis. (The continuum is another name for the real number line.)
  See Math is Fun on sets for some set notation that we will be using.

Test 3 Review, with answers/links

Test 3 is (re)scheduled for Tuesday 15 November.

The Test 3 Review problems are here. (link fixed)

Answers, and/or links to the relevant posts, are below the fold... I am temporarily working with an old computer which is very slow and has slow internet connection and has a difficult ketboard, so pardon any uncorrected typos (let me know about them!)

Thursday 3 November class

Topics:
• Proving that the square root of 2 is irrational: here are my notes, which I handed out in class. We also imitated that proof in the case of the square root of 3.

A similar proof will work in any case of a square root of a prime number. All square roots of prime numbers are irrational. But even more is true: If n is any positive integer (natural number) which is not a perfect square, then the square root of n is irrational. It is just a little more work to prove this if n is not a prime number, as you will see in the exercises.

• Density of rational numbers:
Theorem: between any two rational numbers, there is another rational number.
Proof: Take the average of the two rational numbers. The result is another rational number which is halfway between them.

Example: between $\frac{1}{2}$ and $\frac{3}{4}$ we can find the number $\left(\frac{1}{2} + \frac{3}{4}\right)\frac{1}{2}$ (their average, where instead of dividing by 2 we have multiplied by 2, which is the same thing. This comes out to be $\frac{5}{8}$, which is in between $\frac{1}{2}$ and $\frac{3}{4}$ and is a rational number.

Note: this is not the only rational number in between $\frac{1}{2}$ and $\frac{3}{4}$: but we only needed to show that there was at least one. So this one is convenient to find.

• A consequence of this theorem is that between any two rational numbers there is an infinite number of rational numbers. You can find rational numbers as close together as you like on the real number line. We say that the rational numbers are dense in the real numbers.

But even though the rational numbers are so close together and "thick" on the real line, there is still room enough for an infinite number of irrational numbers! In fact, as we will see next time, there are (in a very concrete sense) more irrational numbers than rational numbers.
• It follows from this that in between every two rational numbers there are infinitely many rational numbers. (Just keep taking averages of averages...)

• Comment: in fact, between every two real numbers (whether or not they are rational) there is a rational number, and also between every two real numbers there is an irrational number. The proofs of those facts are harder so we do not discuss them in this course. Ask Dr. Math gives a proof of the first statement here.

Homework:
• Journal assignment:
- The proof that the square root of 2 is irrational uses at one point the fact that if  a² is divisible by 2, then a must itself be divisible by 2. This happens because of the Fundamental Theorem of Arithmetic (Unique Prime Factorization). Explain why this is so. (Give an example, it may help. Factor both a and a² into primes and see how their prime factorizations are related to each other.)
- What goes wrong if you try to imitate this proof to prove that the square root of 4 is irrational?


• Problems to do:
Related to 0.999999,,, = 1:
1) Write 0.09999999... as a fraction in lowest terms.
2) Write 0.29999999... as a fraction in lowest terms
3) Write 0.45999999... as a fraction in lowest terms

4) Prove that the square root of 5 is irrational

5) Prove that the square root of 6 is irrational. Since 6 is not a prime number, you will have to think about how to handle the step where we say "since a² is divisible by 6, then a must itself be divisible by 6."

6) Challenge! This is extra credit. Prove that the square root of 12 is irrational. You must be extra-careful at the above-mentioned step here!

Next up: Hilbert's Hotel, which always has room for more: up to a point, that is. Measuring the size of infinity. Yes, it makes sense.
Please watch this video and this video (for the Cantor proof) , and here is another video as well. (all three of them are worth watching.)

Report on RSA or other topic (Project 1) - UPDATED

- Report on RSA topic: due Thursday 10 November

Write an essay on one of the following topics, or if you have another idea check with me by email not later than Sunday:
* The history of the RSA algorithm and the people who developed it
* Current uses of the RSA algorithm and other public-key security
* The problem of computer factoring of large numbers: How long would it currently take to factor a number with 100 or more digits? What progress has been made recently? How would this affect the security of the RSA algorithm?

You should use at least two different sources for your essay. List your sources in correct format and make sure to cite them (cite sources for quotes and make bibliography) correctly. Your essay should be approximately 2 pages long (typed in no bigger than 12 point font.)

Citation styles source here. You may use APA style (this is the one most commonly used in the sciences) or MLA if you are more familiar with it.

Note: You may work together with another student, if you like: both together should produce one paper. If you want to do this, please let me know by email BEFORE the due date.

Rational and Irrational numbers UPDATED - Tuesday 1 November class

Update: here are some links to good sources about how people in Euclid's time and place thought about numbers, and about the Pythagoreans in particular:
Euclid's Proof of the Infinitude of Primes (from the Prime Pages, a great source for all things related to prime numbers. This discussed how the numbers were viewed at Euclid's time and place.)
Pythagorus - Greek Mathematics (from The Story of Mathematics website)
Pythagoras - The Music and Math Connection (video, from the Science Channel: Warning: video may autoplay)

• Rational and Irrational numbers:
We begin by defining some important sets of numbers (some we have seen before):
the Natural numbers - which are also called the positive integers
the Whole numbers (which include the Natural numbers) - also called the non-negative integers
the Integers (which include the Whole numbers)
the Rational numbers (which include the Integers)
If we think of "number" as a directed distance  ( a vector) starting from 0 on the number line, then there are points on the number line that correspond to these numbers we have defined so far. But it turns out that there are ponts (distances) which cannot be represented as a ratio of integers. We call these numbers Irrational numbers.

Examples of numbers which are irrational include π and the square root of 2. We will prove later that the square root of 2 is irrational.

We showed how the square root of 2 appears as a length (distance), namely, the hypotenuse of a right triangle whose sides both have length 1. Using the Pythagorean Theorem, the hypotenuse has length the square root of 2.

For any rational number, we can prove (using the Pigeonhole Principle) that its decimal expansion will either terminate or (eventually) repeat (here's another description of the proof from A Math Less Travelled): also, conversely, a terminating or repeating decimal will always represent a rational number. So from this we know that an irrational number must be represented by a nonterminating, nonrepeating decimal. That decimal is called the decimal expansion of the number.

More on the decimal expansions of rational numbers: how long can they go on before they repeat? (Here is a discussion similar to what I said in class which also uses the Pigeonhole principle: scroll down at that link until the header "Decimal representations of rational". )


How to write a repeating decimal as a ratio of integers: videos from Khan Academy part 1, part 2
  So 0.9999999... = 1
[A better way to prove that 0.9999999... = 1 uses the idea of limit and the sum of an infinite geometric series - this is usually done in pre-calculus classes. The fact is that an infinite decimal expansion is really an infinite sum: 0.9999999... means 9/10 + 9/100 + 9/1000 + 9/10000 + ... (the sum has infinitely many terms).]


Homework:
(Journal assignment pending)

Problems to do:
1) By using long division by hand, find the decimal expansions of these rational numbers:
    $\frac{1}{250}$
    $\frac{3}{11}$
    $\frac{7}{12}$
2) Rewrite the following decimals as ratios of integers: reduce to lowest terms
    2.3
    0.056
    0.1717171717...
    0.2555555...

 
Next up: proving that the square root of 2 is irrational; other irrational numbers; more on decimal expansions; the Real Numbers