# 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. ${\displaystyle A\subseteq B}$ if and only if ${\displaystyle A\cap B=A}$.
2. ${\displaystyle A\subseteq B}$ if and only if ${\displaystyle A-B=\emptyset }$.
3. ${\displaystyle A-B=(A\cup B)-B}$.
4. ${\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C)}$.
5. ${\displaystyle A\cap B=A-(A-B)}$.

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

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

A proof of the first goes as follows.

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

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

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

So assume then that ${\displaystyle A\cap B=A}$. We want to show that ${\displaystyle A\subseteq B}$. If we choose ${\displaystyle x\in A}$ arbitrarily, then since ${\displaystyle A\cap B=A}$, we have that ${\displaystyle x\in B}$ as well. But this shows that ${\displaystyle 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 ${\displaystyle 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.