Practice Problems for in-class work

Hammack, Section 12.2:

• Problem 18, then prove that $$\mathbb{N}$$ and $$\mathbb{Z}$$ have the same cardinality. (the relevant function is $$f(n)=((-1)^n(2n-1)+1)/4$$)

• Problems 11, 12: consider the functions $$\theta(a,b)=(-1)^ab$$ and $$\theta(a,b)=a-2ab+b$$ from from $$\{0,1\}\times\mathbb{N}$$ to $$\mathbb{Z}$$. Are they injective? surjective? bijective?

other problems

• Prove that if $$g\circ f$$ is injective, then $$f$$ is injective. Prove that if $$g\circ f$$ is surjective, then $$g$$ is surjective. Give counterexamples showing that $$g\circ f$$ can be injective but $$g$$ not injective, and $$g\circ f$$ is surjective by $$f$$ is not surjective.

• Give an example of a countable subset of the irrational numbers, or prove that no such subset exists.

• How many surjective maps are there from a 3 element set to a 2 element set? From a 4 element set to a 3 element set?

More problems for in-class discussion

• Go through the argument that $$\mathbb{N}\times\mathbb{N}$$ is countable (Figure 14.2)

• Go through Cantor’s diagonalization argument proving that (for example) infinite sequences form an uncountable set. See pp. 271-272 and also Gilbert and Vanstone Theorem 6.67.

More problems still

• Let $$A$$ be the set of sequences of natural numbers $$a_1,a_2,a_3,\ldots$$ that are eventually constant at zero – in other words, a sequence $$a_1,a_2,\ldots$$ is in $$A$$ if there exists an $$N$$ such that $$a_i=0$$ for all $$i\ge N$$. Is $$A$$ countable?

• Prove that the intervals $$(0,1)$$ and $$(a,b)$$ in $$\mathbb{R}$$ have the same cardinality for any $$a,b$$ with $$b>a$$.

• Give 3 examples of functions that are surjective but not injective, and 3 examples of functions that are injective but not surjective

And still more problems

Two tricky problems from Gilbert and Vanstone.

• Prove that a function $$f:X\to Y$$ is injective if and only if, given two maps $$g:T\to X$$ and $$h:T\to X$$, $f\circ g:T\to X = f\circ h:T\to X \implies g=h.$

• If $$f:A\to B$$ and $$g:B\to C$$ are bijective maps, prove that the inverse map to $$f\circ g$$ is $$g^{-1}\circ f^{-1}$$.