MAT511 homework,         Sept. 10, 2003

1. As we did in class, consider the following axiomatic system describing a system of people and clubs. We are considering a finite, nonempty collection $S$ of people, and want to describe the clubs to which they belong.

   Definition

   A club is a non-empty set of people which satisfies certain axioms as outlined below.

   Definition

   If two clubs have no members in common, they are called conjugate clubs. If $\mathcal{C}$ is our club, we can use $\overline{{\mbox{$\mathcal{C}$}}}$ to denote a club which is conjugate to $\mathcal{C}$.

   Axiom 1

   Every person of $S$ is a member of at least one club. (If $p$ is a person in club $\mathcal{C}$, we can use the notation $p\in{\mbox{$\mathcal{C}$}}$ to express this fact.)

   Axiom 2

   For every pair of people of $S$, there is one and only one club to which they both belong.

   Axiom 3

   For every club, there is one and only one conjugate club. (Note that as a consequence of this axiom, the notation $\overline{{\mbox{$\mathcal{C}$}}}$ is not ambiguous. Without this axiom, $\overline{{\mbox{$\mathcal{C}$}}}$ might refer to two different clubs, or no clubs at all.)

   Using these axioms and definitions, we proved the following

   Theorem 1   Every person of $S$ is a member of at least two clubs.

   Here is how the proof we came up with went, pretty much:

   Proof. Let $p$ be an arbitrary person in $S$. By Axiom 1, there is a $\mathcal{C}$ with $p\in{\mbox{$\mathcal{C}$}}$.

   By Axiom 3, there is another club $\overline{{\mbox{$\mathcal{C}$}}}$ which is conjugate to $\mathcal{C}$. By the definition of conjugate, $p$ is not a member of $\overline{{\mbox{$\mathcal{C}$}}}$, and since clubs are nonempty, there must be some other person $q$ for which $q\in{\mbox{$\overline{{\mbox{$\mathcal{C}$}}}$}}$, and also $q\not\in{\mbox{$\mathcal{C}$}}$.

   Now, by Axiom 2, both $p$ and $q$ must be in some club together, but this is neither $\mathcal{C}$ (since $q\not\in{\mbox{$\mathcal{C}$}}$) nor is it $\overline{{\mbox{$\mathcal{C}$}}}$ (since $p\not\in{\mbox{$\overline{{\mbox{$\mathcal{C}$}}}$}}$). Thus, there is a third club $\mathcal{D}$, with $p\in{\mbox{$\mathcal{D}$}}$. So $p$ is in at least two different clubs, namely $\mathcal{C}$ and $\mathcal{D}$.

   Since $p$ was chosen arbitrarily in $S$, we have shown that each person in $S$ is a member of at least two clubs. $\qedsymbol$

   You should prove the following three theorems in this system. You can, of course, use things you have already proven in your proofs.

   Theorem 2   Every club contains at least two members.
   Theorem 3   $S$ contains at least four people.
   Theorem 4   There exist at least six different clubs.

2. During the first class, we proved that $\sqrt 2$ is irrational. Write a proof that $\sqrt 3$ is irrational, using a similar argument.

   In case you forgot, what we did was to assume that there was a rational number $p/q$ in lowest terms for which

   $$\left( \frac{p}{q} \right)^2 = 2$$
   and arrived at the conclusion that both $p$ and $q$ are even, contradicting the assumption that $p/q$ were in lowest terms.

3. Section 1.5 in the 4th edition of the text (I passed out xeroxes), problems 2, 5, and 8abc. If you have the 5th edition, this is section 1.6, problems problems 2, 5, and 7abc.

4. §1.6 in 4th edition of the text, problems 1, 3. In the 5th edition, this is section 1.7, problems 1, 3.

I'd like you to try all the problems. If you run short of time, I am most interested in your work on the first two problems. Let me know on your homework sheet how much time this assignment took you, so I can gauge things.