Introduction

Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set.

Write formal descriptions of the following sets.

Let $A$ be the set $\left\{ \mathrm{x}, \mathrm{y}, \mathrm{z}\right\}$ and $B$ be the set $\left\{ \mathrm{x}, \mathrm{y}\right\}$.

If $A$ has $a$ elements and $B$ has $b$ elements, how many elements are in $A \times B$? Explain your answer.

If $C$ is a set with $c$ elements, how many elements are in the power set of $C$? Explain your answer.

Let $X$ be the set $\left\{ 1,2,3,4,5\right\}$ and $Y$ be the set $\left\{ 6,7,8,9,10\right\}$. The unary function $f: X \longrightarrow Y$ and the binary function $g: X \times Y \longrightarrow Y$ are described in the following tables.

For each part, give a relation that satisfies the condition.

Consider the undirected graph $G=(V, E)$ where $V$, the set of nodes, is $\left\{ 1,2,3,4\right\}$ and $E$, the set of edges, is $\left\{ \left\{ 1,2\right\} ,\left\{ 2,3\right\} ,\left\{ 1,3\right\} ,\left\{ 2,4\right\} ,\left\{ 1,4\right\} \right\}$. Draw the graph $G$. What are the degrees of each node? Indicate a path from node 3 to node 4 on your drawing of $G$.

Write a formal description of the following graph.

Find the error in the following proof that $2=1$. Consider the equation $a=b$. Multiply both sides by $a$ to obtain $a^{2}=a b$. Subtract $b^{2}$ from both sides to get $a^{2}-b^{2}=a b-b^{2}$. Now factor each side, $(a+b)(a-b)=b(a-b)$, and divide each side by $(a-b)$ to get $a+b=b$. Finally, let $a$ and $b$ equal 1, which shows that $2=1$.

Let $S(n)=1+2+\cdots +n$ be the sum of the first $n$ natural numbers and let $C(n)=1^{3}+2^{3}+\cdots +n^{3}$ be the sum of the first $n$ cubes. Prove the following equalities by induction on $n$, to arrive at the curious conclusion that $C(n)=S^{2}(n)$ for every $n$.

Find the error in the following proof that all horses are the same color. Claim: In any set of $h$ horses, all horses are the same color. Proof: By induction on $h$. Basis: For $h=1$. In any set containing just one horse, all horses clearly are the same color. Induction step: For $k \geq 1$, assume that the claim is true for $h=k$ and prove that it is true for $h=k+1$. Take any set $H$ of $k+1$ horses. We show that all the horses in this set are the same color. Remove one horse from this set to obtain the set $H_{1}$ with just $k$ horses. By the induction hypothesis, all the horses in $H_{1}$ are the same color. Now replace the removed horse and remove a different one to obtain the set $H_{2}$. By the same argument, all the horses in $H_{2}$ are the same color. Therefore, all the horses in $H$ must be the same color, and the proof is complete.

Show that every graph with two or more nodes contains two nodes that have equal degrees.

• ᴬ Ramsey's theorem. Let $G$ be a graph. A clique in $G$ is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with $n$ nodes contains either a clique or an anti-clique with at least $\frac{1}{2} \log_{2} n$ nodes.

ᴬ Use Theorem 0.25 to derive a formula for calculating the size of the monthly payment for a mortgage in terms of the principal $P$, the interest rate $I$, and the number of payments $t$. Assume that after $t$ payments have been made, the loan amount is reduced to 0. Use the formula to calculate the dollar amount of each monthly payment for a 30 -year mortgage with 360 monthly payments on an initial loan amount of $100,000 with a 5 annual interest rate.