Chapter 3

Prove each. The set of integers is countably infinite.

Prove. Any subset of a countable set is countable.

Evaluate each sum and product, where \(p\) is a prime and \(I=\\{1,2,3,5\\}.\) $$\begin{aligned} &\prod i^{j}\\\ &i, j \in I\\\ &i \leq j \end{aligned}$$

Using the functions \(f(x)=2 x+3\) and \(g(x)=x^{2}-1,\) find the following. $$(f g)(x)$$

If \(g \circ f\) is injective, then \(f\) is injective.

Prove each. Any subset of a countable set is countable.

Each day of the week, beginning with Sunday, can be identified by a code \(x,\) where \(0 \leq x \leq 6 .\) January 1 of any year \(y\) can be determined using the following formula^{** } $$ x \equiv\left(y+\left\lfloor\frac{y-1}{4}\right\rfloor-\left\lfloor\frac{y-1}{100}\right\rfloor+\left\lfloor\frac{y-1}{400}\right\rfloor\right) \bmod 7 $$ Using this formula determine the first day in each year. $$3000$$

Prove. A set \(A\) is infinite if and only if there exists a bijection between \(A\) and a proper subset of itself.

A square matrix \(A\) of order \(n\) is invertible if there is a matrix \(B\) such that \(A B=I_{n}=B A .\) Then \(B\) is the inverse of \(A,\) denoted by \(A^{-1} .\) In Exercises 44 and \(45,\) verify that \(B=A^{-1} .\) Assume that \(k=a d-b c \neq 0\). $$A=\left[\begin{array}{rrr} 1 & -2 & 0 \\ 3 & 1 & -1 \\ 1 & 2 & -3 \end{array}\right], B=\frac{1}{17}\left[\begin{array}{rrr} 1 & 6 & -2 \\ -8 & 3 & -1 \\ -5 & 4 & -7 \end{array}\right]$$

Let \(f: X \rightarrow Y\) and \(A, B \subseteq X^{\dagger} .\) Prove each. $$f(\mathrm{A} \cup \mathrm{B})=f(\mathrm{A}) \cup f(\mathrm{B})$$

Prove each. A set \(A\) is infinite if and only if there exists a bijection between \(A\) and a proper subset of itself.

Prove. The open interval \((a, b)\) is uncountable. [Hint: Find a suitable bijection from \((0,1)\) to \((a, b) . ]\)

Evaluate each sum and product, where \(p\) is a prime and \(I=\\{1,2,3,5\\}.\) $$\sum_{j=1}^{4}\left(3^{j}-3^{j-1}\right)$$

Find each product. $$\left[\begin{array}{ll}{1} & {2} \\ {2} & {3}\end{array}\right]\left[\begin{array}{l}{x} \\ {y}\end{array}\right]$$

Let \(f: X \rightarrow Y\) and \(A, B \subseteq X^{\dagger} .\) Prove each. $$f(\mathbf{A} \cap \mathbf{B}) \subseteq f(\mathbf{A}) \cap f(\mathbf{B})$$

If \(g \circ f\) is bijective, then \(f\) is injective and \(g\) is surjective.

Prove each. The open interval \((a, b)\) is uncountable. I Hint: Find a suitable bijection from \((0,1) \text { to }(a, b) .]\)

Find each product. $$\left[\begin{array}{ll} 1 & 2 \\ 2 & 3 \end{array}\right]\left[\begin{array}{l} x \\ y \end{array}\right]$$

Prove. The set \(Q^{+}\) of positive rational numbers is countable.

Let \(f: X \rightarrow Y\) and \(A, B \subseteq X^{\dagger} .\) Prove each. If \(\mathrm{B} \subseteq \mathrm{A} \subseteq \mathrm{X},\) then \(f(\mathrm{A})-f(\mathrm{B}) \subseteq f(\mathrm{A}-\mathrm{B}).\)

Find each product. $$\left[\begin{array}{ll}{1} & {0} \\ {0} & {1}\end{array}\right]\left[\begin{array}{l}{x} \\ {y}\end{array}\right]$$

Let \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\) be invertible functions. Prove each. $$f^{-1} \circ f=1_{X}$$

Prove each. The set \(Q^{+}\) of positive rational numbers is countable.

Find each product. $$\left[\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right]\left[\begin{array}{l} x \\ y \end{array}\right]$$

Prove. The set of irrational numbers is uncountable. (Hint: Prove by contradiction.)

Expand each. $$\sum_{j=1}^{2} a_{i j}$$

Find each product. $$\left[\begin{array}{rrr}{1} & {1} & {1} \\ {1} & {-2} & {3} \\ {2} & {-3} & {4}\end{array}\right]\left[\begin{array}{l}{x} \\ {y} \\\ {z}\end{array}\right]$$

