Archive

Archive for October 10th, 2009

1.4 Exercise 5

I had often wondered how to go about proving closure of addition and multiplication of the integers.  After this problem I wondered no more!  It's pretty neat that we can show (by using induction) that by adding any two integers or multiplying them you always get another integer.

"Prove the following properties of $\mathbb{Z}$ and $\mathbb{Z}_+$:

(a) $a, b \in \mathbb{Z}_+ \Rightarrow a+b \in \mathbb{Z}_+$.  [Hint: Show that given $a \in \mathbb{Z}_+$, the set $X = \{x \ | \ x \in \mathbb{R}$ and $a+x \in \mathbb{Z}_+\}$ is inductive.]

(b) $a, b \in \mathbb{Z}_+ \Rightarrow a \cdot b \in \mathbb{Z}_+$.

(c) Show that $a \in \mathbb{Z}_+ \Rightarrow a - 1 \in \mathbb{Z}_+ \cup \{0\}$.  [Hint: Let $X = \{x \ | \ x \in \mathbb{R}$ and $x - 1 \in \mathbb{Z}_+ \cup \{0\}$; show that $X$ is inductive.]

(d) $c, d \in \mathbb{Z} \Rightarrow c + d \in \mathbb{Z}$ and $c - d \in \mathbb{Z}$. [Hint: Prove it first for $d = 1$.]

(e) $c, d \in \mathbb{Z} \Rightarrow c \cdot d \in \mathbb{Z}$."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 35.)

----

SOLUTION

(a)

Using the hint, we proceed by

• Showing $1 \in X$.  Since $a \in \mathbb{Z}_+$, and $\mathbb{Z}_+$ is inductive, it follows that $a + 1 \in \mathbb{Z}_+$.   Therefore $1 \in X$.
• Supposing $k \in X$.  This of course means $a + k \in \mathbb{Z}_+$.
• Showing $k+1 \in X$.  This would mean $a + (k + 1) \in \mathbb{Z}_+$.  Note that by commutativity  and associativity (of the reals, of the integers), we can state $(a + 1) + k$.  But then we know that $(a + 1) \in \mathbb{Z}_+$ by the first point, and that $(a+1) + k \in \mathbb{Z}_+$ by the second point.  So we conclude that indeed $a + (k + 1) \in \mathbb{Z}_+$.

Thus $X$ is inductive.  In particular, then, $\mathbb{Z}_+ \subset X$.  It follows that if we pick $b \in \mathbb{Z}_+ \subset X$, with $a \in \mathbb{Z}_+$ by hypothesis, then we are guaranteed $a+b \in \mathbb{Z}_+$.

(b)

This is proved the same way as before, with a few minor modifications.  Again suppose $a \in \mathbb{Z}_+$.  Let $X' = \{x \ | \ x \in \mathbb{R}$ and $a \cdot x \in \mathbb{Z}_+\}$.  Again we want to show that $X'$ is inductive.

• $1 \in X'$, since $a \cdot 1 = a \in \mathbb{Z}_+$ (by identity axiom of the reals).
• Assume $k \in X'$. This means $a \cdot k \in \mathbb{Z}_+$.
• $k + 1 \in X'$, since $a ( k + 1) = a \cdot k + a$ (by the distributive property axiom of the reals), with $a \in \mathbb{Z}_+$ by the first point and $a \cdot k \in \mathbb{Z}_+$ by the second point.  Finally, $a \cdot k + a \in \mathbb{Z}_+$ by what we proved in part (a).

We conclude $X'$ is inductive, and contains $\mathbb{Z}_+$.  As before, with $a \in \mathbb{Z}_+$, pick $b \in \mathbb{Z}_+ \subset X'$, and we are guaranteed the product $a \cdot b \in \mathbb{Z}_+$.

(c)

Again following the hint, we show:

• $1 \in X$.  This is because $1 - 1 = 0 \in \mathbb{Z}_+ \cup \{0\}$ is true.
• Suppose $k \in X$, which means that $k - 1 \in \mathbb{Z}_+ \cup \{0\}$.
• We show that $k + 1 \in X$.  This would mean that $(k + 1) - 1 \in \mathbb{Z}_+ \cup \{0\}$, or, simplifying, that $k \in \mathbb{Z}_+$, which is true because $k$ is a positive integer by definition.

Thus, $X$ is inductive and $\mathbb{Z}_+ \subset X$.  Picking $a \in \mathbb{Z}_+ \subset X$, we see that $a - 1 \in \mathbb{Z}_+ \cup \{0\}$.

(d)

Taking a hint from previous hints (pun intended), assume $c, d \in \mathbb{Z}$.  Next define $X'' = \{ x \in \mathbb{R}; c + x \in \mathbb{Z}$ and $c - x \in \mathbb{Z}\}$. We want to show that $X''$ is inductive.

• $1 \in X''$.  First of all, we want to show that $c + 1 \in \mathbb{Z}$.  Certainly, $c \in \mathbb{Z}_+ \Rightarrow c+1 \in \mathbb{Z}_+ \subset \mathbb{Z}$ by part (a).  If $c = 0$, then $c + 1 = 1 \in \mathbb{Z}_+ \subset \mathbb{Z}$.  If $c \in \mathbb{Z}_-$, then $c + 1 \Rightarrow -(-c-1)$ with $-c \in \mathbb{Z}_+$, so $-c-1 \in \mathbb{Z}_+ \cup \{0\}$ by part (c), and $-(-c-1) \in \mathbb{Z}_- \cup \{0\} \subset \mathbb{Z}$ (!). Secondly, we want to show that $c - 1 \in \mathbb{Z}$. Then, $c \in \mathbb{Z}_+ \Rightarrow c-1 \in \mathbb{Z}_+ \cup \{0\} \subset \mathbb{Z}$ by part (c). If $c = 0$, $c-1 = -1 \in \mathbb{Z}_- \subset \mathbb{Z}$.  Finally, if $c \in \mathbb{Z}_-$, then $c - 1$ can be rewritten as $-(-c + 1)$ with $-c \in \mathbb{Z}_+$, and $-c + 1 \in \mathbb{Z}_+$ by part (a).  Then certainly $-(-c+1) \in \mathbb{Z}_- \subset \mathbb{Z}$.  Thus $1 \in X''$.
• Suppose that $k \in X''$, which means $c + k \in \mathbb{Z}$ and that $c - k \in \mathbb{Z}$.
• We show that $k + 1 \in X''$.  First, $c + (k + 1)$ means, by rearranging (associativity, commutativity) $(c + 1) + k$.  But we know $(c + 1) \in \mathbb{Z}$ by the first point, and so $(c+1) + k \in \mathbb{Z}$ by the second.  We conclude that indeed $c + (k + 1) \in \mathbb{Z}$.  Next we show $c - (k+1) \in \mathbb{Z}$.  By the distributive property, $c - k - 1$.  Then by associativity, $(c - 1) - k$.  We know $c - 1 \in \mathbb{Z}$ by the first point, and $(c-1) - k \in \mathbb{Z}$ by the second point. We conclude that indeed $c - (k + 1) \in \mathbb{Z}$.

Thus, $X''$ is inductive, and importantly, $\mathbb{Z}_+ \subset X''$. For any integer $c$, picking an integer $d \in \mathbb{Z}_+ \subset X''$ guarantees that $c + d \in \mathbb{Z}$ and $c - d \in \mathbb{Z}$.  If $d = 0$, then simply $c \in \mathbb{Z}$ is true by hypothesis.  This shows quite thoroughly the closure of addition of the integers!

(e)

Again taking a hint from previous hints, assume $c, d \in \mathbb{Z}$.  Next define $X''' = \{x \ | \ x \in \mathbb{R}$ and $c \cdot x \in \mathbb{Z}\}$.  We want to show $X'''$ is inductive.

• $1 \in X'''$. It seems clear that $c \cdot 1 \in \mathbb{Z}$, since simplification means $c \in \mathbb{Z}$, which is true by hypothesis.
• We assume that $k \in X'''$, which means $c \cdot k \in \mathbb{Z}$.
• We show that $k + 1 \in X'''$. This means we will show that $c (k + 1) \in \mathbb{Z}$.  By the distributive property, $c \cdot k + c$.  Now, we know $c \in \mathbb{Z}$ by the first point, and $c \cdot k \in \mathbb{Z}$ by the second.  Thus $c \cdot k + c \in \mathbb{Z}$ by part (d), and indeed $c (k + 1) \in \mathbb{Z}$.

Thus $X'''$ is inductive and $\mathbb{Z}_+ \subset X'''$.  Having $c \in \mathbb{Z}$, pick $d \in \mathbb{Z}_+ \subset X'''$ and we are guaranteed that $c \cdot d \in \mathbb{Z}$.  Next, if $d = 0$, then $c \cdot d = c \cdot 0 = 0 \in \mathbb{Z}$.  If $d \in \mathbb{Z}_-$, make the negative sign explicit, so that $c \cdot (-d)$ and by the properties of the reals this becomes $-c \cdot d$ with $-c \in \mathbb{Z}$ and $d \in \mathbb{Z}_+$, which again guarantees the product to be in $\mathbb{Z}$.  We have just proved closure of multiplication of the integers!