Chapter 2: Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

In this exercise we will show that the Boolean product of zero-one matrices is associative. Assume that A is anm x pzero-one matrix. B is a k x n zero-one matrix, and C is a zero-one matrix. Show that$A\odot (B\odot C)=(A\odot B)\odot C$

Show that $\sum _{\mathrm{j}}^{\mathrm{n}} \left({\mathrm{a}}_{\mathrm{j}}-{\mathrm{a}}_{\mathrm{j}-1}\right)={\mathrm{a}}_{\mathrm{n}}-{\mathrm{a}}_0\text{, where}{\mathrm{a}}_0,{\mathrm{a}}_1,\dots ..{\mathrm{a}}_{\mathrm{n}}$, is a sequence of real numbers. This type of sum is called telescoping.

Find a counterexample, if possible, to these universally quantified statements, where the domain for all variables consists of all integers.

$$\begin{gathered} \mathbf{a}\mathbf{)}\mathbf{\forall }\mathbf{x}\mathbf{(}{\mathbf{x}}^{\mathbf{2}}\mathbf{\ge }\mathbf{x}\mathbf{\left)} \\ \mathbf{b}\mathbf{\right)}\mathbf{}\mathbf{\forall }\mathbf{x}\mathbf{(}\mathbf{x}\mathbf{>}\mathbf{0}\mathbf{\vee }\mathbf{x}\mathbf{<}\mathbf{0}\mathbf{)} \\ \mathbf{c}\mathbf{)}\mathbf{}\mathbf{\forall }\mathbf{x}\mathbf{(}\mathbf{x}\mathbf{=}\mathbf{1}\mathbf{)} \end{gathered}$$

Show that there is no one-to-one correspondence from the set of positive integers to the power set of the set of positive integers. [Hint: Assume that there is such a one-to-one correspondence. Represent a subset of the set of positive integers as an infinite bit string with $i^{\mathrm{th}}$ bit ifi belongs to the subset and 0otherwise. Suppose that you can list these infinite strings in a sequence indexed by the positive integers. Construct a new bit string with its$i^{\mathrm{th}}$ bit equal to the complement of the $i^{\mathrm{th}}$bit of the $i^{\mathrm{th}}$string in the list. Show that this new bit string cannot appear in the list].

How many different elements does A X B have if A has m elements and B has n elements

Show that \(A \oplus B = \left( {A \cup B} \right) - \left( {A \cap B} \right)\).

If f and $f\mathit{\circ }g$ are onto, does it follow that g is onto? Justify your answer.

Show that $|R\times R|=\left|R\right|$. [Hint: Use the Schroder Bernstein theorem to show that $\left|\right(0,1)\times (0,1\left)\right|=\left|\right(0,1\left)\right|$. To construct an injection from (0, 1) X (0,1) to (0,1), suppose that $(x,y)\in (0,1)\times (0,1)$. Map (x, y) to the number with decimal expansion formed by alternating between the digits in the decimal expansions of x and y, which do not end with an infinite string of 9s.]

Show that\(A \oplus B = \left( {A - B} \right) \cup \left( {B - A} \right)\).

Find $f\circ gandg\circ f$and, where $f\left(x\right)=x^2+1andg\left(x\right)=x+2$ , are functions from $\mathbf{ℝ}\mathbf{}\mathit{t}\mathit{o}\mathbf{}\mathbf{ℝ}$.