Graded: 4.1 #16, Supplemental Problem #4.

(Note: 4.1 #8 is not being graded, but if you believed you had a proof of what turns out to be a false statement, then it is a very worthwhile exercise to figure out which step of your proof contains a logical error. There is guaranteed to be one!)

2.5 #4

a) Countable. Here’s an example of a bijection between $\mathbb Z^+$ and this set:

$$\begin{array}{c | ccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots \\ \hline f(n) & 1 & -1 & 2 & -2 & 4 & -4 & 5 & -5 & \cdots\end{array}$$

b) Countable. Similarly to what I did in (a) above, we can order the integers divisible by 5 but not by 7 in increasing order by absolute value: $$5,-5,10,-10,15,-15,20,-20,25,-25,30,-30,40,-40,\ldots,$$ and make this the basis for a bijection to $\mathbb Z^+$.

c) Countable. A possible ordering is $$1, .\overline1, .1, 11, 1.\overline1, 1.1, .11, 111, 11.\overline1, 11.1, 1.11, .111, 1111, \ldots$$ (this ordering is by the number of 1s in the simplest decimal representation, then by value). The description of the set is a bit ambiguous; if negative numbers such as $-1.1$ are to be included, we can easily insert each negative number after the corresponding positive number.

d) Uncountable. Suppose we had a bijection $f$ between $\mathbb Z^+$ and the set of real numbers with decimal representations of all 1s or 9s. Let $$f(n) = [\text{integer part}].d_{n,1}d_{n,2}d_{n,3}d_{n,4}\ldots$$ for $n=1,2,3,\ldots$, where $d_{n,k}\in\{1,9\}$ for all $n,k\ge 1$. Then we can construct the number $$x = 0.e_1e_2e_3e_4\ldots$$ where $$e_n = \begin{cases} 9\text{ if }d_{n,n}=1 \\ 1\text{ if }d_{n,n}=9 \end{cases},$$ so that, for each $n\ge 1$, $x$ differs from $f(n)$ in the $n^{\text{th}}$ place after the decimal point. Thus $x$ is not equal to $f(n)$ for any $n$, which contradicts our premise that $f$ is a bijection. This shows that the set of real numbers with decimals made up of 1s and 9s is uncountable.

2.5 #20

By definition, $|A|=|B|$ means there is a bijection $f:A\to B$. Similarly, $|B|=|C|$ means there is a bijection $g:B\to C$. If these bijections exist, then $g\circ f$ is a bijection to $A$ to $C$ (proof below), so $|A|=|C|$.

Proof that $g\circ f:A\to C$ is a bijection: First, we show that $g\circ f$ is injective. Suppose $g\circ f(a)=g\circ f(a’)$. Because $g$ is injective, we have $f(a)=f(a’)$. Because $f$ is injective, we have $a=a’$. This shows that $g\circ f$ is injective.

Then we show that $g\circ f$ is surjective. Suppose $c\in C$. Because $g$ is surjective, there exists some $b\in B$ such that $g(b)=c$. Because $f$ is surjective, there exists some $a\in A$ such that $f(a)=b$. Thus $g\circ f(a) = g(b) = c$, and so $c$ is in the range of $g\circ f$. This shows that $g\circ f$ is surjective, hence bijective.

4.1 #6

Suppose $a~|~c$ and $b~|~d$. Then there are integers $k,\ell$ such that $ka=c$ and $\ell b=d$. It follows that $k\ell(ab)=cd$, so $ab~|~cd$.

4.1 #8

The statement is false. Counterexample: Let $a=4$, $b=2$, $c=2$. Then $4~|~(2)(2)$, but $4\not|~2$.

Note that the statement is true if we add the hypothesis that $a$ is prime; we’ll prove this in class.

4.1 #14

a) $c=10$, b) $c=5$, c) $c=8$, d) $c=10$, e) $c=3$, f) $c=14$

$\bigstar$ 4.1 #16

Suppose $a\equiv b\pmod m$. Thus, $m~|~b-a$.

By the division algorithm, we may write $a=qm+r$ and $b=q’m+r’$, where $q,q’,r,r’$ are integers, $0\le r\le m-1$, and $0\le r’\le m-1$. Subtracting, we have $$b-a = (q’-q)m+(r’-r),$$ so $m~|~(q’-q)m+(r’-r)$. It follows (by Corollary 1 on p. 239 of the book) that $m~|~r’-r$. But $|r’-r|\le m-1$. The only multiple of $m$ with absolute value less than or equal to $m-1$ is 0, so $r=r’$. By definition, $a\textbf{ mod }m=r$ and $b\textbf{ mod }m=r’$, so $a\textbf{ mod }m=b\textbf{ mod }m$.

4.1 #20

a) 1, b) 4, c) 3, d) 9

4.1 #36