Let \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\) be invertible functions. Prove each. $$f \circ f^{-1}=1_{Y}$$

Prove each. The set of irrational numbers is uncountable. (Hint: Prove by contradiction.)

Find each product. $$\left[\begin{array}{rrr} 1 & 1 & 1 \\ 1 & -2 & 3 \\ 2 & -3 & 4 \end{array}\right]\left[\begin{array}{l} x \\ y \\ z \end{array}\right]$$

Prove. A countable union of countable sets is countable.

Expand each. $$\sum_{i=1}^{3} \sum_{j=1}^{2} a_{i j}$$

(Easter Sunday) The date for Easter Sunday in any year \(y\) can be computed as follows. Let \(a=y \bmod 19, b=y \bmod 4, c=y \bmod 7, d=(19 a+24)\) \(\bmod 30, e=(2 b+4 c+6 d+5) \bmod 7,\) and \(r=(22+d+e) .\) If \(r \leq 31,\) then Easter Sunday is March \(r ;\) otherwise, it is April \([r(\bmod 31)] .\) Compute the date for Easter Sunday in each year. $$1996$$

Rewrite each linear system as a matrix equation \(A X=B\). $$\begin{aligned} &2 x+3 y=4\\\ &4 x+5 y=6 \end{aligned}$$

Let \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\) be invertible functions. Prove each. \(f^{-1}\) is bijective.

Prove each. A countable union of countable sets is countable.

The date for Easter Sunday in any year \(y\) can be computed as follows. Let \(a=y \bmod 19, b=y \bmod 4, c=y \bmod 7, d=(19 a+24)\) \(\bmod 30, e=(2 b+4 c+6 d+5) \bmod 7,\) and \(r=(22+d+e) .\) If \(r \leq 31,\) then Easter Sunday is March \(r ;\) otherwise, it is April \([r(\bmod 31)] .\) Compute the date for Easter Sunday in each year. $$1996$$

Prove. The cartesian product of two countable sets is countable.

Expand each. $$\sum_{j=1}^{2} \sum_{i=1}^{3} a_{i j}$$

(Easter Sunday) The date for Easter Sunday in any year \(y\) can be computed as follows. Let \(a=y \bmod 19, b=y \bmod 4, c=y \bmod 7, d=(19 a+24)\) \(\bmod 30, e=(2 b+4 c+6 d+5) \bmod 7,\) and \(r=(22+d+e) .\) If \(r \leq 31,\) then Easter Sunday is March \(r ;\) otherwise, it is April \([r(\bmod 31)] .\) Compute the date for Easter Sunday in each year. $$2000$$

Rewrite each linear system as a matrix equation \(A X=B\). $$\begin{aligned} x-2 y &=4 \\ 3 x+y-z &=-5 \\ x+2 y-3 z &=6 \end{aligned}$$

Let \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\) be invertible functions. Prove each. $$\left(f^{-1}\right)^{-1}=f$$

Prove each. The cartesian product of two countable sets is countable.

The date for Easter Sunday in any year \(y\) can be computed as follows. Let \(a=y \bmod 19, b=y \bmod 4, c=y \bmod 7, d=(19 a+24)\) \(\bmod 30, e=(2 b+4 c+6 d+5) \bmod 7,\) and \(r=(22+d+e) .\) If \(r \leq 31,\) then Easter Sunday is March \(r ;\) otherwise, it is April \([r(\bmod 31)] .\) Compute the date for Easter Sunday in each year. $$2000$$

Prove. If \(\Sigma\) is a finite alphabet, then \(\Sigma^{*}\) is countable.

(Easter Sunday) The date for Easter Sunday in any year \(y\) can be computed as follows. Let \(a=y \bmod 19, b=y \bmod 4, c=y \bmod 7, d=(19 a+24)\) \(\bmod 30, e=(2 b+4 c+6 d+5) \bmod 7,\) and \(r=(22+d+e) .\) If \(r \leq 31,\) then Easter Sunday is March \(r ;\) otherwise, it is April \([r(\bmod 31)] .\) Compute the date for Easter Sunday in each year. $$2076$$

Let \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\) be invertible functions. Prove each. $$(g \circ f)^{-1}=f^{-1} \circ g^{-1}$$

Prove each. If \(\Sigma\) is a finite alphabet, then \(\Sigma^{*}\) is countable.

Expand each. $$\sum_{1 \leq i

The date for Easter Sunday in any year \(y\) can be computed as follows. Let \(a=y \bmod 19, b=y \bmod 4, c=y \bmod 7, d=(19 a+24)\) \(\bmod 30, e=(2 b+4 c+6 d+5) \bmod 7,\) and \(r=(22+d+e) .\) If \(r \leq 31,\) then Easter Sunday is March \(r ;\) otherwise, it is April \([r(\bmod 31)] .\) Compute the date for Easter Sunday in each year. $$2076$$