# Course:MATH220/Archive/2010-2011/921/Exercises

These are a list of problems from class that are not to be handed in.

## Contents

### May 26th

A list of questions was given out in class. Here is a .pdf of them.

Solutions are here:

### June 2nd

Prove the following, and draw Venn diagrams to illustrate each of them.

1. $A\subseteq B$ if and only if $A\cap B=A$ .
2. $A\subseteq B$ if and only if $A-B=\emptyset$ .
3. $A-B=(A\cup B)-B$ .
4. $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$ .
5. $A\cap B=A-(A-B)$ .

Show using Venn diagrams an example where each of the following fail.

1. $A-B=B-A$ .
2. $A\subseteq B\cup C$ implies $A\subseteq B$ or $A\subseteq C$ .

A proof of the first goes as follows.

Proof: We want to show that $A\subseteq B$ implies $A\cap B=A$ , and that $A\cap B=A$ implies $A\subseteq B$ .

Assume that $A\subseteq B$ . We want to show that $A\cap B=A$ . We know that $A\cap B\subseteq A$ , so it remains to show the reverse containment; that is, that $A\subseteq A\cap B$ .

So let $x\in A$ . As $A\subseteq B$ , we have that $x\in B$ as well. Since $x\in A$ and $x\in B$ , we have that $x\in A\cap B$ , and so we conclude that $A\subseteq A\cap B$ .

So assume then that $A\cap B=A$ . We want to show that $A\subseteq B$ . If we choose $x\in A$ arbitrarily, then since $A\cap B=A$ , we have that $x\in B$ as well. But this shows that $A\subseteq B$ as claimed. QED

### July 4th

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 $n+1$ 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.

QED

### July 5th

In class we discuss the following construction.