I. Sets and Relations

1. Using the basic definition of subsets, show that the empty set is a subset of every set.
2. Definitions:  A relation $R$ on any set $A$ is said to be:
   • Reflexive:   if $\forall x \in A,~~(x,x) \in R$.
   • Transitive:   if $\forall x,y,z \in A,~~((x,y) \in R~AND~(y,z) \in R) \Rightarrow (x,z) \in R$.
   • Symmetric:   if $\forall x,y \in A,~~(x,y) \in R \Rightarrow (y,x) \in R$.
   • Asymmetric:   if $\forall x,y \in A,~~(x,y) \in R \Rightarrow (y,x) \notin R$.

   For each of the following relations, state which of the above five properties hold. We will represent the relation using the symbol $R$.

   1. For $x,y \in \integers$,   $(x,y) \in R \Rightarrow |x| = |y|$.
   2. For $x,y \in \integers$,   $(x,y) \in R \Rightarrow x \lt y$.
   3. For $x,y \in \integers$,   $(x,y) \in R \Rightarrow x+y$ is even.

II. Induction

1. Prove the following proposition \[ P(n):~~~ 2n + 1 \lt 2^n~~{\rm~for~all~} n \geq 3 \]
2. We have seen in class how a chess board of size $2^n$ can be completely filled using $L$-shaped blocks, leaving one square empty as shown in the following figures. In class we used the specific construction that the empty square is at a corner of the board. Using induction, prove that this empty square could, in fact, be placed anywhere in the board.

   

   Figure. Left: A board of size $2^n$ ($n=2)$ filled using L-shaped blocks of size 3, leaving a corner square empty. Right: Filling the same board leaving a different square empty.
3. Using induction, prove that every day is the same day of the week. Formally, you must prove the hypothesis $P(n)$ that “All days in any set of $n$ days are the same day of the week”. In order to do so, you must make a questionable assumption of the base case. Explain the problem. Wikipedia will give you the wrong answer, so don't bother with it.

III. Counting

1. Prove that the set $\{1, 2, 7, 9, 10, 12\}$ is finite.
2. Show that the intersection of a finite set and a countable set is finite.
3. Show that the union of two finite sets is finite.

IV. Axioms

A field is a set for which we have defined an “addition” operation, usually denoted by “$+$”, and a “multiplication” operation, usually denoted by “$\times$”, which satisfy the following axioms. We will denote the field by the symbol $F$ below.

Axioms of addition:

• A1:   $F$ is closed under addition. If $x\in F$ and $y \in F$, then $x+y \in F$.
• A2:   Addition is commutative. $x+y = y+x$.
• A3:   Addition is associative. $x+(y+z) = (x+y)+z$.
• A4:   $F$ contains an element $0$, the “additive identity element”, such that for all $x\in F$, $x + 0 = x$.
• A5:   For every $x \in F$, there is a corresponding “additive inverse” $y \in F$ such that $x+y = 0$. We will represent this additive inverse as “$-x$”.

Axioms of multiplication:

• M1:   $F$ is closed under multiplication. If $x\in F$ and $y \in F$, then $x\times y \in F$.
• M2:   Multiplication is commutative. $x\times y = y\times x$.
• M3:   Multiplication is associative. $x\times(y\times z) = (x\times y)\times z$.
• M4:   $F$ contains a “multiplicative identity” element $1 \neq 0$, such that for all $x\in F$, $x \times 1 = x$.
• M5:   For every $x \in F$, if $x \neq 0$, there is a corresponding “multiplicative inverse” $y \in F$ such that $x\times y = 1$. We will represent this multiplicative inverse as “$\frac{1}{x}$”.

The distributive law: for all $x, y, z \in F$, \[ x\times (y+z) = x\times y + x \times z. \]

Note that the above are axioms. They cannot be derived. They are simply established by definition or diktat.

Using the axioms of multipication, prove the following.

1. If $x \neq 0$ and $x \times y = x \times z$, then $y = z$.
2. If $x \neq 0$ and $x \times y = x$, then $y = 1$.
3. If $x \neq 0$ and $x \times y = 1$, then $y = \frac{1}{x}$.
4. If $x \neq 0$, then $\frac{1}{\frac{1}{x}} = x$.