Suppose $a,b,c,m$ are as stated in the problem. Since $a\equiv b\pmod m$, we have $m~|~b-a$. That is, there is an integer $k$ such that $km = b-a$. Then $k(mc) = bc-ac$, so $mc~|~bc-ac$. Therefore, $ac\equiv bc\pmod{mc}$.

4.1 #40

Let $n$ be odd. Then $n=2k+1$ for some integer $k$, so $n^2 = 4k^2+4k+1 = 4k(k+1)+1$. Since $k$ and $k+1$ are consecutive integers, one of them is even. Therefore, we may write $k(k+1) = 2r$ for some integer $r$. Then $n^2 = 4(2r)+1 = 8r+1$, so $n^2\equiv 1\pmod 8$.

4.1 #46

$$\begin{array}{c | cccccc} +_6 & 0&1&2&3&4&5 \\ \hline 0 & 0&1&2&3&4&5 \\ 1 & 1&2&3&4&5&0 \\ 2 & 2&3&4&5&0&1 \\ 3 & 3&4&5&0&1&2 \\ 4 & 4&5&0&1&2&3 \\ 5 & 5&0&1&2&3&4 \end{array} \qquad \begin{array}{c | cccccc} \cdot_6 & 0&1&2&3&4&5 \\ \hline 0 & 0&0&0&0&0&0 \\ 1 & 0&1&2&3&4&5 \\ 2 & 0&2&4&0&2&4 \\ 3 & 0&3&0&3&0&3 \\ 4 & 0&4&2&0&4&2 \\ 5 & 0&5&4&3&2&1 \end{array}$$

Supplemental #1

Let $U=\bigcup_{n=1}^\infty A_n$ and $I=\bigcap_{n=1}^\infty A_n$.

Claim: $U = \{x\in\mathbb R ~|~ x\ge 1\}$.

Proof: Suppose $x\in U$. Then $x\in A_n$ for some $n\ge 1$, so $x\ge n^2\ge 1^2$. Thus $x\in \{x\in\mathbb R ~|~ x\ge 1\}$. Conversely, suppose $x\ge 1$. Let $n=\lfloor \sqrt x\rfloor$. Then $n\le x < n+1$, so $n^2\le x^2 < (n+1)^2 < (n+10)^2$. Thus $x\in A_n$, so $x\in U$.

Claim: $I = \varnothing$.

Proof: Suppose $x\in I$. Then $x\in A_n$ for all $n\ge 1$. In particular, $x\in A_1$ and $x\in A_{12}$, so $1^2\le x\le 11^2$ and $12^2\le x\le 22^2$. This is a contradiction. Therefore, there are no elements in $I$.

Supplemental #2

The range of $f$ is $\{y\in\mathbb R ~|~ y\ne 1\}$.

Proof: First, we show that all $y\ne 1$ are in the range of $f$. Suppose $y\ne 1$. Let $x = \dfrac y{1-y}$. Then $f(x) = \dfrac{\frac y{1-y}}{\frac y{1-y}+1} = \dfrac y{y+1-y} = y$. Thus $y$ is in the range of $f$.

Second, we show that $y=1$ is not in the range of $f$. We argue by contradiction. If $f(x)=1$, then $\dfrac x{x+1} = 1$, so $x=x+1$. This is a contradiction. Thus 1 is not in the range of $f$.

Supplemental #3

First, we show that $F$ is injective. If $F(x,y)=F(a,b)$, then $x+y=a+b$ and $x-y=a-b$. Adding these equations and dividing by 2 gives $x=a$. Subtracting one equation from the other and dividing by 2 gives $y=b$. Thus $(x,y)=(a,b)$. This shows that $F$ is injective.

Next, we show that $F$ is surjective. Given any $(a,b)\in\mathbb R\times\mathbb R$, we can let $x=\dfrac{a+b}2$ and $y=\dfrac{a-b}2$ so that $f(x,y) = (a,b)$ (check this!). Therefore, $F$ is surjective.

We conclude that $F$ is a bijection, with inverse function given by $F^{-1}(a,b) = \left(\dfrac{a+b}2,\dfrac{a-b}2\right)$.

$\bigstar$ Supplemental #4

We argue by contradiction. Suppose $S$ is countable. Then there is a bijection $f:\mathbb Z^+\to S$. Let $f(n)$ be the sequence $(a_{n,1},a_{n,2},a_{n,3},\ldots)$. (For example, if $f(2014)$ were the Fibonacci sequence, then $a_{2014,6}$ would be the $6^{\text{th}}$ term of the Fibonacci sequence, which is 8.)

Then we construct a sequence $(b_1,b_2,b_3,\ldots)$ such that $b_n \ne a_{n,n}$ for each $n$. This sequence differs from the sequence $f(1)$ in the first position, differs from the sequence $f(2)$ in the second position, and so on. Therefore, this sequence is not $f(n)$ for any $n\ge 1$. This contradicts our premise that $f$ is a bijection from $\mathbb Z^+$ to $S$. We conclude that $S$ is not countable. $\blacksquare$