These are a list of problems from class that are not to be handed in.
A list of questions was given out in class. Here is a .pdf of them.
Solutions are here:
Prove the following, and draw Venn diagrams to illustrate each of them.
- if and only if .
- if and only if .
Show using Venn diagrams an example where each of the following fail.
- implies or .
A proof of the first goes as follows.
Proof: We want to show that implies , and that implies .
Assume that . We want to show that . We know that , so it remains to show the reverse containment; that is, that .
So let . As , we have that as well. Since and , we have that , and so we conclude that .
So assume then that . We want to show that . If we choose arbitrarily, then since , we have that as well. But this shows that as claimed. QED
This problem was stated in class a few days ago.
What is wrong with the following induction proof?
Theorem: All horses are the same colour.
Proof: We prove by induction that for every positive integer n, that a set of n horses must all be the same colour.
The base case is trivially true. If you have 1 horse, it is the same colour as itself. So assume by induction that all groups of n horses must be of the same colour, and let S be a group of horses. If we line up the horses in a row, the first n horses are a group of n horses and so must be all the same colour. Similarly, the last n horses must all be of a single colour. As these two groups overlap, it follows that both of these colours must be the same, and so the whole group must be of a single colour.
Thus be the principle of mathematical induction, it follows that all horses are the same colour.
In class we discuss the following construction.
Start with an equilateral triangle.
At each stage, divide every existing line segment into three equal parts, and remove the middle part, to add back an equilateral triangle in its place.
The two questions that I asked are as follows:
1. What should be a plausible area of the resulting object?
2. What should be a plausible perimeter or the end result?
In both cases, you should be begin by trying to compute the area or perimeter of each stage, and see what happens "in the limit".